2015 Multi-University Training Contest 6

忍不住又补了一题。

只要枚举1与2之间1给2，2给1，什么都不做三种状态。

后面的情况都已经决定了。

（估计只有我比赛的时候把a candy当成a个糖果了吧QAQ）

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <vector>
 5 using namespace std;
 6 typedef pair<int,int> pii;
 7 typedef long long LL;
 8 # define maxn 100010
 9 LL a[maxn],b[maxn],aver;
10 vector <pii> ans;
11 int n;
12 
13 void ans_print(void)
14 {
15     puts("YES");
16     printf("%d
",ans.size());
17     for(int i=0;i<ans.size();i++)
18         printf("%d %d
",ans[i].first,ans[i].second);
19     return;
20 }
21 
22 bool judge(void)
23 {
24     for(int i=2;i<n;i++)
25     {
26         if(a[i]==aver) continue;
27         if(a[i]==aver+1)
28         {
29             a[i]--; a[i+1]++;
30             ans.push_back(pii(i,i+1));
31             continue;
32         }
33         if(a[i]==aver-1&&a[i+1]>0)
34         {
35             a[i]++; a[i+1]--;
36             ans.push_back(pii(i+1,i));
37             continue;
38         }
39         memcpy(a,b,sizeof(a));
40         ans.clear();
41         return false;
42     }
43     if(a[n]==aver&&a[1]==aver) return true;
44     if(a[n]==aver+1&&a[1]==aver-1)
45     {
46         ans.push_back(pii(n,1));
47         return true;
48     }
49     if(a[n]==aver-1&&a[1]==aver+1)
50     {
51         ans.push_back(pii(1,n));
52         return true;
53     }
54     memcpy(a,b,sizeof(a));
55     ans.clear();
56     return false;
57 }
58 
59 int main(void)
60 {
61     int T; cin>>T;
62     while(T--)
63     {
64         scanf("%d",&n);
65         for(int i=1;i<=n;i++) scanf("%d",b+i);
66         LL sum=0;
67         for(int i=1;i<=n;i++) sum+=b[i];
68         if(sum%n) {puts("NO");continue;}
69         aver=sum/(LL)n;
70         memcpy(a,b,sizeof(a));
71         ans.clear();
72         if(a[1]>aver+2||a[1]<aver-2) {puts("NO");continue;}
73         if(judge()){ans_print(); continue;}
74         if(a[1])
75         {
76             ans.push_back(pii(1,2));
77             a[1]--; a[2]++;
78             if(judge()){ans_print(); continue;}
79         }
80         if(a[2])
81         {
82             ans.push_back(pii(2,1));
83             a[1]++; a[2]--;
84             if(judge()){ans_print(); continue;}
85         }
86         puts("NO");
87     }
88     return 0;
89 }

Aguin

1002 Bipartite Graph

1003 Cake

还是把这个补了。

比赛的时候spj写错。放过了很多队（包括我们。

先搜出n<=40的所有情况。

搜索的时候先贪心的找最大的。

最大的不行的时候再找小一点的。这样很快能找到一组解。

其实在1-20内贪心的答案都是对……产生了可以贪的错觉。

第一组不能贪得情况是23 6 。

在20-40一共有9组不能贪的。所以挑挑出来也可以。

n>40的情况不停的取最后的2*m个数字，然后头尾配对放到m组里面。直到n<=40。

然后和之前做好的n<=40的情况合并就好了。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <vector>
 5 using namespace std;
 6 typedef long long LL;
 7 vector<int> ans[41][11][11];
 8 vector<int> tem_ans[11];
 9 int n,m;
10 bool vis[41];
11 
12 bool dfs(int i,int rem,int each)
13 {
14     if(!rem&&i==m)
15     {
16         for(int i=1;i<=m;i++)
17         {
18             for(int j=0;j<tem_ans[i].size();j++)
19             {
20                 int x=tem_ans[i][j];
21                 ans[n][m][i].push_back(x);
22             }
23             tem_ans[i].clear();
24         }
25         return true;
26     }
27     if(!rem&&dfs(i+1,each,each)) return true;
28     for(int pos=n;pos>0;pos--)
29     {
30         if(!vis[pos]&&pos<=rem)
31         {
32             vis[pos]=1;
33             tem_ans[i].push_back(pos);
34             if(dfs(i,rem-pos,each)) return true;
35             tem_ans[i].pop_back();
36             vis[pos]=0;
37         }
38     }
39     return false;
40 }
41 
42 int main(void)
43 {
44     for(n=1;n<=40;n++)
45     {
46         for(m=2;m<=10;m++)
47         {
48             int sum=n*(n+1)/2,each=sum/m;
49             if(sum%m||n<2*m-1) continue;
50             memset(vis,0,sizeof(vis));
51             dfs(1,each,each);
52         }
53     }
54     int T; cin>>T;
55     while(T--)
56     {
57         scanf("%d%d",&n,&m);
58         LL sum=(LL)n*LL(n+1)/2,each=sum/m;
59         if(sum%m||n<2*m-1) {puts("NO"); continue;}
60         puts("YES");
61         for(int i=1;i<=m;i++) tem_ans[i].clear();
62         while(n>40)
63         {
64             for(int i=1;i<=m;i++)
65             {
66                 tem_ans[i].push_back(n-i+1);
67                 tem_ans[i].push_back(n-2*m+i);
68             }
69             n-=2*m;
70         }
71         for(int i=1;i<=m;i++)
72         {
73             printf("%d",ans[n][m][i].size()+tem_ans[i].size());
74             for(int j=0;j<ans[n][m][i].size();j++)
75                 printf(" %d",ans[n][m][i][j]);
76             for(int j=0;j<tem_ans[i].size();j++)
77                 printf(" %d",tem_ans[i][j]);
78             puts("");
79         }
80     }
81     return 0;
82 }

Aguin

1004 Deal

1005 Easy Sequence

1006 First One

终于补了这个。简直感动哭。

因为做法知道了。一直卡在边界。

后来直接把power[0]改成0。把[0,1),[1,2)合成[0,2)。

然后只有在区间左端点合法的时候再加tem。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <algorithm>
 4 using namespace std;
 5 typedef long long LL;
 6 # define maxn 100010
 7 LL sum[maxn],power[40];
 8 
 9 int main(void)
10 {
11     power[0]=1;
12     for(int i=1;i<40;i++) power[i]=power[i-1]<<1;
13     power[0]=0;
14     int T; cin>>T;
15     while(T--)
16     {
17         int n; scanf("%d",&n);
18         for(int i=1;i<=n;i++) scanf("%I64d",sum+i);
19         for(int i=2;i<=n;i++) sum[i]+=sum[i-1];
20         LL ans=0;
21         for(int i=0;i<40;i++)
22         {
23             if(sum[n]<power[i]) break;
24             LL tem=0,l=0,r=0;
25             for(int j=1;j<=n;j++)
26             {
27                 l=max(l,(LL)j);
28                 while(l<n&&sum[l]-sum[j-1]<power[i]) l++; 
29                 while(r<n&&sum[r+1]-sum[j-1]<power[i+1]) r++;
30                 if(sum[l]-sum[j-1]>=power[i]) tem+=(l+r)*(r-l+1)/2+(r-l+1)*(LL)j;
31             }
32             ans+=tem*(LL)(i+1);
33         }
34         printf("%I64d
",ans);
35     }
36     return 0;
37 }

Aguin

1007 Group

1008 Hiking

先区间左端点升序排序。再以右端点为关键字搞个小根堆。

每次取右端点符合条件且最小的即可。

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <algorithm>
 5 # include <queue>
 6 # include <vector>
 7 using namespace std;
 8 # define maxn 100010
 9 bool vis[maxn];
10 vector<int> ans;
11 
12 struct node
13 {
14     int id,l,r;
15     friend bool operator < (node a,node b)
16     {
17         return a.r>b.r;
18     }
19 } soda[maxn];
20 priority_queue <node> q;
21 
22 bool cmp(node a,node b)
23 {
24     return a.l<b.l;
25 }
26 
27 int main(void)
28 {
29     int T ;cin>>T;
30     while(T--)
31     {
32         int n; scanf("%d",&n);
33         memset(vis,0,sizeof(vis));
34         for(int i=1;i<=n;i++) soda[i].id=i;
35         for(int i=1;i<=n;i++) scanf("%d",&soda[i].l);
36         for(int i=1;i<=n;i++) scanf("%d",&soda[i].r);
37         sort(soda+1,soda+1+n,cmp);    
38         int cnt=0,pos=1;
39         ans.clear();
40         while(!q.empty()) q.pop();
41         while(soda[pos].l==0)
42         {
43             q.push(soda[pos]);
44             pos++;
45             if(pos>n) break;
46         }
47         while(!q.empty())
48         {
49             node tem=q.top(); q.pop();
50             if(tem.r<cnt) continue;
51             cnt++;
52             vis[tem.id]=1;
53             ans.push_back(tem.id);
54             while(soda[pos].l==cnt)
55             {
56                 q.push(soda[pos]);
57                 pos++;
58                 if(pos>n) break;
59             }
60         }
61         printf("%d
",ans.size());
62         for(int i=0;i<ans.size();i++) printf("%d ",ans[i]);
63         for(int i=1;i<=n;i++) if(!vis[i]) printf("%d ",i);
64         printf("
");
65     }
66     return 0;
67 }

Aguin

1009 In Touch

1010 Just A String

1011 Key Set

组合数性质。

加和为2^n。奇偶和相等。

 1 # include <iostream>
 2 # include <cstdio>
 3 using namespace std;
 4 typedef long long LL;
 5 const LL mod=1000000007;
 6 
 7 LL Pow(LL m,LL n)
 8 {
 9     LL b=1;
10     while(n>0)
11     {
12         if(n&1) b=(b*m)%mod;
13         n=n>>1;
14         m=(m*m)%mod;
15     }
16     return b;
17 } 
18 
19 int main(void)
20 {
21     int T ;cin>>T;
22     while(T--)
23     {
24         LL n; scanf("%I64d",&n);
25         n--;
26         LL ans=Pow(2,n)-1;
27         printf("%I64d
",ans);
28     }
29     return 0;
30 }

Aguin