2026牛客寒假算法基础集训营1部分题解
A. A+B Problem
题意：
给定八个七段数码管显示器，每个显示器有 7 个灯管（编号 1~7）。每个灯管 \(i\) 被点亮的概率为 \(p_i\%\)（独立）。现在需要将这八个显示器分成两排，每排四个，要求：
1. 每个显示器至少有一个灯管被点亮；
2. 每个显示器显示的数字必须是合法的（0~9）；
3. 第一排四个显示器组成的四位数 \(A\)（允许前导零）与第二排四个显示器组成的四位数 \(B\) 满足 \(A + B = C\)（\(C\) 给定）。
求满足所有条件的概率，结果对 \(998244353\) 取模。
思路：
首先计算单个显示器显示数字 \(d\)（0~9）的概率。每个数字对应一个固定的灯管亮灭模式，对于灯管 \(i\)：
- 若模式中要求点亮，则贡献概率 \(p_i\%\)；
- 若要求熄灭，则贡献概率 \((100-p_i)\%\)。
将所有灯管的概率相乘即可。
由于两排显示器相互独立且概率分布相同，枚举数字 \(x\)（\(0 \le x \le C\)），计算概率，将每个数字概率相乘即可。
最后答案为 \(\sum_{a=0}^{C} dp[a] \times dp[C-a]\)。
代码
点击查看代码
vector<int>g[10]={
{1,1,1,0,1,1,1},
{0,0,1,0,0,1,0},
{1,0,1,1,1,0,1},
{1,0,1,1,0,1,1},
{0,1,1,1,0,1,0},
{1,1,0,1,0,1,1},
{1,1,0,1,1,1,1},
{1,0,1,0,0,1,0},
{1,1,1,1,1,1,1},
{1,1,1,1,0,1,1}
};
int a[N];
int b[N];
void solve() {
int n,m;
cin>>n;
int inv=qpow(100,mod-2);
for(int i=1;i<=7;i++){
cin>>a[i];
a[i]*=inv;
a[i]%=mod;
}
for(int i=0;i<=n;i++){
int x=i;
int p=1;
for(int j=0;j<4;j++){
for(int k=0;k<7;k++){
if(g[x%10][k])p*=a[k+1];
else p*=mod+1-a[k+1];
p%=mod;
}
x/=10;
}
b[i]=p;
}
int ans=0;
for(int i=0;i<=n;i++){
ans+=b[i]*b[n-i]%mod;
ans%=mod;
}
cout<<ans<<endl;
}
B. Card Game
题意
给定长度为 \(2n\) 的排列，分成两个数组 \(a\)（小苯的牌）和 \(b\)（小红的牌），长度均为 \(n\)。游戏规则如下：
- 每轮比较两人当前手牌的第一张，数字大的一方得一分并移除自己的牌，另一方不得分且牌保留。
- 游戏进行直到一方无牌。
- 小苯可以在游戏开始前任意重排自己的牌，目标是最大化自己的得分。
要求计算能使小苯获得最高得分的不同排列方案数，对 \(998244353\) 取模。
思路
模拟游戏过程不难发现，令 \(mn\) 为小红的最小值，\(m\) 为小苯大于 \(mn\) 的个数，得到的得分为最大可能得分 \(m\)。
所有达到最高得分 \(m\) 的排列都满足：所有大于 \(mn\) 的牌（共 \(m\) 张）必须出现在所有小于等于 \(mn\) 的牌（共 \(n-m\) 张）之前。赢的牌内部和输的牌内部可以任意排列。
因此方案数为 \(m! \times (n-m)!\)。
代码
点击查看代码
int a[N];
int b[N];
void solve() {
int n,m;
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
int mn=1e9;
for(int i=1;i<=n;i++){
cin>>b[i];
mn=min(mn,b[i]);
}
int s=0;
for(int i=1;i<=n;i++){
s+=a[i]>mn;
}
int ans=1;
for(int i=1;i<=s;i++){
ans*=i;
ans%=mod;
}
for(int i=1;i<=n-s;i++){
ans*=i;
ans%=mod;
}
cout<<ans<<endl;
}
C. Array Covering
题意：
给定一个长度为 \(n\) 的数组 \(a\)，可以执行任意次操作：每次选择两个下标 \(l\) 和 \(r\)（\(1 \le l < r \le n\)），将开区间 \((l, r)\) 内的所有数替换为 \(\max(a_l, a_r)\)。求操作后数组所有元素之和的最大值。
思路：
由于操作只改变开区间内的数，数组的首位和末位永远无法被改变。其余位置可以通过一系列操作变为全局最大值 \(M\)。答案为 \(M\cdot (n-2)+a_1+a_n\)。
时间复杂度 \(O(n)\)。
代码
点击查看代码
void solve() {
int n;
cin>>n;
int mx=0;
for(int i=1;i<=n;i++){
cin>>a[i];
mx=max(mx,a[i]);
}
cout<<mx*(n-2)+a[1]+a[n]<<endl;
}
D. Sequence Coloring
题意：
给定一个长度为 \(n\) 的序列 \(a\)，\(a_i > 0\) 表示白色，\(a_i = 0\) 表示黑色。初始可以选择最多 \(k\) 个白色元素染红。之后每一秒，每个红色元素会将其右侧 \(a_i\) 个位置内的所有白色元素染红。求所有白色元素都被染红的最短时间，若无法做到输出 \(-1\)。
思路：
首先提取所有白色元素的位置和对应的 \(a\) 值。根据传播规则，将白色元素划分为若干连通块：每个连通块内的白色元素可以通过传播相互到达，不同连通块之间无法传播。若连通块数量 \(blocks > k\)，则无法全部染红，输出 \(-1\)。
否则，二分答案时间 \(T\)。对于每个连通块，预处理 \(next\) 数组：\(next[i]\) 表示从第 \(i\) 个白色元素出发，一秒内能到达的最右白色元素下标。再用倍增预处理 \(go[i][p]\)，表示从 \(i\) 出发 \(2^p\) 秒能到达的最右下标。
对于给定的 \(T\)，计算每个连通块内最少需要的起点数：从左到右贪心，每次选择当前起点 \(i\)，用倍增快速求出 \(T\) 秒内能覆盖的最右下标 \(R\)，然后以 \(R+1\) 作为下一段的起点，计数加一。累加所有连通块的起点数，若总数 \(\le k\) 则 \(T\) 可行。
二分找到最小的可行 \(T\) 即为答案。
代码
点击查看代码
int n, k;
int a[N];
vector<int>b;
vector<PII> q;
vector<vector<int>> nxt;
vector<vector<vector<int>>> go;
bool ok(int T) {
int sum = 0;
for (int j = 0; j < q.size(); j++) {
int l = q[j].first, r = q[j].second;
int i = l, cnt = 0;
while (i <= r) {
++cnt;
int x = i;
for (int p = 0; p <= 20; ++p) {
if ((T >> p) & 1) {
x = go[j][x - l][p];
}
}
i = x + 1;
}
sum += cnt;
if (sum > k) return false;
}
return sum <= k;
}
void solve() {
cin >> n >> k;
b.clear();
for (int i = 1; i <= n; ++i) {
cin >> a[i];
if (a[i] > 0) b.push_back(i);
}
int m = b.size();
if (m == 0) {
cout << 0 << endl;
return;
}
q.clear();
int l = 0;
int x = b[0] + a[b[0]];
for (int i = 1; i < m; ++i) {
if (b[i] <= x) {
x = max(x, b[i] + a[b[i]]);
} else {
q.push_back({l, i - 1});
l = i;
x = b[i] + a[b[i]];
}
}
q.push_back({l, m - 1});
if (q.size() > k) {
cout << -1 << endl;
return;
}
int blocks = q.size();
nxt.assign(blocks, vector<int>());
go.assign(blocks, vector<vector<int>>());
for (int u = 0; u < blocks; u++) {
int L = q[u].first, R = q[u].second;
int len = R - L + 1;
vector<int> &nx = nxt[u];
nx.resize(len);
int j = L;
for (int i = L; i <= R; i++) {
int lim = b[i] + a[b[i]];
while (j <= R && b[j] <= lim) j++;
nx[i - L] = j - 1;
}
vector<vector<int>> &g = go[u];
g.resize(len, vector<int>(20 + 1));
for (int i = 0; i < len; i++) g[i][0] = nx[i];
for (int p = 1; p <= 20; p++) {
for (int i = 0; i < len; ++i) {
int t = g[i][p - 1];
g[i][p] = g[t - L][p - 1];
}
}
}
int L = 0, R = m, ans = -1;
while (L <= R) {
int mid = (L + R) >> 1;
if (ok(mid)) {
ans = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
cout << ans << endl;
}
E. Block Game
题意：
给定一个长度为 \(n\) 的数组 \(a\) 和一个整数 \(k\)。每次操作可以将当前的万能方块 \(k'\) 插入数组左侧，数组整体右移，最右侧的数字成为新的万能方块。可以进行任意次操作（包括 \(0\) 次）。求最终数组的第一个元素与万能方块的和的最大值。
思路：
操作相当于将整个数组 \(C = [k, a_1, a_2, \dots, a_n]\) 循环左移。因此问题转化为在循环数组 \(C\) 中找相邻两个元素和的最大值，即 \(\max\limits_{i=0}^{n} (C[i] + C[(i+1) \bmod (n+1)])\)。
代码
点击查看代码
void solve() {
int n,m;
cin>>n>>m;
int mx=-1e18;
for(int i=1;i<=n;i++){
cin>>a[i];
}
a[0]=m;
for(int i=1;i<=n;i++){
mx=max(mx,a[i]+a[i-1]);
}
mx=max(mx,a[0]+a[n]);
cout<<mx<<endl;
}
G. Digital Folding
题意：
给定一个区间 \([l, r]\)，对于区间内的每个整数 \(i\)，定义其折叠数为：将 \(i\) 的十进制表示反转并去掉前导零后得到的整数。求所有 \(i\) 的折叠数的最大值。
思路：
观察发现，要使折叠数尽可能大，需要让反转后的最高位尽可能大。对于任意一个不超过 \(r\) 的数，我们可以将其调整为以若干个9结尾的形式，这样反转后最高位就是9。
具体做法是：枚举以 \(i\) 个9结尾的数，通过 \(x = \lfloor \frac{r}{p} \rfloor \times p - 1\) 构造出不大于 \(r\) 且以 \(i\) 个9结尾的最大数（其中 \(p = 10^i\)）。如果这个数在 \([l, r]\) 区间内，就用它的折叠数更新答案。同时，\(r\) 本身的折叠数也需要考虑。
代码
点击查看代码
int get(int x){
string s=to_string(x);
reverse(s.begin(),s.end());
return stoll(s);
}
void solve() {
int l,r;
cin>>l>>r;
int mx=get(r);
int p=1;
for(int i=0;i<18;i++){
int x=r/p*p-1;
if(x<l)break;
mx=max(mx,get(x));
p*=10;
}
cout<<mx<<endl;
}
H. Blackboard
题意：
给定数组 \(a_1, a_2, \dots, a_n\)。现在要将数组分成若干连续段，每段内计算所有数的按位或，然后将各段的结果相加。要求这个和等于所有 \(a_i\) 的和。求分割方案数。
思路：
设原数组和为 \(S = \sum a_i\)。对于一种分割，每段 \([l, r]\) 的值为 \(o = \text{OR}_{i=l}^r a_i\)。令所有段的 \(o\) 之和为 \(T\)。需要 \(T = S\)。
注意到对于任意一段，由于按位或的性质，有 \(o \ge \max_{i \in [l, r]} a_i\)，且通常 \(o\) 小于等于段内数字的和。实际上，可以证明 \(T = S\) 当且仅当对于每一段，段内所有数字的二进制表示互不重叠（即任意两个数字的按位与为 \(0\)）。这是因为如果段内数字有重叠的二进制位，那么 \(o\) 会严格小于段内和，导致 \(T < S\)；如果所有段都满足不重叠，则 \(o\) 等于段内和，从而 \(T = S\)。
因此，问题转化为：将序列分成若干连续段，使得每一段内任意两个数字的按位与均为 \(0\)。求分割方案数。
可以用动态规划解决。设 \(dp[i]\) 表示前 \(i\) 个数字的分割方案数。转移时，枚举最后一段的起点 \(j+1\)，要求 \([j+1, i]\) 满足条件，则 \(dp[i] = \sum dp[j]\)。直接转移是 \(O(n^2)\) 的。
优化：对于每个右端点 \(i\)，可以求出最小的左端点 \(L_i\)，使得 \([L_i, i]\) 满足条件，并且对于任意 \(L \ge L_i\)，\([L, i]\) 也满足条件（因为子段必然满足）。那么 \(dp[i] = \sum_{j = L_i-1}^{i-1} dp[j]\)。可以用前缀和优化到 \(O(1)\) 转移。
使用双指针维护当前窗口 \([L, i]\) 的按位或值，并维护每个二进制位出现的次数。当加入 \(a_i\) 时，如果当前按位或与 \(a_i\) 有重叠的二进制位（即按位与不为 \(0\)），则不断右移 \(L\)，并更新按位或，直到无重叠。此时 \(L_i = L\)。由于 \(L_i\) 单调不减，总复杂度为 \(O(n \cdot B)\)，其中 \(B = 31\)。
代码
点击查看代码
void solve() {
cin >> n;
for (int i = 0; i <= n + 2; i++) {
b[i] = c[i] = 0;
}
for (int j = 0; j <= 31; j++) {
lst[j] = 0;
}
for (int i = 1; i <= n; i++) {
cin >> a[i];
}
b[0] = c[0] = 1;
int l = 1;
for (int i = 1; i <= n; i++) {
int nt = 1;
for (int k = 0; k < 31; k++) {
if ((a[i] >> k) & 1) {
nt = max(nt, lst[k] + 1);
}
}
l = max(l, nt);
b[i] = c[i - 1];
if (l >= 2) b[i] = (b[i] - c[l - 2] + mod) % mod;
c[i] = (c[i - 1] + b[i]) % mod;
for (int k = 0; k < 31; k++) {
if ((a[i] >> k) & 1) lst[k] = i;
}
}
cout<<b[n]<<endl;
}
I. AND vs MEX
题意：
给定区间 \([l, r]\)，每次操作可以从区间中选取任意个数字，计算它们的按位与，并将结果加入集合 \(S\)。可以进行任意次操作，求集合 \(S\) 的 MEX的最大值。
思路：
观察发现，由于 AND 操作的结果不会超过 \(r\)，因此答案上界为 \(r+1\)。根据 \(l\) 和 \(r\) 的最高位情况进行分类讨论：
- 若 \(l = 0\)，则区间包含 \(0\)，且每个数自身 AND 得到本身，故能构造出 \(0\) 到 \(r\) 的所有数，答案为 \(r+1\)。
- 若 \(l\) 和 \(r\) 的最高位相同，则区间所有数在该位均为 \(1\)，任何 AND 结果该位也为 \(1\)，无法得到 \(0\)，答案为 \(0\)。
- 若 \(r\) 的最高位比 \(l\) 的最高位至少高两位，则可以构造出 \(0\) 到 \(r\) 的所有数，答案为 \(r+1\)。
- 若 \(r\) 的最高位恰好比 \(l\) 的最高位高一位，则记 \(A = r - 2^{\text{highbit}(r)}\)，以及 \(low\_l\) 为 \(l\) 去掉从最高位开始连续的 \(1\) 右侧部分后得到的值（即保留最高位及其后的连续 \(1\)，后面全置 \(0\)）。若 \(low\_l \le A+1\)，则可以构造出 \(0\) 到 \(r\) 的所有数，答案为 \(r+1\)；否则答案为 \(A+1\)。
代码
点击查看代码
void solve() {
int l, r;
cin >> l >> r;
if (l == 0) {
cout << r + 1 << endl;
return;
}
int b1 = 31 - __builtin_clz(l);
int b2 = 31 - __builtin_clz(r);
if (b1 == b2) {
cout << 0 << endl;
return;
}
if (b2 >= b1 + 2) {
cout << r + 1 << endl;
return;
}
int ans = r - (1 << b2);
int p = b1;
while (p >= 0 && (l >> p) & 1) p--;
int L;
if (p < 0) L = l;
else L = l & (~((1 << (p + 1)) - 1));
if (L <= ans + 1) cout << r + 1 << endl;
else cout << ans + 1 << endl;
}
K. Constructive
题意：
给定正整数 \(n\)，构造长度为 \(n\) 的正整数数组，满足：元素互不相同，且所有元素的乘积等于所有元素的和。如果存在，输出字典序最小的解；否则报告无解。
思路：
当 \(n=1\) 时，数组 \([1]\) 满足条件。
当 \(n=3\) 时，数组 \([1,2,3]\) 满足条件。
对于其他 \(n\)，可以证明不存在满足条件的数组（\(n=2\) 时无解；\(n \ge 4\) 时，数组的积大于数组的和）。
代码
点击查看代码
void solve() {
int n;
cin>>n;
if(n==1){
cout<<"YES\n1\n";
}else if(n==3){
cout<<"YES\n1 2 3\n";
}else{
cout<<"NO\n";
}
}
L. Need Zero
题意：
给定一个正整数 n，你需要选择一个正整数 x，使得 n*x 的个位数是 0。操作必须恰好执行一次。求最小的 x。
思路：
要使 n*x 的个位为 0，即 n*x 是 10 的倍数。由于 10=2*5，考虑 n 是否被2，5整除，对应结果输出即可。
代码
点击查看代码
void solve() {
int n;
cin>>n;
if(n%10==0){
cout<<1<<endl;
}else if(n%2==0){
cout<<5<<endl;
}else if(n%5==0){
cout<<2<<endl;
}else{
cout<<10<<endl;
}
}
浙公网安备 33010602011771号