Codeforces 1215C. Swap Letters

传送门

好像是个挺显然的贪心

首先每次交换当然要尽量一次交换就多两个相同的位置

即

优先把 $\begin{bmatrix}a\\ b\end{bmatrix}$ 和 $\begin{bmatrix}a\\ b\end{bmatrix}$ 交换

优先把 $\begin{bmatrix}b\\ a\end{bmatrix}$ 和 $\begin{bmatrix}b\\ a\end{bmatrix}$ 交换

最后如果剩下$\begin{bmatrix}a\\ b\end{bmatrix}$，$\begin{bmatrix}b\\ a\end{bmatrix}$ 各一个

我们才只好用两次交换次数把它们搞好，这样就是最优的了

当然如果最后某一种情况剩下一个，另一种情况却没了

那就无解了，具体维护看代码吧

#include<iostream>

#include<cstdio>

#include<algorithm>

#include<cstring>

#include<cmath>

#include<vector>

using namespace std;

typedef long long ll;

inline int read()

{

    int x=,f=; char ch=getchar();

    while(ch<''||ch>'') { if(ch=='-') f=-; ch=getchar(); }

    while(ch>=''&&ch<='') { x=(x<<)+(x<<)+(ch^); ch=getchar(); }

    return x*f;

}

const int N=4e5+;

int n,pa,pb;

char A[N],B[N];

vector <int> ans[];

int main()

{

    n=read(); scanf("%s",A+); scanf("%s",B+);

    for(int i=;i<=n;i++)

    {

        if(A[i]==B[i]) continue;

        if(A[i]=='a')

        {

            if(!pa) pa=i;

            else ans[].push_back(pa),ans[].push_back(i),pa=;

        }

        else

        {

            if(!pb) pb=i;

            else ans[].push_back(pb),ans[].push_back(i),pb=;

        }

    }

    if((pa&&!pb)||(!pa&&pb)) { printf("-1\n"); return ; }

    if(pa&&pb) { ans[].push_back(pa); ans[].push_back(pa); ans[].push_back(pa); ans[].push_back(pb); }

    int len=ans[].size();

    printf("%d\n",len);

    for(int i=;i<len;i++) printf("%d %d\n",ans[][i],ans[][i]);

    return ;

}

巴特西

Codeforces 1215C. Swap Letters

最新文章

热门文章