codeforce 685 div2 C

题意：
给 a,b两个字符串，然后让a变成b
方法：可以对前缀1-k的01串进行翻转，最后对前缀序列进行翻转

思路：
很简单一个题，我们只需要保证a的后位和b的后位相同即可，呢么我们从后往前枚举，
若k位相同可以不管，若不相同，我们观察第1位和b的k位的关系，若相同我们先把第1位
变成和k位不相同，然后再对k位整体进行翻转即可，这样当前位的k位相同，然后我们向后
枚举即可

参考代码：

#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <map>
#include <queue>
#include <set>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <math.h>
using namespace std;
typedef long long ll;
const int N = 1005;
const int maxn = 1e5 + 5;
map<int, int> mp;
vector<int> vec;
string rev(string a, int k)
{
    for (int i = 0; i <= k; i++)
    {
        if (a[i] == '1')
            a[i] = '0';
        else
            a[i] = '1';
    }
    reverse(a.begin(), a.begin() + k);
    return a;
}
void solve(string a, string b, int n)
{
    n--;
    for (int i = n; i >= 0; i--)
    {
        while (a[i] != b[i])
        {
            if (a[0] == b[i])
            {
                a = rev(a, 0);
                vec.push_back(1);
            }
            else
            {
                a = rev(a, i+1);
                vec.push_back(i + 1);
            }
        }
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while (t--)
    {
        vec.clear();
        int n;
        cin >> n;
        string a, b;
        cin >> a >> b;
        solve(a, b, n);
        cout << vec.size() << ' ';
        int m = vec.size();
        for (int i = 0; i < m; i++)
        {
            cout << vec[i] << ' ';
        }
        cout << endl;
    }
}

本文地址：https://blog.csdn.net/yangzijiangac/article/details/107513693