CF c.swap Letter

题目大意,给定两个长度相同,都只包含字母a,b的字符串s1,s2,变换方式:可以交换字符s1[i],s2[j],交换次数不限,问是否可以经过多次交换后使得两个字符串相同,如果不能输出-1,如果可以输出最小的交换次数和每次交换的两个字符在两个字符串的位置。

思想:由于字串中的元素只有a,b两种,只需要统计s1[i]!=s2[i]情况下s1[i] =a 和s1[i] = b的位置即可,s1[i]  =a的情况两个为一组交换位置,s1[i] = b的情况同理。

aa

bb

如果a的个数是奇数个并且b的个数是奇数个,那么对于最后一个需要两步

ab->bb->ab

ba   aa   ab

如果ab中有一个的个数是奇数,则无解

 

//#include<string>
#include<vector>
#include<stdio.h>
#pragma warning(disable:4996)
#define maxn 200000+33
using namespace std;
vector<int>a, b;
char s1[maxn], s2[maxn];
int n;
int main()
{
    scanf("%d", &n);
    scanf("%s", s1 + 1);
    scanf("%s",s2+1);
    for (int i = 1; i <= n; i++)
    {
        if (s1[i] != s2[i])
        {
            if (s1[i] == 'a')a.push_back(i);
            else
                b.push_back(i);
        }
    }
    if ((a.size() + b.size()) & 1) printf("-1");
    else
    {
        int res = a.size() / 2 + b.size() / 2;
        if (a.size() & 1 && b.size() & 1) res += 2;
        printf("%d\n", res);
        for (int i = 0; i + 1 < a.size(); i += 2)
            printf("%d %d\n",a[i],a[i+1]);
        for (int i = 0; i + 1 < b.size(); i += 2)
            printf("%d %d\n", b[i], b[i+1]);
        if (a.size() & 1 && b.size() & 1)
        {
            printf("%d %d\n",a[a.size()-1],a[a.size()-1]);
            printf("%d %d\n",a[a.size()-1],b[b.size()-1]);
        }
    }
    
    return 0;

}

第一等人,有本事,没脾气;

第二等人,有本事,有脾气;

第三等人,没本事,脾气比谁都大;

 

上一篇:浏览器图片问题


下一篇:python在linux中随机生成密码