PAT 甲级 2016年春季

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

1 PAT 甲级 1108 Finding Average

#include <bits/stdc++.h>
using namespace std;
bool IsValid(string s,double &ans){int c1=0,c2=0,pos_p;for(size_t i=0;i<s.size();++i){if(s[i]=='-') ++c1;else if(s[i]=='.') {++c2; pos_p=i;}else if(s[i]<'0'||s[i]>'9') return false;}// 负号 if(c1!=0&&c1!=1) return false;if(c1&&s[0]!='-') return false;// 小数点 if(c2!=0&&c2!=1) return false;if(c2&&pos_p+3<s.size()) return false;double tmp=atof(s.c_str());if(tmp>1000||tmp<-1000) return false;ans=tmp;return true;
}
int main() {int n;cin>>n;double sum=0;int ctr=0;for(int i=0;i<n;++i){string tmp;cin>>tmp;double tmp_lf;if(IsValid(tmp,tmp_lf)){++ctr,sum+=tmp_lf;}else{printf("ERROR: %s is not a legal number\n",tmp.c_str());}}if(ctr==0) printf("The average of 0 numbers is Undefined");else if(ctr==1) printf("The average of 1 number is %.2lf",sum);else printf("The average of %d numbers is %.2lf",ctr,sum/ctr);
}

2 PAT 甲级 1109 Group Photo

#include <bits/stdc++.h>
using namespace std;
struct P{string name;int h;P(string _name,int _h):name(_name),h(_h){}
};
int main() {int n,k;cin>>n>>k;vector<P> p;for(int i=0;i<n;++i){string name;int h;cin>>name>>h;p.emplace_back(name,h);}sort(p.begin(),p.end(),[](P&a,P&b){if(a.h!=b.h) return a.h>b.h;return a.name<b.name;});int ctr=0;for(int i=0;i<k;++i){deque<string> q;bool is_right=true; int sz;if(i==0) sz=n-n/k*(k-1);else sz=n/k;for(int j=0;j<sz;++j){if(is_right) q.push_back(p[ctr++].name);else q.push_front(p[ctr++].name);is_right=!is_right;}for(int i=0;i<sz;++i){if(i!=0) cout<<" ";cout<<q.front();q.pop_front();}cout<<endl;}
}

3 PAT 甲级 1110 Complete Binary Tree

#include <bits/stdc++.h>
using namespace std;
int lchild[50],rchild[50];
bool have_p[50];
vector<int> layer;
void BFS(int root){queue<int> q;q.push(root);while(!q.empty()){int now=q.front();q.pop();layer.push_back(now);if(lchild[now]!=-1) q.push(lchild[now]);if(rchild[now]!=-1) q.push(rchild[now]);}
}
int main() {int n;cin>>n;for(int i=0;i<n;++i){string a,b;cin>>a>>b;if(a=="-") lchild[i]=-1;else lchild[i]=atoi(a.c_str());if(b=="-") rchild[i]=-1;else rchild[i]=atoi(b.c_str());if(lchild[i]!=-1) have_p[lchild[i]]=true;if(rchild[i]!=-1) have_p[rchild[i]]=true;}int root=0;for(int i=0;i<n;++i) if(!have_p[i]) root=i;BFS(root);bool is_complete=true,find_no_null=false;for(int i=n-1;i>=0;--i){if(find_no_null&&rchild[layer[i]]==-1) is_complete=false;if(rchild[layer[i]]!=-1) find_no_null=true;if(find_no_null&&(lchild[layer[i]]==-1)) is_complete=false;if(lchild[layer[i]]!=-1) find_no_null=true;}if(is_complete) cout<<"YES "<<layer.back();else cout<<"NO "<<root;
}

4 PAT 甲级 1111 Online Map

#include <bits/stdc++.h>
using namespace std;
const int MAXN=550;
const int INF=0x3f3f3f3f;
struct QNode{int v,c;QNode(int _v,int _c):v(_v),c(_c){}bool operator< (const QNode &r) const{return c>r.c;};
};
struct Edge{int to,cost;Edge(int _to,int _cost):to(_to),cost(_cost){}
};vector<Edge> g1[MAXN],g2[MAXN];
int gdata1[MAXN][MAXN],gdata2[MAXN][MAXN];int dis1[MAXN],dis2[MAXN];bool done[MAXN];
set<int> pre1[MAXN],pre2[MAXN];
void Dijkstra(int s,int mode){auto &dis=(mode==1?dis1:dis2);auto &g=(mode==1?g1:g2);auto &pre=(mode==1?pre1:pre2);memset(dis,INF,sizeof(dis));memset(done,false,sizeof(done));priority_queue<QNode> q;dis[s]=0;q.push(QNode(s,0));while(!q.empty()){int now=q.top().v;q.pop();if(done[now]) continue;done[now]=true;for(auto edge:g[now]){int to=edge.to,cost=edge.cost;if(!done[to]&&dis[to]>=dis[now]+cost){if(dis[to]!=dis[now]+cost) pre[to].clear();dis[to]=dis[now]+cost;//printf("Cost :%d\n",cost);q.emplace(to,dis[to]);pre[to].insert(now);}}}
}
vector<int> path1,path2,tmp;
int min_time=INF,min_ctr=INF;
void DFS1(int to,int time){if(pre1[to].size()==0){if(time<min_time){min_time=time;path1=tmp;}}for(auto from:pre1[to]){tmp.push_back(from);DFS1(from,time+gdata2[from][to]);tmp.pop_back();}
}
void DFS2(int to,int ctr){if(pre2[to].size()==0){if(ctr<min_ctr){min_ctr=ctr;path2=tmp;}}for(auto from:pre2[to]){tmp.push_back(from);DFS2(from,ctr+1);tmp.pop_back();}
}
int main() {int n,m;cin>>n>>m;for(int i=0;i<m;++i){int a,b,c,d,e;cin>>a>>b>>c>>d>>e;gdata1[a][b]=d,gdata2[a][b]=e;g1[a].emplace_back(b,d),g2[a].emplace_back(b,e);if(c==0){gdata1[b][a]=d,gdata2[b][a]=e;g1[b].emplace_back(a,d),g2[b].emplace_back(a,e);}}int s,t;cin>>s>>t;Dijkstra(s,1);    Dijkstra(s,2);DFS1(t,0);DFS2(t,1);reverse(path1.begin(),path1.end());reverse(path2.begin(),path2.end());if(path1!=path2){printf("Distance = %d: ",dis1[t]);for(size_t i=0;i<path1.size();++i){printf("%d -> ",path1[i]);}printf("%d\n",t);printf("Time = %d: ",dis2[t]);for(size_t i=0;i<path2.size();++i){printf("%d -> ",path2[i]);}printf("%d\n",t);}else{printf("Distance = %d; Time = %d: ",dis1[t],dis2[t]);for(size_t i=0;i<path1.size();++i){printf("%d -> ",path1[i]);}printf("%d\n",t);}
}

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

---