C、Prefix Flip

两题题意相同，变化在 n 的取值范围
(可以直接看C2部分)

C1、Easy Version(代码与 C2 不同)

题意 :
(多组输入)(n <= 1000)
给你两个长度为 n 的01字符串 s1 与 s2
选中 s1 任意长度的前缀，将他们01转换，再转置这个前缀，最多可进行 3n 次上述操作，让其变成 s2

例: 01一次操作后仍是01

问题 :
求操作次数 (不要求最少) 和 每次选择的前缀长度
(每组输出为一行，第一个为操作次数 后面为前缀长度)

样例 :

input :
5
2
01
10
5
01011
11100
2
01
01
10
0110011011
1000110100
1
0
1

output :
3 1 2 1
6 5 2 5 3 1 2
0
9 4 1 2 10 4 1 2 1 5
1 1

思路 :
3n的操作次数限制，只要遍历s1，若 i 位置上和s2 不同我们就记录一次操作，并将变化后的字符串替换s1。

但考虑到每次操作都会改变从头一直到操作位置的串，若我们从头往后遍历，在对后面操作时会改变前面的串，很难再回头操作。

因此我们要从后往前遍历。

AC代码 :

#include <iostream>#include <algorithm>#include <str欢乐颂主题曲ing>#include <cstdio>#include <cstring>#include <queue>#include <map>#include <cmath>#include <t>#define ll long long#define pb push_backconst int MAX = 1e5 + 10;const 背景音乐克隆int MOD = 1e9 + 7;const int INF = 0x3f3f3f3f;using namespace std;int n, m, a[MAX];string s, p;vector<int> cz;int main(){    ios::sync_with_stdio(fal);    cin.tie(NULL);    cout.tie(NULL);    int t;    cin >> t;    while (t--)    {        cz.clear();        cin >> n >> s >> p;        for (int i = n - 1; i >= 0; i--)        {            if (p[i] == s[i])                continue;            if (p[i] == s[0])            {                if (s[0] == '0')                    s[0] = '1';                el                    s[0] = '0';                cz.pb(1);            }            cz.pb(i + 1);            for (int j = 0; j < n; j++)            {                if (s[j] == '0')                    s[j] 七年级上册英语听力= '1';                el                    s[j] = '0';            }            rever(s.begin(), s.begin() + i + 1);        }        cout << cz.size() << " ";        for (int j = 0; j < cz.size(); j++)            cout << cz[j] << " ";        cout << endl;    }    return 0;}

C2、Hard Version

题意 :
(多组输入)(n <= 100000)
同 C1

问题 :
同 天津交通职业学院C1

样例 :
同 C1

n 取值范围变大，C1 中替换 s1 复杂度过高，在这会TLE，因此需要转换思路

方法1 :

思路 :

关键

两次操作 等于变回 原串，因此可以在找到需要替换位置 i 时，对 i 的前缀的两次操作中加对 头 的操作 (等同于只修改了第i位)

例: 0011 要变成 0001
在第3位时，
step1. 对前3位操作得到0111
step2. 对第1位操作得到1111
step3. 对前3位操作得到0001

方法2 ：

思路 :

Q1. 复杂度高的原因

操作中的转置对 s1 变成 s2 影响很大，转置后位置难以保存，只能直接替换 s1 实现，而每次保存 s1 需要 O(n) 的复杂度。

Q2. 01转换的影响

若只有01的转换 可以通过控制操作位置，很简单的变成目标串 s2 。

Q3. 如何将 转置影响 去掉？

回文串 可以避免 转置影响，但要保证每次操作完后仍然是 回文串，只能选 纯0串 或 纯1串 。

最后

因此，先将 s1 变为 纯0串 或 纯1串 ，再从尾到头遍历修改为 s2 即可

AC代码

#include <iostream>#include <algorithm>#include <string>#include <cstdio>#include <cstring>#include <queue>#include <map>#include <cmath>#include <t>#include <bitt>#define ll long long#define pb push_backconst int MAX = 1e5 春雨诗歌+ 10;const int MOD = 1e9 + 10;const int INF = 0x3f3f3f3f;using namespace std;int n;string s1, s2;int main(){    ios::sync_with_stdio(fal);    cin.tie(NULL);    cout.tie(NULL);    int t;    cin >> t;    while (t--)    {        vector<int> cnt;        cin >> n >> s1 >> s2;        char fg = s1[0];        for (int i = 0; i < n - 1; i++)            if (s1[i] != s1[i + 1])            {                cnt.pb(i + 1);                fg = s1[i + 1];            }        for (int i = n - 1; i >= 0; i--)        {            if (s2[i] != fg)            {                cnt.pb(i + 1);                fg = (fg == '0' ? '1' : '0');            }        }        cout << cnt.size() << " ";        for (int i = 0; i < cnt.size(); i++)            cout << cnt[i] << " ";        cout << endl;    }     return 0;}

本文地址：https://blog.csdn.net/qq_14904619/article/details/107512712