Codeforces Round #666 (Div. 2)总结（A、B、C、D）

水深无声 2022-12-02 13:37 96阅读 0赞

# Codeforces Round \#666 (Div. 2)总结（A、B、C、D） #

上午LeetCode周赛自闭，晚上cf再次自闭…

## A：Juggling Letters ##

[**题目链接**][Link 1]

#### 题意 ####

n个字符串，每次操作可以选择两个字符串（可以相同）选择其中一个字符串中某一字符插入到另一字符串。问：操作任意次，能否使得所有字符串都相同？

#### 题解 ####

只需判断所有字符串的任意字符的数量都是n的倍数即可。（看题慢了，再加上上场没注意很多细节，导致交的比较慢…）

#### AC代码（cpp） ####

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<iostream>
    #include<string>
    #include<map>
    #define lowbit x x&(-x)
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    string s;
    map<char,int>mp;
    int main(){
        
        int t,n;
        scanf("%d",&t);
        while(t--){
        
            mp.clear();
            scanf("%d",&n);
            for(int i=1;i<=n;i++){
        
                cin>>s;
                int len=s.length();
                for(int j=0;j<len;j++) mp[s[j]]++;
            }
            int flag=0;
            map<char,int>::iterator it;
            for(it=mp.begin();it!=mp.end();it++){
        
                int num=it->second;
                if(num%n==0) continue;
                else{
        
                    flag=1;break;
                }
            }
            if(flag==0) printf("YES\n");
            else printf("NO\n");
        }
        return 0;
    }

## B：Power Sequence ##

[**题目链接**][Link 2]

#### 题意 ####

n个数组成的数组，下标为0~n-1，首先对数组从小到大排序，然后有一操作：可以对任意数组中任意一个元素的值加一或者减一，代价为1；问最少需要多少代价可以使得数组a\[i\]= c i c^i ci.

#### 题解 ####

首先最差的情况是所有的元素都为1，然后可以枚举c，并不断更新此时的最差代价，如果出现某一c的值所取得的代价比当前最差代价还要大时，则证明已经找到最小代价。具体见代码

#### AC代码（cpp） ####

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<iostream>
    #include<string>
    #include<map>
    #define lowbit x x&(-x)
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    int a[maxn],n;
    ll ans;
    int check(int c){
        
        ll now=1;
        ll sum=abs(a[1]-1);
        for(int i=2;i<=n;i++){
        
            now*=c;
            sum+=abs(a[i]-now);
            if(sum>=ans) return 0;
        }
        ans=sum;
        return 1;
    }
    int main(){
        
        scanf("%d",&n);
        ans=0;
        for(int i=1;i<=n;i++){
        
            scanf("%d",&a[i]);
            ans+=a[i];
        }
        sort(a+1,a+n+1);
        ans-=n;
        for(int c=2;;c++){
        
            if(check(c)==0) break;
        }
        printf("%lld\n",ans);
        return 0;
    }

## C：Multiples of Length ##

[**题目链接**][Link 3]

#### 题意 ####

n个元素组成的数组，有一操作：对于某一段区间\[l,r\]，可以加上该区间长度len的任意倍数。题目说明：可以证明三次操作可以使得数组所有元素都变成0。

#### 题解 ####

*  首先考虑n=1的情况，直接第一步将元素变成0，后面两步都加0即可；
 *  n>1时：
    
    1.  首先对前n-1个元素加上(n-1)\* a\[i\]；这样使得前n-1个元素都变成了n\*a\[i\]；
    2.  将第n个元素变成0；
    3.  将n个元素都加上对应的-n\*a\[i\]，这样便使得所有元素都变成了0

#### AC代码（cpp） ####

#include<cstdio>
    #include<cstring>
    #include<algorithm>
    #include<queue>
    #include<iostream>
    #include<string>
    #include<map>
    #define lowbit x x&(-x)
    #define inf 0x3f3f3f3f
    #define ll long long
    using namespace std;
    const int maxn=1e5+5;
    ll a[maxn];
    int main(){
        
        int n;
        scanf("%d",&n);
        for(int i=1;i<=n;i++){
        
            scanf("%lld",&a[i]);
        }
        if(n==1){
        
            printf("1 1\n%lld\n",-a[1]);
            printf("1 1\n0\n");
            printf("1 1\n0\n");
            return 0;
        }
        printf("1 %d\n",n-1);
        for(int i=1;i<n;i++){
        
            printf("%lld",a[i]*(n-1));
            if(i==n-1) printf("\n");
            else printf(" ");
            a[i]=a[i]*n;
        }
        printf("%d %d\n",n,n);
        printf("%d\n",-a[n]);
        a[n]=0;
        printf("1 %d\n",n);
        for(int i=1;i<=n;i++){
        
            printf("%lld",-a[i]);
            if(i==n) printf("\n");
            else printf(" ");
        }
        return 0;
    }

## D：Stoned Game ##

恶心的博弈，赛后看的tourist的代码…

#### AC代码（cpp） ####

[Link 1]: https://codeforces.com/contest/1397/problem/A
[Link 2]: https://codeforces.com/contest/1397/problem/B
[Link 3]: https://codeforces.com/contest/1397/problem/C