A B C D E H I J L 题解

赛时开题顺序： A B J I C L E D H

最后一个小时 F G K 三选一选了 F，显然是没做出来的。

这一场感觉前中期题的思维含量有一点点高（C L E），但是 D H 的做法感觉还是相对好想一些的。

前期（A B J I）

A

签到题，判断一下输入的运算符是什么，构造相应的 $m$ 和 $n$ 即可。

只需要注意到 $x \times 1 = x, (x - 1) + 1 = x, (x + 1) - 1 = x$ 即可。

赛时代码：

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5 + 10;

void solve() {
	i64 x;
	char op;
	std::cin >> x >> op;

	if (op == '*') {
		std::cout << x << " " << 1 << '\n';
	} else if (op == '+') {
		std::cout << x - 1 << " " << 1 << '\n';
	} else {
		std::cout << x + 1 << " " << 1 << '\n';
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	solve();

	return 0;
}

B

显然对于每一段连续的“鸡场”，我们希望它的长度恰好为 $t$ ，否则会造成炸鸡讲解的场次的浪费。

除掉小 L 代讲的 $k$ 段以外，炸鸡还有 $n - k$ 场比赛可以讲，这些比赛可以分出 $\lfloor \dfrac{n - k}{t} \rfloor$ 段“鸡场”。

需要注意的是，由于小 L 一共只代讲 $k$ 场比赛，所以这 $n$ 场比赛至多被分成 $k + 1$ 段。

赛时代码：

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5 + 10;

void solve() {
	int n, t, k;
	std::cin >> n >> t >> k;

	std::cout << std::min(k + 1, (n - k) / t) << '\n';
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t = 1;
	std::cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

J

模拟题。笔者的写法是使用变量 ans 记录行驶的路程，使用变量 v 记录当前的速度。根据题意维护它们即可。

赛时代码：

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5 + 10;

void solve() {
	int n;
	std::cin >> n;

	std::string str;
	std::cin >> str;

	i64 ans = 0, v = 0;
	for (int i = 0; i < n; i++) {
		if (str[i] == '0') {
			v += 10;
			ans += v;
		} else if (str[i] == '1') {
			v = std::max(v - 5, 0ll);
			ans += v;
		} else {
			ans += std::max(v - 10, 0ll);
		}
	}
	std::cout << ans << '\n';
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	solve();

	return 0;
}

I

首先注意到两个 corner case：

如果 $n = m$ ，答案一定是 Yes
在不满足 $n = m$ 的前提下，如果 $n = 0$ 或者 $m = 0$ ，答案一定是 No

在其它情况下，笔者大胆猜想答案一定是 Yes，然后就过了。具体证明看官方题解怎么说。

赛时代码：

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5 + 10;

void solve() {
	int n, m;
	std::cin >> n >> m;

	if (n == m) {
		std::cout << "Yes" << '\n';
		return;
	}

	if (n == 0 || m == 0) {
		std::cout << "No" << '\n';
		return;
	}

	std::cout << "Yes" << '\n';
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t = 1;
	std::cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

前中期（C L E）

C

我们可以先扫一遍 $a, b, c$ ，找到哪些位没有满足 $a_i \oplus b_i = c_i$ 。我们把这些位提取出来，并且按照 $(a_i, b_i)$ 分别计数。

这里，笔者开了一个数组 cnt[4] 进行计数，其中 cnt[0] 表示 $(a_i, b_i) = (0, 0)$ 的数量；cnt[1] 表示 $(a_i, b_i) = (0, 1)$ 的数量；cnt[2] 表示 $(a_i, b_i) = (1, 0)$ 的数量；cnt[3] 表示 $(a_i, b_i) = (1, 1)$ 的数量。

此时问题化归为，有 $4$ 种物品，数量分别为 $cnt_0, cnt_1, cnt_2, cnt_3$ ，每次我们可以选择两个种类不同的物品，花费 $y$ 点代价让它们消失，也可以任意选择一种物品，花费 $x$ 点代价让它消失。

这个问题是一个比较经典的贪心。首先，假如 $2 \times x \leq y$ ，那么我们可以对于全部物品，分别花费 $x$ 点代价即可。否则，如果数量最多的物品（假设为第 $3$ 种）多于其它三种物品的数量的和，我们可以每次选择一个第 $3$ 种物品和另一种物品，最后剩下的第 $3$ 种物品再分别花费 $x$ 点代价即可。如果数量最多的物品（假设为第 $3$ 种）不多于其它三种物品的数量的和，这些物品要么全都可以两两抵消，要么只剩下一个（如果物品的总数是奇数）。后面这种贪心策略可以手玩几组样例试一下。

赛时代码：

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5 + 10;

void solve() {
	int n;
	i64 x, y;
	std::cin >> n >> x >> y;

	std::string a, b, c;
	std::cin >> a >> b >> c;

	int cnt[4] = {0, 0, 0, 0};
	for (int i = 0; i < n; i++) {
		if (c[i] == (a[i] == b[i] ? '0' : '1')) {
			continue;
		}
		cnt[0] += (a[i] == '0' && b[i] == '0');
		cnt[1] += (a[i] == '0' && b[i] == '1');
		cnt[2] += (a[i] == '1' && b[i] == '0');
		cnt[3] += (a[i] == '1' && b[i] == '1');
	}

	i64 ans = (cnt[0] + cnt[1] + cnt[2] + cnt[3]) * x;
	std::sort(cnt, cnt + 4);

	if (cnt[3] > cnt[0] + cnt[1] + cnt[2]) {
		ans = std::min(ans, (cnt[0] + cnt[1] + cnt[2]) * y + (cnt[3] - cnt[0] - cnt[1] - cnt[2]) * x);
	} else {
		ans = std::min(ans, (cnt[0] + cnt[1] + cnt[2] + cnt[3]) / 2 * y + (cnt[0] + cnt[1] + cnt[2] + cnt[3]) % 2 * x);
	}

	std::cout << ans << '\n';
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	solve();

	return 0;
}

L

这题需要稍微对一下脑电波。大体上的构造方案是：

每 $6$ 个数一组。对于每一组数， $(6n + 1, 6n + 2, 6n + 4)$ 是一个合法的三元组， $(6n + 3, 6n + 5, 6n + 6)$ 是一个合法的三元组。

对于 $n \equiv 0 \pmod 6$ 的情况，构造方法即上述方法。如果 $n$ 模 $6$ 余 $1$ 或 $2$ , 显然剩下的数不够再构造出任何一组三元组。而如果 $n$ 模 $6$ 余 $4$ 或 $5$ ，剩下的数还可以构造出一组三元组，我们使用 $(6n + 1, 6n + 2, 6n + 4)$ 构造即可。

对于 $n \equiv 3 \pmod 6$ 的情况。假如 $n \geq 9$ ，我们考虑将前一组数“借过来”，也就是说，现在我们的最后一组数是 $9$ 个一组。这个时候，我们可以构造出 $(6n + 1, 6n + 2, 6n + 4), (6n + 3, 6n + 5, 6n + 9), (6n + 6, 6n + 7, 6n + 8)$ 。

赛时代码：

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 1e6 + 10;

struct NODE {
	int x, y, z;
};

void solve() {
	int n;
	std::cin >> n;

	int lst = 0;
	std::vector<NODE> vec;
	for (int i = 1; i + 5 <= n; i += 6) {
		vec.push_back({i, i + 1, i + 3});
		vec.push_back({i + 2, i + 4, i + 5});
		lst = i + 5;
	}

	std::vector<int> res;
	for (int i = lst + 1; i <= n; i++) {
		res.push_back(i);
	}

	if (res.size() == 3) {
		if (vec.size() >= 2) {
			vec.pop_back(), vec.pop_back();
			res.push_back(res[0] - 1);
			res.push_back(res[0] - 2);
			res.push_back(res[0] - 3);
			res.push_back(res[0] - 4);
			res.push_back(res[0] - 5);
			res.push_back(res[0] - 6);
			std::sort(res.begin(), res.end());
			vec.push_back({res[0], res[1], res[3]});
			vec.push_back({res[2], res[4], res[8]});
			vec.push_back({res[5], res[6], res[7]});
		}
		
	} else if (res.size() == 4) {
		vec.push_back({res[0], res[1], res[3]});
	} else if (res.size() == 5) {
		vec.push_back({res[0], res[1], res[3]});
	}
	// std::map<int, int> cc;
	std::cout << vec.size() << '\n';
	for (const auto &[x, y, z] : vec) {
		std::cout << x << " " << y << " " << z << '\n';
		// assert(cc[x] == 0 && cc[y] == 0 && cc[z] == 0);
		// cc[x] = cc[y] = cc[z] = 1;
		// int cnt = (std::__gcd(x, y) == 1) + (std::__gcd(y, z) == 1) + (std::__gcd(z, x) == 1);
		// assert(cnt == 2);
	}
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t = 1;
	std::cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

E

题目中给出的保证此时棋盘上双方落子数量相同的条件相当重要。我们先处理出来简单的情况。

首先，如果棋盘上双方都没有落子，小 L 是必胜的，因为它只需要如下落子：

XGG
GXG
GGG

这时，炸鸡只能走右下角，而小 L 将子落在右上角即可形成必胜局面。

当双方均落下一子时，很显然炸鸡的一枚棋子无法封住小 L 的所有取胜方向。由于小 L 可以连下两字，所以小 L 可以立即获胜。

当双方均落下四子时，小 L 只有一个位置可以落子，直接判断即可。而双方均落下三子时，显然此时小 L 先下两子是最优的，所以我们只需要枚举三种情况即可。

最后，如果双方均落下两字，结论是小 L 仍然必胜。比较容易出错的是如下情况：

OXG
XOG
GGG

需要注意的是，小 L 这时如果只落一子在右下角，形成如下局面：

OXG
XOG
GGX

无论炸鸡接下来怎么落子，小 L 都可以连下两子取得胜利。

赛时代码：

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5 + 10;

char map[5][5];

void solve() {
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			std::cin >> map[i][j];
		}
	}

	int cnt = 0;
	for (int i = 1; i <= 3; i++) {
		for (int j = 1; j <= 3; j++) {
			cnt += map[i][j] == 'X';
		}
	}
	if (cnt <= 1) {
		std::cout << "Yes" << '\n';
		return;
	}

	auto check = [&]() -> bool {
		for (int i = 1; i <= 3; i++) {
			bool isok = 1;
			for (int j = 1; j <= 3; j++) {
				if (map[i][j] != 'X') {
					isok = 0;
				}
			}
			if (isok) {
				return 1;
			}
		}

		for (int j = 1; j <= 3; j++) {
			bool isok = 1;
			for (int i = 1; i <= 3; i++) {
				if (map[i][j] != 'X') {
					isok = 0;
				}
			}
			if (isok) {
				return 1;
			}
		}

		if (map[1][1] == 'X' && map[2][2] == 'X' && map[3][3] == 'X') {
			return 1;
		}

		if (map[1][3] == 'X' && map[2][2] == 'X' && map[3][1] == 'X') {
			return 1;
		}

		return 0;
	};

	if (cnt == 2) {
		// if (map[1][2] == 'X' && map[2][3] == 'X' && map[2][2] == 'O' && map[1][3] == 'O') {
		// 	std::cout << "No" << '\n';
		// 	return;
		// }

		// if (map[1][2] == 'X' && map[2][1] == 'X' && map[2][2] == 'O' && map[1][1] == 'O') {
		// 	std::cout << "No" << '\n';
		// 	return;
		// }

		// if (map[3][2] == 'X' && map[2][3] == 'X' && map[2][2] == 'O' && map[3][3] == 'O') {
		// 	std::cout << "No" << '\n';
		// 	return;
		// }

		// if (map[3][2] == 'X' && map[2][1] == 'X' && map[2][2] == 'O' && map[3][1] == 'O') {
		// 	std::cout << "No" << '\n';
		// 	return;
		// }

		std::cout << "Yes" << '\n';
	}

	if (cnt == 3) {
		std::pair<int, int> point[3];
		int idx = 0;

		for (int i = 1; i <= 3; i++) {
			for (int j = 1; j <= 3; j++) {
				if (map[i][j] == 'G') {
					map[i][j] = 'X';
					point[idx++] = {i, j};
				}
			}
		}

		for (int i = 0; i < 3; i++) {
			map[point[i].first][point[i].second] = 'O';

			if (check()) {
				std::cout << "Yes" << '\n';
				return;
			}

			map[point[i].first][point[i].second] = 'X';
		}
		std::cout << "No" << '\n';
	}

	if (cnt == 4) {
		for (int i = 1; i <= 3; i++) {
			for (int j = 1; j <= 3; j++) {
				if (map[i][j] == 'G') {
					map[i][j] = 'X';
				}
			}
		}	

		if (check()) {
			std::cout << "Yes" << '\n';
		} else {
			std::cout << "No" << '\n';
		}
	}

}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int t = 1;
	std::cin >> t;
	while (t--) {
		solve();
	}

	return 0;
}

中期及中后期（D H）

D

由于操作可以任意排列每一段，所以我们只需要关心每一段内是否全为 $1$ 或全为 $0$ 或 $0$ 与 $1$ 都有。这个性质可以使用前缀和记录前 $i$ 位 $1$ 的数量维护。

无论 $k$ 为多少，最小贡献值首先至少是 $1$ 。如果某一段全为 $1$ 或全为 $0$ ，我们可以让这一段都等于前一段的末尾的字符，使得这一段和前一段“合并”；反之，如果这一段既有 $0$ 又有 $1$ ，那么这一段一定会增加一个贡献。

注意到时间复杂度实际上是 $O(n \log n)$ ，这是调和级数的性质。

赛时代码：

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 2e5 + 10;

void solve() {
	int n;
	std::cin >> n;

	std::string str;
	std::cin >> str;

	str = " " + str;

	std::vector<int> pre(n + 1, 0);
	for (int i = 1; i <= n; i++) {
		pre[i] = pre[i - 1] + (str[i] == '1');
	}

	int ans = 0;
	for (int k = 1; k <= n; k++) {
		int tmp = 1;
		for (int i = 1; i <= n; i += k) {
			int l = i, r = std::min(n, i + k - 1);
			tmp += ((pre[r] - pre[l - 1]) < (r - l + 1) && (pre[r] - pre[l - 1]) > 0);
		}
		ans ^= tmp;
	}
	std::cout << ans << '\n';
}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	solve();

	return 0;
}

H

考虑计算每一个可能的子区间对答案的贡献。首先特判一下 $k = 1$ 和 $k = 2$ 的情况。这是因为 $k \leq 2$ 时，子区间“并不自由”。

对于 $k \geq 3$ 的情况，分以下几种情况讨论：

子区间 $[l, r]$ 满足 $1 \lt l \leq r \lt n$ 。这个时候，左边还有 $l - 1$ 个数，右边还有 $n - r$ 个数，一共需要分成 $k - 1$ 段。考虑隔板法，此时相当于中间已经强制放置了一个隔板，所以我们现在只需要再放置 $k - 3$ 个隔板即可。由于一共有 $l - 2 + n - r - 1$ 个间隔，所以这个子区间对答案的贡献次数为 $C_{n + l - r - 3}^{k - 3}$ 。
子区间 $[l, r]$ 满足 $l = 1$ 或 $r = n$ 。做法和第一种情况类似， $l = 1$ 时贡献次数为 $C_{n - r - 1}^{k - 2}$ ， $r = n$ 时贡献次数为 $C_{l - 2}^{k - 2}$ 。

每一个子区间的贡献用 ST 表维护即可。对于组合数的部分，可以预处理模意义下的阶乘和阶乘的逆元。笔者赛时直接使用的快速幂求逆元，也可以通过。

赛时代码：

#include <bits/stdc++.h>

using i64 = long long;

constexpr int N = 3000 + 10;
constexpr int mod = 998244353;

i64 a[N];
i64 Sparse_Table_f_max[N][30], Sparse_Table_f_min[N][30];

void init(i64 st[], int n)
{
	// 初始化 ST 表
	for (int i = 1; i <= n; i++)
	{
		Sparse_Table_f_max[i][0] = Sparse_Table_f_min[i][0] = st[i];
	}
	for (int j = 1; j <= log(n) / log(2); j++)
	{

		for (int i = 1; i <= n - (1 << j) + 1; i++)
		{ // 维护静态区间最大值
			Sparse_Table_f_max[i][j] = std::max(Sparse_Table_f_max[i][j - 1], Sparse_Table_f_max[i + (1 << (j - 1))][j - 1]);
			Sparse_Table_f_min[i][j] = std::min(Sparse_Table_f_min[i][j - 1], Sparse_Table_f_min[i + (1 << (j - 1))][j - 1]);
		}
	}
}

i64 queryMax(int l, int r)
{
	// 查询区间最大值
	int x = log(r - l + 1) / log(2);
	return std::max(Sparse_Table_f_max[l][x], Sparse_Table_f_max[r - (1 << x) + 1][x]);
}

i64 queryMin(int l, int r)
{
	// 查询区间最小值
	int x = log(r - l + 1) / log(2);
	return std::min(Sparse_Table_f_min[l][x], Sparse_Table_f_min[r - (1 << x) + 1][x]);
}

i64 pw[10000];

i64 qpow(i64 a, i64 b, i64 p)
{
	i64 res = 1;
	while (b)
	{
		if (b & 1)
			res = (res * a) % p;
		a = a * a % p;
		b >>= 1;
	}
	return res;
}

i64 inv(i64 x, i64 p)
{
	return qpow(x, p - 2, p);
}

i64 C(i64 n, i64 m) {
	if (n < m) {
		return 0;
	}
	return pw[n] * inv(pw[m], mod) % mod * inv(pw[n - m], mod) % mod;
}

void solve() {
	int n, k;
	std::cin >> n >> k;

	for (int i = 1; i <= n; i++) {
		std::cin >> a[i];
	}

	init(a, n);

	if (k == 1) {
		std::cout << queryMax(1, n) * queryMin(1, n) % mod << '\n';
		return;
	}

	if (k == 2) {
		i64 ans = 0;
		for (int k = 1; k < n; k++) {
			ans = (ans + queryMax(1, k) * queryMin(1, k) % mod + queryMax(k + 1, n) * queryMin(k + 1, n) % mod) % mod;
		}
		std::cout << ans << '\n';
		return;
	}

	i64 ans = 0;
	for (int l = 1; l <= n; l++) {
		for (int r = l; r <= n; r++) {
			i64 add = queryMax(l, r) * queryMin(l, r) % mod;
			if (l == 1 && r == n) {
				continue;
			} else if (l == 1 && r != n) {
				ans = (ans + add * C(n - r - 1, k - 2)) % mod;
			} else if (l != 1 && r == n) {
				ans = (ans + add * C(l - 2, k - 2)) % mod;
			} else {
				ans = (ans + add * C(n + l - r - 3, k - 3)) % mod;
			}
		}
	}

	std::cout << ans << '\n';

}

int main() {
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	pw[0] = 1;
	for (int i = 1; i <= 8000; i++) {
		pw[i] = pw[i - 1] * i % mod;
	}

	solve();

	return 0;
}

题解 | ABCDEHIJL

A B C D E H I J L 题解

前期（A B J I）

A

B

J

I

前中期（C L E）

C

L

E

中期及中后期（D H）

D

H