2026牛客寒假算法基础集训营2 题解
A. 比赛安排
题意：
有三种类型的比赛，你需要判断是否可以排列这些比赛使得任意连续的三场比赛互不相同。
题解：
思考样例前三种：
2 2 2
2 2 3
2 2 4
如果数量相同即可表示为：1 2 3 1 2 3 这种形式。
如果最大值比最小值大 \(1\) 可以把最大值放前面：3 1 2 3 1 2 3。
如果最大值比最小值大超过 \(1\) 你无论如何无法组合成连续三场比赛互不相同。
#include<bits/stdc++.h>
#define int long long
using namespace std;
void sol(){
int a, b, c; cin >> a >> b >> c;
int mx = max({a, b, c}), mn = min({a, b, c});
cout << (mx - mn <= 1? "YES" : "NO") << endl;
}
signed main(){
int t = 1; cin >> t;
while(t --) sol();
return 0;
}
B. NCPC
题意：
有 \(n\) 个选手做披萨，美味值为 \(a_i\) 。比赛规则为如果美味值相同一起淘汰，不同的话美味值小的淘汰。你需要为每个选手判断是否有一种比赛顺序的排列能够让自己胜利。
题解：
思考，你是最大值的情况下如果最大值有奇数个你一定能获胜（使用最大值与比它小的值比赛随后最大值之间消除），反之一定不行。
思考，如果你不是最大值。你可以让比最大值小的都去跟最大值比赛，构造出仅剩最大值和你的结果。此时如果最大值是偶数个它们可以互相消除你就可以获胜。
综合：最大值为偶数的时候，非最大值一定能获胜。最大值是奇数的时候，最大值一定能获胜。
#include<bits/stdc++.h>
#define int long long
using namespace std;
void sol() {
int n, mx = 0, cnt = 0; cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i ++) cin >> a[i], mx = max(mx, a[i]);
for (int i = 0; i < n; i ++) if (a[i] == mx) cnt ++;
for (int i = 0; i < n; i ++)
if (cnt % 2) cout << (a[i] == mx ? '1' : '0');
else cout << (a[i] == mx ? '0' : '1');
cout << endl;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);
int t = 1; cin >> t;
while(t --) sol();
return 0;
}
F. x?y?n!
题意：
给定一个数 \(n\) 构造\(\gcd(x,y)=n,1 \leq x,y < 2^{63},x != y,min(x \oplus y)\)。
题解：
思考，易证 \(\gcd(x,y)=n, min(x \oplus y) = n\) 如何构造才能使得 \(x,y\) 满足条件呢？
思考若，$n \times 2^{31} $ 与 $n \times 2^{31} + n $ 之间的异或和 \(gcd\) 关系。
使用欧几里得法求 \(gcd\) 可证明 \(gcd\) 为 \(n\)，保证高位相同低位为 \(0\) 异或值为 \(n\) 是最小值。
#include<bits/stdc++.h>
#define int long long
using namespace std;
void sol() {
int n; cin >> n;
cout << (n << 31) << " " << (n << 31) + n << endl;
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);
int t = 1; cin >> t;
while(t --) sol();
return 0;
}
H. 权值计算
题意：
给定一个数组。对任意子数组 \(s[l \dots r]\)，按给定伪代码从左到右扫描，每遇到一个“第一次出现的新元素”，当前不同元素个数 \(+1\)，并把当前不同元素个数累加进 \(total\)。这个 \(total\) 就是该子数组的权值。要求所有非空子数组的权值之和。
题解：
把所有子数组的权值之和拆成每个位置 \(i\) 的贡献。
观察第 \(i\) 个位置 \(a_i\) 它对某个子数组有贡献时满足 \(l \leq i \leq r\) 且 \(a_i\) 在子数组中第一次出现。
设 \(p\) 是 \(a_i\)上一次出现的位，置没有则 \(p = 0\)。
那么只要 \(l\) 出现在 \(p+1\)后面，\(i\) 前面那么 \(a_i\) 就是新元素。
固定 \(i\)，可选的左边 \(l\) 有 \(i − p\) 种。右边 \(r\) 可以从 \(i\) 到 \(n\)，共 \(n − i + 1\) 种
总的就是：\((i−p)×(n−i+1)\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
void print(__int128 x){
if(x < 0) cout << '-', x =- x;
if(x>=10) print(x / 10);
printf("%c",('0' + x % 10));
}
void sol() {
int n; cin >> n;
vector<int> a(n + 1);
unordered_map<int, int> mp;
for (int i = 1; i <= n; i ++) cin >> a[i];
__int128 ans = 0, tmp = 0;
for (int i = 1; i <= n; i ++) {
int p = 0;
if (mp.find(a[i]) != mp.end()) p = mp.find(a[i])->second;
tmp += i - p;
ans += tmp * (__int128)(n - i + 1);
mp[a[i]] = i;
}
print(ans);cout << '\n';
}
signed main(){
// ios::sync_with_stdio(false);cin.tie(0);
int t = 1; cin >> t;
while(t --) sol();
return 0;
}
I. 01回文
题意：
给一个 \(n\times m\) 的 01 矩阵。对每个格子 \((i,j)\)，问是否存在另一个不同的终点 \((x,y)\) 和一条从起点到终点的简单路径，使得沿路径依次取到的 0/1 拼成的字符串是回文串。能则输出 Y，否则 N。每个起点独立判断。
题解：
你从某个格子出发，想拼出回文，最省事就是走一步拼成 \(00\) 或 \(11\)，只要全图里和你同值的格子不止一个，基本就能想办法走到一个同值位置并凑出回文，所以答案只看这个值出现次数够不够。
只要能找到任意一条回文路径即可，路径怎么走不重要，最容易构造的回文是就是 \(00\) 或 \(11\)。、
问题简化为：
对每个格子，是否存在一个相邻格子与它同值。进一步观察在网格图里，如果某个值在整张图里出现次数至少 2，那么这两个相同值的格子之间总能连出一条简单路径。
#include<bits/stdc++.h>
#define int long long
using namespace std;
void sol() {
int n, m; cin >> n >> m;
vector<string> a(n);
int cnt1 = 0 ,cnt0 = 0;
for (int i = 0; i < n; i++) {
cin >> a[i];
for(int j = 0; j < m; j ++)
cnt1 += a[i][j] == '1',
cnt0 += a[i][j] == '0';
}
for (int i = 0; i < n; i ++) {
for (int j = 0; j < m; j ++)
if (a[i][j] == '0') cout << (cnt0 >= 2 ? 'Y' : 'N');
else cout << (cnt1 >= 2 ? 'Y' : 'N');
cout << '\n';
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);
int t = 1; cin >> t;
while(t --) sol();
return 0;
}
E. 01矩阵
题意：
构造一个 \(n\times n\) 的 01 矩阵，使得：
- 每一行的 1 的个数刚好 \(0,1,\dots,n-1\) 各出现一次。
- 每一列的 1 的个数刚好 \(0,1,\dots,n-1\) 各出现一次。
- 相同数字按上下左右连通分块，0 的连通块数 + 1 的连通块数一共正好是 \(n\)。
题解：
我们先随便造一个特殊的排列 \(p = 1, n, 2, n-1, 3, n-2, \dots\)。
然后让第 \(i\) 行第 \(j\) 列，如果 \(p_i > p_j\) 就填 1，否则填 0。
为什么对呢？
填法只看只关注：\(p_i\) 和 \(p_j\) 谁大。
对固定的一行 \(i\)，这一行哪些位置是 \(1\)？就是那些 \(p_j\) 比 \(p_i\) 小的列。
因为 \(p\) 是 \(1\sim n\) 的一个排列，比 \(p_i\) 小的数有且只有 \(p_i-1\) 个，所以第 \(i\) 行里 1 的个数正好是 \(p_i-1\)。
当 \(i\) 从上到下变化时，\(p_i\) 把 \(1,2,\dots,n\) 全用了一遍，于是行和就是 \(0,1,2,\dots,n-1\)。
列同理。
排列 \(p\) 的构造的时候小数和大数交替出现。
这样做结果是，要么新的一行只是把已有的 0 或 1 区域往外扩一点，不会破坏的连通块。要么刚好产生一个新连通块。整个过程中，每一行最多只产生一个新的连通块，最后累加下来，0 的连通块和 1 的连通块加在一起，数量正好就是 \(n\)。
#include<bits/stdc++.h>
#define int long long
using namespace std;
void sol() {
int n; cin >> n;
vector<int> p;
int l = 1, r = n;
while(l <= r){
p.push_back(l);
if (l < r)
p.push_back(r);
l ++, r --;
}
for (int i = 0; i < n; i ++) {
for (int j = 0; j < n; j ++)
cout << (p[i] > p[j] ? '1' : '0');
cout << '\n';
}
}
signed main(){
ios::sync_with_stdio(false);cin.tie(0);
int t = 1; //cin >> t;
while(t --) sol();
return 0;
}
浙公网安备 33010602011771号