Codeforces Round #658 (Div. 2) (C1、C2)

C、Prefix Flip

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

C₁、Easy Version(代码与 C₂ 不同)

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

例: 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的操作次数限制，只要遍历s₁，若 i 位置上和s₂ 不同我们就记录一次操作，并将变化后的字符串替换s₁。

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

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

AC代码 :

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#define ll long long
#define pb push_back
const 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(false);
    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';
                else
                    s[0] = '0';
                cz.pb(1);
            }
            cz.pb(i + 1);
            for (int j = 0; j < n; j++)
            {
                if (s[j] == '0')
                    s[j] = '1';
                else
                    s[j] = '0';
            }
            reverse(s.begin(), s.begin() + i + 1);
        }
        cout << cz.size() << " ";
        for (int j = 0; j < cz.size(); j++)
            cout << cz[j] << " ";
        cout << endl;
    }
    return 0;
}

C₂、Hard Version

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

问题 :
同 C₁

样例 :
同 C₁

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

方法1 :

思路 :

关键

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

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

方法2 ：

思路 :

Q1. 复杂度高的原因

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

Q2. 01转换的影响

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

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

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

最后

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

AC代码

#include <iostream>
#include <algorithm>
#include <string>
#include <cstdio>
#include <cstring>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <bitset>
#define ll long long
#define pb push_back
const 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(false);
    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