Good Game

题目链接QOJ 4273

题目大意

给你一个 01 串每次可以删一个长度为 2/3 的全 0 子串或者全 1 子串。
要你构造一种方法把串删空或者输出无解。

思路

首先发现这个删 $2/3$ 其实就等价于删 $2$ 以上的。
那我们就可以把 $2$ 以及以上的都看成 $2$相当于把串改成了另一个 $01$ 串你每次可以把 $1$ 删了或者把 $x1x$ 变成 $1$要删完。

那考虑怎么弄进行一个分类讨论。

首先串长为奇数。
那一个最简单的想法是如果最中间的位置是 $1$那我们就一直用 $x1x$ 变成 $1$最后把 $1$ 去掉就好。
但如果中间是 $0$ 呢考虑让这个位置变成 $1$那我们能用的方法就只有 $x1x$。
那你哪边用这个一下就把中间位置往另一边移了。
那你就找到两半距离中间最近的 $1$然后如果近的那边到中间的距离是 $x$那你就在远的那边操作 $x$ 次就可以到中间了。
那考虑一下无解条件思考一下如果 $01$ 串长度为 $2k+1$那如果中间那个 $0$ 所在的 $0$ 区间长度达到 $k$ 就无解了而思考一下会发现如果到达了 $k$ 的长度一定会包括中间的 $0$。

那接下来长度为偶数。
那不难想象你每次基本上都是用 $x1x$ 删的那最后的时候一定要剩下两个 $1$ 才行那这两个 $1$ 我们是否可以认为是我们把这个 $01$ 串分成两个长度为奇数的 $01$ 串分别得到的呢
没错是可以的那我们就枚举分界的地方那一个串有无解这个我们前面已经知道了中间是 $1$ 或者不存在长度为串一半的 $0$ 连续段
那这个后面的条件我们可以处理前缀和后缀的最长 $0$ 连续串来得到。
那就可以弄了。

具体的实现可以看代码。

代码

#include<cstdio>
#include<vector>

using namespace std;

const int N = 1e6 + 100;
int n, m, ls[N], rs[N], a[N], Ls[N], Rs[N];
char s[N];
vector <pair<int, int> > ans;
bool shit;

void write() {
	if (shit) {printf("-1"); return ;}
	printf("%d\n", ans.size());
	for (int i = 0; i < ans.size(); i++) printf("%d %d\n", ans[i].first, ans[i].second);
}

void clean(int l, int sz) {
	if (sz & 1) ans.push_back(make_pair(l, 3)), sz -= 3;
	while (sz) ans.push_back(make_pair(l, 2)), sz -= 2;
}

void lnk_clean(int x, int y) {
	clean(ls[x], rs[x] - ls[x] + 1 + ((x ^ y) ? rs[y] - ls[y] + 1 : 0));
}

void work() {
	if (shit) return ;
	int k = (m + 1) / 2;
	if (a[k] == 2) {
		int clsz = 0;
		for (int i = 1; i <= k; i++) {
			int l = k - i + 1, r = k + i - 1;
			clean(ls[l], rs[r] - ls[l] + 1 - clsz);
			clsz = rs[r] - ls[l] + 1;
		}
		return ;
	}
	if (Ls[m] >= m / 2) {shit = 1; return ;}
	int lc = -1, rc = -1;
	for (int i = k - 1; i >= 1; i--) if (a[i] == 2) {lc = i; break;}
	for (int i = k + 1; i <= m; i++) if (a[i] == 2) {rc = i; break;}
	if (lc == -1 || rc == -1) {shit = 1; return ;}
	int dis = min(k - lc, rc - k);
	if (k - lc < rc - k) {
		for (int i = 1; i <= dis; i++) lnk_clean(rc - i + 1, rc + i - 1);
		int tmp = rs[rc + dis - 1] - ls[rc - dis + 1] + 1;
		rs[rc - dis] = rs[rc + dis] - tmp;
		for (int i = rc + dis + 1; i <= m; i++) ls[i - dis * 2] = ls[i] - tmp, rs[i - dis * 2] = rs[i] - tmp;
		m -= dis * 2;
	}
	else {
		for (int i = 1; i <= dis; i++) lnk_clean(lc - i + 1, lc + i - 1);
		int tmp = rs[lc + dis - 1] - ls[lc - dis + 1] + 1;
		rs[lc - dis] = rs[lc + dis] - tmp;
		for (int i = lc + dis + 1; i <= m; i++) ls[i - dis * 2] = ls[i] - tmp, rs[i - dis * 2] = rs[i] - tmp;
		m -= dis * 2;
	}
	k = (m + 1) / 2;
	int clsz = 0;
	for (int i = 1; i <= k; i++) {
		int l = k - i + 1, r = k + i - 1;
		clean(ls[l], rs[r] - ls[l] + 1 - clsz);
		clsz = rs[r] - ls[l] + 1;
	}
}

int main() {
	scanf("%d", &n);
	scanf("%s", s + 1);
	
	for (int L = 1, R; L <= n; L = R + 1) {
		R = L; while (R < n && s[R + 1] == s[R]) R++;
		m++; ls[m] = L; rs[m] = R; if (L != R) a[m] = 2; else a[m] = 1;
	}
	
	int num = 0;
	for (int i = 1; i <= m; i++) {
		if (a[i] == 2) Ls[i] = Ls[i - 1], num = 0;
			else {
				num++; Ls[i] = max(Ls[i - 1], num);
			}
	}
	num = 0;
	for (int i = m; i >= 1; i--) {
		if (a[i] == 2) Rs[i] = Rs[i + 1], num = 0;
			else {
				num++; Rs[i] = max(Rs[i + 1], num);
			}
	}
	
	if (m & 1) {work(); write(); return 0;}
	
	int bk = -1;
	for (int i = 1; i <= m; i += 2)
		if ((a[(i + 1) / 2] == 2 || Ls[i] < i / 2) && (a[(m + i + 1) / 2] == 2 || Rs[i + 1] < (m - i) / 2)) {
			bk = i; break;
		}
	if (bk == -1) shit = 1;
	int tmp = m, tmp_d = rs[bk];
	m = bk; work(); m = tmp;
	for (int i = bk + 1; i <= m; i++) ls[i - bk] = ls[i] - tmp_d, rs[i - bk] = rs[i] - tmp_d, a[i - bk] = a[i];
	m = m - bk; Ls[m] = Rs[bk + 1]; work(); m = tmp;
	write();
	
	return 0;
}