P15036 「chaynOI R2 T1」构造字符串
题目描述
本题字符集Σ = { a , b , c } \Sigma = \{\text{a},\text{b},\text{c}\}Σ={a,b,c}，即默认所有字符为a , b , c \text{a},\text{b},\text{c}a,b,c中的一个。
flow 有一个字符串T TT和一个初始为空的字符串S SS，其中∣ T ∣ = n |T|=n∣T∣=n，为了方便起见，保证T 1 = a , T 2 = b T_1=\text{a},T_2=\text{b}T1=a,T2=b。
flow 有两种操作：
- 向S SS末尾添加一个字符x xx，需要满足∄ 1 ≤ i ≤ ∣ S ∣ , S i = x \nexists 1\le i\le |S|,S_i=x∄1≤i≤∣S∣,Si=x。
- 选择一个位置i ii满足2 ≤ i ≤ ∣ S ∣ 2\le i\le |S|2≤i≤∣S∣且S i ≠ S i − 1 S_i\ne S_{i-1}Si=Si−1，将S i S_iSi修改为x xx满足x ∉ { S i − 1 , S i } x\not\in\{S_{i-1},S_i\}x∈{Si−1,Si}（可以注意到，x xx唯一）。
请你帮助 flow 在至多10 6 10^6106次操作后将S SS修改为与T TT相同，输出任意一个合法的解均可。
数据保证有解。
输入格式
一行一个字符串T TT。
输出格式
第一行一个正整数k kk，表示你的操作次数，需要满足1 ≤ k ≤ 10 6 1\le k\le 10^61≤k≤106。
接下来k kk行，每行为1 x或2 i，表示操作1 11加入字符x xx或操作2 22修改位置i ii。
输入输出样例 #1
输入 #1
abca输出 #1
8 1 a 1 c 1 b 2 3 1 b 2 2 2 3 2 4说明/提示
样例 1 解释
S SS的变换过程为[] → [a] → [ac] → [acb] → [aca] → [acab] → [abab] → [abcb] → [abca] \text{[]}\to\text{[a]}\to\text{[ac]}\to\text{[acb]}\to\text{[aca]}\to\text{[acab]}\to\text{[abab]}\to\text{[abcb]}\to\text{[abca]}[]→[a]→[ac]→[acb]→[aca]→[acab]→[abab]→[abcb]→[abca]。
数据范围
本题采用捆绑测试。
对于100 % 100\%100%的数据，3 ≤ n ≤ 222222 3\le n\le2222223≤n≤222222，T i ∈ Σ T_i\in \SigmaTi∈Σ。
- Subtask1(10pts)：n ≤ 5 n\le 5n≤5。
- Subtask2(10pts)：n ≤ 1000 n\le 1000n≤1000。
- Subtask3(10pts)：∀ 3 ≤ i ≤ n \forall 3\le i\le n∀3≤i≤n，T i = c T_i=\text{c}Ti=c。
- Subtask4(20pts)：n ≤ 2 × 10 5 n\le 2\times10^5n≤2×105。
- Subtask5(50pts)：无特殊限制。
思路
直接暴力构造，倒序实现。
代码见下
#include<bits/stdc++.h>usingnamespacestd;string str;chars[1000006],t[1000006];structone{longlonga;charx;longlongi;}a[1000006];longlongn,k;intmain(){cin>>str;for(inti=0;i<str.size();i++){t[++n]=str[i];}s[1]=t[1];s[2]=t[2];a[++k]={1,'a',0};a[++k]={1,'b',0};for(inti=3;i<=n;i++){a[++k]={1,'c',0};a[++k]={2,' ',i};if(i%2==1){s[i]='a';}else{s[i]='b';}}for(inti=n;i>=1;i--){if(s[i]!=t[i]){if(s[i]=='a'){if(t[i]=='b'){a[++k]={2,' ',i-1};a[++k]={2,' ',i};s[i-1]='c';}else{a[++k]={2,' ',i};}}elseif(s[i]=='b'){if(t[i]=='a'){a[++k]={2,' ',i-1};a[++k]={2,' ',i};s[i-1]='c';}else{a[++k]={2,' ',i};}}else{if(t[i]=='a'){if(s[i-1]=='b'){a[++k]={2,' ',i};}else{a[++k]={2,' ',i};a[++k]={2,' ',i-1};a[++k]={2,' ',i};s[i-1]='c';}}else{if(s[i-1]=='a'){a[++k]={2,' ',i};}else{a[++k]={2,' ',i};a[++k]={2,' ',i-1};a[++k]={2,' ',i};s[i-1]='c';}}}}}if(k<=1000000){cout<<k<<endl;for(inti=1;i<=k;i++){if(a[i].a==1){cout<<a[i].a<<" "<<a[i].x<<'\n';}else{cout<<a[i].a<<" "<<a[i].i<<'\n';}}}else{k=0;n=0;for(inti=0;i<str.size();i++){t[++n]=str[i];}s[1]=t[1];s[2]=t[2];a[++k]={1,'a',0};a[++k]={1,'b',0};for(inti=3;i<=n;i++){a[++k]={1,'c',0};a[++k]={2,' ',i};if(i%2==1){s[i]='a';}else{s[i]='b';}}for(inti=n;i>=1;){if(s[i]!=t[i]){if(s[i]=='a'){if(t[i]=='b'){intu=i;for(intj=i;j>=1;j--){if(s[j]==t[j]||t[j]=='c'){u=j+1;break;}}for(intj=u;j<=i;j+=2){a[++k]={2,' ',j};}for(intj=u+1;j<=i;j+=2){a[++k]={2,' ',j};}for(intj=u;j<=i;j+=2){a[++k]={2,' ',j};}a[++k]={2,' ',u-1};a[++k]={2,' ',u};a[++k]={2,' ',u-1};i=u-1;}else{a[++k]={2,' ',i};i--;}}else{if(t[i]=='a'){intu=i;for(intj=i;j>=1;j--){if(s[j]==t[j]||t[j]=='c'){u=j+1;break;}}for(intj=u;j<=i;j+=2){a[++k]={2,' ',j};}for(intj=u+1;j<=i;j+=2){a[++k]={2,' ',j};}for(intj=u;j<=i;j+=2){a[++k]={2,' ',j};}a[++k]={2,' ',u-1};a[++k]={2,' ',u};a[++k]={2,' ',u-1};i=u-1;}else{a[++k]={2,' ',i};i--;}}}else{i--;}}cout<<k<<endl;for(inti=1;i<=k;i++){if(a[i].a==1){cout<<a[i].a<<" "<<a[i].x<<'\n';}else{cout<<a[i].a<<" "<<a[i].i<<'\n';}}}return0;}```
