ZR1541 小W与屠龙游戏

zrzring 2020-11-18 PM 14℃ 0条

你有n对石子堆,每对石子堆包含两个石子数为$s_i$的石子堆,且每对石子堆有一个权值$w_i$,现在你要选择一些对的石子堆使得下述游戏你必胜且使得选择的石子堆权值和最大

你为后手,你和boss轮流从至多两堆石子堆取任意数量的石子,不能取石子的一方判负

双方轮流从$n$堆石子中取$x$堆石子的任意数量,把每一堆的数量用二进制数表示,对应位相加并对$x+1$取模,每一位都为$0$即为先手必败状态

证明其正确性,考虑一个状态是必败状态当且仅当它的所有后继状态均为必胜状态,那么如果堆石子数满足上面的性质的话,应该是它的后继状态不会满足这个性质,才使命题正确

如果我们要对这$x$堆二进制下某一位集体$-1$的话,是不会在$x+1$取模下继续为$0$的,但是对于该位如果对某些堆$-1$并对某些堆$+1$的话,在更高的位是一定会被减的(NIM游戏只能“取”),也就是我们一定会存在一个极多$-1$的位且该位置不会出现加法的,而这个极多$-1$的位置不可能达到减去$x+1$,于是他的后继状态不可能有满足上述性质的状态

因为权值不能拆,所以每对石子堆是一个整体,上述引出本体的形式化解决方法

把所有石子堆的二进制看成向量,设每对石子堆选取$x_i \in \{0, 1, 2\}$堆石子,那么我们要求一组$x_i$满足以下条件即可

$$ \sum x_ia_i \not= 0 $$

线性基即可解决

#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <queue>
using namespace std;
void file() {
    freopen("std.in", "r", stdin);
    freopen("wa.out", "w", stdout);
}
const int N = 1e6 + 10, inf = 1e9;
inline int read() {
    bool sym = 0; int res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}
inline long long lread() {
    bool sym = 0; long long res = 0; char ch = getchar();
    while (!isdigit(ch)) sym |= (ch == '-'), ch = getchar();
    while (isdigit(ch)) res = (res << 3) + (res << 1) + (ch ^ 48), ch = getchar();
    return sym ? -res : res;
}
struct NODE {
    long long p1, p2; int val;
} a[N];
NODE operator + (const NODE a, const NODE b) {
    long long ra = ~(a.p1 | a.p2), rb = ~(b.p1 | b.p2);
    return (NODE){a.p2 & b.p2 | a.p1 & rb | ra & b.p1, a.p1 & b.p1 | a.p2 & rb | ra & b.p2, a.val};
}
NODE operator - (const NODE a, const NODE b) {
    long long ra = ~(a.p1 | a.p2), rb = ~(b.p1 | b.p2);
    return (NODE){a.p2 & b.p1 | a.p1 & rb | ra & b.p2, a.p1 & b.p2 | a.p2 & rb | ra & b.p1, a.val};
}
int n, m;
long long ans;
void ins(NODE x) {
    for (int i = 60; i >= 0; i--) {
        if (x.p1 >> i & 1 | x.p2 >> i & 1) {
            if (!a[i].val) {
                ans += x.val; a[i] = x; return;
            }
            if (x.val > a[i].val) {
                ans += x.val - a[i].val; swap(a[i], x);
            }
            if ((x.p1 >> i & 1) & (a[i].p1 >> i & 1) | (x.p2 >> i & 1) & (a[i].p2 >> i & 1)) {
                x = x - a[i];
            } else {
                x = x + a[i];
            }
        }
    }
}
int main() {
    n = read();
    for (int i = 1; i <= n; i++) {
        long long x = lread() ^ ans; int y = read();
        ins((NODE){x, 0, y}); printf("%lld\n", ans);
    }
    return 0;
}

评论


您还没有登录呦


登录 注册
Title - Artist
0:00