Codeforces Round #666 (Div. 2) A-D
Codeforces Round #666 (Div. 2) A-D
A.Juggling Letters
题意：
给出 n 个字符串，每次操作可以将第 i 个字符串的一个字符移动到第 j 个字符串的任意位置，问经过数次操作后，能否使得 n 个字符串都相等。
思路：
比较简单的一道题目，若要使得 n 个字符串都相等，那么对于每个字母而言，要么不出现，要么出现次数为 n 的倍数才能恰好平均分给 n 个字符串，所以做法就是将 n 个字符串的每个字母的出现次数统计一下，最后看看对于 26 个字母而言是否全部满足条件即可，即 cnt[ i ] % 26 == 0。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int MAX_N=201000;
char s[MAX_N];
int cnt[30];
int main(void){
int T,n,i,j;
cin>>T;
while(T--){
scanf("%d",&n);
for(i=0;i<26;i++)
cnt[i]=0;
for(i=1;i<=n;i++){
scanf("%s",s);
int len=strlen(s);
for(j=0;j<len;j++)
cnt[s[j]-'a']++;
}
int flag=1;
for(i=0;i<26;i++){
if(cnt[i]%n!=0){
flag=0;
break;
}
}
if(flag)
printf("YES\n");
else
printf("NO\n");
}
return 0;
}
B.Juggling Letters
题意：
首先规定 ”power sequence” 为一个长度为 n 的数列 a ，下标从 0 ~ n-1，满足存在一个正整数 c ，使得 0 <= i <= n-1 有 a[ i ] = c^i现在给出一个数列 a ，可以对其进行任意次数的下列两种操作：1.使得 a 排列为任意顺序，代价为 0。2.对于任意一个位置 i ，使得 a[ i ] = a[ i ] + 1 或 a[ i ] = a[ i ] - 1，代价为 1问将数列 a 变为 ”power sequence” 的最小代价是多少。
思路：
读完题感觉无从下手，但很快可以发现一个点就是，n 的大小为 1e5 ，当 c 取 1 时，
，而当 c 取大于 1 的数值时，
将变得非常非常大再需要发现 a[ i ] 的取值最大只能取到 1e9 ，所以当 c 取 1 得时候，最终的贡献最大也不过
，极限情况的贡献也就是 ( 1e9 - 1 ) * 1e5 = 1e14，换句话说，需要满足对于 0 <= i <= n - 1 的所有
都小于等于 1e14 + 1e9 ，如果第 i 项的
大于 1e14 + 1e9，则会有
，
，这样答案显然不如 c = 1 时更优 上面说的是最大情况，还有最小情况，也就是 n = 3 时，此时设最终序列为 1 , x , x * x ，因为上面我们求出的约束是每个数都要小于等于 1e14 + 1e9 ，即 x * x 需要满足
，这样也就确定下来所需要枚举的 c 的范围了开个根号就可以发现枚举 c 的范围在 1 ~ 1e7 ，每次计算贡献时，因为指数增长特别快，当 c = 2 时，
就已经达到 1e15 了，所以估算一下时间复杂度也不过 1e7 * 50 = 8e5，实际上远远到不了这么大需要注意的一个点是运算的时候记得开__int128来辅助运算，因为1e14 * 1e7 = 1e21，已经超出 long long 的范围了，当然实际实现的时候阈值也不用开的这么大，比赛时我枚举的范围是1 ~ 1e5 ，阈值设置为 1e13 ，用 long long 依然是通过数据且未被 hack.
因为使用了__int128所以编译器提交的时候选择GUN G++17 9.2.0 (64 bit,msys 2).
#include<iostream>
#include<cstdio>
#include<cmath>
#include<algorithm>
using namespace std;
const int MAX_N=101000;
const long long INF=0x3f3f3f3f3f3f3f3f;
long long a[MAX_N];
int n;
long long solve(__int128 bt){
__int128 res=1;
long long ans=0;
int i;
for(i=1;i<=n;i++){
if(res>=1e14+1e9)
return INF;
ans+=llabs(a[i]-(long long)res);
res*=bt;
}
return ans;
}
int main(void){
int limit=sqrt(1e14+1e9)+1,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
sort(a+1,a+n+1);
long long ans=INF;
for(i=1;i<=limit;i++)
ans=min(ans,solve(i));
printf("%lld\n",ans);
return 0;
}
C.Multiples of Length
题意：
给出一个长度为 n 的数列 a ，现在需要进行恰好三次操作，使得整个数列全部变为 0 ，对于每次操作，可以选择一段区间 [ l , r ] ，设 len = r - l + 1 ，对于 [ l , r ] 中的每个位置都可以加上 len 的倍数（倍数可以为 0 也可以为负数），输出如何操作。
思路：
既然是三次操作，其中有一次所需要选择的区间肯定是 [ 1 , n ] 了，换句话说，我们可以通过两次操作使得 n 个数都变为 n 的倍数，这样在选择区间 [ 1 , n ] 时，就可以将其全部置零了。考虑如何将每个数都变为 n 的倍数，比较简单的一个做法是，先选择一个长度为 n - 1 的区间，假如区间内的某个数为 x ，则将其加上 x * ( n - 1 ) 即可，这样 x + x * ( n - 1 ) = x * n，也就变成 n 的倍数了，因为选择了长度为 n - 1 的区间进行一次操作后，还剩了一个点没有被操作到，所以第二次操作选择长度为 n - 1 的区间将这个点覆盖到，然后进行同样的处理即可，这样最后一次操作前所有的数都是 n 的倍数了，最后一次操作选择 [ 1 , n ] 全部置零即可。需要注意的是 n == 1 的时候需要特判一下。
#include<iostream>
#include<cstdio>
using namespace std;
const int MAX_N=101000;
long long a[MAX_N];
int main(void){
int n,i;
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%lld",&a[i]);
if(n==1){
printf("%d %d\n",1,1);
printf("%lld\n",-a[1]);
printf("%d %d\n",1,1);
printf("%d\n",0);
printf("%d %d\n",1,1);
printf("%d\n",0);
return 0;
}
long long len=n-1;
printf("%d %d\n",1,n-1);
for(i=1;i<=n-1;i++){
if(a[i]%n==0)
printf("%d ",0);
else if(a[i]>0){
printf("%lld ",a[i]*len);
a[i]+=a[i]*len;
}
else if(a[i]<0){
printf("%lld ",a[i]*len);
a[i]+=a[i]*len;
}
}
printf("\n");
printf("%d %d\n",2,n);
for(i=2;i<=n;i++){
if(a[i]%n==0)
printf("%d ",0);
else if(a[i]>0){
printf("%lld ",a[i]*len);
a[i]+=a[i]*len;
}
else if(a[i]<0){
printf("%lld ",a[i]*len);
a[i]+=a[i]*len;
}
}
printf("\n");
printf("%d %d\n",1,n);
for(i=1;i<=n;i++)
printf("%lld ",-a[i]);
printf("\n");
return 0;
}
D.Stoned Game
题意：
两个人在玩游戏，初始时有 n 堆石子，每堆石子有 a[ i ] 个，两人轮流取石子，每次可以选择一堆石子然后取走一个，第一个人第一次可以任意选择一堆，后续每个人不能选择前一个人上次选择的那一堆，无法取走石子的人失败，问先手必胜还是必败。
思路：
假设当前只有一堆仍然还有石子，因为先手取完之后，无论这堆石子还剩多少个，后手都无法选择该堆石子，所以先手必胜假设当前有至少两堆仍然还有石子，如果先手选择了第 i 堆石子，且 a[ i ] 不是最大值，那么后手只需要选择第 j 堆石子，满足 a[ j ] >= a[ i ] 即可，这样有点像尼姆博奕的那个思想，就是先手打破 xor = 0 ，后手选择将 xor 重新置零的方案即可，如果先手选择的 a[ i ] 是剩余石子中的最大值，那么后手无论如何选择，都只能选择小于等于 a[ i ] 的石子，当较少的石子堆被取完时，先手仍然选最多的石子堆，后手就没有办法翻盘了所以对于每个人来说：选择当前可以选择的石子堆中，数量最大的石子堆一定是最优的，因为数据范围比较小，直接模拟的话时间复杂度是 n^3 ，没什么细节直接实现就好了。
#include<iostream>
#include<cstdio>
using namespace std;
const int MAX_N=101000;
int a[MAX_N],n;
bool solve(int &pre){
int sum=0,mmax=0,pos=-1,i;
for(i=1;i<=n;i++){
if(i==pre)
continue;
sum+=a[i];
if(mmax<a[i]){
pos=i;
mmax=a[i];
}
}
pre=pos;
if(mmax==0)
return false;
a[pos]--;
return true;
}
int main(void){
int T,i;
cin>>T;
while(T--){
scanf("%d",&n);
for(i=1;i<=n;i++)
scanf("%d",&a[i]);
int pre=-1;
int flag=0;
while(solve(pre))
flag++;
if(flag%2==1)
printf("T\n");
else
printf("HL\n");
}
return 0;
}
