[COCI2019-2020#1] Trobojnica 题解

· · 题解

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

考虑两条相邻且颜色不同的边，用一条剩余颜色的边与之形成一个三角剖分，可使原 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;
}