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;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注