「FZOI」 Round #41 (Div. 0) – 解题报告

A – 吴国十分危险

他妈看错题，啊，心态崩了。（虽然看对了都不一定能推出结论）。

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

using namespace std;

const int MAX_N = 110;

int T, n, k, siz[MAX_N];
vector<int> G[MAX_N];
bool flag;

void dfs(int u, int fa)
{
    siz[u] = 1;
    int leaf = 0;
    for (int v : G[u])
        if (v != fa)
        {
            dfs(v, u), siz[u] += siz[v];
            if (siz[v] == 1)
                leaf++;
        }
    if (leaf >= 2)
        flag = true;
}

void cut(int u, int fa)
{
    siz[u] = 1;
    for (int v : G[u])
        if (v != fa)
        {
            cut(v, u);
            if (siz[v] == 2)
                siz[v] = 0, k--;
            siz[u] += siz[v];
        }
    if (siz[u] > 2)
        flag = true;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d%d", &n, &k), flag = false;
        for (int i = 1; i <= n; i++)
            G[i].clear(), siz[i] = 0;
        for (int i = 1, u, v; i <= n - 1; i++)
            scanf("%d%d", &u, &v), G[u].push_back(v), G[v].push_back(u);
        if (n % 2 == 1)
        {
            puts("Alice");
            continue;
        }
        if (n == 2)
        {
            puts("Bob");
            continue;
        }
        dfs(1, 0), cut(1, 0);
        if (flag || k < 0 || siz[1] != 2)
            puts("Alice");
        else
            puts("Bob");
    }
    return 0;
}

B – 董先生的钦定

先不考虑剔除空集的情况，对于每一个非空集合而言，其补集和该集合本身至少有一个数量和大于全集的一半，知道这个之后就发现这个东西一一对应，所以对于没有空集的情况而言，答案就是 \( \frac{S}{2} \)，其中 \(S\) 是全集和。对于没有空集的情况，那肯定稍大，考虑 DP 出来然后找附近的即可。

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

using namespace std;

const int MAX_N = 2020;

int n, ai[MAX_N], m;
bitset<MAX_N * MAX_N> f;

int main()
{
    scanf("%d", &n), f[0] = 1;
    for (int i = 1; i <= n; i++)
        scanf("%d", &ai[i]), m += ai[i], f = f | (f << ai[i]);
    m = (m + 1) >> 1;
    for (int i = 1; i <= n * n; i++)
        if (i >= m && f[i])
            printf("%d\n", i), exit(0);
    return 0;
}

C – 超越潜能

我们可以考虑维护前缀和和后缀和。对于指针向右的情况，我们只需要维护从左到右的前缀和和贡献和即可；对于指针向左的情况，我们需要维护后缀和和线段树，我们可以通过后缀和和前缀和来算这个 \(0\) 的窗口位置，用线段树来维护一条条线段，询问时只需要找到 \(0\) 的绝对位置。

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

using namespace std;

const int MAX_N = 3e5 + 200, INF = 1e9;

int n, m, ptot;
char cmdlet[10];

struct node
{
    int lson, rson, tag;
} nodes[MAX_N * 120];

#define mid ((l + r) >> 1)

int update(int ql, int qr, int l, int r, int pre)
{
    int p = ++ptot;
    nodes[p] = nodes[pre];
    if (ql <= l && r <= qr)
        return nodes[p].tag++, p;
    if (ql <= mid)
        nodes[p].lson = update(ql, qr, l, mid, nodes[pre].lson);
    if (mid < qr)
        nodes[p].rson = update(ql, qr, mid + 1, r, nodes[pre].rson);
    return p;
}

int query(int qx, int l, int r, int p)
{
    if (p == 0)
        return 0;
    int ret = nodes[p].tag;
    if (l == r)
        return ret;
    if (qx <= mid)
        ret += query(qx, l, mid, nodes[p].lson);
    else
        ret += query(qx, mid + 1, r, nodes[p].rson);
    return ret;
}

struct axisManager
{

    int ptr, org[MAX_N], roots[MAX_N], pre[MAX_N], pre_prod[MAX_N], suf[MAX_N];

    void moveLeft()
    {
        if (ptr == 1)
            return;
        roots[ptr] = roots[ptr + 1], suf[ptr] = suf[ptr + 1] + org[ptr];
        int lft = min(suf[ptr] - org[ptr], suf[ptr]), rig = max(suf[ptr] - org[ptr], suf[ptr]);
        roots[ptr] = update(lft, rig, -INF, INF, roots[ptr]), ptr--;
    }

    void moveRight()
    {
        if (ptr == n)
            return;
        ptr++;
        pre[ptr] = pre[ptr - 1] + org[ptr];
        pre_prod[ptr] = pre_prod[ptr - 1] + ((pre[ptr] > 0) ^ (pre[ptr - 1] > 0));
    }

    void build()
    {
        ptr = 0, org[0] = pre[0] = 1;
        for (int i = 1; i <= n; i++)
            moveRight();
        for (int i = n; i > 1; i--)
            moveLeft();
    }

    void updateOnAxis(int d)
    {
        org[ptr] = d, pre[ptr] = pre[ptr - 1] + org[ptr];
        pre_prod[ptr] = pre_prod[ptr - 1] + ((pre[ptr] > 0) ^ (pre[ptr - 1] > 0));
    }

    int queryOnAxis() { return query(pre[ptr] + suf[ptr + 1], -INF, INF, roots[ptr + 1]) + pre_prod[ptr]; }

} dr[2];

int main()
{
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &dr[0].org[i], &dr[1].org[i]);
    dr[0].build(), dr[1].build(), scanf("%d", &m);
    while (m--)
    {
        scanf("%s", cmdlet + 1);
        if (cmdlet[1] == 'B')
            dr[0].moveLeft(), dr[1].moveLeft();
        else if (cmdlet[1] == 'C')
        {
            int nx, ny;
            scanf("%d%d", &nx, &ny);
            dr[0].updateOnAxis(nx), dr[1].updateOnAxis(ny);
        }
        else if (cmdlet[1] == 'F')
            dr[0].moveRight(), dr[1].moveRight();
        else if (cmdlet[1] == 'Q')
            printf("%d\n", dr[0].queryOnAxis() + dr[1].queryOnAxis());
    }
    return 0;
}