首页 > 代码库 > 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 }
View Code

 

 

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 }
View Code

 

 

 

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 }
View Code

 

 

 

 

end

2014ACM/ICPC亚洲区广州站 北大出题