Codeforces Round 671 (Div. 2) A-D
Codeforces Round 671 (Div. 2) A-D
A. Digit Game
题意：
给出一个长度为 n 的数列（下标从1开始），A和B两个人在玩游戏，规定A只能从奇数的位置取数，B只能从偶数的位置取数，当且仅当数列中剩下一个数时游戏结束，如果剩下的这个数是奇数，则A获胜，否则B获胜，若从A开始取数，且双方都用最优的策略进行游戏，问最后谁能取胜。
思路：
如果 n 已经确定时，最后剩下的那个位置的奇偶性也随之确定了，如果 n 是奇数的话，因为奇数多一个，所以最后剩下的那个数显然是奇数，同理如果 n 是偶数的话，因为奇数先取，所以最后会剩下一个偶数。所以如果 n 是奇数的话，只要奇数位置存在一个奇数，A 保留这个奇数直到最后就能赢，同理当 n 是偶数时，B 保留一个偶数直到最后就能赢，根据 n 的奇偶分类讨论一下即可。
#include<iostream>
#include<cstdio>
using namespace std;
const int MAX_N=1e5+100;
char s[MAX_N];
int main(void){
int T;
cin>>T;
while(T--){
int n;
scanf("%d%s",&n,s);
if(n&1){//剩下一个奇数
bool flag=false;
for(int i=0;i<n;i+=2){
if((s[i]-'0')%2!=0)
flag=true;
}
if(flag)
printf("1\n");
else
printf("2\n");
}
else{//剩下一个偶数
bool flag=false;
for(int i=1;i<n;i+=2)
if((s[i]-'0')%2==0)
flag=true;
if(flag)
printf("2\n");
else
printf("1\n");
}
}
return 0;
}
B. Stairs
题意：
首先规定 n 阶楼梯的定义是，对于每一层的高度而言，第一个位置高度为 1，第二个位置高度为 2 ，... 第 n 个位置高度为 n，再规定 "nice" 楼梯的定义是，n 阶楼梯可以被划分为恰好 n 个互不相交的正方形，现在问用 x 个方块，最多可以同时构造多少种互不相同的 “nice” 楼梯。
思路：
首先不难看出，n 最小的 “nice” 楼梯是当 n = 1 的时候，其次就是 n = 3 的时候了，再结合样例中给出的 n = 7 时的 “nice” 楼梯，可以观察出，第 x + 1 个 “nice” 楼梯是由两个第 x 个“nice”楼梯加上一个正方形拼接而成的，而每次的 n 对应的变成 n * 2 + 1。因为题目中需要尽可能多的同时构造“nice”楼梯，所以优先构造出 n 比较小的楼梯显然是最优的，又因为“nice”楼梯的 n 每次都会增长到两倍还要多，也就保证了时间复杂度是 log 级别的，对于 n 阶楼梯而言，其需要用到的方块呈等差数列，即
，剩下的直接模拟即可。
#include<iostream>
#include<cstdio>
using namespace std;
long long cal(long long n){
return n*(n+1)/2;
}
int main(void){
int T;
cin>>T;
while(T--){
long long n;
scanf("%lld",&n);
int ans=0,pos=1;
while(cal(pos)<=n){
n-=cal(pos);
pos=pos*2+1;
ans++;
}
printf("%d\n",ans);
}
return 0;
}
C. Killjoy
题意：
给出 n 个人，每个人都有一个权值 a[ i ] ，现在模拟传播病毒的过程，初始时有一个权值为 x 的人感染了病毒（不属于这 n 个人之中），规定如果有一个人感染了病毒，那么所有与其权值相同的人都将会被传染，现在可以进行操作，每次操作可以将 n 个人的权值任意赋值，不过需要保证每个人权值变化的delta总和为0，问最少需要进行多少次操作，可以使所有人都感染病毒。
思路：
不难看出，对于一般情况而言，最多进行两次操作就能使所有人都感染病毒，具体操作如下：将 n 个人分为两组，第一组只有随便一个人，第二组有剩余的 n - 1 个人，第一次操作将第一组的这个人赋值为 x，用第二组的人进行平衡（因为需要满足
），这样第一组的这一个人就被感染了，第二次操作可以将第二组的 n - 1 个人都赋值为 x ，然后让第一组的这一个人进行平衡，这样 n 个人就都能被感染了。考虑什么时候答案为 0 或 1。题目中样例已经给提示了，当 n 个人都为 x 时，显然答案为 0 ，当 n 个人的平均值为 x 时，仅用一次操作就可以将 n 个人都变为 x ，从而达成目标，最后还剩一种情况不算容易想到，就是如果前面的条件都不满足，但是整个数列中存在这至少一个数等于 x 的话，那么在进行一般操作时，将这些等于 x 的数分成第一组，就可以省略掉一次操作，从而使得总操作数为 1 了，实现的话就比较简单了，分类讨论一下就好。
#include<iostream>
#include<cstdio>
using namespace std;
int main(void){
int T,n,x,i;
cin>>T;
while(T--){
scanf("%d%d",&n,&x);
int delta=0,cnt=0,num;
for(i=1;i<=n;i++){
scanf("%d",&num);
if(num==x)
cnt++;
delta+=num-x;
}
if(cnt==n)
printf("0\n");
else if(cnt||delta==0)
printf("1\n");
else
printf("2\n");
}
return 0;
}
D. Sage's Birthday
题意：
给出 n 个物品，每个物品都有权值，现在需要对其重新排列，使得 a[ i ] < a[ i - 1 ] && a[ i ] < a[ i +1 ] 的位置尽可能多。
思路：
根据题目中的样例可以知道，第一个位置和最后一个位置是不能提供贡献的，且提供贡献的位置显然互相间隔为 1 是最优的，这样可以使得相对大小关系之间的利用最大化，回顾一下可以提供贡献的位置是 a[ i ] < a[ i + 1 ] && a[ i ] < a[ i - 1 ] ，所以我们可以贪心去放置 a[ i - 1 ] 和 a[ i + 1 ] 的这些位置，即
的位置（下标从1开始，满足
），显然是把较大的
个数字依次放在这些位置是最优的，此时还剩下了
个数字尚未填充，因为我们刚刚是按照降序的顺序填充的
的位置，所以取三个已经填充的位置 a[ i ] , a[ i + 2 ] 和 a[ i + 4 ] ，满足 a[ i ] >= a[ i + 2 ] >= a[ i + 4 ] ，此时 a[ i + 1 ] 和 a[ i + 3 ] 需要填充数值来尽可能多的提供贡献，假设在 a[ i + 1 ] 处填充了一个 x ，在 a[ i + 3] 处填充了一个 y ，且都对答案提供了一个单位的贡献，因为 x < a[ i + 2 ]，y < a[ i + 4 ] ，且 a[ i + 2 ] >= a[ i + 4 ] ，则肯定有 x >= y ，再讨论两种情况，如果某个数 x 在 a[ i + 1 ] 处可以提供一个单位的贡献，那么将 x 放置在 a[ i + 3 ] 的位置必然也是可以提供贡献的，但是反之，如果某个数 x 在 a[ i + 3 ] 可以提供一个单位的贡献，将其放置在 a[ i + 1 ] 的位置不一定可以提供贡献，所以贪心策略呼之欲出，对于 a[ i - 1 ] 和 a[ i + 1 ] 而言，a[ i ] 中放置小于 min( a[ i - 1 ] , a[ i + 1 ] ) 的最大的那个数是最优的，对于那些无处可放的数，最后随便放就行了，因为无论放到哪里都不会产生贡献，只要不影响前面的数就好。
#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAX_N=1e5+100;
int a[MAX_N],b[MAX_N];
bool vis[MAX_N];
bool cmp(int a,int b){
return a>b;
}
int main(void){
int n,i,j;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+1+n,cmp);
for(i=1,j=1;i<=n;i+=2){
vis[j]=true;
b[i]=a[j++];
}
int ans=0;
for(i=2;i<=n;i+=2){
while(j<=n&&a[j]>=b[i+1])
j++;
if(j<=n){
vis[j]=true;
b[i]=a[j++];
ans++;
}
}
for(i=1,j=1;i<=n;i++){
if(!b[i]){
while(vis[j])
j++;
b[i]=a[j++];
}
}
printf("%d\n",ans);
for(i=1;i<=n;i++)
printf("%d ",b[i]);
return 0;
}