SCNUCPC 2026 赛后补题(简单题)

做题点击这里：题目链接

本人认为简单题有如下几道：

Signin: E, F
Easy: A, B, K, J

以上题目适合入门，本人是菜比，只能补出来这些了

Signin 两题比较简单就不赘述了

A. Hello, SCNUCPC!

题目描述：

在 8000 年后，全世界的人类与 AI 都在『月读』里打 SCNUCPC。

『月读』中有一条名为『魔法街』的街道。八千代需要布置魔法街，以迎接今年的 SCNUCPC。

魔法街上排列着 $n$ 个摊位，每个摊位的类型可以由一个 A $\sim$ Z 的大写字母表示。

最初街上只有一些摊位布置成 C 型，其他摊位都未布置，标记为 ?。八千代想布置所有未布置的摊位！

摊位的初始布置状态表示为一个长度为 $n$ 的字符串，仅由 C 和 ? 两种字母组成。

用字符串 $s$ 表示布置后的魔法街摊位状态，若

$$ s_i s_{i+1} \cdots s_{i+5}s_{i+6} = \text{SCNUCPC} $$

则称 $i$ 是一个赛场。

请你给出一个布置方案 $s$，使得魔法街上恰好有 $k$ 个赛场，或报告无解。

如果存在多种合法方案，输出其中任意一种即可。

输入格式：

每个测试文件由多个测试用例组成。第一行包含一个整数 $T(1 \le T \le 10^3)$ 表示测试用例数。

对于每个测试用例，第一行包含两个整数 $n, k(0 \le k < n \le 2 \times 10^5)$，表示摊位数和赛场数。

随后是一个长度为 $n$ 的字符串，其中仅包含 C 和 ? 两种字符，代表魔法街的初始摊位状态。

数据保证所有测试用例的 $n$ 的总和不超过 $2 \times 10^5$。

输出格式：

对于每个测试用例，若无解，输出一行 No；

否则，输出一行 Yes，随后输出一个长度为 $n$ 的字符串，表示布置方案 $s$。

输入样例：

2
7 1
????C??
16 2
??C?C??C??C??C?C

输出样例：

Yes
SCNUCPC
No

分析：

这题考察贪心算法，要注意不要破坏原字符串中的 C，并且此题不会出现两个子串相互重叠的情况

AC代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int T;
	cin >> T;

	while (T--) {
		int n, k;
		cin >> n >> k;

		string s;
		cin >> s;

		if (n < 7 * k) {
			cout << "No" << endl;
			continue;
		}

		string ans;
		if (k == 0) {
			while (ans.size() < n) ans += 'C';
			cout << "Yes" << endl;
			cout << ans << endl;
			continue;
		}

		auto match = [&](const string& s) -> bool {
			for (int i = 0; i < 7; i++) {
				if (i == 0 || i == 2 || i == 3 || i == 5) {
					if (s[i] != '?') return false;
				}
			}
			return true;
		};

		int l = 0, r = 6, sum = 0;
		while (r < n && sum < k) {
			string sub = s.substr(l, 7);
			if (match(sub)) {
				sum++;
				ans += "SCNUCPC";
				l = r + 1;
				r = l + 6;
			} else {
				ans += 'C';
				l++;
				r++;
			}
		}

		if (sum == k) {
			while (ans.size() < n) ans += 'C';
			cout << "Yes" << endl;
			cout << ans << endl;
		} else {
			cout << "No" << endl;
		}
	}

	return 0;
}

B. 0100101

题目描述：

给定一个长度为 $n$ 的 01 串 $s$ 和一个正整数 $k$。

你需要构造一个满足以下要求的正整数序列 $a$：

• 长度为 $n + 1$；

• $1 \le a_i \le 100$；

• 对于 $1$ 到 $n$ 之间的任意整数 $i$，当且仅当 $s_i = 1$ 时，$\dfrac{a_i}{a_{i+1}}$ 在 $k$ 进制下数位有限。

可以证明：在本题的数据范围约束下，总有满足以上要求的序列存在。

Note:

例如在 $10$ 进制下，$\dfrac{1}{8} = 0.125$ 数位有限，但 $\dfrac{1}{3} = 0.333\cdots$ 数位无限。

输入格式：

每个测试文件由多个测试用例组成。第一行包含一个整数 $T(1 \le T \le 10^3)$ 表示测试用例数。

对于每个测试用例，第一行包含两个整数 $n, k(1 \le n \le 2 \times 10^5,\ 2 \le k \le 10^{18})$。

第二行包含一个长度为 $n$ 的 01 串 $s(s_i \in {0, 1})$。

数据保证所有测试用例的 $n$ 的总和不超过 $2 \times 10^5$。

输出格式：

对于每个测试用例，输出一行 $n + 1$ 个正整数 $a_i(1 \le a_i \le 100)$，表示你构造的序列 $a$。

输入样例：

2
3 10
101
7 2
0100101

输出样例：

2 1 3 6
1 3 4 5 7 8 9 9

分析：

这题考察数论知识

• 重要结论:

  对任意最简分数 $\dfrac{p}{q}$ 在 $k$ 进制下是有限小数，当且仅当分母 $q$ 的质因子全部包含于 $k$ 的质因子中

• 直观理解:

  记 $k$ 进制下的有限小数为 $0.d_1d_2 \cdots d_n$，则

  $$ 0.d_1d_2 \cdots d_n = \dfrac{d_1}{k} + \dfrac{d_2}{k^2} + \cdots + \dfrac{d_n}{k^n} = \dfrac{d_1 \cdot k^{n-1} + d_2 \cdot k^{n-2} + \cdots + d_n}{k^n} $$

  可以观察到 $k$ 进制下的有限小数可以表达为 某个整数 除以 $k$ 的某个幂次，即 $\dfrac{A}{k^m}(A \in \mathbb{Z}, m \in \mathbb{N^*})$

  当 $q$ 的质因子全部包含于 $k$ 的质因子集合中时，总会有一个足够大的 $m$ 使得 $q \mid k^m$，即 k^m % q == 0

• 相关理论:

  算术基本定理: 每个大于 $1$ 的自然数，要么本身就是素数，要么可以写为 $2$ 个或以上的素数的积，而且这些素因子按大小排列之后，写法仅有一种方式

于是在此题中可以在 $1 \thicksim 100$ 的 素数 中找到两个整数使得 $p, q \nmid k$，则 $k$ 质因子中一定没有 $p, q$，接着就可以构造出序列:

• 当 s[i] == 1 时，a[i] = a[i - 1]

• 当 s[i] == 0 时，a[i] = p + q - a[i - 1]

可验证，一定存在两个素数使得去掉该素数后，$1 \thicksim 100$ 中其它素数的乘积 $2 \times 3 \times 5 \times \cdots > 10^{18}$ ，即不存在 $k$ 使得找不到两个素数 $p,q \nmid k$，故此题必定有解

AC代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
	auto isPrime = [&](int x) -> bool {
		if (x == 2) return true;
		for (int i = 2; i * i <= x; i++) {
			if (x % i == 0) return false;
		}
		return true;
	};

	vector<int> prime;
	for (int i = 2; i <= 100; i++) {
		if (isPrime(i)) prime.push_back(i);
	}

	int T;
	cin >> T;

	while (T--) {
		int n;
		ll k;
		cin >> n >> k;

		string s;
		cin >> s;

		vector<int> candidate;
		for (int x: prime) {
			if (k % x != 0) candidate.push_back(x);
		}

		int p = candidate[0];
		int q = candidate[1];

		vector<int> ans(n + 1);
		ans[0] = p;

		for (int i = 0; i < n; i++) {
			if (s[i] == '1') {
				ans[i + 1] = ans[i];
			} else {
				ans[i + 1] = p + q - ans[i];
			}
		}

		for (int x: ans) {
			cout << x << ' ';
		}
		cout << endl;
	}


	return 0;
}

J. 别玩网格图了

题目描述：

你完成了上次的谜题，又被传送到另一个世界。这次这里没有香草，只有在 cos 香草的 pwp，坐在空白世界里唯一的桌子上。

你是谁，你怎么穿着品……咳咳，香子兰的衣服？问题还在心里没有说出口，pwp 便回答，"pwp 就是 pwp 喵。奇怪的是，这里明明是君的梦境，怎喵会梦到 pwp 喵？" pwp 说着，晃着双腿。梦吗？那……"是哦。不过别想着在梦里干什喵怪事喵，心声都露出来了哦。" pwp 说着，按了几下桌上的铃。唔……

"更优先的不是应该从梦里出去喵？" pwp 指了指地面。又是网格图？"既然从上一层梦境下来了，总应该能破解这个谜题叭喵。" pwp 说完，尾巴把桌上一张 +4 牌扫下，落在某个格子边缘，落在的那条边忽地变得更醒目更宽大了。

人类，上面的话都不重要喵——pwp 参上 $\sim$

给定 $n \times m$ 大小的网格图，在每个网格放置一个带有一条边的方形。

求用 1, 2, 3, 4 标识对应四种方向的方形，在这个网格图上能围出的最大封闭空间面积。

输入格式：

每个测试文件由多个测试用例组成。第一行包含一个整数 $T(1 \le T \le 1500)$ 表示测试用例数。

对于每个测试用例，输入一行两个整数 $n, m(1 \le n, m \le 10^6,\ 1 \le n \times m \le 10^6)$，表示网格图大小。

数据保证所有测试用例的 $n \times m$ 的总和不超过 $10^6$。

输出格式：

对于每个测试用例，第一行输出一个整数，表示能围出的最大封闭空间的面积；

若无法形成面积大于 $0$ 的封闭空间，则输出 $0$。

输入样例：

2
2 5
4 4

输出样例：

6
8

分析：

此题可以找到如下规律：

• 当 min(n, m) == 1 时，无法围出有效面积，S = 0

• 当 2 <= min(n, m) <= 4 时，S = n * m - 2 * min(n, m)

• 当 min(n, m) >= 5 时，S = n * m - 8

  此时是四个角落各挖去一个 1 * 2 的块

感觉懵的话可以画画图，尽量不要问 AI，它很有可能得不到正确答案

AC代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int T;
	cin >> T;

	while (T--) {
		int n, m;
		cin >> n >> m;

		if (n == 1 || m == 1) cout << 0 << endl;
		else if (min(n, m) <= 4) cout << n * m - 2 * min(n, m) << endl;
		else cout << n * m - 8 << endl;
	}

	return 0;
}

K. NTT

题目描述：

给定一个 $n$ 次多项式函数

$$ F(x) = f_0 + f_1x + f_2x^2 + \cdots + f_nx^n $$

以及一个素数 $p$。

随后有 $q$ 次询问，每次给定一个整数 $x_i$，你需要求出 $F(x_i) \bmod p$ 的值。

可以证明，存在唯一的整数 $r$ 满足 $0 \le r < p$ 且

$$ F(x_i) \equiv r \pmod p $$

$r$ 即为你需要输出的数。

输入格式：

每个测试文件由多个测试用例组成。第一行包含一个整数 $T(1 \le T \le 100)$ 表示测试用例数。

对于每个测试用例，第一行包含三个整数 $n, p, q(1 \le n \le 10^6,\ 2 \le p < 5 \times 10^3,\ 1 \le q \le 5 \times 10^3)$，分别表示多项式 $F(x)$ 的次数、给定的素数以及询问的次数。

第二行包含 $n + 1$ 个整数，表示 $F(x)$ 从低次到高次的系数 $f_i(0 \le f_i \le 10^6)$。

接下来 $q$ 行，每行包含一个整数 $x_i(|x_i| \le 10^6)$，你需要求出 $F(x_i) \bmod p$ 的值。

数据保证所有测试用例 $n$ 的总和不超过 $10^6$，$q$ 的总和不超过 $5 \times 10^3$。

输出格式：

对每次询问，输出一行一个整数，即 $F(x_i) \bmod p$ 的值。

输入样例：

2
3 5 3
0 9 0 6
-5
-7
-10
3 7 3
8 0 2 4
1
9
-10

输出样例：

0
4
0
0
6
2

理论知识：

费马小定理：$a \in \mathbb{Z}$，$p$ 为素数，若 $\gcd(a, p) = 1$，则 $a^{p-1} \equiv 1 \pmod p$

分析：

• 由费马小定理可知，当 $p \nmid x$ 时，$x^i \equiv x^{i \bmod (p - 1)} \pmod p$

  于是指数最大为 $p-1$，将时间复杂度从 $O(nq)$ 降到了 $O(pq)$，使题目可做

• 注意：

  • 当 $p \mid x$ 即 $x$ 为 $p$ 的倍数时 $\gcd(x, p) = p$，不满足费马小定理的使用条件，此时易知 $F(x) \equiv f[0] \pmod p$，因此要记录第一个系数作为此情况下的输出

  • 系数 $f[i] \equiv f[i] \bmod p \pmod p$，不要忘记取模！

AC代码：

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

int main()
{
	int T;
	cin >> T;

	while (T--) {
		int n, p, q;
		cin >> n >> p >> q;

		int zero;
		vector<int> f(p - 1, 0);
		for (int i = 0; i <= n; i++) {
			int num;
			cin >> num;

			if (i == 0) {
				zero = num % p;
				if (zero < 0) zero += p;
			}

			int exp = i % (p - 1);
			f[exp] = (f[exp] + num) % p;
		}

		for (int i = 0; i < q; i++) {
			ll ans = 0;
			int x, p_pow = 1;
			cin >> x;

			x %= p;
			if (x < 0) x += p;

			if (x == 0) {
				cout << zero << endl;
				continue;
			}

			for (int j = 0; j < p - 1; j++) {
				ans = (ans + 1LL * f[j] * p_pow) % p;
				p_pow = 1LL * (p_pow * x) % p;
			}

			cout << ans << endl;
		}
	}

	return 0;
}