AtCoder Grand Contest 045 – 解题报告

A – Xor Battle

感觉有点傻逼啊。

对于 0 而言，我们只需要最后的答案为 0 即可。那么，我们从后往前进行维护，维护 \(0\) 位置上权值组合而成的线性基，然后每次到 \(1\) 位置的时候就在里面查即可，如果没查到，那么对于 \(1\) 而言，后面的 \(0\) 并不足以抵消该操作，所以可以判 \(1\) 获胜，亦而反之。

// A.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 220;

typedef long long ll;

int T, n;
ll base[MAX_N], ai[MAX_N];
char str[MAX_N];

void insert(ll x)
{
    for (int i = 62; i >= 0; i--)
        if (x & (1LL << i))
        {
            if (base[i] == 0)
            {
                base[i] ^= x;
                break;
            }
            x ^= base[i];
        }
}

bool query(ll x)
{
    for (int i = 62; i >= 0; i--)
        if (x & (1LL << i))
            x ^= base[i];
    return x == 0;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%lld", &ai[i]);
        scanf("%s", str + 1);
        for (int i = 0; i <= 62; i++)
            base[i] = 0;
        bool flag = false;
        for (int i = n; i >= 1; i--)
        {
            if (str[i] == '0')
                insert(ai[i]);
            else if (!query(ai[i]))
            {
                flag = true;
                break;
            }
        }
        puts(flag ? "1" : "0");
    }
    return 0;
}

B – 01 Unbalanced

为啥我觉得这个题也很傻逼啊，但是就是没想出来…日了。

本质上是求一个给 ? 的赋权方案，使得前缀和极差最小。那么我们可以套路的去枚举整个前缀和的最小值，然后在这个最小值上进行调整。枚举 \(M\) 为最小值，然后我们可以用一个后缀最小值来判断调整 ? 会不会让后面的最小元素越界：也就是比最小值还小。这样是 \(\Theta(n^2)\) 的。

不过可以思考到：我们这个东西是求极差，所以我们的最小值不一定要很小，发现在全局最小值的附近就可以达到效果。（极差是浮动的，设全局最小值 \(X\)，那么答案从 \(X – 2\) 往下走，就会有 \(-1\) 或 \(1\) 没法做到缩小极差的作用）

// B.cpp
#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 1e6 + 200;

int n, pre[MAX_N], suf[MAX_N], ans = 0x7fffffff;
char str[MAX_N];

void prepare()
{
    for (int i = 1; i <= n; i++)
        pre[i] = pre[i - 1] + (str[i] == '0' ? -1 : 1);
    suf[n + 1] = MAX_N;
    for (int i = n; i >= 0; i--)
        suf[i] = min(suf[i + 1], pre[i]);
}

void solve(int lbound)
{
    int bias = 0, upper = 0;
    for (int i = 1; i <= n; i++)
    {
        if (str[i] == '?' && suf[i] - 2 - bias >= lbound)
            bias += 2;
        pre[i] -= bias, upper = max(upper, pre[i]);
    }
    ans = min(ans, upper - lbound);
}

int main()
{
    scanf("%s", str + 1), n = strlen(str + 1);
    prepare(), solve(suf[0]);
    prepare(), solve(suf[0] - 1);
    printf("%d\n", ans);
    return 0;
}