A – 奇妙的棋盘

一定要思考，不能想当然。这句话是说给我听的。

把连通块连边，每一次 BFS 扩展就算做一次点击，然后\(O(n^2)\)确定路径长度，再按奇偶性判断就行了。

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

using namespace std;

const int MAX_N = 75, MAX_P = 4910, INF = 0x3f3f3f3f;

int n, m, mem[MAX_P], head[MAX_P], current, tot, dep[MAX_P];
char opt[MAX_N][MAX_N];
bool mp[MAX_P][MAX_P], vis[MAX_P];

struct edge
{
    int to, nxt;
} edges[MAX_P << 3];

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

int getId(int x, int y) { return (x - 1) * m + y; }

int find(int x) { return x == mem[x] ? x : mem[x] = find(mem[x]); }

int main()
{
    memset(head, -1, sizeof(head));
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++)
        scanf("%s", opt[i] + 1);
    for (int i = 1; i <= n * m; i++)
        mem[i] = i;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (i > 1 && opt[i][j] == opt[i - 1][j])
                mem[find(getId(i - 1, j))] = mem[find(getId(i, j))];
            if (j > 1 && opt[i][j] == opt[i][j - 1])
                mem[find(getId(i, j - 1))] = mem[find(getId(i, j))];
        }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (vis[find(getId(i, j))] == false)
                vis[find(getId(i, j))] = true, tot++;
            if (i > 1 && opt[i][j] != opt[i - 1][j] && !mp[find(getId(i, j))][find(getId(i - 1, j))])
                addpath(find(getId(i, j)), find(getId(i - 1, j))), addpath(find(getId(i - 1, j)), find(getId(i, j)));
            if (j > 1 && opt[i][j] != opt[i][j - 1] && !mp[find(getId(i, j))][find(getId(i, j - 1))])
                addpath(find(getId(i, j)), find(getId(i, j - 1))), addpath(find(getId(i, j - 1)), find(getId(i, j)));
        }
    int gans = INF;
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            if (find(getId(i, j)) != getId(i, j))
                continue;
            memset(dep, 0x3f, sizeof(dep));
            int id = getId(i, j), ans = 0;
            queue<int> q;
            q.push(id), dep[id] = 0;
            while (!q.empty())
            {
                int u = q.front();
                q.pop();
                for (int i = head[u]; i != -1; i = edges[i].nxt)
                    if (dep[edges[i].to] == INF)
                        q.push(edges[i].to), dep[edges[i].to] = dep[u] + 1, ans = max(ans, dep[edges[i].to]);
            }
            if (((ans & 1) && opt[i][j] == 'W') || ((ans & 1) == 0 && opt[i][j] == 'B'))
                ans++;
            gans = min(gans, ans);
        }
    printf("%d", gans);
    return 0;
}

B – 生命

曼哈顿距离转切比雪夫距离板子题。

转换好坐标之后，搞二维前缀和即可。

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

using namespace std;

const int MAX_N = 2300, MAX_P = 500010, DOM = 1010;

int n, k, q, lb, ub, dist[MAX_N][MAX_N], pts[MAX_N * MAX_N][2];

inline int getId(int x, int y) { return (x - 1) * n + y; }

int main()
{
    scanf("%d%d%d", &n, &k, &q);
    for (int i = 1, x, y; i <= k; i++)
        scanf("%d%d", &x, &y), dist[x + y][x - y + n]++;
    for (int x = 1; x <= n; x++)
        for (int y = 1; y <= n; y++)
            pts[getId(x, y)][0] = x + y, pts[getId(x, y)][1] = x - y + n;
    for (int i = 1; i <= 2 * n; i++)
        for (int j = 1; j <= 2 * n; j++)
            dist[i][j] += dist[i - 1][j] + dist[i][j - 1] - dist[i - 1][j - 1];
    for (int s, i = 1; i <= q; i++)
    {
        scanf("%d", &s);
        if (s > n + 1)
            printf("%d\n", k);
        else
        {
            int ans = 0;
            for (int i = 0, x0, y0, x1, y1; i <= getId(n, n); i++)
            {
                x0 = max(pts[i][0] - s - 1, 0), y0 = max(pts[i][1] - s - 1, 0);
                x1 = min(pts[i][0] + s, n << 1), y1 = min(pts[i][1] + s, n << 1);
                ans = max(ans, dist[x1][y1] - dist[x0][y1] - dist[x1][y0] + dist[x0][y0]);
            }
            printf("%d\n", ans);
        }
    }
    return 0;
}

C – 死亡之树

这道题还是很好的。

考虑设计状态\(dp[vertexSet][leaveSet]\)，总结点集合和叶子结点集合。每次转移的时候，都找一个新节点接到旧节点上。为了防止重复，我们保证新节点编号比旧节点大就行了。很好的一道题。

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

using namespace std;

const int MAX_N = 11;

int mp[MAX_N][MAX_N], dp[1 << MAX_N][1 << MAX_N], n, m, k;

int main()
{
    scanf("%d%d%d", &n, &m, &k);
    for (int i = 1, x, y; i <= m; i++)
        scanf("%d%d", &x, &y), mp[x - 1][y - 1] = mp[y - 1][x - 1] = 1;
    for (int i = 0; i < n; i++)
        for (int j = i + 1; j < n; j++)
            if (mp[i][j])
                dp[(1 << i) | (1 << j)][(1 << i) | (1 << j)] = 1;
    for (int i = 1; i < (1 << n); i++)
        for (int j = 1; j < (1 << n); j++)
            if ((i & j) == j && dp[i][j] > 0 && __builtin_popcount(j) <= k)
                for (int p = 0; p < n; p++)
                    if ((i & (1 << p)) == 0)
                        for (int to = 0; to < n; to++)
                            if (mp[p][to] && (i & (1 << to)) && (j & (~(1 << to))) < (1 << p))
                                dp[i ^ (1 << p)][j & (~(1 << to)) ^ (1 << p)] += dp[i][j];
    int ans = 0;
    for (int stat = 1; stat < (1 << n); stat++)
        if (__builtin_popcount(stat) == k)
            ans += dp[(1 << n) - 1][stat];
    printf("%d", ans);
    return 0;
}