Codeforces Round #770 (Div.2) A-F 完整题解

A.Reverse and Concatenate

容易发现，对于一个回文串，s+rev（s）=rev（s）+s；而任意字符串在执行一次操作以后会变成回文串，即ans=(是回文串?)1:2。

注意特判k=0的情况。

#include 
using namespace std;
typedef long long ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;cin >> t;
    while (t--) {
        int n,a,b,c;
        cin>>a>>b;
        string s;cin>>s;
        string m=s;std::reverse(s.begin(), s.end());
        if(b==0){cout<<1<continue;}
        if(s==m){cout<<1<continue;}
        else {cout<<2<continue;}
   

B. Fortune Telling

比较阴间的思维题

考虑到加法和xor产生的答案奇偶性一致，即可做出本题。

#include 
using namespace std;
typedef long long ll;
ll x[200005];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;cin >> t;
    while (t--) {
        ll n,a,b,c;
        cin>>n>>a>>b;b%=2;
        for(int i=1;i<=n;i++){cin>>x[i];x[i]%=2;b+=x[i];}
        b=abs(a-b)%2;
        if(b==0){cout<<"Alice"<<endl;}
        else cout<<"Bob"<<endl;
    }
}

C. OKEA

题意：对于n*k个物品，第i个i元，重新摆放所有物品，使得对于每一行任意k个物品，其平均价值是整数。

首先，可以直观的发现，对于一行的物品，要么价值全为奇数，要么价值全为偶数，否则存在一个奇数价值的物品与一个偶数价值的物品相邻，平均数不是整数；因此，对于给定n、k，若其中奇数个数无法恰好被k整除，它一定无解，计算发现这样的情况是n%2==1&&k!=1；

其次，对于剩下的情况，考虑构造的方法，能够很直观地发现：使用等差数列的摆放方式可以使得解存在。

#include 
using namespace std;
typedef long long ll;
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;cin >> t;
    while (t--) {
        int n,k;
        cin>>n>>k;
        if(n%2==1&&k!=1){cout<<"NO"<continue;}
        else{cout<<"YES"<<endl;
            if(n%2==1){
                for(int i=1;i<=n;i++)cout<'\n';
            }
            else{int cnt=1;
                for(int i=1;i<=n/2;i++){
                    for(int j=1;j<=k;j++){cout<' ';cnt+=2;}
                    cout<<'\n';
                }
                cnt=2;
                for(int i=1;i<=n/2;i++){
                    for(int j=1;j<=k;j++){cout<' ';cnt+=2;}
                    cout<<'\n';
                }
            }
        }
    }
}

D. Finding Zero交互题

题意：有一组数组，其中恰有一个0；可以选择数组中的三个数询问，返回值为其中最大的数-最小的数；最多询问2*n-2次，要求输出两个可能是0的位置。

题目暗示1：最后答案输出的是两个位置，换言之，你无法通过询问恰好找到某个数字是0

题目暗示2：只有一个0，但是题目返回的不是数字，而是两个数的差值。也就是说，考虑的是数字间的大小关系，因此把题目中的0理解做“最小的数”比较合适。

考虑任意四个数a,b,c,d,不妨设a<=b<=c<=d;

对这四个数中的每三个询问一次，返回答案为d-a，d-b，c-a，d-a

惊喜地发现d-a出现了两次，这两次询问分别为a c d与a b d;于是对于这样的两组询问，可以分别排除b与c；

当c-a=d-a或者d-b=d-a时，通过验算就能发现，上述性质不受到影响；从而每四次询问必然能够排除两个数，我们从而可以在2n-2次询问以内找到答案。

请注意考虑边界情况的处理；笔者因为没有考虑吃了五发WA。

#include 
using namespace std;
int m[4],ans[4];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;cin >> t;
    while (t--) {
        int qry=0;
        int n;cin>>n;int mx;
        int bj[4]={0,0,0,0};
        int cnt=5;
        m[0]=1,m[1]=2,m[2]=3,m[3]=4;
        while(qry<(n-1)/2*4){
            mx=0;
            for(int i=0;i<4;i++){
                cout<<"? ";
                for(int j=0;j<4;j++){if(i!=j)cout<' ';}
                cout<<endl;
                cin>>ans[i];
                if(ans[i]>mx)mx=ans[i];
            }
            int ct=0;
            for(int i=0;i<4;i++){
                if(ans[i]==mx&&ct<2){bj[i]=0,ct++;}
                else bj[i]=1;
            }
            for(int i=0;i<4;i++)if(bj[i]==0){
                m[i]=cnt++;
                if(cnt>n){
                    cnt-=n;
                }
                for(int j=0;j<=3;j++){if(j==i)continue;if(m[j]==m[i])cnt++,m[i]++;}
            }
            qry+=4;
        }
        cout<<"! ";
        for(int i=0;i<4;i++){if(bj[i]==1)cout<' ';}
        cout<<endl;
    }
}

E. Fair Share

题意：给出M个偶数长度的数组，每个数组中的数一半被放在多重集合L中，另一半被放在多重集合R中。

是否存在一种分法，使得集合L与集合R中的数完全一致？

一个显然的必要条件是，每一种数必须在所有M个数组中出现偶数次，否则无解。

接下来，对于该条件的充分性，考虑构造法。由于题目要求把所有数置于两个集合中，并且任意一个数在L/R的出现次数相等，任意一个数组中的数在L/R中的出现次数相等，这会使人想到二分图染色的方法。于是题目的难点变成构造一个满足题意的二分图。

考虑对每个数出现的第1、3、5……i次和第2、4、6、……i+1次连边，对每个数组中的第1、3、5、……i个数和第2、4、6……i+1个数连边，从而使得每个点的度均为2，可以形成一张二分图。

然后填上L、R，然后AC。

#include 
using namespace std;
vectorint>>mp,cnt;
vectorchar>>color;
map<int,int>lsh;
vectorint,int>>eg[200010];
char col[2]={'L','R'};
void dfs(int i,int j,int nmb){
    if(color[i][j]!=0)return;
    color[i][j]=col[nmb];
    if(color[i][j^1]!=0){
        dfs(eg[lsh[mp[i][j]]][cnt[i][j]^1].first,eg[lsh[mp[i][j]]][cnt[i][j]^1].second,nmb^1);
    }
    else dfs(i,j^1,nmb^1);
}
int main() {int tot=0;
    int m;cin>>m;
    mp.resize(m);color.resize(m);cnt.resize(m);
    for(int i=0;iint n;cin>>n;
        mp[i].resize(n);color[i].resize(n);cnt[i].resize(n);
        for(int j=0;j){
            cin>>mp[i][j];
            if(lsh[mp[i][j]]==0)lsh[mp[i][j]]=++tot;
            eg[lsh[mp[i][j]]].emplace_back(i,j);
            cnt[i][j]=eg[lsh[mp[i][j]]].size()-1;
        }
    }
    for(int i=1;i<=tot;i++){
        if(eg[i].size()&1){cout<<"NO\n";
        return 0;}
    }
    for(int i=0;i){
        for(int j=0;j){
            dfs(i,j,0);
        }
    }cout<<"YES"<<'\n';
    for(int i=0;i){
        for(int j=0;j){
            cout<<color[i][j];
        }cout<<'\n';
    }
}

F. Fibonacci Additions

题意：对于一个区间[l,r]，有一种叫作“斐波那契加”的操作，即对于[l，r]区间，x[l] += F[1]，x[l+1] += F[2]，……，x[r] += F[r-l+1]；其中F为斐波那契数列，即F[1]=1,F[2]=1,F[3]=2……。

给定两个长度为N的区间与模数p，对于q次操作，每次操作在A/B的一个区间上执行一次斐波那契加。每次加完后，若A、B模p意义下同余，则输出"YES"，否则输出"NO"。

对于这样的题目，先考虑作一些对于复杂度没什么用，但是比较显然，并且让题目更加简明的优化。

优化1：令数组C[i]=(A[i]-B[i])%p，则当C全部是0时，输出YES，否则输出NO。

优化2：考虑维护cnt，即数组C中非0元素的数量，cnt=0时有C[i]全部为零。

优化3：预处理出斐波那契数列在模p意义下的每一项。

所有显而易见的优化都用完了。

思考1：如果是普通的区间加，我们会考虑维护一个差分数列，这样对于每一次区间和，我们只需要修改差分数列中的两个数。

思考2：对于区间加，我们的差分思想来自于(x_i+c) - (x_i-1+c) = x_i - x_i-1。

那么对于区间斐波那契加呢？

我们可以类似地发现：

(x_i+F_i) - (x_i-1-F_i-1) - (x_i-2-F_i-2)=x_i - x_i-1 - x_i-2

从而，我们维护一个斐波那契差分数列D，其中D[1]=C[1],D[i]=C[i]-C[i-1]-C[i-2]；从而对于每一次斐波那契加，我们只需要考虑D[i]区间边界上最多三个数值的变化，因此复杂度降至O(n)；

同样的，我们用cnt来维护这样一列D。

#include
using namespace std;
typedef long long ll;
const int N=3e5+10;
ll a[N],b[N],c[N],d[N];
ll f[N];
int main(){cin.tie(0);ios::sync_with_stdio(0);cout.tie(0);
    int n,q,mod,cnt=0;
    cin>>n>>q>>mod;f[1]=1;
    for(int i=2;i<=n;i++){
        f[i]=(f[i-1]+f[i-2])%mod;
    }
    for(int i=1;i<=n;i++)cin>>a[i];
    for(int i=1;i<=n;i++)cin>>b[i];
    for(int i=1;i<=n;i++)c[i]=(a[i]-b[i]+mod)%mod;
    d[1]=c[1];
    if(d[1]!=0)cnt++;
    for(int i=2;i<=n;i++){
        d[i]=((c[i]-c[i-1]-c[i-2])%mod+mod)%mod;
        if(d[i]!=0)cnt++;
    }
    while(q--){
        char ch;int l,r;
        cin>>ch>>l>>r;
        if(ch=='A'){
            if(d[l]==0)cnt++;
            d[l]=(d[l]+1)%mod;
            if(d[l]==0)cnt--;
            if(d[r+1]==0&&r+1<=n)cnt++;
            d[r+1]=(d[r+1]+mod-f[r-l+2])%mod;
            if(d[r+1]==0&&r+1<=n)cnt--;
            if(d[r+2]==0&&r+2<=n)cnt++;
            d[r+2]=(d[r+2]+mod-f[r-l+1])%mod;
            if(d[r+2]==0&&r+2<=n)cnt--;
        }
        if(ch=='B'){
            if(d[l]==0)cnt++;
            d[l]=(d[l]+mod-1)%mod;
            if(d[l]==0)cnt--;
            if(d[r+1]==0&&r+1<=n)cnt++;
            d[r+1]=(d[r+1]+f[r-l+2])%mod;
            if(d[r+1]==0&&r+1<=n)cnt--;
            if(d[r+2]==0&&r+2<=n)cnt++;
            d[r+2]=(f[r-l+1]+d[r+2])%mod;
            if(d[r+2]==0&&r+2<=n)cnt--;
        }
        if(cnt)cout<<"NO\n";
        else cout<<"YES\n";
    }
}