欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  移动技术

codeforce 685 div2 C

程序员文章站 2022-12-30 22:29:08
题意:给 a,b两个字符串,然后让a变成b方法:可以对前缀1-k的01串进行翻转,最后对前缀序列进行翻转思路:很简单一个题,我们只需要保证a的后位和b的后位相同即可,呢么我们从后往前枚举,若k位相同可以不管,若不相同,我们观察第1位和b的k位的关系,若相同我们先把第1位变成和k位不相同,然后再对k位整体进行翻转即可,这样当前位的k位相同,然后我们向后枚举即可参考代码:#include #include #include &l...

题意:
给 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