2016 China Collegiate Programming Contest Final

Problem A. The Third Cup is Free  签到

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int inf=0x3f3f3f3f;
 4 const int maxn=100005;
 5 int T,n,a[maxn],b[4],tot;
 6 int main()
 7 {
 8     scanf("%d",&T);
 9     for (int cas=1;cas<=T;++cas) {
10         scanf("%d",&n);
11         tot=0;
12         for (int i=0;i<n;++i) {
13             scanf("%d",&a[i]);
14             tot+=a[i];
15         }
16         sort(a,a+n);
17         for (int i=n-1;i>=0;i-=3)
18             if (i>=2)
19                 tot-=a[i-2];
20         printf("Case #%d: %d\n",cas,tot);
21     }
22     return 0;
23 }      

View Code

Problem B. Wash 

1 #include <cstdio>
 2 #include <algorithm>
 3 #include <queue>
 4 using namespace std;
 5 typedef pair<long long,long long> pll;
 6 const int maxn=100005;
 7 const int maxl=1000005;
 8 const long long inf=0x3f3f3f3f3f3f3f3f;
 9 int T,n,m1,m2;
10 long long t1[maxn],t2[maxn],res1[maxl],res2[maxl];
11 priority_queue<pll,vector<pll>,greater<pll> > que;
12 int main()
13 {
14     scanf("%d",&T);
15     for (int cas=1;cas<=T;++cas) {
16         scanf("%d%d%d",&n,&m1,&m2);
17         for (int i=0;i<m1;++i) {
18             scanf("%I64d",&t1[i]);
19             que.push(pll(t1[i],t1[i]));
20         }
21         for (int i=1;i<=n;++i) {
22             res1[i]=que.top().first;
23             long long id=que.top().second;
24             que.pop();
25             que.push(pll(res1[i]+id,id));
26         }
27         while (!que.empty())
28             que.pop();
29         for (int i=0;i<m2;++i) {
30             scanf("%I64d",&t2[i]);
31             que.push(pll(t2[i],t2[i]));
32         }
33         for (int i=1;i<=n;++i) {
34             res2[i]=que.top().first;
35             long long id=que.top().second;
36             que.pop();
37             que.push(pll(res2[i]+id,id));
38         }
39         while (!que.empty())
40             que.pop();
41         long long res=0;
42         for (int i=1;i<=n;++i)
43             res=max(res,res1[i]+res2[n-i+1]);
44         printf("Case #%d: %I64d\n",cas,res);
45     }
46     return 0;
47 }      

View Code

Problem G. Pandaland 删边暴力最短路，在暴力过程中分支界限法剪枝。

1 #include <bits/stdc++.h>
 2 #define REP(i,x,y) for(int i=x;i<(y);i++)
 3 const long long mod = 1e9+7;
 4 const double ex = 1e-10;
 5 #define inf 0x3f3f3f3f
 6 #define maxn 8010
 7 using namespace std;
 8 typedef pair<int,int>pii;
 9 int n,m;
10 map<pii,int>ma;
11 struct edge{
12     int v,to,cost,flag;
13     edge(){}
14     edge(int v,int _to,int _cost,int flag=0):v(v),to(_to),cost(_cost),flag(flag){}
15 };
16 int tmp = inf;
17 vector<edge>edges;
18 vector<int>e[maxn];
19 inline void add_edge(int u,int v,int w) {
20     edges.push_back(edge(u,v,w,0));
21     edges.push_back(edge(v,u,w,0));
22     int cnt=edges.size();
23     e[u].push_back(cnt-2);
24     e[v].push_back(cnt-1);
25 }
26 int dis[maxn],vis[maxn];
27 void spfa(int st) {
28     memset(dis,inf,sizeof(int)*(n+5));memset(vis,0,sizeof(int)*(n+5));
29     dis[st]=0;vis[st]=1;
30     priority_queue<int>que;
31     que.push(st);
32     while(!que.empty()){
33         int now=que.top();que.pop();
34         for(int i=0;i<e[now].size();i++){
35             int next=edges[e[now][i]].to;int len=edges[e[now][i]].cost;
36             if(edges[e[now][i]].flag==1) continue;
37             if(dis[next]>dis[now]+len){
38                 dis[next]=dis[now]+len;
39                 if(!vis[next]&&dis[next] <= tmp){
40                     que.push(next);
41                     vis[next]=1;
42                 }
43             }
44         }
45         vis[now]=0;
46     }
47 }
48 int main()
49 {
50     int T,cas=1;scanf("%d",&T);
51     while(T--) {
52         scanf("%d",&m);
53         n=0;
54         edges.clear();ma.clear();
55         for(int i=0;i<maxn;i++) e[i].clear();
56         REP(i,1,m+1) {
57             int u,v,x,y,w;scanf("%d %d %d %d %d",&u,&v,&x,&y,&w);
58             pii now=make_pair(u,v),now2=make_pair(x,y);
59             if(ma.count(now)==0) ma[now]=++n;
60             if(ma.count(now2)==0) ma[now2]=++n;
61           //  cout<<ma[now]<<" "<<m
62             add_edge(ma[now],ma[now2],w);
63            // add_edge(ma[now2],ma[now],w);
64         }
65         int ans=inf+(inf/2);
66         for(int i=0;i<edges.size();i++) {
67             if(i%2) continue;
68             edges[i].flag=1;
69             edges[i^1].flag=1;
70             tmp = ans - edges[i].cost;
71             spfa(edges[i].v);
72           //  REP(i,1,n+1) cout<<i<<" "<<dis[i]<<endl;
73             ans=min(ans,edges[i].cost+dis[edges[i].to]);
74             edges[i].flag=0;
75             edges[i^1].flag=0;
76         }
77         if (ans >= inf) ans = 0;
78         printf("Case #%d: %d\n",cas++,ans);
79     }
80     return 0;
81 }      

View Code

Problem H. Engineer Assignment 状压DP

1 #include <bits/stdc++.h>
 2 using namespace std;
 3 int T,n,m,p[15][4],c[15][3],dp[11][1024];
 4 bool ok[11][1024];
 5 inline bool check(int x,int st) {
 6     for (int k=1;k<=p[x][0];++k) {
 7         bool flag=false;
 8         for (int i=0;i<m;++i) {
 9             if ((st>>i)&1)
10                 for (int j=1;j<=c[i][0];++j)
11                     if (p[x][k]==c[i][j]) {
12                         flag=true;
13                         break;
14                     }
15             if (flag)
16                 break;
17         }
18         if (!flag)
19             return false;
20     }
21     return true;
22 }
23 int main()
24 {
25     scanf("%d",&T);
26     for (int cas=1;cas<=T;++cas) {
27         scanf("%d%d",&n,&m);
28         for (int i=1;i<=n;++i) {
29             scanf("%d",&p[i][0]);
30             for (int j=1;j<=p[i][0];++j)
31                 scanf("%d",&p[i][j]);
32         }
33         for (int i=0;i<m;++i) {
34             scanf("%d",&c[i][0]);
35             for (int j=1;j<=c[i][0];++j)
36                 scanf("%d",&c[i][j]);
37         }
38         int s=1<<m;
39         for (int i=1;i<=n;++i)
40             for (int j=0;j<s;++j) {
41                 ok[i][j]=check(i,j);
42                 dp[i][j]=0;
43             }
44         for (int i=1;i<=n;++i) {
45             for (int j=0;j<s;++j)
46                 dp[i][j]=dp[i-1][j];
47             for (int j=0;j<s;++j) if (ok[i][j])
48                 for (int k=0;k<s;++k)
49                     if ((j&k)==0)
50                         dp[i][j^k]=max(dp[i][j^k],dp[i-1][k]+1);
51         }
52         int res=0;
53         for (int i=1;i<=n;++i)
54             for (int j=0;j<s;++j)
55                 res=max(res,dp[i][j]);
56         printf("Case #%d: %d\n",cas,res);
57     }
58     return 0;
59 }      

View Code

Problem I. Mr. Panda and Crystal 类似于SPFA一样DP，之后裸的完全背包

1 #include <bits/stdc++.h>
  2 const long long mod = 1e9+7;
  3 const double ex = 1e-10;
  4 #define inf 0x3f3f3f3f
  5 using namespace std;
  6 int cost[300];
  7 int vv[300];
  8 int vis[300];
  9 struct node{
 10     int to,id,nex;
 11 }E[40044];
 12 int head[300];
 13 int cnt = 0;
 14 void addedge(int x,int y,int id){
 15     E[cnt] = node{y,id,head[x]};
 16     head[x] = cnt++;
 17 }
 18 int num[300];
 19 typedef pair<int,int> pii;
 20 int dp[10001];
 21 vector <pii> fun[300][300];
 22 int main()
 23 {
 24     int T;
 25     scanf("%d",&T);
 26     int cas = 1;
 27     while (T--){
 28         int n,m,k;
 29         scanf("%d%d%d",&m,&n,&k);
 30         memset(head,-1,sizeof(head));
 31         memset(num,0,sizeof(num));
 32         for (int i = 1 ; i<300; i++)
 33         for (int j = 0; j<300;j++){
 34             fun[i][j].clear();
 35         }
 36         cnt = 0;
 37         queue<int> Q;
 38         for (int i = 1; i<=n;i++){
 39             int t;
 40             scanf("%d",&t);
 41             if ( t == 1 ){
 42                 int d;
 43                 scanf("%d",&d);
 44                 cost[i] = d;
 45                 Q.push(i);
 46                 vis[i] = 1;
 47             }
 48             else cost[i] = inf;
 49             int c;
 50             scanf("%d",&c);
 51             vv[i] = c;
 52         }
 53         for (int i = 1; i <= k ; i++){
 54             int x,y;
 55             scanf("%d%d",&x,&y);
 56             num[x]++;
 57             for (int j = 1; j <= y ; j++){
 58                 int u,v;
 59                 scanf("%d%d",&u,&v);
 60                 addedge(u,x,num[x]);
 61                 fun[x][num[x]].push_back(make_pair(u,v));
 62             }
 63         }
 64 
 65         while (!Q.empty()){
 66             int now = Q.front();
 67             Q.pop();
 68             for (int i = head[now] ; i!=-1 ; i=E[i].nex){
 69                 int to = E[i].to;
 70                 int id = E[i].id;
 71                 int sum = 0;
 72                 for (int j = 0 ; j<fun[to][id].size() ; j++){
 73                     if (cost[fun[to][id][j].first]==inf) {sum = inf;break;}
 74                     sum += cost[fun[to][id][j].first] * fun[to][id][j].second;
 75                     if (sum > inf ) break;
 76                 }
 77                 if (sum < cost[to]){
 78                     cost[to] = sum;
 79                     if (!vis[to]){
 80                         Q.push(to);
 81                         vis[to] = 1;
 82                     }
 83                 }
 84             }
 85             vis[now] = 0;
 86         }
 87         memset(dp,0,sizeof(dp));
 88         for (int i = 1; i<=n; i++){
 89             for (int j = cost[i]; j<=m; j++){
 90                 dp[j] = (max(dp[j - cost[i]] + vv[i],dp[j]));
 91             }
 92         }
 93         int ans = 0;
 94         for (int i = 1 ; i<=m ;i++){
 95             ans = max(ans,dp[i]);
 96         }
 97         printf("Case #%d: %d\n",cas++,ans);
 98     }
 99     return 0;
100 }      

View Code

Problem J. Worried School 目测岛娘嘲讽黄金熊

1 #include <bits/stdc++.h>
 2 const long long mod = 1e9+7;
 3 const double ex = 1e-10;
 4 #define inf 0x3f3f3f3f
 5 using namespace std;
 6 string S[6][25];
 7 map<string,int> M;
 8 int main()
 9 {
10     int T;
11     int cas = 0;
12     scanf("%d",&T);
13     while (T--){
14         int n;
15         scanf("%d",&n);
16         string SS;
17         cin >> SS;
18         for (int i = 0 ;i<=5 ;i++)
19         {
20             for (int j = 0 ; j<20 ;j++)
21             cin >> S[i][j];
22         }
23         int i = 0;
24         for (i = 0 ; i<=n; i++){
25             M.clear();
26             int cnt = 0;
27             for (int j = 1; j <= n-i ;j++){
28                 while (M[S[cnt%5][cnt/5]]!=0){
29                     cnt++;
30                 }
31                 //cout << S[cnt%5][cnt/5] << endl;
32                 M[S[cnt%5][cnt/5]]++;
33             }
34             cnt = 0;
35             for (int j = 1; j<=i ;j++){
36                 while (M[S[5][cnt]]!=0){
37                     cnt++;
38                 }
39                 //cout << S[5][cnt] << endl;
40                 M[S[5][cnt]]++;
41             }
42             if ( M[SS] == 0 ) break;
43         }
44         printf("Case #%d: ",++cas);
45         if (i>n) {
46             printf("ADVANCED!\n");
47         }
48         else {
49             printf("%d\n",i);
50         }
51     }
52     return 0;
53 }      

View Code

Problem L. Daylight Saving Time 时间模拟

1 #include <bits/stdc++.h>
 2 #define maxn 100010
 3 #define inf 0x3f3f3f3f
 4 #define REP(i,x,y) for(int i=x;i<(y);i++)
 5 #define RREP(i,x,y) for(int i=x;i>(y);i--)
 6 using namespace std;
 7 typedef long long ll;
 8 typedef pair<int,int> pii;
 9 inline int check(int month,int flag) {
10     if(flag==1&&month==2) return 29;
11     else if(flag==0&&month==2) return 28;
12     if(month==1||month==3||month==5||month==7||month==8||month==10||month==12) return 31;
13     else return 30;
14 }
15 int main()
16 {
17     int T;scanf("%d",&T);int cas=1;
18     while(T--) {
19         int year,month,day,hour,minute,second,flag=0;
20         scanf("%d-%d-%d",&year,&month,&day);
21         scanf("%d:%d:%d",&hour,&minute,&second);
22         printf("Case #%d: ",cas++);
23         if((year%4==0&&year%100!=0)||(year%400==0)) flag=1;
24        // int limit=check(month,flag);
25         if(month>3&&month<11) {puts("PDT");continue;}
26         else if(month<3&&month>11) {puts("PST");continue;}
27         if(month==1||month==2) {
28             year--;
29             if(month==1) month=13;
30             else month=14;
31         }
32         int c=year/100;int y=year%100;
33         if(month==3) {
34             int tmp=0,cnt=0;
35             for(int i=1;i<=31;i++) {
36                 int w=y+y/4+c/4-2*c+26*(month+1)/10+i-1;
37                 if((w%7+7)%7==0) cnt++;
38                 if(cnt==2) {tmp=i;break;}
39             }
40           //  cout<<tmp<<endl;
41             if(tmp<day) puts("PST");
42             else if(tmp>day) puts("PDT");
43             else {
44                 if(hour==2) puts("Neither");
45                 else if(hour>2) puts("PDT");
46                 else puts("PST");
47             }
48         }
49         if(month==11) {
50             int tmp=0,cnt=0;
51             for(int i=1;i<=31;i++) {
52                 int w=y+y/4+c/4-2*c+26*(month+1)/10+i-1;
53                 if((w%7+7)%7==0) cnt++;
54                 if(cnt==1) {tmp=i;break;}
55             }
56             if(tmp<day) puts("PDT");
57             else if(tmp>day) puts("PST");
58             else {
59                 if(hour==1) puts("Both");
60                 else if(hour<1) puts("PDT");
61                 else puts("PST");
62             }
63         }
64     }
65 }      

View Code

转载于:https://www.cnblogs.com/myhappinessisall/p/7599014.html