参考了各路题解。
首先如果一个多边形全部都是一种颜色显然无法分割。
又，我们注意到 $1 \oplus 2 \oplus 3 = 0$。
故一个符合条件的三角形三边颜色异或和为 $0$。
故一个多边形的颜色异或和必须为 $0$ 才能有解。
让我们考虑一次在多边形上分割三角形操作带来的影响，这会使得两种不同颜色的边数量减少 $1$，另一种颜色的边数量增加 $1$，不影响颜色异或和。
考虑我们每一次都只选择两条颜色不一样且数量都不为 $1$ 的边合并。
首先这是一定可以做到的（比较显然）。
然后因为这样分割我们一定不会使得多边形的边都变成同一种颜色（比较显然），又颜色异或和恒为 $0$，所以我们一定可以分割这个多边形。
我们考虑不断查找第一个符合上述合并条件的边，然后与其下一条边合并。
合并完之后，它可能和它的下一条边可以继续合并，所以在上一次操作的位置继续找下去即可。
这样扫在第一次的时候可能有些边无法合并，那么在第二轮扫的时候必定可以合并，否则它是永远无法合并的，这与我们的题设矛盾。
所以一条边最多只会被扫描两次，时间复杂度是 $O(n)$ 的。
可以结合代码思考。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| #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;
}
|