PAT 2016年浙大复试机试

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

1 PAT 甲级 1112 Stucked Keyboard

#include <bits/stdc++.h>
using namespace std;
int num[256];
bool broken[256];
int main() {fill(broken,broken+256,true);int n;cin>>n;string s;cin>>s;char old,now;for(size_t i=0;i<s.size();++i){now=s[i];if(i==0||now!=old){num[now]=1;if(i!=0&&num[old]!=0) broken[old]=false;}else num[now]=(num[now]+1)%n;old=now;}if(num[now]!=0) broken[now]=false;set<int> ans;for(auto i:s){if(broken[i]){cout<<i;ans.insert(i); broken[i]=false;}}cout<<"\n";for(size_t i=0;i<s.size();++i){cout<<s[i];if(ans.count(s[i])!=0) i+=(n-1);}cout<<"\n";
}

2 PAT 甲级 1113 Integer Set Partition

#include <bits/stdc++.h>
using namespace std;
const int MAXN=1e5+10;
int num[MAXN];
int main() {int n;cin>>n;for(int i=0;i<n;++i){cin>>num[i];}sort(num,num+n);int ans=0;for(int i=0;i<n;++i){ans=i<n/2?(ans-num[i]):(ans+num[i]);}cout<<n%2<<" "<<ans; 
}

3 PAT 甲级 1114 Family Property

#include <bits/stdc++.h>
using namespace std;
const int N=10010;
struct Family{int m,ts,ta;
};
unordered_map<int,Family> ans_data;
int estate[N],area[N];
set<int> all_p,ids;
vector<int> ans;int father[N];
int Find(int x){if(father[x]!=x) father[x]=Find(father[x]);return father[x];
}
void Union(int a,int b){int ra=Find(a),rb=Find(b);if(ra<rb) father[rb]=ra;else father[ra]=rb;
}
int main() {for(int i=0;i<N;++i) father[i]=i;int n;cin>>n;for(int i=0;i<n;++i){int id,fa,ma,k,m,a,chi;cin>>id>>fa>>ma>>k;all_p.insert(id);if(fa!=-1) {Union(id,fa); all_p.insert(fa);}if(ma!=-1) {Union(id,ma); all_p.insert(ma);}for(int j=0;j<k;++j){cin>>chi;if(chi!=-1) {Union(id,chi); all_p.insert(chi);}}cin>>m>>a;estate[id]=m,area[id]=a;}for(auto i:all_p){int id=Find(i);ans_data[id].m++;ans_data[id].ts+=estate[i];ans_data[id].ta+=area[i];ids.insert(id);}for(auto i:ids) ans.push_back(i);sort(ans.begin(),ans.end(),[](int a,int b){int oa=ans_data[a].ta*ans_data[b].m;int ob=ans_data[b].ta*ans_data[a].m;if(oa!=ob) return oa>ob;else return a<b;});printf("%lu\n",ans.size());for(auto i:ans){printf("%04d %d %.3lf %.3lf\n",i,ans_data[i].m,ans_data[i].ts*1.0/ans_data[i].m,ans_data[i].ta*1.0/ans_data[i].m);}
}

4 PAT 甲级 1115 Counting Nodes in a BST

#include <bits/stdc++.h>
using namespace std;
struct Node{int val,layer;Node *lchild{NULL},*rchild{NULL};
};
void Insert(Node *&root,int val){if(root==NULL){root=new Node();root->val=val;}else{if(val<=root->val) Insert(root->lchild,val);else Insert(root->rchild,val);}
}
vector<Node*>nodes;
int max_layer=1;
void BFS(Node *root){if(root==NULL) return;queue<Node*> q;q.push(root);root->layer=1;while(!q.empty()){Node* now=q.front();q.pop();nodes.push_back(now);if(now->lchild){now->lchild->layer=now->layer+1;max_layer=max(max_layer,now->layer+1);q.push(now->lchild);}if(now->rchild){now->rchild->layer=now->layer+1;max_layer=max(max_layer,now->layer+1);q.push(now->rchild);}}
}
int main() {int n;cin>>n;Node *root=NULL;for(int i=1;i<=n;++i){int tmp;cin>>tmp;Insert(root,tmp);}BFS(root);int c1=0,c2=0;for(auto p:nodes){if(p->layer==max_layer-1) ++c2;if(p->layer==max_layer) ++c1;}cout<<c1<<" + "<<c2<<" = "<<c1+c2<<"\n";
}