PAT 甲级 2017年春季

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

1 PAT 甲级 1124 Raffle for Weibo Followers

#include <bits/stdc++.h>
using namespace std;
string id[1010];
set<string> st;
int main() {int m,n,s;cin>>m>>n>>s;for(int i=0;i<m;++i) cin>>id[i];if(s>m) cout<<"Keep going...\n";else{int now=s-1;while(now<m){if(st.count(id[now])==0){cout<<id[now]<<"\n";st.insert(id[now]);now+=n;}else ++now;}}
}

2 PAT 甲级 1125 Chain the Ropes

#include <bits/stdc++.h>
using namespace std;
multiset<int> st;
int main() {int n,m=0;cin>>n;for(int i=0;i<n;++i){int tmp;cin>>tmp;st.insert(tmp);m=max(m,tmp);}while(st.size()>=2){int a=*st.begin();st.erase(st.begin());int b=*st.begin();st.erase(st.begin());st.insert((a+b)/2);}cout<<min(m,*st.begin());
}

3 PAT 甲级 1126 Eulerian Path

#include <bits/stdc++.h>
using namespace std;
int father[50];
int Find(int x){if(x!=father[x]) father[x]=Find(father[x]);return father[x];
}
void Union(int a,int b){father[Find(a)]=father[Find(b)];
}
int main() {int n,m;cin>>n>>m;vector<int> v(n);for(int i=0;i<n;++i) father[i]=i;for(int i=0;i<m;++i){int x,y;cin>>x>>y;--x,--y;v[x]++,v[y]++;Union(x,y);}// 测试点三判断连通性int odd_ctr=0,block_ctr=0;set<int> block;for(int i=0;i<n;++i) block.insert(Find(i));block_ctr=block.size();for(int i=0;i<n;++i){if(i!=0) cout<<" ";cout<<v[i];if(v[i]%2!=0) ++odd_ctr;}cout<<"\n";if(block_ctr<=1&&odd_ctr==0) cout<<"Eulerian";else if(block_ctr<=1&&odd_ctr==2) cout<<"Semi-Eulerian";else cout<<"Non-Eulerian";
}

4 PAT 甲级 1127 ZigZagging on a Tree

#include <bits/stdc++.h>
using namespace std;int in[50],post[50];
map<int,int> key,val;
int lchild[50],rchild[50],height[50];
int n; vector<int> ans;int Build(int l1,int r1,int l2,int r2){if(l1>r1) return -1;int root=post[r1],mid;for(mid=l2;mid<=r2&&in[mid]!=root;++mid);int len=mid-l2;lchild[root]=Build(l1,l1+len-1,l2,mid-1);rchild[root]=Build(l1+len,r1-1,mid+1,r2);return root;
}
void BFS(int root){height[root]=1;queue<int> q;q.push(root);while(!q.empty()){int now=q.front();q.pop();ans.push_back(now);if(lchild[now]!=-1){height[lchild[now]]=height[now]+1;q.push(lchild[now]);}if(rchild[now]!=-1){height[rchild[now]]=height[now]+1;q.push(rchild[now]);}}
}
void Print(){int left=0,right=0;while(left<n){while(right<n&&height[ans[right]]==height[ans[left]])++right;if(height[ans[left]]%2!=0)reverse(ans.begin()+left,ans.begin()+right);left=right;}for(int i=0;i<n;++i){if(i!=0) cout<<" ";cout<<val[ans[i]];}
}
int main() {cin>>n;for(int i=0;i<n;++i){cin>>val[i];key[val[i]]=i;in[i]=i;}for(int i=0;i<n;++i){int tmp;cin>>tmp;post[i]=key[tmp];}int root=Build(0,n-1,0,n-1);BFS(root);Print();
}

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

---