A - Are you ready for it?

本套试题除第 $6$ 题和第 $10$ 题外均出自 CCF NOI 2024 笔试题库。

'1': A
'2': D
'3': B
'4': B
'5': C
'6':
  - B
  - C
'7':
  - A
  - B
'8': '10101011'
'9': '0'
'10': cq_irritater

B - Sleeping Bear's Honey 1

直接从 B 位置开始 Floodfill 即可。如果 Floodfill 到了 L 位置，那么答案为 Yes，否则为 No。

#include <bits/stdc++.h>
using namespace std;
const int K = 1000 + 12;
char x[K][K];
int main()
{
	freopen("honey1.in", "r", stdin);
	freopen("honey1.out", "w", stdout);
	int T;
	cin >> T;
	while (T--)
	{
		int k, sx, sy;
		cin >> k;
		for (int i = 1; i <= k; i++)
			for (int j = 1; j <= k; j++)
			{
				cin >> x[i][j];
				if (x[i][j] == 'B') sx = i, sy = j;
			}
		for (int i = 0; i <= k + 1; i++)
			x[0][i] = x[i][0] = x[i][k + 1] = x[k + 1][i] = 'X';
		queue<pair<int, int> > q;
		q.push(make_pair(sx, sy));
		x[sx][sy] = 'X';
		bool ok = false;
		while (!q.empty())
		{
			pair<int, int> u = q.front();
			q.pop();
			if (x[u.first][u.second + 1] == 'L')
			{
				ok = true;
				puts("Yes");
				break;
			}
			if (x[u.first][u.second + 1] != 'X')
			{
				x[u.first][u.second + 1] = 'X';
				q.push(make_pair(u.first, u.second + 1));
			}
			if (x[u.first][u.second - 1] == 'L')
			{
				ok = true;
				puts("Yes");
				break;
			}
			if (x[u.first][u.second - 1] != 'X')
			{
				x[u.first][u.second - 1] = 'X';
				q.push(make_pair(u.first, u.second - 1));
			}
			if (x[u.first + 1][u.second] == 'L')
			{
				ok = true;
				puts("Yes");
				break;
			}
			if (x[u.first + 1][u.second] != 'X')
			{
				x[u.first + 1][u.second] = 'X';
				q.push(make_pair(u.first + 1, u.second));
			}
			if (x[u.first - 1][u.second] == 'L')
			{
				ok = true;
				puts("Yes");
				break;
			}
			if (x[u.first - 1][u.second] != 'X')
			{
				x[u.first - 1][u.second] = 'X';
				q.push(make_pair(u.first - 1, u.second));
			}
		}
		if (!ok) puts("No");
	}
	return 0;
}

C - Sleeping Bear's Honey 2

很明显，如果 Sleeping Bear 从 L 的位置开始倒着走，那么它每次可以执行以下操作之一：

• 沿着所面向的方向，向前走一格。
• 沿着所面向的方向，向前走一格，然后右转（顺时针转向）$90^\circ$。
• 也就是说，Sleeping Bear 每次只能直行或右转，不能掉头或左转。

因此，我们可以从 L 的位置开始，将每个位置按照面向的方向拆成四个状态，然后根据上述移动规则像上一题那样 Floodfill 就可以了。

#include <bits/stdc++.h>
using namespace std;
const int K = 1000 + 12;
char x[K][K];
bool y[K][K][4];
struct S
{
	int x;
	int y;
	int w;
};
// 0 - 3: right, left, down, up
int main()
{
	freopen("honey2.in", "r", stdin);
	freopen("honey2.out", "w", stdout);
	int T;
	cin >> T;
	while (T--)
	{
		memset(y, 0, sizeof y);
		int k;
		cin >> k;
		queue<S> q;
		for (int i = 1; i <= k; i++)
			for (int j = 1; j <= k; j++)
			{
				cin >> x[i][j];
				if (x[i][j] == 'B') x[i][j] = 'R';
				if (x[i][j] == 'L')
				{
					for (int w = 0; w <= 3; w++)
					{
						y[i][j][w] = true;
						q.push((S) {i, j, w});
					}
				}
			}
		for (int i = 0; i <= k + 1; i++)
			x[0][i] = x[i][0] = x[i][k + 1] = x[k + 1][i] = 'X';
		while (!q.empty())
		{
			S u = q.front();
			q.pop();
			if (u.w == 0 && x[u.x][u.y + 1] != 'X')
			{
				if (!y[u.x][u.y + 1][0]) q.push((S) {u.x, u.y + 1, 0});
				if (!y[u.x][u.y + 1][2]) q.push((S) {u.x, u.y + 1, 2});
				y[u.x][u.y + 1][0] = y[u.x][u.y + 1][2] = true;
			}
			if (u.w == 1 && x[u.x][u.y - 1] != 'X')
			{
				if (!y[u.x][u.y - 1][1]) q.push((S) {u.x, u.y - 1, 1});
				if (!y[u.x][u.y - 1][3]) q.push((S) {u.x, u.y - 1, 3});
				y[u.x][u.y - 1][1] = y[u.x][u.y - 1][3] = true;
			}
			if (u.w == 2 && x[u.x + 1][u.y] != 'X')
			{
				if (!y[u.x + 1][u.y][2]) q.push((S) {u.x + 1, u.y, 2});
				if (!y[u.x + 1][u.y][1]) q.push((S) {u.x + 1, u.y, 1});
				y[u.x + 1][u.y][2] = y[u.x + 1][u.y][1] = true;
			}
			if (u.w == 3 && x[u.x - 1][u.y] != 'X')
			{
				if (!y[u.x - 1][u.y][3]) q.push((S) {u.x - 1, u.y, 3});
				if (!y[u.x - 1][u.y][0]) q.push((S) {u.x - 1, u.y, 0});
				y[u.x - 1][u.y][3] = y[u.x - 1][u.y][0] = true;
			}
		}
		for (int i = 1; i <= k; i++)
			for (int j = 1; j <= k; j++)
			{
				x[i][j] = 'X';
				for (int w = 0; w <= 3; w++)
					if (y[i][j][w]) x[i][j] = 'L';
			}
		for (int i = 1; i <= k; i++)
		{
			for (int j = 1; j <= k; j++)
				cout << x[i][j];
			cout << endl;
		}
	}
	return 0;
}

D - Sleeping Bear's Honey 3

随着 $y$ 的值从 $0$ 增大到 $k^2-1$，格子与格子之间一共连上了 $2k(k-1)$ 条边，而这可以看成 $2k(k-1)$ 次加边操作。

在开始处理询问前，我们可以用并查集将 $2k(k-1)$ 次加边操作完整地维护一遍，并对每 $k$ 次操作分块。在每个块中，我们需要完整地保存此时并查集的状态，以及此时每个 $x$ 的取值对应的答案。

在并查集中，我们可以在每个连通块的根部记录该连通块的大小以及该连通块内的海拔。在每个 $x$ 的取值对应的答案时，我们只要扫描所有根部存储的信息，再结合前缀和就可以求出每个 $x$ 的取值对应的答案了。

对于每次询问，我们只需要访问其 $y$ 值对应的那一块，并在那一块的并查集上暴力进行剩下的加边操作，在加边的同时维护最终答案相对于之前存储的答案的变化，并在输出答案后复原并查集中被修改的部分，就可以做到在线回答询问了。

最终的时间复杂度为 $O(k^3+qk)$，空间复杂度为 $O(k^3)$。

#include <bits/stdc++.h>
using namespace std;
const int K = 250 + 12;
const int L = 500 + 12;
const int M = 62500 + 12;
const int N = 125000 + 12;
const int O = 0xffff;
int alt[K][K];
pair<int, int> at[M];
int eto[M];
int k, q, A;
pair<unsigned short, unsigned short> e[N];
int ec = 0;
struct Q
{
    unsigned short id;
    unsigned short ld;
    unsigned short sz;
    unsigned short mina;
};
struct R
{
    unsigned short ld[M], sz[M], ans[M], mina[M];
    stack<Q> rec;
    void init()
    {
        for (unsigned short i = 1; i <= k * k; i++)
            ld[i] = i, sz[i] = 1;
        for (unsigned char i = 1; i <= k; i++)
            for (unsigned char j = 1; j <= k; j++)
                mina[(i - 1) * k + j] = alt[i][j];
    }
    unsigned short get(unsigned short x)
    {
        if (ld[x] == x) return x;
        ld[x] = get(ld[x]);
        return ld[x];
    }
    void mrg(int x, int y)
    {
        x = this -> get(x);
        y = this -> get(y);
        if (x == y) return;
        unsigned short xx = sz[x], yy = sz[y];
        if (xx < yy)
        {
            swap(x, y);
            swap(xx, yy);
        }
        ld[y] = x;
        sz[x] = xx + yy;
        sz[y] = 0;
        mina[x] = min(mina[x], mina[y]);
        mina[y] = O;
    }
    unsigned short get_rec(unsigned short x)
    {
        rec.push((Q) {x, ld[x], sz[x], mina[x]});
        if (ld[x] == x) return x;
        ld[x] = get_rec(ld[x]);
        return ld[x];
    }
    unsigned short mrg_rec(int x, int y, int v)
    {
        x = this -> get_rec(x);
        y = this -> get_rec(y);
        if (x == y) return 0;
        unsigned short xx = sz[x], yy = sz[y];
        if (xx < yy)
        {
            swap(x, y);
            swap(xx, yy);
        }
        ld[y] = x;
        unsigned short res = 0;
        if (mina[x] <= v && mina[y] > v) res = yy;
        if (mina[x] > v && mina[y] <= v) res = xx;
        sz[x] = xx + yy;
        sz[y] = 0;
        mina[x] = min(mina[x], mina[y]);
        mina[y] = O;
        return res;
    }
    void recover()
    {
        while (!rec.empty())
        {
            Q u = rec.top();
            rec.pop();
            ld[u.id] = u.ld;
            sz[u.id] = u.sz;
            mina[u.id] = u.mina;
        }
    }
};
R rt[L];
int main()
{
    ios::sync_with_stdio(0);
    cin >> k >> q;
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= k; j++)
            cin >> alt[i][j];
    for (int i = 0; i <= k + 1; i++)
        alt[0][i] = O;
    for (int i = 0; i <= k + 1; i++)
        alt[k + 1][i] = O;
    for (int i = 0; i <= k + 1; i++)
        alt[i][0] = O;
    for (int i = 0; i <= k + 1; i++)
        alt[i][k + 1] = O;
    A = k;
    for (int i = 1; i <= k; i++)
        for (int j = 1; j <= k; j++)
            at[alt[i][j]] = make_pair(i, j);
    for (int i = 0; i <= k * k - 1; i++)
    {
        int x = at[i].first, y = at[i].second;
        if (alt[x][y + 1] < alt[x][y])
        {
            ec++;
            e[ec] = make_pair((x - 1) * k + y, (x - 1) * k + (y + 1));
        }
        if (alt[x][y - 1] < alt[x][y])
        {
            ec++;
            e[ec] = make_pair((x - 1) * k + y, (x - 1) * k + (y - 1));
        }
        if (alt[x + 1][y] < alt[x][y])
        {
            ec++;
            e[ec] = make_pair((x - 1) * k + y, x * k + y);
        }
        if (alt[x - 1][y] < alt[x][y])
        {
            ec++;
            e[ec] = make_pair((x - 1) * k + y, (x - 2) * k + y);
        }
        eto[i] = ec;
    }
    rt[0].init();
    for (int i = A, j = 1; i <= ec; i += A, j++)
    {
        rt[j] = rt[j - 1];
        for (int ii = i, jj = 1; jj <= A; ii--, jj++)
            rt[j].mrg(e[ii].first, e[ii].second);
    }
    for (int i = 0, j = 0; i <= ec; i += A, j++)
    {
        for (unsigned short ii = 1; ii <= k * k; ii++)
            if (rt[j].mina[ii] != 0xffff) rt[j].ans[rt[j].mina[ii]] += rt[j].sz[ii];
        for (unsigned short ii = 1; ii <= k * k; ii++)
            rt[j].ans[ii] += rt[j].ans[ii - 1];
    }
    for (int i = 0, j = 0; i <= ec; i += A, j++)
        for (int ii = 1; ii <= k * k; ii++)
            rt[j].get(ii);
    while (q--)
    {
        int x, y;
        cin >> x >> y;
        int z = eto[y - 1] / A;
        int ans = rt[z].ans[x];
        for (int i = z * A + 1; i <= eto[y - 1]; i++)
            ans += rt[z].mrg_rec(e[i].first, e[i].second, x);
        cout << y - ans << endl;
        rt[z].recover();
    }
    return 0;
}

E - Classic Counting Problem

$f(x)=Cat_x=\dfrac{C_{2x}^x}{x+1}$，证明如下。（10 分）

设 $G=\{V,E\}$ 是一棵基环树，$V=\{1,2,\ldots,n\}$（$n$ 个结点），$E=\{i \to a_i|i \in V\}$（$i$ 号结点向 $a_i$ 号结点连边）。（20 分）

很明显，$G$ 应该有且只有一个环，并且这个环是自环。（30 分）

由于 $a_i\ge a_{i+1}$，对于满足前两个条件的 $\{a_n\}$，环的长度一定不大于 $2$，并且 $G$ 中一定有环。（40 分）

因此，只需要排除 $a_i=j,a_j=i\ (i \ne j)$ 的情况即可。（50 分）

设 $b_i=a_i-i$，则 $b_i>b_{i+1}$，$|b_i| \le n-1$，且存在 $x$ 使得 $b_x=0$，不存在 $x \ne y$ 使得 $b_x=y-x,b_y=x-y$。（60 分）

我们可以用一个 deque 构造 $\{b_n\}$：

• 先放入 $0$。
• 对于每个 $1 \le n-1$，讨论：
  • 是否在 deque 头部放入 $i$。
  • 是否在 deque 尾部放入 $-i$。
  • 如果都放入，是否会出现 $x \ne y$ 使得 $b_x=y-x,b_y=x-y$。（70 分）

设讨论 $i$ 轮后 deque 中共有 $j-1$ 个数。

我们发现：

• $i=0$ 时 $j=i=0$；
• $i=n-1$ 时 $j=i=n-1$；
• $i=j$ 时，如果第 $i+1$ 轮放入两个数，就会出现 $x \ne y$ 使得 $b_x=y-x,b_y=x-y$，因此最多只能放入一个数，该轮结束后 $i \ge j$；
• $i>j\ (i-1 \ge j)$ 时，第 $i+1$ 轮最多只能放入两个数该轮结束后 $i \ge j$。

综上，每轮结束后都有 $i \ge j$。（80 分）

设 $x=i-j$，$y$ 为 deque 中正数的个数与负数的个数之差，并且 $x,y$ 确定了一个二维平面上的点 $A(x,y)$，那么：

• $A$ 的初始坐标为 $(0,0)$；
• $n-1$ 轮讨论后 $A$ 的 $x$ 坐标仍为 $0$；
• 在任何一个时刻，$A$ 的 $x$ 坐标不小于 $0$；
• 每经过一轮讨论后，$A$ 的位移有四种情况：
  • $(x,y) \to (x-1,y)$；（向左）
  • $(x,y) \to (x+1,y)$；（向右）
  • $(x,y) \to (x,y+1)$；（向上）
  • $(x,y) \to (x,y-1)$；（向下）（90 分）

观察发现，$A$ 的 $n-1$ 次位移可以与 $n$ 个元素的入栈出栈操作序列（$2n$ 次操作）一一对应：

• 第一次操作一定是入栈；
• 最后一次操作一定是出栈；
• 剩下的 $2n-2$ 次操作中，一次位移对应两次操作：
  • 向右：入栈，入栈；
  • 向左：出栈，出栈；
  • 向上：入栈，出栈；
  • 向下：出栈，入栈。

很明显，$n$ 个元素的入栈出栈操作序列共有 $Cat_n=\dfrac{C_{2n}^n}{n+1}$ 个，故 $f(x)=Cat_x=\dfrac{C_{2x}^x}{x+1}$，命题得证。（100 分）