[C++知识库]Codeforces Round #821 (Div. 2) A~D1（模拟、构造）

A. Consecutive Sum

普通的签到题

简而言之就是把每个数的index mod k的余数相同的数字中取最大值，然后不同余数的最大值加起来就可以了

注意取最大值的时候要初始化，以及开long long

#include<bits/stdc++.h>
using namespace std;
#define int long long
int v[104];
signed main()
{
    int t,a;cin>>t;
    while(t--){
        int n,k;int sum=0;cin>>n>>k;
        memset(v,0,sizeof(v));
        for(int i=1;i<=n;i++){cin>>a;v[i%k]=max(v[i%k],a);}
        for(int i=0;i<k;i++)sum+=v[i];
        cout<<sum<<endl;
    }
    return 0;
}

B. Rule of League

题意：一共有n-1场比赛，每个人胜利了x次或者y次，问比赛的每场情况谁赢了

思路：做了一会才发现，因为第一场比赛1和2比，总会有一个人的胜利次数为0，所以如果x和y有且只有一个0的时候才会有比赛结果

之后就是硬模拟了

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t;cin>>t;int n,a,b;
    while(t--){
        cin>>n>>a>>b;
        if(a==0&&b==0)cout<<"-1\n";
        else if(a==0||b==0){
            if((n-1)%max(a,b)==0){
                    int flag=1;int cou=0;
                    for(int qq=2;qq<=n;qq++){
                        cout<<flag<<" ";cou++;
                        if(cou==max(a,b)){flag=qq+1;cou=0;}
                    }
                    cout<<endl;
            }
            else cout<<"-1\n";
        }
        else cout<<"-1\n";
    }

    return 0;
}

C. Parity Shuffle Sorting

题意：

• Choose two indices?l and?r?(1≤l<r≤n).
• If?al+ar?is odd, do?ar:=al. If?al+ar?is even, do?al:=ar.
• 求最后不下降序列
• 输出操作的序号（不要求最小步骤）

思路：

1.a[0] 等于 a[n] 或者 a[n] 等于 a[0]

2.若 a[0]+a[i] 是奇数，a[i]=a[0]；否则偶数的话，a[i] = a[n-1]；

3.记录下答案，之后输出就可以了

（比赛的时候还以为只能是相邻的选择，不过就算读对题了也不一定想到orz）

#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,a[200005],b;
signed main()
{
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        for(int i=1;i<=n;i++)cin>>a[i];
        vector<pair<int,int>>v;
        if(n==1){cout<<0<<endl;continue;}
        if((a[1]+a[n])%2==1)a[n]=a[1];
        else a[1]=a[n];
        v.push_back({1,n});
        for(int i=2;i<=n-1;i++){
            if((a[1]+a[i])%2==1){a[i]=a[1];v.push_back({1,i});}
            else if((a[n]+a[i])%2==0){a[i]=a[n];v.push_back({i,n});}
        }
        cout<<v.size()<<endl;
        for(int i=0;i<v.size();i++){
            cout<<v[i].first<<" "<<v[i].second<<endl;
        }
    }

    return 0;
}

D1. Zero-One (Easy Version)

题意：

1.给两个01串a和b，字符串长度大于等于5，选择两个在字符串a中的两个字符

2.对这两个字符进行0变1和1变0这两个操作，使得a==b

3.如果这两个字符是相邻的，那么花费x；如果不相邻，那么花费y。（y<x）

4.求最小费用

思路：

1.首先容易看出字符串a如果有奇数个字符和字符串b不一样，那么输出不可能。

2.如果字符串a只有两个相邻的字符和b不一样，那么它有两个操作：1）花费x直接变换。2）花费2*y，两次都和同一个第三个字符变化。这两个操作取最小值就可以。

***3.剩下的其他情况无论怎么样都可以化作用y的方式去做。

（ 第3点是比赛的时候我没想到的orz ）?

代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
signed main()
{
    int t;int n,x,y;cin>>t; string a,b;
    while(t--){
        cin>>n>>x>>y;cin>>a>>b;a=" "+a;b=" "+b;
        vector<int>v;int co=0;int sum=0;
        for(int i=1;i<=n;i++){
            if(a[i]!=b[i])co++;
            else if(co!=0){v.push_back(co);sum+=co;co=0;}
        }
        if(co){v.push_back(co);sum+=co;}
        if(sum%2==1)cout<<-1<<endl;
        else if(v.size()==1&&v[0]==2)cout<<min(x,2*y)<<endl;
        else cout<<sum/2*y<<endl;
    }
    return 0;
}