题解 P6185 【[NOI Online 提高组]序列（民间数据）】

· · 题解

思路

大家都太强了……看了半天都是图论大神。

我只好写一个蒟蒻的做法，小小的 带权并查集。

我是这么想哒，考虑 i,j 和 j,k 两种操作，能够给 i,k 带来什么：

所以说，对于这种三个点的关系，其中一个作为中介的时候，如果 i,j 和 j,k 的状态不同，就可以做到同时增加；否则得到一增一减的结果。

于是，把同时增加设为1、一增一减设为0，连边之后，二者的关系为路径的异或和。而且，这也是自洽的，因为自己到自己的长度是0，相当于增加了又减少，没有问题。

然后就有了带权并查集的思路，因为 所有的操作可以等价于直接与并查集的根操作，毕竟是异或和，dis(a,rt)\oplus dis(b,rt)=dis(a,b) 嘛，所以 a,b 本来就可以选择 root 作为中介点。

加出来一个环怎么办？如果这会导致一个长度为1的环，那么在根节点上打一个标记，表示“可以自行消化偶数权值”。否则，没什么鸟用，因为每个节点本身就有一个隐藏的长度为零的自环。

最后，暴力检查每一个根节点是否达到了要求即可，因为根节点就已经没有人能够跟它操作了，除了自环消化偶数。

我没有打启发式合并，普通的路径压缩，最坏是 \mathcal O(n\log n) 的。还是能过。

却因为没有清空挂掉了。事实上，三道题都因为奇怪的原因挂掉了

代码

实现的时候，可以只存储 b_i-a_i ，也就是 a_i 需要的变化量。

#include <cstdio>
#include <iostream>
#include <vector>
using namespace std;
inline long long readint(){
    long long a = 0; char c = getchar(), f = 1;
    for(; c<'0'||c>'9'; c=getchar())
        if(c == '-') f = -f;
    for(; '0'<=c&&c<='9'; c=getchar())
        a = (a<<3)+(a<<1)+(c^48);
    return a*f;
}
inline void writeint(long long x){
    if(x < 0) putchar('-'), x = -x;
    if(x > 9) writeint(x/10);
    putchar((x%10)^48);
}

# define MB template < typename T >
MB void getMax(T &a,const T &b){ if(a < b) a = b; }
MB void getMin(T &a,const T &b){ if(b < a) a = b; }

const int MaxN = 100005;

int fa[MaxN], val[MaxN];
inline int findSet(int a){
    if(fa[a] == a) return a;
    int root = findSet(fa[a]);
    val[a] ^= val[fa[a]];
    return fa[a] = root;
}
bool win[MaxN]; // 是否有长度为1的自环
void unionSet(int a,int b,int c){
    int x = findSet(a), y = findSet(b);
    int dis = val[a]^c^val[b];
    if(x == y) win[x] = win[x] or dis == 1;
    else{
        fa[x] = y, val[x] = dis;
        win[y] = win[y] or win[x];
    }
}

long long a[MaxN]; int n, m;
int main(){
    // freopen("sequence.in","r",stdin);
    // freopen("sequence.out","w",stdout);
    for(int T=readint(); T; --T){
        n = readint(), m = readint();
        for(int i=1; i<=n; ++i){
            a[i] = readint();
            fa[i] = i, val[i] = 0;
            win[i] = false;
        }
        for(int i=1; i<=n; ++i)
            a[i] = readint()-a[i];
        for(int opt,x; m; --m){
            opt = readint()%2, x = readint();
            unionSet(x,readint(),opt);
        }
        for(int i=1,rt; i<=n; ++i){
            rt = findSet(i);
            if(rt == i) continue;
            if(val[i] == 1) // a[i]-=a[i],a[rt]-=a[i]
                a[rt] -= a[i]; // 权值同时增加a[i] ...
            else a[rt] += a[i]; // ... 需求便减少了
        }
        bool ok = true;
        for(int i=1,rt; i<=n and ok; ++i){
            rt = findSet(i);
            if(rt != i) continue;
            if(win[rt]) a[rt] %= 2;
            if(a[rt] != 0) ok = false;
        }
        if(ok) puts("YES"); else puts("NO");
    }
    return 0;
}

也许是错的——希望有大佬在看出错误之后 心狠手辣地、尖酸刻薄地 指出，受教了！