自动搬运

查看原文

来自洛谷，原作者为

	Ecrade_ 算法竞赛打 APIO，就像，只能度过一个相对失败的人生。

搬运于2025-08-24 22:27:37，当前版本为作者最后更新于2022-10-05 00:16:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

首先，当各边颜色均相同时显然无解。接下来仅考虑存在颜色不同的边的情况。

考虑两条相邻且颜色不同的边，用一条剩余颜色的边与之形成一个三角剖分，可使原 $n$ 边形的剖分问题化归为一个 $n-1$ 边形的剖分问题。

那么可将题意转化为：每次选择两条相邻且颜色不同的边，将其合并为一条剩余颜色的边，直到剩余三条边为止，求一种可行的操作序列。

接下来我们断言，若给出的 $n$ 条边的颜色的异或和为 $0$ 则有解，反之无解。

证明：注意到上述合并操作可用异或表述（如颜色 1 与颜色 3 合并为颜色 2 可视为 1 与 3 合并为它们的异或和，即 2），每次合并后剩余所有边的异或和不变。根据题意，最终剩余三条边的颜色必然是 1,2,3 各一种，它们的异或和为 $0$，故若有解，初始所有边颜色的异或和亦需为 $0$。

下面对满足所有边颜色异或和为 $0$ 的情况进行构造。

我们开一个栈来维护当前未被合并的所有边，先将第一条边压入栈。

记最后一个与第 $n$ 条边颜色不同的边为第 $pos$ 条边。依次遍历 $2\sim pos$ 的每条边，记当前遍历到了第 $i$ 条边，其颜色为 $c_i$。若 $c_i$ 与栈顶边的颜色相同，则将 $i$ 压入栈；否则将 $i$ 不断与栈顶边合并并弹出栈顶边，直到栈空，最后将 $i$ 压入栈。特殊地，当 $i=pos$ 时，我们需要保证最终栈的大小不少于 $2$，即合并的过程中不能将栈弹空。

最终，我们可以证明，所有未被合并的边一定形如 $abcc\dots c$ 或者 $aa\dots abb\dots b$。对于第一种情况，将 $b$ 不断与右边的 $c$ （除了最后一个）合并即可；对于第二种情况，将最右边的 $a$ 不断与 $b$ （除了最后一个）合并，再将其不断与左边的 $a$ （除了第一个）合并即可。

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

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,tp,sum,cur,pos,stk[200009];
char s[200009];
inline ll read(){
	ll s = 0,w = 1;
	char ch = getchar();
	while (ch > '9' || ch < '0'){ if (ch == '-') w = -1; ch = getchar();}
	while (ch <= '9' && ch >= '0') s = (s << 1) + (s << 3) + (ch ^ 48),ch = getchar();
	return s * w;
}
int main(){
	n = read(),scanf("%s",s + 1);
	for (ll i = 1;i <= n;i += 1) sum ^= s[i] - '0';
	if (sum){
		puts("NE");
		return 0;
	}
	for (ll i = n - 1;i >= 1;i -= 1){
		if (s[i] ^ s[i + 1]){
			pos = i;
			break;
		}
	}
	if (!pos){
		puts("NE");
		return 0;
	}
	puts("DA");
	stk[++ tp] = 1,cur = s[1] - '0';
	for (ll i = 2;i <= pos;i += 1){
		if (s[i] - '0' == cur){
			stk[++ tp] = i;
			continue;
		}
		ll tmp = cur;
		cur = s[i] - '0';
		while (tp > (i == pos)){
			cur ^= tmp;
			printf("%lld %lld %lld\n",stk[tp --],i + 1,cur);
		}
		tp += 1;
		if (i == pos && tp == 2) stk[tp] = i;
	}
	for (ll i = pos + 2;i <= n;i += 1){
		cur ^= s[n] - '0';
		printf("%lld %lld %lld\n",stk[tp],i,cur);
	}
	ll tmp = cur ^ (s[n] - '0');
	for (ll i = tp - 1;i >= 2;i -= 1){
		cur ^= tmp;
		printf("%lld %lld %lld\n",stk[i],n,cur);
	}
	return 0;
}