A – 仓鼠的石子游戏

诶嘿题。画了几张图发现只有\(1\)的情况先手必胜，所以考虑多轮交换先后手即可。

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

using namespace std;

const int MAX_N = 1e3 + 200, table[8] = {0, 0, 1, 1, 1, 1, 1, 1};

int T, n, ai[MAX_N];

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++)
            scanf("%d", &ai[i]);
        bool flag = false;
        for (int i = 1; i <= n; i++)
            flag ^= (ai[i] == 1);
        printf(flag ? "rabbit\n" : "hamster\n");
    }
    return 0;
}

B – 乃爱与城市拥挤程度

\(\Theta(n^2)\)很好做，就不说了。

考虑进行换根 DP，把父亲的信息换到儿子，然后再恢复回来。但是太特么难写了，所以还是建议各位用 Up & Down 写（而且那样的写法也确实比较好看）。这个是赛时 80 分代码：

// B.cpp
#include <bits/stdc++.h>
#pragma GCC optimize(2)

using namespace std;

const int MAX_N = 1e5 + 200, MAX_K = 15, mod = 1e9 + 7;

int head[MAX_N], current, n, k, dp[MAX_N][MAX_K], prod[MAX_N][MAX_K];
int ans[MAX_N], ans2[MAX_N], org[MAX_N][MAX_K];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

namespace IO
{
const int MAXSIZE = 1 << 20;
char buf[MAXSIZE], *p1, *p2;
#define gc()                                                                 \
    (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, MAXSIZE, stdin), p1 == p2) \
         ? EOF                                                               \
         : *p1++)
inline int rd()
{
    int x = 0, f = 1;
    char c = gc();
    while (!isdigit(c))
    {
        if (c == '-')
            f = -1;
        c = gc();
    }
    while (isdigit(c))
        x = x * 10 + (c ^ 48), c = gc();
    return x * f;
}
} // namespace IO

int quick_pow(int bas, int tim)
{
    int ret = 1;
    while (tim)
    {
        if (tim & 1)
            ret = 1LL * ret * bas % mod;
        bas = 1LL * bas * bas % mod;
        tim >>= 1;
    }
    return ret;
}

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

void build_prod(int u, int fa)
{
    prod[u][0] = dp[u][0] % mod;
    for (int i = 1; i <= k; i++)
        prod[u][i] = (1LL * prod[u][i - 1] + 1LL * dp[u][i]) % mod;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
            for (int j = 1; j <= k; j++)
                prod[u][j] = (1LL * prod[u][j] * prod[edges[i].to][j - 1] % mod);
}

void dfs(int u, int fa)
{
    dp[u][0] = 1;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
        {
            dfs(edges[i].to, u);
            for (int j = 1; j <= k; j++)
                dp[u][j] += dp[edges[i].to][j - 1];
        }
    // get the prod;
    build_prod(u, fa);
}

void redfs(int u, int fa)
{
    // collecting data;
    for (int i = 0; i <= k; i++)
        ans[u] += dp[u][i];
    build_prod(u, 0);
    ans2[u] = prod[u][k];
    // to change the root;
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (edges[i].to != fa)
        {
            // make things ready for the subtree;
            for (int j = 1; j <= k; j++)
                dp[u][j] -= dp[edges[i].to][j - 1];
            for (int j = 1; j <= k; j++)
                dp[edges[i].to][j] += dp[u][j - 1];

            build_prod(u, edges[i].to);

            redfs(edges[i].to, u);

            for (int j = 1; j <= k; j++)
                dp[edges[i].to][j] -= dp[u][j - 1];
            for (int j = 1; j <= k; j++)
                dp[u][j] += dp[edges[i].to][j - 1];

            build_prod(edges[i].to, u);
            build_prod(u, 0);
            // rec on myself;
            for (int j = 1; j <= k; j++)
                prod[u][j] = 1LL * prod[u][j] * prod[edges[i].to][j - 1] % mod;
        }
}

int main()
{
    memset(head, -1, sizeof(head));
    n = IO::rd(), k = IO::rd();
    for (int i = 1, u, v; i <= n - 1; i++)
        u = IO::rd(), v = IO::rd(), addpath(u, v), addpath(v, u);
    dfs(1, 0), redfs(1, 0);
    for (int i = 1; i <= n; i++)
        printf("%d ", ans[i]);
    puts("");
    for (int i = 1; i <= n; i++)
        printf("%d ", ans2[i]);
    puts("");
    return 0;
}

C – 小w的魔术扑克

看来要好好复习下二分图。

可以考虑建一个二分图，左部为牌面，右部为牌的编号。见图方式见代码：这样建图，利用了一个性质，就是顺子都是一大块极大连通块，所有的顺子都是极大连通块的子集；从右端点做匈牙利可以匹配出最大可以匹配的部分，然后发现如果没法匹配那么上次到的左边必须放弃：因为与上一个可以连通的部分断开了。

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

using namespace std;

const int MAX_N = 2e5 + 200;

int head[MAX_N], current, n, k, q, vis[MAX_N], pre[MAX_N], lft[MAX_N], ncnt, matching[MAX_N];

struct edge
{
    int to, nxt;
} edges[MAX_N << 1];

void addpath(int src, int dst)
{
    edges[current].to = dst, edges[current].nxt = head[src];
    head[src] = current++;
}

bool hungery(int u, int org)
{
    for (int i = head[u]; i != -1; i = edges[i].nxt)
        if (vis[edges[i].to] != org)
        {
            vis[edges[i].to] = org;
            if (!matching[edges[i].to] || hungery(matching[edges[i].to], org))
            {
                matching[edges[i].to] = u, pre[u] = edges[i].to;
                return true;
            }
        }
    return false;
}

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &k);
    for (int i = 1, u, v; i <= k; i++)
    {
        scanf("%d%d", &u, &v);
        addpath(u, i + n), addpath(i + n, u);
        addpath(v, i + n), addpath(i + n, v);
    }
    int lcur = 1;
    for (int i = 1; i <= n; i++)
    {
        // fine the leftmost point to pair a conti;
        while (!hungery(i, ++ncnt) && lcur <= i)
            matching[pre[lcur]] = false, lcur++;
        lft[i] = lcur;
    }
    scanf("%d", &q);
    while (q--)
    {
        int l, r;
        scanf("%d%d", &l, &r);
        if (lft[r] <= l)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}