首页 > 代码库 > 2014ACM/ICPC亚洲区广州站 北大出题
2014ACM/ICPC亚洲区广州站 北大出题
http://acm.hdu.edu.cn/showproblem.php?pid=5131
现场赛第一个题,水题。题意:给水浒英雄排序,按照杀人数大到小,相同按照名字字典序小到大。输出。然后对每个查询的名字,计数有多少人杀人数大于他,输出个数加1,计数有多少人杀人数相同,但名字小,如果没有不输出,否则输出个数加1。
1 #include<cstdio> 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 struct G{ 6 string name; 7 int kill; 8 friend bool operator <(const G a,const G b){ 9 return a.kill>b.kill||(a.kill==b.kill&&a.name<b.name);10 }11 }g[512];12 string str;13 int main(){14 int n,m,id;15 while(~scanf("%d",&n),n){16 for(int i=0;i<n;i++){17 cin>>g[i].name>>g[i].kill;18 }19 sort(g,g+n);20 for(int i=0;i<n;i++){21 cout<<g[i].name<<" "<<g[i].kill<<endl;22 }23 scanf("%d",&m);24 while(m--){25 cin>>str;26 for(int i=0;i<n;i++){27 if(str==g[i].name){28 id=i;29 break;30 }31 }32 int ansa=1,ansb=1;33 for(int i=0;i<id;i++){34 if(g[i].kill>g[id].kill){35 ansa++;36 }37 else{38 ansb++;39 }40 }41 printf("%d",ansa);42 if(ansb>1){43 printf(" %d",ansb);44 }45 puts("");46 }47 }48 return 0;49 }
http://acm.hdu.edu.cn/showproblem.php?pid=5137
第二题,最短路。题意:给一个n点m边带权无向图,可以破坏2到n-1号中任意一个,问破坏哪个后1到n的最短路最长。做法:枚举破坏的点,对于每个最短路,求最大值。
1 #include<cstdio> 2 #include<cstring> 3 #include<queue> 4 #define mt(a,b) memset(a,b,sizeof(a)) 5 using namespace std; 6 const int inf=0x3f3f3f3f; 7 bool can[64]; 8 class Spfa { ///单源最短路o(2*ME) 9 typedef int typec;///边权的类型10 static const int ME=2010;///边的个数11 static const int MV=64;///点的个数12 struct E {13 int v,next;14 typec w;15 } e[ME];16 int n,le,head[MV],inque[MV];17 typec dist[MV];18 bool used[MV];19 queue<int> q;20 public:21 void init(int tn) { ///传入点的个数22 n=tn;23 le=0;24 mt(head,-1);25 }26 void add(int u,int v,typec w) {27 e[le].v=v;28 e[le].w=w;29 e[le].next=head[u];30 head[u]=le++;31 }32 bool solve(int s) { ///传入起点,下标0开始,存在负环返回false33 for(int i=0; i<=n; i++) {34 dist[i]=inf;35 used[i]=true;36 inque[i]=0;37 }38 used[s]=false;39 dist[s]=0;40 inque[s]++;41 while(!q.empty()) q.pop();42 q.push(s);43 while(!q.empty()) {44 int u=q.front();45 q.pop();46 used[u]=true;47 for(int i=head[u]; ~i; i=e[i].next) {48 int v=e[i].v;49 if(can[v]) continue;50 if(dist[v]>dist[u]+e[i].w) {51 dist[v]=dist[u]+e[i].w;52 if(used[v]) {53 used[v]=false;54 q.push(v);55 inque[v]++;56 if(inque[v]>n) return false;57 }58 }59 }60 }61 return true;62 }63 typec getdist(int id) {64 return dist[id];65 }66 } g;67 int main(){68 int n,m,u,v,w;69 while(~scanf("%d%d",&n,&m),n|m){70 g.init(n);71 while(m--){72 scanf("%d%d%d",&u,&v,&w);73 g.add(u,v,w);74 g.add(v,u,w);75 }76 int ans=0;77 for(int i=2;i<n;i++){78 mt(can,0);79 can[i]=true;80 g.solve(1);81 ans=max(ans,g.getdist(n));82 }83 if(ans==inf){84 puts("Inf");85 continue;86 }87 printf("%d\n",ans);88 }89 return 0;90 }
http://acm.hdu.edu.cn/showproblem.php?pid=5135
第三题,bfs。题意:给n个棒子的长度,可以任意挑3个一组组成三角形,不一定要全用完,问最后三角形之和最大是多少。做法:用二进制表示是否用过某个棒子,然后bfs。
1 #include<cstdio> 2 #include<cstring> 3 #include<cmath> 4 #include<queue> 5 #define mt(a,b) memset(a,b,sizeof(a)) 6 using namespace std; 7 double area_triangle(double a,double b,double c) {//计算三角形面积,输入三边长 8 double s=(a+b+c)/2; 9 return sqrt(s*(s-a)*(s-b)*(s-c));10 }11 double len[16],ans;12 bool vis[1<<12][1<<12];13 int n;14 struct Q{15 int sta;16 double area;17 }now,pre;18 queue<Q> q;19 bool judge(double x,double y,double z){20 return x+y>z&&x+z>y&&y+z>x;21 }22 void bfs(){23 mt(vis,0);24 now.sta=0;25 now.area=0;26 while(!q.empty()) q.pop();27 q.push(now);28 while(!q.empty()){29 pre=q.front();30 q.pop();31 ans=max(ans,pre.area);32 for(int i=0;i<n;i++){33 if((pre.sta>>i)&1) continue;34 for(int j=i+1;j<n;j++){35 if((pre.sta>>j)&1) continue;36 for(int k=j+1;k<n;k++){37 if((pre.sta>>k)&1) continue;38 if(!judge(len[i],len[j],len[k])) continue;39 now.sta=pre.sta|(1<<i)|(1<<j)|(1<<k);40 if(vis[pre.sta][now.sta]) continue;41 vis[pre.sta][now.sta]=true;42 now.area=pre.area+area_triangle(len[i],len[j],len[k]);43 q.push(now);44 }45 }46 }47 }48 }49 int main(){50 while(~scanf("%d",&n),n){51 for(int i=0;i<n;i++){52 scanf("%lf",&len[i]);53 }54 ans=0;55 bfs();56 printf("%.2f\n",ans);57 }58 return 0;59 }
end
2014ACM/ICPC亚洲区广州站 北大出题
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。