省选测试43

A 石子游戏

题目大意 ： 俩人做nim游戏，删去一些堆的石子，问最多剩下多少堆石子和使的后手胜利

• nim游戏里，如果所有堆的石子数异或和为0后手就胜利，所以就找到最少的堆数可以使异或和为sum

• 删去i堆石子可到达的状态异或卷积删去j堆石子可到达的状态就是删去i+j堆石子可到达的状态

• 而log堆就一定可以达到sum，所以FWTlog次就能得到答案

Code

Show Code

#include <cstdio>

using namespace std;
const int N = 1 << 19;

int read(int x = 0, int f = 1, char c = getchar()) {
    for (; c < '0' || c > '9'; c = getchar()) if (c == '-') f = -1;
    for (; c >='0' && c <='9'; c = getchar()) x = x * 10 + c - '0';
    return x * f;
}

int a[N], b[N], n, s;

void FWT(int *a) {
    for (int d = 1; d < N; d *= 2) {
        for (int i = 0, d2 = d * 2; i < N; i += d2) {
            for (int j = i; j < i + d; ++j) {
                int x = a[j], y = a[j+d];
                a[j] = x + y; a[j+d] = x - y;
            }
        }
    }
}

int main() {
    freopen("nim.in", "r", stdin);
    freopen("nim.out", "w", stdout);
    n = read();
    for (int i = 1; i <= n; ++i) {
        int x = read(); b[x] = 1; s ^= x;
    }
    a[s] = 1; FWT(b);
    while (!a[0] && n--) {
        FWT(a); 
        for (int i = 0; i < N; ++i)
            a[i] = a[i] * b[i];
        FWT(a);
        for (int i = 0; i < N; ++i)
            a[i] = (bool) a[i];
    }
    printf("%d
", n);
    return 0;
}

B 函数 (Unaccepted)

题目大意 ：

Code

Show Code

C 画 (Unaccepted)

题目大意 ：

Code

Show Code