LGP7202 [COCI2019-2020#1] Trobojnica

参考了各路题解。

首先如果一个多边形全部都是一种颜色显然无法分割。

又，我们注意到 $1 \oplus 2 \oplus 3 = 0$。

故一个符合条件的三角形三边颜色异或和为 $0$。

故一个多边形的颜色异或和必须为 $0$ 才能有解。

让我们考虑一次在多边形上分割三角形操作带来的影响，这会使得两种不同颜色的边数量减少 $1$，另一种颜色的边数量增加 $1$，不影响颜色异或和。

考虑我们每一次都只选择两条颜色不一样且数量都不为 $1$ 的边合并。

首先这是一定可以做到的（比较显然）。

然后因为这样分割我们一定不会使得多边形的边都变成同一种颜色（比较显然），又颜色异或和恒为 $0$，所以我们一定可以分割这个多边形。

我们考虑不断查找第一个符合上述合并条件的边，然后与其下一条边合并。

合并完之后，它可能和它的下一条边可以继续合并，所以在上一次操作的位置继续找下去即可。

这样扫在第一次的时候可能有些边无法合并，那么在第二轮扫的时候必定可以合并，否则它是永远无法合并的，这与我们的题设矛盾。

所以一条边最多只会被扫描两次，时间复杂度是 $O(n)$ 的。

可以结合代码思考。

#include<bits/stdc++.h>
using namespace std;
const int maxn=2e5;
int n;
char s[maxn+5];
int cnt[5],sum;
int nxt[maxn+5],col[maxn+5];
int ansx[maxn+5],ansy[maxn+5],ansc[maxn+5];
signed main(){
	scanf("%d",&n);
	scanf("%s",s);
	for(int i=0;i<n;i++){
		nxt[i]=(i+1)%n;
		col[i]=s[i]-'0';
		cnt[col[i]]++;
		sum^=col[i];
	}
	int x=0,y;
	if(cnt[1]==n||cnt[2]==n||cnt[3]==n||sum){
		puts("NE");
		return 0;
	}
	for(int t=0;t<n-3;t++){
		for(;col[x]==col[nxt[x]]
			||(cnt[col[x]]==1&&cnt[col[nxt[x]]]==1);x=nxt[x]);
		y=nxt[x];
		cnt[col[x]]--;
		cnt[col[y]]--;
		cnt[col[x]^col[y]]++;
		nxt[x]=nxt[y];
		col[x]=col[x]^col[y];
		ansx[t]=x;
		ansy[t]=nxt[x];
		ansc[t]=col[x];
	}
	puts("DA");
	for(int t=0;t<n-3;t++)
		printf("%d %d %d\n",ansx[t]+1,ansy[t]+1,ansc[t]);
	return 0;
}