codeforces-#658-C2

codeforces-#658-C2

七月 22, 2020

C2. Prefix Flip (Hard Version)

题意
给出两个长度为n<2e5的01串

一个原串s和一个目标串t

要求不超过2n次操作将s变为t串

一次操作：

选择s的一个前缀 将前缀中的0变成1，1变成0

然后将这个前缀翻转

题解

有很多种构造方法

easy版On^2 复杂度用2n次操作:

从后往前遍历 逐个修改s[i]

若s[i]!=t[i] 它必然需要被操作 由于一次操作时一定有一个前缀的整体翻转

所以s[i]处的bit一定是由s[0]处翻转得到的

所以策略是先操作第一个bit s[0] (要判断是否需要) 然后再操作前缀s[0~i]

On^2是需要模拟操作种的取反+反转

hard版可以用同样策略优化到

需要考虑如何优化掉模拟操作带来的复杂度

注意到每次取反翻转 使得s[i]=t[i] 对于当前状态的s的前缀对应最初s的某一段子串

只需要追踪当前状态的s的前缀对应最初s串中那个下标 并且是否是翻转得到

就可以On处理处答案

实际实现时出了一对bug调到心累 逻辑不够清晰代码写的稀烂

另一种策略:

更直观的策略是用n次操作将s变为全0串

再用n次操作将t变为全0串

那么答案是 将s变为全0串的过程+t变为全0串的逆过程

官方代码 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include <bits/stdc++.h>

using namespace std;

//方案2，摘自社论
//我们不进行模拟，而是存储两个变量idx和flip
//它们告诉我们足够的信息来询问过程中第一个比特的值
//如果flip为false，则表示子字符串s[idx，…， idx + i)目前是s的开始
//如果翻转为真，则表示翻转子字符串s[idx - i + 1，…目前是s的开始
//我们在每位O(1)时间或O(n)时间内正确地更新idx和翻转

int t, n;
string a, b;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> t;
    while(t--) {
        cin >> n >> a >> b;
        bool flip = false;
        int idx = 0;
        vector<int> ops;
        for(int i = n - 1; i >= 0; i--) {
            if(flip ^ (a[idx] == b[i])) {
                ops.push_back(1);
            }
            ops.push_back(i + 1);
            if(flip) idx -= i;
            else idx += i;
            flip = !flip;
        }
        cout << ops.size() << ' ';
        for(int x : ops) {
            cout << x << ' ';
        }
        cout << '\n';
    }
}

第二种实现方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> P;
#define endl '\n'
#define Turnoff std::ios::sync_with_stdio(false)

const int mod=2e3;
const int Max=2000+5;
int data[Max],dp[2][Max];

/*
4
10
0110011011
1000110100
7 1 10 8 7 1 2 1
*/
string s,ns;int n;
int main(){
    Turnoff;
    int t;cin>>t;
    while(t--){
        int n;cin>>n;
        string s,ns;cin>>s>>ns;
        s+='0',ns+='0';
        vector<int>ans,temp;
        for(int i=0;i<n;i++){
            if(s[i]!=s[i+1])ans.push_back(i+1);
            if(ns[i]!=ns[i+1])temp.push_back(i+1);
        }
        reverse(temp.begin(),temp.end());
        cout<<ans.size()+temp.size();
        for(auto i:ans)cout<<" "<<i;
        for(auto i:temp)cout<<" "<<i;
        cout<<endl;
    }
}