首页 > 代码库 > Codeforces Round #273 (Div. 2)

Codeforces Round #273 (Div. 2)

a.题意很简单,有五个人每个人开始有相同不为0数量的赌注,赌注可以在他们之间流通,给出最终状态,问原来每个人的赌注是多少。 这题在cf a题中也算是个大水题了,加起来看能不能被5整除就可以了。  可是。。。 坑爹的cf卡的要死,2分钟敲完准备交,11分钟才交上去,然后发现wa,然后再读了几遍题发现忘记判断0的情况,又等好久才交上去,20几分钟才A。。。

 

b.n个人放入m堆,两个人在相同一堆就有一个关系,然后问最多的关系和最小的关系。 最多关系的情况就是尽量放在一堆,最小的关系就是尽量分开来分。

#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>#include <algorithm>#include <string>#include <queue>#include <stdlib.h>using namespace std;int main(){    long long int n,m;    cin>>n>>m;    long long tmp=n-m+1;    long long int yu=n%m;    tmp=n/m;    long long mi=0;    for(int i=1;i<=m;i++)    {        if(yu!=0)        {            mi+= (tmp+1)*tmp/2;            yu--;        }        else mi+=(tmp-1)*tmp/2;    }    cout<<mi<<" "<<(n-m+1)*(n-m)/2;    return 0;}
View Code

 

c.这题还是比较坑,开始苦想各种解法,各种贪心,最后想出来时发现三行代码搞定。

#include <iostream>#include <stdio.h>#include <string.h>#include <math.h>#include <algorithm>#include <string>#include <queue>#include <stdlib.h>using namespace std;long long g[5];int main(){    for(int i=0;i<3;i++)        scanf("%d",g+i);    sort(g,g+3);    long long ans;    long long x=g[1]-g[0],y=g[2]-g[0];    if( g[2]>=2*(g[0]+g[1]) )        ans=g[0]+g[1];    else ans=(g[2]+g[0]+g[1])/3;    cout<<ans;    return 0;}
View Code

 

d.这题要用到一点dp了,首先求出最大高度,即最大的h使得 h(h+1)/2<(r+g),求出高度后dp求出高度为i时有j个红色块的方法数(1<=i<=h,0<=j<=r),然后枚举r的个数是的r+g=h*(h+1)/2,记录总和即可。

(注意能不用取模尽量不用取模,取模操作比加减操作慢太多吧。估计有个10几倍吧,这题直接取模用了1.5s,用减法只需0.8s)

 1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 #include <math.h> 5 #include <algorithm> 6 #include <string> 7 #include <queue> 8 #include <stdlib.h> 9 using namespace std;10 #define MOD 100000000711 12 long long int dp[402000][2];13 14 15 long long int r,g;16 17 int main()18 {19     cin>>r>>g;20     long long h;21     for(h=1;h*(h+1)/2<=r+g;h++) ;22     h--;23     int a=0;24     memset(dp,0,sizeof(dp));25     dp[1][a]=1;26     dp[0][a]=1;27     for(int i=2;i<=h;i++)28     {29         for(int j=0;j<=r;j++)30             dp[j][a^1]=0;31         for(int j=0;j<=r;j++)32             if(j>=i)33                 dp[j][a^1] = (dp[j][a]+dp[j-i][a])%MOD;34             else35                 dp[j][a^1] = dp[j][a];36         a=a^1;37     }38     long long ans=0;39     long long cnt=h*(h+1)/2;40     for(int i=0;i<=r;i++)41     {42         if( cnt-i<=g &&cnt-i>=0)43         {44             ans = (ans+dp[i][a])%MOD;45         }46     }47     cout<<(ans+MOD)%MOD;48     return 0;49 }
View Code

 

Codeforces Round #273 (Div. 2)