【题解】CF1852D Miriany and Matchstick

ricky_lin / 2023-09-05 / 原文

考虑 dp，设 $f_{i,0/1}$ 表示考虑到前 $i$ 位，且第 $i$ 位填入 A/B 可能的答案集合，显然地朴素转移时间复杂度 $O(n^2)$。

试分析 dp 性质，观察发现所有 dp 中得到的集合为区间内抠去至多一个点。

证明
我们首先来观察转移过程是怎样的。第一种是第二行中 $i-1$ 填入的字母与第一行中 $i$ 填入的字母相同的情况，此时根据我们填入的字母与其相同与否，集合会整体平移 $0$ 或 $2$；第二种是不同的情况，此时无论我们如何填入字母，集合都会整体平移 $1$。由于我们只关心集合的相对位置关系，我们可以将转移视为将 $f_{i-1,0/1}$ 固定不动，将 $f_{i-1,1/0}$ 平移 $1$ 以及 $-1$，分别进行取或操作，得到 $f_{i}$。
首先容易发现，$f_i$ 的两个集合两侧端点的差的绝对值分别不超过 $2$。这是由于这两个集合是由一个固定的集合或上另外一个集合平移 $1/-1$ 得到的。现在，我们可以归纳说明一个更强的结论：$f_i$ 的两个集合中至多存在一个集合中存在且恰存在一个空位。

显然 $1$ 满足条件。假设 $i-1$ 满足此条件。由于区间过小时的情况比较神秘，我们在此只讨论 $r-l+1\ge5$ 的情况。对于区间更小的情况打表可证。在这种情况下，最坏是 $f_{i-1,x}$ 为 $[l,r]$ 抠去 $p(p\in(l,r))$，$f_{i-1,1-x}$ 为 $[l+2,r-2]$。此时，若 $i$ 不满足此条件，则存在一个 $p$ 使得 $[l+2,r-2]$ 无论平移 $1$ 还是 $-1$ 都无法覆盖到，而这显然无解。

故证毕。证得比原结论更强的结论，故原结论也证毕。

褐自落谷题解

所以说对于每个 $f_{i,0/1}$ 只需要维护 $(l,r,p)$，即（左端点，右端点，中间挖去的点）

时间复杂度 $O(n)$。

code：

#include<bits/stdc++.h>
using namespace std;
const int NN = 2e5 + 8;
int T;
int n,k;
char s[NN],S[NN];
struct Node{
	int l,r,p;
	Node operator + (int x){
		return {l+x,r+x,p==-1?-1:p+x};
	}
	bool ckin(int x){
		return l <= x && x <= r && x != p;
	}
}f[NN][2];
Node operator ^ (Node a, Node b){
	if(a.l > b.l) swap(a,b);
	Node res = {min(a.l,b.l),max(a.r,b.r),-1};
	if(a.r + 2 == b.l) res.p = a.r + 1;
	else{
		if(a.p != -1 && !b.ckin(a.p)) res.p = a.p;
		if(b.p != -1 && !a.ckin(b.p)) res.p = b.p;
	}
	return res;
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&k);
		scanf("%s",s+1);
		for(int i = 1; i < n; ++i) k -= (s[i]!=s[i+1]);
		if(k < 0){puts("NO");continue;}//判第一行
		int type = s[1] - 'A';
		f[1][type^1] = {1,1,-1}; f[1][type] = {0,0,-1};
		
		int ty;
		for(int i = 2; i <= n; ++i){
			ty = s[i]-'A';
			f[i][ty] = f[i-1][ty] ^ f[i-1][ty^1]+1;
			f[i][ty^1] = f[i-1][ty]+2 ^ f[i-1][ty^1]+1;
		}
		
		ty = -1;
		if(f[n][0].ckin(k)) ty = 0;
		if(f[n][1].ckin(k)) ty = 1;
		if(ty == -1) {puts("NO");continue;}
		puts("YES");
		for(int i = n; i; --i){
			S[i] = 'A' + ty;
			if(i == 1) break;
			k -= (S[i]!=s[i]);
			if(f[i-1][ty].ckin(k)) continue;//只要有答案就走 
			ty ^= 1, --k;
		}
		printf("%s\n",S+1);//ans collecting
		for(int i = 1; i <= n; ++i) S[i] = '\000';
	}
}