Codeforces Round #452 (Div. 2)划水报告

本文主要是介绍Codeforces Round #452 (Div. 2)划水报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

A. Splitting in Teams
贪心
先把二人组和一人组配对
然后一人组单独组成3个

#include <iostream>
#include <cstdio>
using namespace std;
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n;scanf("%d",&n);int x,num1=0,num2=0;for(int i=1;i<=n;i++){scanf("%d",&x);if(x==1)num1++;else num2++;}int ans=0;ans+=min(num1,num2);num1-=min(num1,num2);ans+=num1/3;printf("%d\n",ans);
return 0;
}

B. Months and Years
将3个平年1个闰年3个平年拼起来跑字符串匹配

#include <iostream>
#include <cstdio>
using namespace std;
int A[12*20];
int B[30];
int C[13]={0,31,28,31,30,31,30,31,31,30,31,30,31};
int D[13]={0,31,29,31,30,31,30,31,31,30,31,30,31};
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);int n;scanf("%d",&n);for(int i=1;i<=n;i++)scanf("%d",&B[i]);int tot=0;for(int i=1;i<=3;i++)for(int j=1;j<=12;j++)A[++tot]=C[j];for(int j=1;j<=12;j++)A[++tot]=D[j];for(int i=1;i<=3;i++)for(int j=1;j<=12;j++)A[++tot]=C[j];int tl=0;for(int i=1;i<=tot;i++){if(i+n-1>tot)break;int ok=1;for(int j=1;j<=n;j++)if(A[i+j-1]!=B[j])ok=0;if(ok)tl=1;}if(tl)puts("YES");else puts("NO");
return 0;
}

C. Dividing the numbers
答案不是0就是1
将奇数与偶数分组
发现可以将奇数偶数调换来实现(奇数组+2,偶数组-2),(奇数组-2,偶数组+2)
求一下要调换的组数即可

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);ll n;scanf("%lld",&n);if(n%2==0){ll res=n/2;printf("%lld\n",res%2);ll u=res/2;printf("%lld ",res);for(ll i=1;i<=u;i++)printf("%lld ",i*2);for(ll i=u+1;i<=res;i++)printf("%lld ",i*2-1);}else {ll res=n/2;ll N=res*2;ll tmp=res+1;ll u=tmp/2;printf("%lld\n",tmp%2);printf("%lld ",res);for(ll i=1;i<=u;i++)printf("%lld ",2*i+1);for(ll i=u+1;i<=res;i++)printf("%lld ",2*i);}
return 0;
}

D. Shovel Sale
设输入数为x
若x首位>=5则最长的9s位数为x的位数
否则为x位数-1
然后考虑较大数对较小数贡献
若位数==9s位数
每一个较大数都会存在唯一的较小数与其对应
枚举首位计算贡献即可
否则则有其首位数-1个数可以对应(比如4kl,有3ij,2ij,ij对应,k+i==9,l+j==9)
然后首位相同的数的贡献就是去掉首位后的子问题，枚举首位计算
（首位=x首位单独计算，因为其他贡献都是9999…的子问题，而他是x去掉第一位的子问题）
注意99999..和0的贡献要减去

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
ll base[12];
ll bse[12];
int vis[200];
inline ll len(ll x){if(!x)return 0;ll cnt=0;while(x){x/=10;cnt++;}return cnt-1;
}
int main(){//freopen("a.in","r",stdin);//freopen("a.out","w",stdout);ll n;scanf("%lld",&n);if(n<5){printf("%lld\n",n*(n-1)/2);return 0;}base[1]=1;for(int i=2;i<=11;i++)base[i]=base[i-1]*10;bse[1]=9;for(int i=2;i<=11;i++)bse[i]=bse[i-1]*10+9;ll le=1;while(n>=base[le])le++;le--;ll u=n/base[le];ll tl;if(u>=5)tl=le;else tl=le-1;ll ans=0;//printf("%lld %lld\n",le,tl);if(tl!=1){if(tl==le){for(int i=5;i<u;i++)ans+=base[tl];ans+=(n%base[tl])+1;if(n==bse[tl])ans--;}else {for(int i=u;i>=2;i--){ans+=base[le]*(i-1);ans--;}for(int i=5;i<=9;i++)ans+=base[le-1]*u;ans--;//printf("%d\n",ans);ans+=(n%base[le]+1)*u;//printf("%d\n",ans);u=(n%base[le])/base[le-1];n=n%base[le];//printf("%d %d\n",n,u);if(n==bse[le-1])ans--;if(u>=5){for(int i=5;i<u;i++)ans+=base[le-1];ans+=(n%base[le-1]+1);}}}else {for(ll i=1;i<=n;i++){ll p=i%10;ll t=9-p;ll cl=0;for(ll j=i+1;j<=n;j++)if(j%10==t)ans++;}}printf("%lld\n",ans);
return 0;
}