首页 > 代码库 > 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;}
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;}
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 }
Codeforces Round #273 (Div. 2)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。