1. 知识点总结
100/100,2h✨
总体来讲和之前某次模拟考试的题目高度相近~很多都是原题的轻微变式,所以做的时候比较容易。真正考试肯定不会这么简单,戒骄戒躁┗|`O′|┛ 嗷~~
题目 | 难度 | 知识点 |
---|---|---|
1140 Look-and-say Sequence | 🎯 | 字符串+找规律 |
1141 PAT Ranking of Institutions | 🎯 | 结构体排序 |
1142 Maximal Clique | 🎯 | 图论 |
1143 Lowest Common Ancestor | 🎯 | LCA+BST |
2. 分题题解
2.1 PAT 1140 Look-and-say Sequence
Look-and-say sequence is a sequence of integers as the following:
D, D1, D111, D113, D11231, D112213111, ...
where D
is in [0, 9] except 1. The (n+1)st number is a kind of description of the nth number. For example, the 2nd number means that there is one D
in the 1st number, and hence it is D1
; the 2nd number consists of one D
(corresponding to D1
) and one 1 (corresponding to 11), therefore the 3rd number is D111
; or since the 4th number is D113
, it consists of one D
, two 1’s, and one 3, so the next number must be D11231
. This definition works for D
= 1 as well. Now you are supposed to calculate the Nth number in a look-and-say sequence of a given digit D
.
Input Specification:
Each input file contains one test case, which gives D
(in [0, 9]) and a positive integer N (≤ 40), separated by a space.
Output Specification:
Print in a line the Nth number in a look-and-say sequence of D
.
Sample Input:
1 8
Sample Output:
1123123111
这题主要是需要看懂题意,文中的序列特点是,第n+1个字符串是对于第n个字符串的描述“
[数字1][该位置数字1的连续的个数][数字2][该位置数字2的连续的个数]……[数字n][该位置数字n的连续的个数]
”第一个数字是D,所以第二个数字按照规律为D1以此类推
#include<bits/stdc++.h>
using namespace std;
int D,N;
//对前一个数字的描述
int main(){
scanf("%d%d",&D,&N);
string ans=to_string(D);
string temp="";
for(int i=2;i<=N;i++){
int cnt=1;//连续字母的个数
temp+=ans[0];
for(int j=1;j<ans.length();j++){
if(ans[j]==ans[j-1]){
cnt++;
}else{
temp+=to_string(cnt);
temp+=ans[j];
cnt=1;
}
}
temp+=to_string(cnt);
ans=temp;
temp="";
}
printf("%s",ans.c_str());
return 0;
}
2.2 PAT 1141 PAT Ranking of Institutions
题解:这题的问题在于,TWS的算法,需要先算每一个scoreA\scoreT\scoreB的总值,再进行相应的乘除法,否则因为计算顺序会导致最后一个样例过不去。
#include<bits/stdc++.h>
using namespace std;
//22分
string id,sname;int score;//Testee
struct School{
string name;
int TWS=0;
int a=0,t=0,b=0;
int Ns=0;
};
int N;
map<string,School>mp;
vector<School>school;//保存学校信息
void to_lower(string &str){
for(int i=0;i<str.length();i++){
if(str[i]<='Z'&&str[i]>='A'){
str[i]=str[i]-'A'+'a';
}
}
}
bool cmp(School a ,School b){
if(a.TWS!=b.TWS){
return a.TWS > b.TWS ;
}else if(a.Ns!=b.Ns){
return a.Ns<b.Ns;
}else{
return a.name<b.name;
}
}
int main(){
scanf("%d",&N);
for(int i=0;i<N;i++){
cin>>id>>score>>sname;
to_lower(sname);
mp[sname].Ns++;
mp[sname].name=sname;
if(id[0]=='T'){
mp[sname].t+=score;
}else if(id[0]=='A'){
mp[sname].a+=score;
}else{
mp[sname].b+=score;
}
}
for(map<string,School>::iterator it=mp.begin();it!=mp.end();it++){
(it->second).TWS=(it->second).t*1.5+(it->second).a+(it->second).b/1.5;
school.push_back(it->second);
}
sort(school.begin(),school.end(),cmp);
int rank=1;
int len=school.size();
printf("%d\n",len);
for(int i=0;i<len;i++){
if(i==0){
cout<<rank<<" "<<school[i].name<<" "<<int(school[i].TWS)<<" "<<school[i].Ns<<"\n";
}else if(school[i].TWS==school[i-1].TWS){
cout<<rank<<" "<<school[i].name<<" "<<int(school[i].TWS)<<" "<<school[i].Ns<<"\n";
}else{
rank=i+1;
cout<<rank<<" "<<school[i].name<<" "<<int(school[i].TWS)<<" "<<school[i].Ns<<"\n";
}
}
return 0;
}
2.3 PAT 1142 Maximal Clique
考察强连通图,图论的问题。注意这里会卡时间复杂度,之前考过相似的,解决方法如下:
#include<bits/stdc++.h>
using namespace std;
int Nv,Ne,M,K;
int u,v;
vector<vector<bool>>graph;
vector<vector<int>>rels;
vector<int>q;
int main(){
scanf("%d%d",&Nv,&Ne);
graph.resize(Nv+1);
rels.resize(Nv+1);
for(int i=0;i<Nv+1;i++){
graph[i].resize(Nv+1);
fill(graph[i].begin(),graph[i].end(),false);
}
for(int i=0;i<Ne;i++){
scanf("%d%d",&u,&v);
graph[u][v]=true;
graph[v][u]=true;
rels[u].push_back(v);
rels[v].push_back(u);
}
scanf("%d",&M);
for(int i=0;i<M;i++){
scanf("%d",&K);
q.resize(K);
for(int j=0;j<K;j++){
scanf("%d",&q[j]);
}
//是否是强关联
bool flag=true;
for(int x=0;x<K;x++){
for(int y=x+1;y<K;y++ ){
if(!graph[q[x]][q[y]]){
printf("Not a Clique\n");
flag=false;
break;
}
}
if(!flag){
break;
}
}
if(!flag){
continue;
}
//是否可以再加上别的
for(int x=0;x<K;x++){
for(int y=0;y<rels[q[x]].size();y++){
int nv=rels[q[x]][y];
if(find(q.begin(),q.end(),nv)!=q.end()){
continue;
}else{
bool has=true;
for(int p=0;p<K;p++){
if(!graph[nv][q[p]]){
has=false;
break;
}
}
if(has==true){
printf("Not Maximal\n");
flag=false;
break;
}
}
if(!flag)break;
}
if(!flag)break;
}
if(!flag)continue;
printf("Yes\n");
}
return 0;
}
2.4 PAT 1143 Lowest Common Ancestor
我记得是之前一次还是前两天遇到的一摸一样的题目,唯一的区别在于中序遍历的list需要自己排完序后得出来。
#include<bits/stdc++.h>
using namespace std;
int M,N,u,v;
vector<int>pre;
vector<int>in;
struct Node{
int val;
Node*left=NULL;
Node*right=NULL;
Node*parent=NULL;
};
Node*build(int inL,int inR,int preL,int preR){
if(inL>inR||preL>preR||inL<0||inR>=N||preL<0||preR>=N){
return NULL;
}
Node* root=new Node;
root->val=pre[preL];
int k;
for(k=inL;k<=inR;k++){
if(in[k]==root->val){
break;
}
}
int num=k-inL;
root->left=build(inL,k-1,preL+1,preL+num);
root->right=build(k+1,inR,preL+num+1,preR);
return root;
}
map<int,vector<int>>path;
map<int,Node*>nodes;
void levelTravel(Node*root){
queue<Node*>q;
q.push(root);
while(!q.empty()){
Node*top=q.front();
nodes[top->val]=top;
q.pop();
if(top->left!=NULL){
top->left->parent=top;
q.push(top->left);
}
if(top->right!=NULL){
top->right->parent=top;
q.push(top->right);
}
}
}
int main(){
scanf("%d%d",&M,&N);
pre.resize(N);
in.resize(N);
for(int i=0;i<N;i++){
scanf("%d",&pre[i]);
}
in=pre;
sort(in.begin(),in.end());
Node*root=build(0,N-1,0,N-1);
levelTravel(root);
for(int i=0;i<M;i++){
scanf("%d%d",&u,&v);
if(find(pre.begin(),pre.end(),u)==pre.end()){
if(find(pre.begin(),pre.end(),v)==pre.end()){
printf("ERROR: %d and %d are not found.\n",u,v);
}else{
printf("ERROR: %d is not found.\n",u);
}
}else{
if(find(pre.begin(),pre.end(),v)==pre.end()){
printf("ERROR: %d is not found.\n",v);
}else{
//寻找两个结点的最近的父辈
int p;
if(path.find(u)==path.end()){
p=u;
while(nodes[p]->parent!=NULL){
path[u].push_back(p);
p=nodes[p]->parent->val;
}
reverse(path[u].begin(),path[u].end());
}
if(path.find(v)==path.end()){
p=v;
while(nodes[p]->parent!=NULL){
path[v].push_back(p);
p=nodes[p]->parent->val;
}
reverse(path[v].begin(),path[v].end());
}
int a=root->val;
for(int i=0;i<min(path[u].size(),path[v].size());i++){
if(path[u][i]==path[v][i]){
a=path[u][i];
}else{
break;
}
}
if(a==u){
printf("%d is an ancestor of %d.\n",a,v);
}else if(a==v){
printf("%d is an ancestor of %d.\n",a,u);
}else{
printf("LCA of %d and %d is %d.\n",u,v,a);
}
}
}
}
return 0;
}
3. 参考资料
无~