PAT 甲级 2016年秋季

本文主要是介绍PAT 甲级 2016年秋季，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1 PAT 甲级 1116 Come on! Let’s C

#include <bits/stdc++.h>
using namespace std;
map<int,string> mp; 
bool is_prime[10010];
void Init(){fill(is_prime,is_prime+10010,true);is_prime[0]=is_prime[1]=false;for(int i=2;i<10010;++i){if(is_prime[i]){for(int j=i*2;j<10010;j+=i){is_prime[j]=false;}}}
}int main() {Init();int n;cin>>n;for(int i=1;i<=n;++i){int tmp;cin>>tmp;if(i==1) mp[tmp]="Mystery Award";else if(is_prime[i]) mp[tmp]="Minion";else mp[tmp]="Chocolate";}int k;cin>>k;while(k--){int tmp;cin>>tmp;if(mp.count(tmp)==0) printf("%04d: Are you kidding?\n",tmp);else{printf("%04d: %s\n",tmp,mp[tmp].c_str());mp[tmp]="Checked";}}
}

2 PAT 甲级 1117 Eddington Number

#include <bits/stdc++.h>
using namespace std;
int mile[100010];
int main() {int n;cin>>n;for(int i=0;i<n;++i) cin>>mile[i];sort(mile,mile+n,[](int a,int b){return a>b;});int ans=0;while(ans<n&&mile[ans]>ans+1) ++ans;cout<<ans;
}

3 PAT 甲级 1118 Birds in Forest

#include <bits/stdc++.h>
using namespace std;
set<int> birds;
int father[10010];
int Find(int x){if(father[x]!=x) father[x]=Find(father[x]);return father[x];
}
int Union(int a,int b){father[Find(a)]=Find(b);
}
int main() {for(int i=0;i<10010;++i) father[i]=i;int n;cin>>n;for(int i=0;i<n;++i){int k;cin>>k;int b0,bt;for(int i=0;i<k;++i){cin>>bt;if(i==0) b0=bt;else Union(b0,bt);birds.insert(bt);}}set<int> trees;for(auto i:birds){trees.insert(Find(i));}cout<<trees.size()<<" "<<birds.size()<<"\n";int q;cin>>q;while(q--){int x,y;cin>>x>>y;if(Find(x)==Find(y)) cout<<"Yes\n";else cout<<"No\n";}
}

4 PAT 甲级 1119 Pre-and Post-order Traversals

#include <bits/stdc++.h>
using namespace std;
int lchild[50],rchild[50];
int pre[50],post[50];
map<int,int> key,val;
bool multi=false;
void Build(int l1,int r1,int l2,int r2){if(l1==r1){lchild[l1]=rchild[l1]=-1;return;}int root=pre[l1],lc=pre[l1+1],rc=post[r2-1];int idx=l2;while(idx<r2&&post[idx]!=lc) ++idx;if(idx==r2-1){multi=true;lchild[root]=lc;rchild[root]=-1;Build(l1+1,l1+1+idx-l2,l2,idx);}else{lchild[root]=lc;rchild[root]=rc;Build(l1+1,l1+1+idx-l2,l2,idx);Build(l1+1+idx-l2+1,r1,idx+1,r2-1);}
}
vector<int> ans;
void InOrder(int root){if(lchild[root]!=-1) InOrder(lchild[root]);ans.push_back(val[root]);if(rchild[root]!=-1) InOrder(rchild[root]);
}
int main() {int n;cin>>n;for(int i=0;i<n;++i){int tmp;cin>>tmp;key[tmp]=i,val[i]=tmp;pre[i]=i;}for(int i=0;i<n;++i){int tmp;cin>>tmp;post[i]=key[tmp];}Build(0,n-1,0,n-1);if(multi) cout<<"No\n";else cout<<"Yes\n";InOrder(pre[0]);for(int i=0;i<n;++i){if(i!=0) cout<<" ";cout<<ans[i];}cout<<"\n";
}

这篇关于PAT 甲级 2016年秋季的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---