P7940题解

· · 题解

Solution

由题意，我们必须恰好改变每队恰好 n 个人的出拳方案。即会出现在已经构造出全胜方案之后还有剩余的操作次数的情况。所以我们必须考虑如何构造，维持最终得分为 2n。

下面讲讲我的做法。

我们不妨定义修改 A 组的操作为操作 x，修改 B 组的操作为操作 y。

  1. 依次使用操作 x,y，构造出 A 组全胜的状态。
  2. 在经过上一步之后，可能存在操作次数还未用完的情况。对此我们不妨找出之前未被修改的对局（即 A 组本来就胜利的情况），同时对 a_i,b_i 进行修改，使得两种操作的使用次数同时增加。
  3. 经过以上两轮之后，可以发现要么已经构造完毕，要么还剩下一次 y 操作（第 1 步中可能会出现 cnt_x=cnt_y+1 的情况）。对于这种情况，不妨找出第一次被修改的对局，对其使用一次 y 操作即可。

Code

#include<bits/stdc++.h>
using namespace std;
int t,n,a[200005],b[200005],c[200005],d[200005];//把修改后的数存在数组c,d中
bool check(int x,int y){
    if(x==1&&y==2)return 1;
    if(x==2&&y==3)return 1;
    if(x==3&&y==1)return 1;
    return 0;
}//判断胜负
bool vis[200005];
int main(){
    cin>>t;
    while(t--){
        cin>>n; 
        int cnt=0,cntx=0,cnty=0;
        for(int i=1;i<=n*2;i++){
            cin>>a[i];
            c[i]=a[i];
            vis[i]=0;
        }
        for(int i=1;i<=n*2;i++){
            cin>>b[i];
            d[i]=b[i];
        }
        for(int i=1;i<=2*n;i++){
            if(check(a[i],b[i]))continue;
            cnt++;
            if(cnt%2==1){
                cntx++;
                c[i]=d[i]-1;
                if(c[i]==0)c[i]=3;
            }//改a
            else{
                cnty++;
                d[i]=c[i]+1;
                if(d[i]==4)d[i]=1;
            }//改b
            vis[i]=1;           
        }//改为a必胜的局面
        for(int i=1;i<=2*n;i++){
            if(vis[i])continue;
            if(cntx<n&&cnty<n){
                c[i]+=1;
                if(c[i]==4)c[i]=1;
                d[i]+=1;
                if(d[i]==4)d[i]=1;
                cntx++,cnty++;
            }
            if(cntx==cnty&&cntx==n)break;
        }//消耗多余的操作次数
        if(cnty<n){
            for(int i=1;i<=n*2;i++){
                if(vis[i]){
                    for(int j=1;j<=3;j++){
                        for(int k=1;k<=3;k++)
                            if(j!=a[i]&&k!=b[i]&&check(j,k))c[i]=j,d[i]=k;
                    }//此处直接暴力修改即可，记得判重
                    break;
                }   
            }
        }
        cout<<n*2<<endl;
        for(int i=1;i<=n*2;i++)cout<<c[i]<<" ";
        cout<<endl; 
        for(int i=1;i<=n*2;i++)cout<<d[i]<<" ";
        cout<<endl;     
    }
    return 0;
}