锐客网

  1. 首页 > 睿知 > it技术 > >

Codeforces Round #671 (Div. 2) A-D2

codeforces

Codeforces Round #671 (Div. 2) A. Digit Game 问题分析：
n个数字，R只能删除任意奇数位的数字,B只能删除任意偶数位的数字
B先走，然后如果最后剩的 数字是奇数R赢了，否则B赢了
当n为奇数的时候 ，奇数位的数量是n/2+1; R先走,最后一定会剩下一个奇数位的数字
这时候只要 所有奇数位里 有一个 奇数就一定是 R赢得比赛
当n为偶数的时候，奇/偶位置都是n/2 而且R先走，最后一定会剩下一个 偶数位的数字
同理，偶数位有偶数 就一定是B赢
AC代码：

#include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define mem(a,b) memset((a),(b),sizeof(a)); #define lowbit(a) ((a)&-(a)) const ll inf=0x3f3f3f3f; //1061109567,2*未超int，allinf=mem(a,0x3f,sizeof(a)); const int N=2e5+10; ll a[32]; ll sum; int main(){ // #define io #ifdef io freopen("in.txt","r",stdin); #endif cin.tie(0); int t; cin>>t; while(t--){ int n; cin>>n; int ro,bd; ro=bd=0; string s; cin>>s; for(int k=0; k.length(); k++){ int x=s[k]-'0'; int i=k+1; //cout<

B. Stairs 问题分析：
看图吧
阶梯 数量 变化是 1 3 7 15
为 n2+1 每次增加 比前面阶数+1个
而组成阶梯的 小方块数量每列 是 等差数列
即 sum= n(n+1)/2；
然后 问的是不同阶数的最大总数 枚举暴力
AC代码：
#include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define mem(a,b) memset((a),(b),sizeof(a)); #define lowbit(a) ((a)&-(a)) const ll inf=0x3f3f3f3f; //1061109567,2*未超int，allinf=mem(a,0x3f,sizeof(a)); const int N=2e5+10; ll a[32]; ll sum; int main(){ // #define io #ifdef io freopen("in.txt","r",stdin); #endif cin.tie(0); int t; while(cin>>t){ while(t--){ ll x; cin>>x; ll cnt=0; ll temp; for(ll i=1; ; ){ temp=(i+1)*i/2; if(x

C. Killjoy 问题分析：
。。。。好难，。，。
一个人可以在赛前或者赛后感染其他和他 分数相同的人
然后通过每场比赛 感染着可以操作所有人分数，但是所有分数变化之差必须为0
问 最少需要 几次竞赛 才能感染所有的人
分为几种情况
  1. 所有的人的分数 都和他相同 直接赛前（ 0）
  2. 所有人中至少有一个人的分数和他相同 赛前感染，赛中所有 分数变化产生的差值全都转移到 赛前被感染的人身上（1）
  3. 所有的的分制之和的平均值等于 初始感染者的分数，赛中 加加减减 所有人变为，。，。（1）
  4. 不满足以上任何一种情况
    先在第一场 赛中 操作 一个人的分数变为 初始感染者相同，赛后感染，，，，
    第二场 赛中 秀和第二种情况的操作，，，然后赛后所有人感染（2）
AC代码：
#include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define mem(a,b) memset((a),(b),sizeof(a)); #define lowbit(a) ((a)&-(a)) const ll inf=0x3f3f3f3f; //1061109567,2*未超int，allinf=mem(a,0x3f,sizeof(a)); const int N=2e5+10; ll a[32]; ll sum; int main(){ // #define io #ifdef io freopen("in.txt","r",stdin); #endif cin.tie(0); int t; cin>>t; while(t--){ int n,m; cin>>n>>m; int sum=0; int flag=0; for(int i=0; i>x; sum+=x; if(x==m)flag++; } if(flag==n)cout<<0; else if(flag||sum==n*m)cout<<1; else cout<<2; cout<

D1. Sage’s Birthday (easy version) 问题分析：
给定一个 每一项各不相同的数组
要求重新排列 使得 某项比理他最近的 左右两侧的数最小这样的项数的数量最多
怎么说呢 一想就是 大数夹小数
极端的想法就是取两端
分两种情况
  1. 奇数 可以夹的数的数量是 n/2
    大数从 n/2+1开始 取 小数从1开始 因为 大数 小数不相等要注意 最后一项
  2. 偶数 夹的数量是 n/2-1
    大数从n/2+1开始 小数从1 直接一组 一组输出记性
    具体看代码
AC代码：
#include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define mem(a,b) memset((a),(b),sizeof(a)); #define lowbit(a) ((a)&-(a)) const ll inf=0x3f3f3f3f; //1061109567,2*未超int，allinf=mem(a,0x3f,sizeof(a)); const int N=2e5+10; int a[N]; int main(){ // #define io #ifdef io freopen("in.txt","r",stdin); #endif cin.tie(0); int n; cin>>n; for(int i=1; i<=n; i++){ cin>>a[i]; } sort(a+1,a+n+1); if(n%2){ cout<

D2. Sage’s Birthday (hard version） 问题分析：
和D1题意基本相同 不同的是 各项允许有相同的 数字出现
想了下 还是D1的做法。。。因为 D1呢种 排序方案感觉在D2中也是最优的
为什么这么说呢
因为 排完序后 是从中间部分 往后作为大数 ，而从头往后作为小数
这样就尽量保证较小的大数一定夹的是较小的小数
例子 举一个 特殊的吧
9 444444555

答案：5夹4
`
2
444454545
【Codeforces Round #671 (Div. 2) A-D2】| - | - | - | - |
`
然后就是统计数量不在是简单的公式了 这个就需要判断
这个简单了 扫一遍嘛
AC代码：
#include #include #include #include #include #include #include #include #include #include using namespace std; #define ll long long #define mem(a,b) memset((a),(b),sizeof(a)); #define lowbit(a) ((a)&-(a)) const ll inf=0x3f3f3f3f; //1061109567,2*未超int，allinf=mem(a,0x3f,sizeof(a)); const int N=2e5+10; int a[N],b[N]; int main(){ // #define io #ifdef io freopen("in.txt","r",stdin); #endif cin.tie(0); int n; cin>>n; for(int i=1; i<=n; i++){ cin>>a[i]; } sort(a+1,a+n+1); int ans=0; if(n%2){ for(int i=n/2+1; i

    推荐阅读


    上一篇：android|Android studio开发APP通过esp8266WiFi控制51单片机LED灯亮灭

    下一篇：杂文|Codeforces Round #757 (Div. 2) 题解