2026牛客寒假算法基础集训营2 思路与题解（A I B F H）
One Last Kiss – 宇多田ヒカル
「私だけのモナリザ」
因为独属于我的蒙娜丽莎
「もうとっくに出会ってたから」
我早已遇见
官方题解：https://blog.karasu.us/wp-content/uploads/2026/02/solution.pdf
A 比赛安排
题意：
$T$ 组询问，每组询问给定小白月赛，练习赛，挑战赛的场次 $a, b, c$，要求排期使得对于任意连续三场的比赛类型都不相同，求是否可能做到。
数据范围：$1 \le T \le 10^4, 1 \le a, b, c \le 10^9$
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
//const int N = 2e5 + 5;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
int a, b, c;
cin >> a >> b >> c;
if (max({a, b, c}) - min({a, b, c}) > 1) cout << "NO" << '\n';
else cout << "YES" << '\n';
}
return 0;
}I 01回文
题意：
给定 $n \times m$ 的 01 矩阵，询问任意一个位置开始拼接字符，任意非起始位置结束，能否拼接得到一个回文串。
数据范围：$1 \le n \times m \le 10^6$
思路：
注意到只要矩阵中存在两个相同数字就可满足 （注意力惊人）
#include <iostream>
using namespace std;
typedef long long ll;
//const int N = 1e6 + 5;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
int n, m;
cin >> n >> m;
char matrix[n + 5][m + 5];
int cnt1 = 0, cnt0 = 0;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
{
cin >> matrix[i][j];
if (matrix[i][j] == '1') cnt1++;
else cnt0++;
}
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= m; j++)
{
if (matrix[i][j] == '1')
{
if (cnt1 >= 2) cout << "Y";
else cout << "N";
}
else
{
if (cnt0 >= 2) cout << "Y";
else cout << "N";
}
}
cout << '\n';
}
}
return 0;
}B NCPC
题意：
给定 $n$ 个整数，每次可以选定两个整数，若两个数字不等，留下较大值，否则全部删除，问对于每个整数能否是最后剩下的数字。
数据范围：$1 \le n \le 2 \times 10^5$
#include <iostream>
using namespace std;
typedef long long ll;
const int N = 2e5 + 5;
int a[N];
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
int n, mxcnt = 0, mx = 0;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
if (a[i] > mx)
{
mx = a[i];
mxcnt = 1;
}
else if (a[i] == mx) mxcnt++;
}
for (int i = 1; i <= n; i++)
{
//如果是最大值，所有的最大值抵消后剩一个才能获胜
if (a[i] == mx) cout << (mxcnt & 1 ? 1 : 0);
//如果不是最大值，用最大值抵消比自己大的数后，最大值相互抵消才能获胜
else cout << (mxcnt & 1 ? 0 : 1);
}
cout << '\n';
}
return 0;
}F x?y?n!
题意：
给定一个整数 $n$，构造两个不相等的整数 $x, y$ 满足 $\gcd(x, y) = n$ 且 $x \oplus y$ 最小。
数据范围：$1 \le T \le 10^4, 1 \le n \le 10^6$
思路：
（什么你问思路？我不道啊直接看出来的）
在 $n$ 的二进制最高位前面重复写一遍它的二进制数得到的数就是 $x$，把 $x$ 加上 $n$ 就是 $y$
代码：
#include <iostream>
using namespace std;
typedef long long ll;
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0);
int T;
cin >> T;
while (T--)
{
ll n;
cin >> n;
ll temp = n;
int len = 0;
while (temp > 0)
{
len++;
temp /= 2;
}
ll x = n << len;
ll y = x + n;
cout << x << ' ' << y << '\n';
}
return 0;
}H 权值计算
题意：
定义一个数组的权值为其所有前缀中不同数字的个数，求所有子数组的权值之和。
数据范围：$1 \le n \le 10^5, 1 \le a_i \le 10^9$
思路：
正难则反，考虑一个数字能给多少个子数组贡献答案以及贡献的大小。
在算 $a_i$ 时，考虑的子数组必然是包含 $i$ 这个位置的，所以计算过程只会被上一个 $a_i$ 的位置 $j$ 影响，影响的区间左端点个数为 $i-j$ 个，而以 $l(j < l \le i)$ 为左端点，$r(i \le r \le n)$ 为右端点的区间贡献多少次呢？考虑如下：
$r = i$ 时：1 次
$r = i + 1$ 时：2 次
$r = i + 2$ 时：3 次
…
$r = n$ 时：$n – i + 1$ 次
归纳之后便可以得出答案为 $(i – j) \times \frac{(1 + n – i + 1) \times (n – i + 1)}{2}$，最后对每个位置都这样求和即可。