C. Parity Shuffle Sorting

思路： 构造方法1：如果第一个和最后一个元素不同，则先让第一个元素与最后一个元素相同，然后对于2~n-1位置的元素，如果该元素与第1个元素和为奇数，则操作(1,i)，否则操作(i,n)

构造方法2：先判断第一个元素是奇数还是偶数，假设为奇数，设位置为omin，最后出现的奇数位置为omax，然后对于每个位置，如果该位置为奇数，则操作(i,omax)，否则操作(omin,i)

代码（法2）：

void slove(){
   int n;
   cin>>n;
   int v[n];
   _for(i,0,n)cin>>v[i];
   int judge[n];
   int omax=-1,emax=-1;
   int ocnt=0,ecnt=0;
   int omin=1e9+7,emin=1e9+7;
   _for(i,0,n){
    if(v[i]&1){
        ocnt++;
        judge[i]=1;
        omax=max(omax,i);
        omin=min(omin,i);
    }
    else{
        ecnt++;
        judge[i]=0;
        emax=max(emax,i);
        emin=min(emin,i);
    }
   }
   ll total=0;
   if(emax==-1||omax==-1){
    cout << n-1 << endl;
    _for(i,0,n-1){
        cout << i+1 << " " << n << endl;
    }
   }else if(emin<omin){
    cout << ecnt-1+ocnt << endl;
    if(emin!=emax)cout << emin+1 << " " << emax+1 << endl;
    _for(i,0,n){
        if(i==emin||i==emax)continue;
        if(v[i]%2==0)cout << i+1 << " " << emax+1 << endl;
        else cout << emin+1 << " " << i+1 << endl;
    }
   }else if(emin>omin){
    cout << ocnt-1+ecnt << endl;
    if(omin!=omax)cout << omin+1 << " " << omax+1 << endl;
    _for(i,0,n){
        if(i==omin||i==omax)continue;
        if(v[i]&1)cout << i+1 << " " << omax+1 << endl;
        else cout << omin+1 << " " << i+1 << endl;
    }
   }
}

D2. Zero-One (Hard Version)

思路： 对于每次操作，我们能选择ａ，ｂ中两个位置i,j，如果a[i]=b[i]则操作后a[i]!=b[i],j同理，因此我们可以观察到每次操作会改变俩个位置的性质，相同变不同，不同变相同，而每步操作如果能减少不同的位置数目的话一定是减少两个，因此a[i]与b[i]不同的位置个数必须是偶数个，否则无解。

对于简单版本，有ｙ＜＝ｘ的限制，我们先遍历数组，将a[i]与b[i]不同的位置存入数组v，假设v中元素个数为偶数且大于2，那么可以贪心的知道全部用y肯定最好，假设有k个元素，只要分别对1，k/2; 2,k/2+1 ......进行操作即可。如果恰好有两个元素，因为原数组的元素个数大于等于5，因此操作的花费要么是x，要么是2y，两者取最小即可。（假设i,j不同，则2y的操作是先(i,k)，再(k,j)

法1：O(n^2)dp（正确性证不出来，难受，但能AC）

而对于复杂版本，当y<=x时做法与简单版本一样，而当y>x时，任意使两个不同的位置i,j变相同的花费为有两种情况：1. i,j相邻：x或2*y, 2. i,j不相邻：y或者(j-i)*x，此时无法贪心，因此可以使用dp，令dp[l][r]表示使得v数组中[l,r]区间上的a数组等于b数组的最小花费，因为每次操作都是减少两个不同的位置，假设l-r-1区间长度的情况已经确定，考虑从l-r-1区间长度向l-r+1区间长度转移时只有三种情况，一种是最后两个全加在左边，即dp[l][r]=min(dp[l][r],dp[l+2][r]+get(l,l+1))，另一种是全加在右边，即dp[l][r]=min(dp[l][r],dp[l][r-2]+get(r-1,r))，最后是一个加左边，一个加右边，即dp[l][r]=min(dp[l][r],dp[l+1][r-1]+get(l,r))

代码：

const int N = 200010;
const int mod=1e9+7;

ll n,x,y;

ll get(int l,int r){
    if(l+1==r)return x;
    else return min(y,(r-l)*x);
}

void slove(){
   cin>>n>>x>>y;
   string a,b;
   cin>>a>>b;
   vi v;
   ll cnt=0;
   _for(i,0,n){
    if(a[i]!=b[i]){
        cnt++;
        v.pb(i);
    }
   }
   if(cnt&1){
    cout << -1 << endl;
    return;
   }
   if(y<=x){
    if(cnt==2){
        if(v[1]-v[0]==1)cout << min(x,2*y) << endl;
        else cout << y << endl;
    }
    else cout << cnt/2*y << endl;
   }
   else{
    if(cnt==0){
        cout << 0 << endl;
        return;
    }
    ll dp[cnt][cnt];
    mm(dp,0x3f);
    _for(i,0,cnt-1){
        dp[i][i+1]=get(v[i],v[i+1]);
    }
    int dis=4;
    while(dis<=cnt){
        _for(i,0,cnt-dis+1){
            int l=i,r=i+dis-1;
            dp[l][r]=min(dp[l][r],dp[l+1][r-1]+get(v[l],v[r]));
            dp[l][r]=min(dp[l][r],dp[l+2][r]+get(v[l],v[l+1]));
            dp[l][r]=min(dp[l][r],dp[l][r-2]+get(v[r-1],v[r]));
        }
        dis+=2;
    }
    cout << dp[0][cnt-1] << endl;
   }
}

法2：O(n)dp

先证明用x消去的一定都是两两相邻的。

情况1：假设不会出现用y消除的两点之间包含奇数个用x消除的点的情况

首先先将用y消去的删掉。因为删去的花费为俩点之间距离乘以x，剩下的如果不是两两相邻消去的话假设i与j不是俩俩消去，则将i与j之间的所有元素改成俩俩消去的话总距离一定小于初识，因为光是i与j间的距离就已经大于等于俩俩消去的距离了。

情况2：出现y消除夹奇数个x

这种情况下，将1，4用y消除，2，3用x消除不会比原本花费高，因为13用y消，那么14肯定也是用y消划算，而将23用x消一定比24花费低，因此得知就算出现这种情况也能转换为第一种情况，且花费不会变多

令dp[i]表示使v中前i个不同变相同的最小花费。

当i为偶数时，就是全消掉，当i为奇数时，有1个还未消去。当i为偶数时，考虑最后一步，假设最后一步用y消的，那么dp[i]=dp[i-1]+y，假设最后一步用x消的，则一定是与第i-1个消，那么dp[i]=dp[i-2]+(v[i]-v[i-1])*x;

当i为奇数时，假设最后一步不消，i空着，那么dp[i]=dp[i-1]，假设最后一步用x消，那么dp[i]=dp[i-2]+(v[i]-v[i-1])*x,假设最后一步用y消，则dp[i]=dp[i-2]+y，但是由偶数的情况可以知道dp[i-1]=min(dp[i-2]+y,dp[i-3]+(v[i-2]-v[i-3])*x)，因此dp[i-1]<=dp[i-2]+y，所以可以不用考虑dp[i-2]+y，直接用dp[i-1]就行

代码：

ll n,x,y;

ll get(int l,int r){
    if(l+1==r)return x;
    else return min(y,(r-l)*x);
}

void slove(){
   cin>>n>>x>>y;
   string a,b;
   cin>>a>>b;
   vi v;
   ll cnt=0;
   _for(i,0,n){
    if(a[i]!=b[i]){
        cnt++;
        v.pb(i);
    }
   }
   if(cnt&1){
    cout << -1 << endl;
    return;
   }
   if(y<=x){
    if(cnt==2){
        if(v[1]-v[0]==1)cout << min(x,2*y) << endl;
        else cout << y << endl;
    }
    else cout << cnt/2*y << endl;
   }
   else{
    if(cnt==0){
        cout << 0 << endl;
        return;
    }
    ll dp[cnt+1];
    mm(dp,0x3f);
    dp[0]=0;
    _fore(i,1,cnt){
        if(i&1){
            if(i>1)dp[i]=min(dp[i],dp[i-2]+(v[i-1]-v[i-2])*x);
            dp[i]=min(dp[i],dp[i-1]);
        }
        else{
            dp[i]=min(dp[i-1]+y,dp[i-2]+(v[i-1]-v[i-2])*x);
        }
    }
    cout << dp[cnt] << endl;
   }
}