Codeforces Round #273 (Div. 2)

A. Initial Bet

水题就不说了，记得写完一定要想想有没有特殊情况，注意有不考虑全是0的情况的话会wrong answer on pretest 3

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<set>
 7 #include<map>
 8 #include<stack>
 9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define ALL(x) x.begin(),x.end()
15 #define INS(x) inserter(x,x.begin())
16 using namespace std;
17 typedef long long LL;
18 int i,j,k,n,m,x,y,T,ans,big,cas,sum;
19 bool flag;
20 int main()
21 {
22     for(i=1;i<=5;i++)
23     {
24         scanf("%d",&x);
25         sum+=x;
26     }
27     if (sum%5!=0||sum==0) printf("-1
");
28     else printf("%d
",sum/5); 
29     return 0;
30 }

View Code

B. Random Teams

就是给n个人，分到m个队里，每个队至少一人，分数为各个队人数的平方相加起来的总和，求最小值和最大值

显然的极限问题，当m-1个队人数为1，另一个队人数为n-m+1时分数最大，当各个队人数想接近即 n%m个队人数为n/m+1，m-n%m个队人数为n/m（"/"均为整除）时分数最小

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<set>
 7 #include<map>
 8 #include<stack>
 9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define ALL(x) x.begin(),x.end()
15 #define INS(x) inserter(x,x.begin())
16 using namespace std;
17 typedef long long LL;
18 int i,j,k,x,y,T,ans,cas;
19 LL low,big,n,m,d,num;
20 bool flag;
21 int main()
22 {
23     scanf("%I64d%I64d",&n,&m);
24     d=n%m;
25     num=n/m;
26     big=((n-m+1)*(n-m+1)+m-n-1)/2;
27     low=(num*num*(m-d)+(num+1)*(num+1)*d-n)/2;
28     printf("%I64d %I64d
",low,big);
29     return 0;
30 }

View Code

C. Table Decorations

有三种颜色气球，数量分别为a,b,c，现在要将气球放在桌子上，每个桌子上放三个气球且这三个颜色不能全相同，求最多几个桌子可以摆上气球

据说很多人C题hack了个爽Σ( ° △ °|||)︴我没有被hack因为我wrong answer on pretest 5

不妨设a<b<c，则当c>=2*(a+b)时答案ans=a+b，当c<2*(a+b)时答案ans=(a+b+c)/3 （"/"均为整除，下边也是）

以下是证明：

当c>=2*(a+b)时，显然每次在c中取2个，在max(a,b)中取1个，共取a+b次，没有更优的了

当c<2*(a+b)时，我们要证明答案是(a+b+c)/3。首先从c中取2个，然后从max(a,b)中取1个，因为c<2*(a+b)所以c肯定不会减到0，一直进行此操作，直到c=max(a,b)或者|c-max(a,b)|<2（考虑到有多出1个或2个气球不能组成一组的情况）那么现在max(a,b,c)-second_max(a,b,c)<2

我们还使用a,b,c，排序使得a<b<c，由上边的推导c-b<2，我们现在希望a,b,c尽量接近，然后三个不同颜色的气球组成一桌，如果b-a>=3那么从b,c中各取3个组成两桌（bbc和bcc）直到b-a<3，这样就可以用组成min(a,b,c)桌了，显然最后剩余的气球(0,0,1)或者(0,1,1)，这样是最优的。因此答案ans=(a+b+c)/3

注意a,b,c要使用long long否则会wrong answer on test7

不多说什么了，C题真的很神。。。题解是从CF的评论区里找到的，大致翻译了一下

像这种题，只有先猜结论，再进行证明，猜结论受到了智商压制，证明也是醉的不行= =。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<set>
 7 #include<map>
 8 #include<stack>
 9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define ALL(x) x.begin(),x.end()
15 #define INS(x) inserter(x,x.begin())
16 using namespace std;
17 typedef long long LL;
18 int i,j,k,n,m,x,y,T,ans,big,cas;
19 bool flag;
20 int main()
21 {
22     LL a,b,c;
23     cin>>a>>b>>c;
24     if (a>b) swap(a,b);
25     if (b>c) swap(b,c);
26     if (a>b) swap(a,b);
27     
28     if (c>=2*(a+b)) cout<<a+b<<endl;
29     else cout<<(a+b+c)/3<<endl;
30     return 0;
31 }

View Code

D. Red-Green Towers

红绿塔，就是用红色砖块，绿色砖块堆成，共h层，第i层有i块砖块，并且要求每一层的砖块颜色相同，现在给R个红色砖块，G个绿色砖块，问能拼成多少个不同的红绿塔

线性DP问题，首先我们能求出红绿塔的层数

设dp[i][j]为前i层使用了j个红色砖块时的方案数，则dp[i][j]=dp[i-1][j]（即新的一层全部为绿色）+dp[i-1][j-i]（即新的一层全部为红色），答案为所以dp[h]的和

i最多到900，j最多到2·10⁵，显然数组不能开到这么大，所以需要使用滚动数组。就是这样了。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<iostream>
 5 #include<algorithm>
 6 #include<set>
 7 #include<map>
 8 #include<stack>
 9 #include<vector>
10 #include<queue>
11 #include<string>
12 #include<sstream>
13 #define eps 0.000001
14 #define ALL(x) x.begin(),x.end()
15 #define INS(x) inserter(x,x.begin())
16 #define MOD 1000000007
17 using namespace std;
18 typedef long long LL;
19 int i,j,k,n,m,x,y,T,ans,big,cas,dp[2][200005],h,a,b,num[900],u,v;
20 bool flag;
21 int main()
22 {
23     scanf("%d%d",&a,&b);
24     for (h=0;(h+1)*(h+2)/2<=a+b;h++);
25     if (a>0) dp[0][1]=1; else dp[0][1]=0;
26     if (b>0) dp[0][0]=1; else dp[0][0]=0;
27     
28     
29     for (i=2,num[1]=1;i<=h;i++) num[i]+=num[i-1]+i; 
30     for (i=2;i<=h;i++)
31     {
32         u=(i+1)%2;v=u^1;
33         for (j=max(num[i]-b,0);j<=min(a,num[i]);j++)
34         {
35             dp[u][j]=dp[v][j];
36             if (j>=i) dp[u][j]=(dp[u][j]+dp[v][j-i])%MOD;
37         }
38     }
39     
40     ans=0;u=(h+1)%2;
41     for (i=max(num[h]-b,0);i<=min(a,num[h]);i++)
42     {
43         ans=(ans+dp[u][i])%MOD;
44     }
45     cout<<ans<<endl;
46     return 0;
47 }

View Code

E. Wavy numbers

既然没有人做就不写喽╮(╯-╰)╭

===============================

总之这次比赛的题目相当好，尤其是C题，但是也因此rating继续下跌Σ(っ °Д °;)っ下次还跌的话就要绿了。。。

附上一个转自CF评论区的图片23333