2015 Multi-University Training Contest 6

忍不住又补了一题。

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

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

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

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <vector>

 using namespace std;

 typedef pair<int,int> pii;

 typedef long long LL;

 # define maxn

 LL a[maxn],b[maxn],aver;

 vector <pii> ans;

 int n;

 void ans_print(void)

 {

     puts("YES");

     printf("%d\n",ans.size());

     for(int i=;i<ans.size();i++)

         printf("%d %d\n",ans[i].first,ans[i].second);

     return;

 }

 bool judge(void)

 {

     for(int i=;i<n;i++)

     {

         if(a[i]==aver) continue;

         if(a[i]==aver+)

         {

             a[i]--; a[i+]++;

             ans.push_back(pii(i,i+));

             continue;

         }

         if(a[i]==aver-&&a[i+]>)

         {

             a[i]++; a[i+]--;

             ans.push_back(pii(i+,i));

             continue;

         }

         memcpy(a,b,sizeof(a));

         ans.clear();

         return false;

     }

     if(a[n]==aver&&a[]==aver) return true;

     if(a[n]==aver+&&a[]==aver-)

     {

         ans.push_back(pii(n,));

         return true;

     }

     if(a[n]==aver-&&a[]==aver+)

     {

         ans.push_back(pii(,n));

         return true;

     }

     memcpy(a,b,sizeof(a));

     ans.clear();

     return false;

 }

 int main(void)

 {

     int T; cin>>T;

     while(T--)

     {

         scanf("%d",&n);

         for(int i=;i<=n;i++) scanf("%d",b+i);

         LL sum=;

         for(int i=;i<=n;i++) sum+=b[i];

         if(sum%n) {puts("NO");continue;}

         aver=sum/(LL)n;

         memcpy(a,b,sizeof(a));

         ans.clear();

         if(a[]>aver+||a[]<aver-) {puts("NO");continue;}

         if(judge()){ans_print(); continue;}

         if(a[])

         {

             ans.push_back(pii(,));

             a[]--; a[]++;

             if(judge()){ans_print(); continue;}

         }

         if(a[])

         {

             ans.push_back(pii(,));

             a[]++; a[]--;

             if(judge()){ans_print(); continue;}

         }

         puts("NO");

     }

     return ;

 }

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的情况合并就好了。

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <vector>

 using namespace std;

 typedef long long LL;

 vector<int> ans[][][];

 vector<int> tem_ans[];

 int n,m;

 bool vis[];

 bool dfs(int i,int rem,int each)

 {

     if(!rem&&i==m)

     {

         for(int i=;i<=m;i++)

         {

             for(int j=;j<tem_ans[i].size();j++)

             {

                 int x=tem_ans[i][j];

                 ans[n][m][i].push_back(x);

             }

             tem_ans[i].clear();

         }

         return true;

     }

     if(!rem&&dfs(i+,each,each)) return true;

     for(int pos=n;pos>;pos--)

     {

         if(!vis[pos]&&pos<=rem)

         {

             vis[pos]=;

             tem_ans[i].push_back(pos);

             if(dfs(i,rem-pos,each)) return true;

             tem_ans[i].pop_back();

             vis[pos]=;

         }

     }

     return false;

 }

 int main(void)

 {

     for(n=;n<=;n++)

     {

         for(m=;m<=;m++)

         {

             int sum=n*(n+)/,each=sum/m;

             if(sum%m||n<*m-) continue;

             memset(vis,,sizeof(vis));

             dfs(,each,each);

         }

     }

     int T; cin>>T;

     while(T--)

     {

         scanf("%d%d",&n,&m);

         LL sum=(LL)n*LL(n+)/,each=sum/m;

         if(sum%m||n<*m-) {puts("NO"); continue;}

         puts("YES");

         for(int i=;i<=m;i++) tem_ans[i].clear();

         while(n>)

         {

             for(int i=;i<=m;i++)

             {

                 tem_ans[i].push_back(n-i+);

                 tem_ans[i].push_back(n-*m+i);

             }

             n-=*m;

         }

         for(int i=;i<=m;i++)

         {

             printf("%d",ans[n][m][i].size()+tem_ans[i].size());

             for(int j=;j<ans[n][m][i].size();j++)

                 printf(" %d",ans[n][m][i][j]);

             for(int j=;j<tem_ans[i].size();j++)

                 printf(" %d",tem_ans[i][j]);

             puts("");

         }

     }

     return ;

 }

Aguin

1004 Deal

1005 Easy Sequence

1006 First One

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

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

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

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

 # include <iostream>

 # include <cstdio>

 # include <algorithm>

 using namespace std;

 typedef long long LL;

 # define maxn

 LL sum[maxn],power[];

 int main(void)

 {

     power[]=;

     for(int i=;i<;i++) power[i]=power[i-]<<;

     power[]=;

     int T; cin>>T;

     while(T--)

     {

         int n; scanf("%d",&n);

         for(int i=;i<=n;i++) scanf("%I64d",sum+i);

         for(int i=;i<=n;i++) sum[i]+=sum[i-];

         LL ans=;

         for(int i=;i<;i++)

         {

             if(sum[n]<power[i]) break;

             LL tem=,l=,r=;

             for(int j=;j<=n;j++)

             {

                 l=max(l,(LL)j);

                 while(l<n&&sum[l]-sum[j-]<power[i]) l++;

                 while(r<n&&sum[r+]-sum[j-]<power[i+]) r++;

                 if(sum[l]-sum[j-]>=power[i]) tem+=(l+r)*(r-l+)/+(r-l+)*(LL)j;

             }

             ans+=tem*(LL)(i+);

         }

         printf("%I64d\n",ans);

     }

     return ;

 }

Aguin

1007 Group

1008 Hiking

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

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

 # include <iostream>

 # include <cstdio>

 # include <cstring>

 # include <algorithm>

 # include <queue>

 # include <vector>

 using namespace std;

 # define maxn

 bool vis[maxn];

 vector<int> ans;

 struct node

 {

     int id,l,r;

     friend bool operator < (node a,node b)

     {

         return a.r>b.r;

     }

 } soda[maxn];

 priority_queue <node> q;

 bool cmp(node a,node b)

 {

     return a.l<b.l;

 }

 int main(void)

 {

     int T ;cin>>T;

     while(T--)

     {

         int n; scanf("%d",&n);

         memset(vis,,sizeof(vis));

         for(int i=;i<=n;i++) soda[i].id=i;

         for(int i=;i<=n;i++) scanf("%d",&soda[i].l);

         for(int i=;i<=n;i++) scanf("%d",&soda[i].r);

         sort(soda+,soda++n,cmp);

         int cnt=,pos=;

         ans.clear();

         while(!q.empty()) q.pop();

         while(soda[pos].l==)

         {

             q.push(soda[pos]);

             pos++;

             if(pos>n) break;

         }

         while(!q.empty())

         {

             node tem=q.top(); q.pop();

             if(tem.r<cnt) continue;

             cnt++;

             vis[tem.id]=;

             ans.push_back(tem.id);

             while(soda[pos].l==cnt)

             {

                 q.push(soda[pos]);

                 pos++;

                 if(pos>n) break;

             }

         }

         printf("%d\n",ans.size());

         for(int i=;i<ans.size();i++) printf("%d ",ans[i]);

         for(int i=;i<=n;i++) if(!vis[i]) printf("%d ",i);

         printf("\n");

     }

     return ;

 }

Aguin

1009 In Touch

1010 Just A String

1011 Key Set

组合数性质。

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

 # include <iostream>

 # include <cstdio>

 using namespace std;

 typedef long long LL;

 const LL mod=;

 LL Pow(LL m,LL n)

 {

     LL b=;

     while(n>)

     {

         if(n&) b=(b*m)%mod;

         n=n>>;

         m=(m*m)%mod;

     }

     return b;

 } 

 int main(void)

 {

     int T ;cin>>T;

     while(T--)

     {

         LL n; scanf("%I64d",&n);

         n--;

         LL ans=Pow(,n)-;

         printf("%I64d\n",ans);

     }

     return ;

 }

Aguin

巴特西

2015 Multi-University Training Contest 6

最新文章

热门文章