题解：P7759 [COCI 2012/2013 #3] PROCESOR

· · 题解

非常板子的一道题（但是卡空间

题意

你有一个未知序列 a[1\dots n]，你现在知道若干个操作和对应的结果：

求字典序最小的初始序列。

思路

涉及二进制，考虑对于每个二进制位单独考虑。

先不考虑操作一，那么异或操作，相当于告诉了若干对二进制位是否相等。

这启发我们可以把每个数的二进制位看成图上的若干个点，相等的点连边。

但是每个二进制位有 0 和 1 两种取值，所以可以拆点。形式化地，对于 a_i 的二进制第 j 位，建两个点 (i, j, 0) 和 (i, j, 1) 分别表示取值与第 j 位相等，或者等于第 j 位取反。

那么如果两个位置相等，它们取反后也相等。而如果数位 u 和数位 v 不同，则 u = \neg v, \neg u = v，所以可以交叉建边。

而加上操作一也是简单的，直接把循环位移的偏移量记录下来，在操作二建边的时候考虑一下就行了。

现在我们得到一张图，连边表示点权相同，可以用并查集来维护。

考虑判断无解，发现如果 (i, j, 0) 与 (i, j, 1) 在同一个连通分量中，那么肯定无解（显然，一个数位不可能和它取反后相等），而其他情况一定有解。

考虑贪心构造最小字典序，肯定从 1 枚举到 n，再贪心的让最高位尽量为 0。考虑一个数位 (i, j)，如果该数位的连通分量中的其他数位都没有被访问过，那么该位置一定可以为 0，同时，将 (i, j, 0) 和 (i, j, 1) 所在的连通分量标记一下，表示这个连通分量已经被赋值过了，下次访问到连通分量中的点，只能取某个固定的值。

注意要用 unsigned int

代码

#include <bits/stdc++.h>
using namespace std;

typedef unsigned u32;
// #define int u32

const int maxN = int(1e5+7);
const int V = maxN*64;

int n, e;
u32 ans[maxN];
int rot[maxN];
int fa[V];

int find(int x) { return fa[x] <= 0 ? x : fa[x] = find(fa[x]); }

void merge(int u, int v)
{
    if (find(u) == find(v))
        return;
    fa[find(u)] = find(v);
}

int main()
{
    scanf("%d%d", &n, &e);
    auto id = [=](int n, int p, int b)
    {
        int x = (n-1)*32+p+1;
        if (b)
            x += ::n*32;
        return x;
    };
    for (int cas = 1; cas <= e; ++cas)
    {
        int opt, k, l;
        scanf("%d%d%d", &opt, &k, &l);
        if (opt == 1)
        {
            rot[k] = (rot[k] + l) % 32;
        }
        if (opt == 2)
        {
            u32 res;
            scanf("%u", &res);
            for (int i = 0; i < 32; ++i)
            {
                int val = (res>>i)&1;
                if (!val)
                {
                    merge(id(k, (i+rot[k])%32, 0), id(l, (i+rot[l])%32, 0));
                    merge(id(k, (i+rot[k])%32, 1), id(l, (i+rot[l])%32, 1));
                }
                else
                {
                    merge(id(k, (i+rot[k])%32, 0), id(l, (i+rot[l])%32, 1));
                    merge(id(k, (i+rot[k])%32, 1), id(l, (i+rot[l])%32, 0));
                }
            }
        }
    }
    bool flag = false;
    for (int i = 1; i <= n; ++i)
    {
        for (int j = 0; j < 32; ++j)
        {
            if (find(id(i, j, 0)) == find(id(i, j, 1)))
                flag = true;
        }
        assert(id(i, 31, 0) <= n*32);
    }
    if (flag)
    {
        printf("-1\n");
    }
    else
    {
        for (int i = 1; i <= n; ++i)
        {
            for (int j = 31; ~j; --j)
            {
                if (fa[find(id(i, j, 0))] == 0)
                {
                    fa[find(id(i, j, 0))] = -1;
                    fa[find(id(i, j, 1))] = -2;
                }
                else
                {
                    if (fa[find(id(i, j, 0))] == -2)
                    {
                        ans[i] += (1u<<j);
                    }
                }
            }
        }
        for (int i = 1; i <= n; ++i)
            printf("%u%c", ans[i], " \n"[i == n]);
    }
    return 0;
}