2026“钉耙编程”中国大学生算法设计春季联赛（4）

1007 Turn Of A Page

Problem Description

有一本共有 $n$ 页的魔法书，以及一个神奇的数字 $S$。魔法书的每一页都有一个魔力值。其中第 $i$ 页的魔力值为 $a_i$。

称一个页码 $R$ 为神奇的，当且仅当至少存在一个页码 $L$（$1 \le L \le R$），满足

$$\sum_{i=L}^{R} a_i = S$$

如果书中每一页都是神奇的，则称这本书为神奇的魔法书。

现在，你可以重新打乱数组 $a$。问是否存在一种重排，使得得到的书是神奇的魔法书？

如果存在这样的重排，请输出 YES，否则输出 NO。

Input

输入包含多组测试数据。

第一行包含一个整数 $T$（$1 \le T \le 10^5$），表示测试数据的组数。

对于每组测试数据：

• 第一行包含一个整数 $n$（$1 \le n \le 10^5$）和一个整数 $S$（$0 \le S \le 10^9$），表示魔法书的页数和神奇数字 $S$。
• 第二行给出一个长度为 $n$ 数组 $a_1,a_2,\ldots,a_n$（$0 \le a_i \le 10^9$），表示魔法书每一页的魔法值。

保证所有测试数据的 $\sum n \le 3 \times 10^5$。

Output

对于每组测试数据，输出一行结果。

若存在一种排列使得魔法书是神奇的，输出 YES；否则输出 NO。

解题思路

若n=1，那么第一个数一定是s；若n>1，那么第一个数是s，后面的数只能是0或者s。

注意要先考虑s为0情况。

题解代码

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

void sol() {
    int n, s; cin >> n >> s;
	unordered_map<int, int> mp;
	for (int i = 1; i <= n; i++){
		int x; cin >> x;
		mp[x]++;
	}
	if (s == 0){
		if (mp[s] == n)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	else{
		if (mp[s] >= 1 && mp[s] + mp[0] == n)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--)
	    sol();
    return 0;
}

1008 谁输谁洗碗

Problem Description

决定谁去洗碗是情侣之间的一个难题。所幸有人发明了一个好游戏来帮忙做出决定。

这个游戏是这样的：双方各自选一个四位数字（可以有前导 $0$），然后轮流猜数。猜的人选一个四位数，另一个人会告诉他对了几位（位置和数字都要正确）。最先猜到对方数字的人获胜，输的人就要乖乖去洗碗。

现在，给你一方的猜测序列，你能通过这个序列求出正确的数字吗？

Input

第一行一个正整数 $T$（$1 \le T \le 10^5$），表示数据组数。

对于每组数据：

第一行一个正整数 $n$，表示该猜测序列的序列长度。

接下来 $n$ 行，每行一个四位数 $s$ 和整数 $k$，表示猜测的数字以及正确的位数。

输入数据保证

$$\sum n \le 10^5$$

Output

对于每组数据：

输出一个四位数，表示正确的数字（需要加上前导 $0$）。

数据保证有且仅有一个四位数满足猜测序列。

解题思路

暴力枚举，如果tle的话就改变下枚举的顺序。

题解代码

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

#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
typedef long long ls;
typedef unsigned long long uls;
const int inf = 0x3f3f3f3f;

struct STU{
	int q, b, s, g, cnt;
};

bool check(int a, int b, int c, int d, STU t){
	if ((a == t.q) + (b == t.b) + (c == t.s) + (d == t.g) == t.cnt)
		return true;
	return false;
}

void sol(){	
	int n; cin >> n;
	vector<STU> arr(n);
	for (int i = 0; i < n; i++){
		int x, k; cin >> x >> k;
		arr[i].q = x / 1000;
		arr[i].b = x % 1000 / 100;
		arr[i].s = x / 10 % 10;
		arr[i].g = x % 10;
		arr[i].cnt = k;
	}
	for (int a = 0; a <= 9; a++)
		for (int b = 0; b <= 9; b++)
			for (int c = 0; c <= 9; c++)
				for (int d = 0; d <= 9; d++){
					bool f = true;
					for (int i = 0; i < n; i++)
						if (!check(a, b, c, d, arr[i])){
							f = false;
							break;
						}
					if (f){
						cout << a << b << c << d << endl;
						return;
					}
				}
}

int main(){
	IO
	int t; cin >> t;
	while (t--)
		sol();
	return 0;
}

1010 Sort

Problem Description

给定一个 $n \times m$ 的二维数组 $a$。你需要为每一行 $i$（$1 \le i \le n$）选择一个下标 $j_i$（$1 \le j_i \le m$），并令：

$$b_i = a_{i,j_i}$$

问是否存在一种选择方式，使得序列 $b_1,b_2,\ldots,b_n$ 是严格递增的，即：

$$b_1 < b_2 < b_3 < \cdots < b_n$$

Input

每个测试文件包含多组测试数据。

第一行输入一个正整数 $T$（$1 \le T \le 2 \times 10^4$），表示测试数据的数量。

对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$（$1 \le n,m \le 10$），分别表示数组的行数和列数。

接下来 $n$ 行，每行包含 $m$ 个整数，表示数组 $a$ 的元素。（$1 \le a_{i,j} \le 100$）。

Output

如果存在满足条件的选择方式，输出 YES，否则输出 NO。

题面解读

给定一个二维数组，判断是否能在每行找一个数出来，使得这些数递增

解题思路

贪心，每行选择比上一行选择的数大的最小数。

题解代码

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

const int inf = 0x3f3f3f3f;

void sol() {
    int n, m; cin >> n >> m;
	int lst = -1;
	bool ans = true;
	for (int i = 0; i < n; i ++){
		bool f = true;
		int minn = 1000;
		for (int j = 0; j < m; j ++){
			int x; cin >> x;
			if (x > lst){
				minn = min(minn, x);
				f = false;
			}
		}
		if (!f){
			lst = minn;
		}
		else{
			ans = false;
		}
	}
	if (ans)
		cout << "YES" << endl;
	else
		cout << "NO" << endl;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while (t--)
	    sol();
    return 0;
}

1004 左右脑互搏

Problem Description

左脑擅长逻辑，右脑擅长感知，他们谁都不服谁，经常互搏。尖尖的头顶想到了一个游戏，来让他们一决高下。游戏规则如下：

1. 游戏采用回合制，两脑轮流操作，左脑先手，右脑后手。
2. 游戏一开始给出了包含 $n$ 个正整数的多重集合（即可以包含重复元素）。
3. 每次操作时，脑子必须从集合中删除一个数，并且必须满足删除的这个数大于删除这个数后集合中剩余元素的异或和。若当前集合中只有一个元素，则可以直接删去。
4. 无法操作的脑子失败。

现在已知游戏初始给出的集合，两脑都采用最佳策略，请问最后左右脑谁能获胜。

Input

第一行包含一个整数 $T$，表示测试的组数，$1 \le T \le 10$。

对于每组测试数据：

第一行包含一个整数 $n$（$1 \le n \le 20$），表示初始元素的数量。接下来一行 $n$ 个正整数，表示 $n$ 个初始元素。元素范围 $[1,100000]$。

Output

如果左脑先手获胜，输出 "Left"，否则输出 "Right"。

解题思路

sg函数，转移的是整个数组，为了方便操作使用二进制来表示这个数组每个数是否出现过，根据sg函数性质，题目中要用到异或，可以先初始化出来。

题解代码

#include <bits/stdc++.h>
using namespace std;
#define IO ios::sync_with_stdio(0); cin.tie(0);
#define endl '\n'
#define PII pair<int, int>
typedef unsigned long long uls;
typedef long long ls;
const int inf = 0x3f3f3f3f;
const int N = 1LL << 21;
const int M = 25;

int n;
int a[M], f[N];
int xr[N];

int sg(int x){
	if (f[x] != -1)
		return f[x];
	unordered_set<int> se;
	for (int i = 0; i < n; i++)
		if ((x >> i) & 1){
			int nxt = x ^ (1 << i);
			if (xr[nxt] < a[i])
				se.insert(sg(nxt));
		}
	for (int i = 0; ;i++)
		if (!se.count(i))
			return f[x] = i;
}

void sol(){
	memset(f, -1, sizeof f);
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];
	for (int i = 0; i < (1 << n); i++){
		xr[i] = 0;
		for (int j = 0; j < n; j++)
			if (i & (1 << j))
				xr[i] = xr[i] ^ a[j];
	}
	if (sg((1 << n) - 1))
		cout << "Left" << endl;
	else
		cout << "Right" << endl;
}

signed main(){
	IO
	int t; cin >> t;
	while (t--)
		sol();
	return 0;
}