提供 2026 牛客寒假算法基础集训营 1 的完整题解。内容涵盖 A 至 L 题，涉及概率计算、逆元、贪心策略、二分查找、位运算及动态规划等核心算法。A 题利用状态压缩计算数字显示概率；B 题通过排序与组合数学优化得分；D 题二分答案配合贪心模拟染色；H 题使用前缀和优化 DP 计数；I 题结合位运算构造求解 MEX 最大值。所有代码基于 C++ 实现，已修正格式并去除冗余信息。
有八个独立的数位显示器，每个显示器的每个二极管被点亮的概率为 pi，二极管之间互相独立，显示器之间也相互独立。求分别显示出两个四位合法数字，且数字之和等于输入的常数 C 的概率。
需满足以下条件：
由于显示器完全独立，可先计算每个显示器表示 0-9 的概率，进而通过独立概率乘积计算特定数字的概率。枚举 0 到 C 的所有数字组合，计算概率和。
计算 0-9 的概率需使用状态压缩技巧。将需要点亮的灯管定为 1，不需要的定为 0，预存 0-9 的二进制状态表。
整个过程涉及取模运算，除法需用乘法逆元代替。
在模数 m 为质数且 b 不是 m 倍数的情况下，根据费马小定理： a / b mod m = a * (b^(m-2)) mod m 即 1/b = b^(m-2) mod m。这避免了小数精度问题。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod = 998244353;
int c;
int p[8];
int S[10];
void init() {
S[0] = (1 << 0) | (1 << 1) | (1 << 2) | (1 << 4) | (1 << 5) | (1 << 6);
S[1] = (1 << 2) | (1 << 5);
S[2] = (1 << 0) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 6);
S[3] = (1 << 0) | (1 << 2) | (1 << 3) | (1 << 5) | (1 << 6);
S[4] = (1 << 1) | (1 << 2) | (1 << 3) | (1 << 5);
S[5] = (1 << 0) | (1 << 1) | (1 << 3) | (1 << 5) | (1 << 6);
S[6] = (1 << 0) | (1 << 1) | (1 << 3) | (1 << 4) | (1 << 5) | (1 << 6);
S[7] = (1 << 0) | (1 << 2) | (1 << 5);
S[8] = (1 << 0) | (1 << 1) | (1 << 2) | (1 << 3) | (1 << 4) | (1 << 5) | (1 << 6);
S[9] = (1 << 0) | (1 << 1) | (1 << 2) | (1 << 3) | (1 << 5) | (1 << 6);
}
int ksm(int a, int b, int mod) {
int ans = 1;
a = a % mod;
for (; b; b >>= 1) {
if (b & 1) ans = (ans * a) % mod;
a = (a * a) % mod;
}
return ans;
}
int inv100 = ksm(100, mod - 2, mod);
void solve() {
cin >> c;
for (int i = 0; i < 7; i++) {
cin >> p[i];
p[i] = (p[i] * inv100) % mod;
}
vector<int> digit(10, 1);
for (int i = 0; i < 10; i++) {
for (int j = 0; j < 7; j++) {
if ((S[i] >> j) & 1) {
digit[i] = (digit[i] * p[j]) % mod;
} else {
int not_p = (1 - p[j] + mod) % mod;
digit[i] = (digit[i] * not_p) % mod;
}
}
}
auto calc = [&](int x) -> int {
if (x == 0) {
return (((digit[0] * digit[0]) % mod) * digit[0]) % mod * digit[0] % mod;
} else {
int ans = 1, len = 0;
int tmp = x;
while (tmp > 0) {
ans = (ans * digit[tmp % 10]) % mod;
len++;
tmp /= 10;
}
for (int i = 0; i < 4 - len; i++) {
ans = (ans * digit[0]) % mod;
}
return ans;
}
};
int ans = 0;
for (int a = 0; a <= c; a++) {
int b = c - a;
ans = (ans + calc(a) * calc(b) % mod) % mod;
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
init();
int t;
cin >> t;
while (t--) solve();
return 0;
}
两人各持 n 张牌，共 2n 张牌构成排列。游戏过程为比较双方当前最大牌，大者得分并弃牌，小者保留。小苯可重排自己的牌以最大化得分。
只要手中大于对方最小值的牌都可以得分。策略是将大于对方最小值的牌排在前方，小于对方最小值的牌排在后方。方案数为两个组合数相乘。
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 2e5 + 5;
const int mod = 998244353;
int a[N], n, b[N];
long long fact[N];
void preprocess() {
fact[0] = 1;
for (int i = 1; i <= N; ++i) {
fact[i] = fact[i - 1] * i % mod;
}
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i];
for (int i = 1; i <= n; i++) cin >> b[i];
sort(b + 1, b + 1 + n);
int k = 0;
for (int i = 1; i <= n; i++) {
if (a[i] > b[1]) k++;
}
long long ans = fact[k] * fact[n - k] % mod;
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
preprocess();
int t;
cin >> t;
while (t--) solve();
return 0;
}
简单题目，直接输出答案即可。
给定序列包含白色和黑色数字。初始可选择 k 个白数字染红，每秒红色数字会将其右侧 x 个数字里的白色数字染红。求将所有白色数字染红的最短时间。
答案具有单调性，可二分时间 x。使用 check 函数模拟染色过程，从左往右贪心，维护已染色数量和最远覆盖位置。注意跳过黑色方块。
#include <bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int a[N];
int pre[N];
void solve() {
int n, k;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a[i];
int now = 0;
if (a[i]) now = min(i + a[i] + 1, n);
pre[i + 1] = max(now, pre[i]);
}
auto check = [&](int x) {
int cur = 0;
while (cur < n && !a[cur]) cur++;
for (int i = 0; i < k && cur < n; i++) {
cur++;
for (int j = 0; j < x && pre[cur] > cur; j++) {
cur = pre[cur];
}
while (cur < n && !a[cur]) cur++;
}
return cur == n;
};
int lo = 0, hi = n;
while (lo < hi) {
int x = (lo + hi) / 2;
if (check(x)) hi = x;
else lo = x + 1;
}
if (lo == n) lo = -1;
cout << lo << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin >> T;
while (T--) solve();
return 0;
}
有 n 个小方块，第 i 个数字为 ai，另有一个万能方块数字为 1。可将万能方块从左侧插入，其余后移，末尾变为新万能方块。最大化第一个方块数字 + 万能方块数字。
万能方块与第一个数字相邻。遍历所有相邻数字对，找到最大和即可。
给定区间 [L, R]，定义 f(x) 为 x 十进制翻转后去除前导 0 的值。求区间内 f(x) 的最大值。
#include <bits/stdc++.h>
using namespace std;
#define int long long
void solve() {
string L, R;
cin >> L >> R;
int nl = L.size(), nr = R.size();
int l = stoll(L), r = stoll(R);
string t = "1";
for (int i = 0; i < nr - 1; i++) t += '0';
if (R == t) {
if (L == R) cout << 1 << '\n';
else cout << r - 1 << '\n';
return;
}
if (nl < nr) {
L = t;
L.back() += 1;
assert(L.size() == R.size());
}
string ans;
int k = -1;
for (int i = 0; i < nr; i++) {
if (L[i] != R[i]) {
k = i;
break;
}
}
if (k == -1) {
ans = L;
while (ans.size() > 1 && ans.back() == '0') ans.pop_back();
reverse(ans.begin(), ans.end());
} else {
bool flag = 1;
for (int i = k + 1; i < nr; i++) {
ans += '9';
flag &= (R[i] == '9');
}
ans += (R[k] - !flag);
for (int i = k - 1; i >= 0; i--) ans += L[i];
}
cout << ans << '\n';
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
给定序列 a，问有多少种方式将加号替换为位或运算符，使得运算式值不变。
使用 DP 结合前缀和优化。记录上一次出现某位的索引，利用前缀和快速转移。
#include <bits/stdc++.h>
using namespace std;
const int mod = 998244353;
void solve() {
int n;
cin >> n;
vector<int> a(n + 1);
int lst = 0;
vector<int> pre(n + 1);
for (int i = 1; i <= n; i++) {
cin >> a[i];
pre[i] = lst;
if (a[i] > 0) lst = i;
}
vector<int> dp(n + 2);
vector<int> s(n + 2);
dp[1] = 1;
s[1] = 1;
for (int i = 1; i <= n; i++) {
int j = i;
int val = 0;
while (j > 0 && (val & a[j]) == 0) {
val |= a[j];
j = pre[j];
}
dp[i + 1] = (s[i] - s[j] + mod) % mod;
s[i + 1] = (s[i] + dp[i + 1]) % mod;
}
cout << dp[n + 1] << '\n';
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
给定区间 [l, r]，可选若干数字进行 AND 操作加入集合 S，求 S 的 MEX 最大值。
#include <bits/stdc++.h>
using namespace std;
void solve() {
int l, r;
cin >> l >> r;
auto highbit = [&](int x) {
for (int i = 32; i >= 0; i--) {
if ((x >> i) & 1) return i;
}
return -1;
};
int b1 = highbit(l), b2 = highbit(r);
if (b1 == -1) {
cout << r + 1 << '\n';
} else if (b1 == b2) {
cout << 0 << '\n';
} else if (b2 > b1 + 1) {
cout << r + 1 << '\n';
} else {
int ans = r - (1LL << b2) + 1;
int L = 0;
for (int i = b1; i >= 0; i--) {
if (!((l >> i) & 1)) break;
else L |= (1 << i);
}
if (L <= ans) ans = r + 1;
cout << ans << '\n';
}
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int t;
cin >> t;
while (t--) solve();
return 0;
}
构造字典序最小的长度为 n 的正整数数组，满足互不相同且和等于积。
经尝试发现仅 n=1 和 n=3 符合。
简单题目，直接输出答案即可。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online