第十七届蓝桥杯国赛C++ B组 个人题解+考场思路复盘及备赛经验
文章目录
说明:官方暂未发布正式题目,以下基于现有题目回忆与洛谷测试数据整理,部分题目仅给出考场暴力做法,完整正解后续补充更新。
【2026.8.5更新H题正解】【2026.8.6更新E题正解】
试题A:玩具青蛙(5分)
考场思路
现场通过打表全部数据快速发现规律:
n=1时和为4
n=2时和为7
n=3时和为10

规律: x + y = 3 n + 1 x+y = 3n + 1 x+y=3n+1,代入 n = 2026 n=2026 n=2026 直接计算出结果。
代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
int tmp=1;
for(int i=1;i<=10;i++){
if(i==1)tmp=3;
else tmp*=(2*i+1);
int x=0,y=tmp;
for(int j=1;j<=i;j++){
x+=tmp/((2*j-1)*(2*j+1));
}
int d=__gcd(x,y);
x/=d,y/=d;
cout<<x+y<<' ';
}
return 0;
}
复盘
可用裂项相消证明,打表快速找规律
试题B:生成派生码(5分)
赛后补题思路(分类讨论)
基础码覆盖1-8位,插入后派生码位数为2-9位,按位数分段计算:
2位 ~ 8位派生码:逆向思维:任意一个 2 位到 8 位的正整数,都一定能由某个基础码插入一位得到
数量为:
90+900+9000+⋯+90000000
即:
99999990
9位派生码
基础码最大是 20260606,所以 8 位基础码范围是:
10000000∼20260606
我们把 8 位基础码分成两段讨论。
一:基础码以 1 开头
10000000∼19999999
分两种情况:
如果插入的位置不在最左边,那么生成的 9 位数一定以 1 开头
如果插入的位置在最左边,那么生成的 9 位数第二位一定是 1
所以,以 1 开头的基础码,可以生成所有满足下面条件之一的 9 位数:
第一位是 1
第二位是 1
第一位是 1 的 9 位数有:
100000000
第二位是 1,但第一位不是 1 的 9 位数有:
8×10000000=80000000
所以这一部分共有:
100000000+80000000=180000000
二:基础码以 2 开头
剩下的基础码范围是:
20000000∼20260606
可直接使用set暴力算,并且注意与第一部分去重
代码
#include<bits/stdc++.h>
using namespace std;
int main() {
set<int>st;
for(int i=20000000;i<=20260606;i++){
string s=to_string(i);
//枚举插入位置
for(int pos=0;pos<=8;pos++){
//枚举插入的数字
for(int j=0;j<=9;j++){
//跳过前导零
if(pos==0&&j==0)continue;
string tmp="",ss=to_string(j);
tmp+=s.substr(0,pos);
tmp+=ss;
if(pos!=8)tmp+=s.substr(pos);
// 去重
if(tmp[0]=='1'||tmp[1]=='1') continue;
st.insert(stoll(tmp));
}
}
}
cout<<st.size()<<'\n';
cout<<st.size()+99999990+180000000;
return 0;
}

复盘
考场没来得及细看,赛后发现是「大范围分类计数 + 小范围暴力去重」,属于技巧型题目。
试题C:奇偶校验排列(10分)
考场思路
默认首位放1(奇数),根据01串推导每个位置的奇偶性,再依次填入最小可用数字。只通过了部分测试点(洛谷过了85%),忽略了首位必须为偶数的特殊情况。
正确思路
根据差的奇偶性确定两数奇偶性,当首位奇偶性确定后,整个排列的奇偶序列唯一确定。
分别假设首位为1、首位为2
都不满足 → 输出-1
仅一种满足 → 采用该方案
都满足 → 优先选择1开头(字典序更小)
确定奇偶序列后,贪心填数:每个位置按顺序放数,即可得到字典序最小排列。
代码
#include<bits/stdc++.h>
using namespace std;
int n;
string s;
bool check(int x, vector<int>& ans) {
ans[0] = x;
for (int i = 1; i < n; ++i) {
if (s[i-1] == '1') ans[i] = ans[i-1] ^ 1;
else ans[i] = ans[i-1];
}
int cnt1 = 0, cnt0 = 0;
for (int x : ans) x == 1 ? cnt1++ : cnt0++;
int real1 = (n + 1) / 2, real0 = n / 2;
return cnt1 == real1 && cnt0 == real0;
}
int main() {
cin>>n>>s;
vector<int>ans(n);
bool ok1 = check(1, ans);
bool ok0 = check(0, ans);
if (!ok1 && !ok0) {
cout << -1 << endl;
return 0;
}
ok1 ? check(1, ans) : check(0, ans);
int num1 = 1, num0 = 2;
for (int i = 0; i < n; ++i) {
if (ans[i] == 1) {
cout << num1 << " ";
num1 += 2;
} else {
cout << num0 << " ";
num0 += 2;
}
}
return 0;
}
复盘
漏了偶数开头的情况会丢失测试点,构造排列类题目优先贪心策略,奇偶性转化是解题关键。
试题D:灯带修补(10分)
考场思路
暴力枚举所有切口与所有子段,用前缀和预处理不稳定对数量,复杂度 O ( N 2 ) O(N^2) O(N2),能通过约60%数据(洛谷过75%)
暴力代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m, k;
cin >> n >> m >> k;
vector<int> a(2 * n);
for (int i = 0; i < n; ++i) {
cin >> a[i];
a[i + n] = a[i]; // 破环为链
}
vector<int> b(2 * n, 0);
for (int i = 0; i < 2 * n - 1; ++i) {
if (abs(a[i] - a[i+1]) > k) b[i] = 1;
}
int ans = 1;
for (int i = 0; i < n; ++i) {
int sum = 0;
for (int j = i; j < i + n - 1; ++j) {
sum += b[j];
if (sum > m) break;
ans = max(ans, j - i + 2);
}
}
cout << ans << endl;
return 0;
}
正解思路(双指针/滑动窗口)
不稳定对计数非负,满足滑动窗口单调性:右指针右移时不稳定对数量只增不减,左指针右移时只减不增。
破环为链后,用滑动窗口维护区间内不稳定对数量≤M,且窗口长度不超过N,时间复杂度
O
(
N
)
O(N)
O(N),可通过全部测试用例。
#include<bits/stdc++.h>
using namespace std;
const int N=4e5+9;
int n,m,k;
int a[N];
int cnt,ans;
signed main()
{
cin>>n>>m>>k;
for(int i=0;i<n;i++)
cin>>a[i];
for(int i=0;i<n;i++)
a[n+i]=a[i];
int p=0;
int q=0;
while(q<2*n)
{
q++;
if(abs(a[q]-a[q-1])>k)
cnt++;
while(cnt>m)
{
p++;
if(abs(a[p]-a[p-1])>k)
cnt--;
}
ans=max(ans,q-p+1);
}
if(ans>n)
cout<<n;
else
cout<<ans;
return 0;
}
复盘
经典环形子数组最值问题,破环为链是常规操作,可用双指针优化,暴力只能拿到一半分数。
试题E:密码提取(15分)
考场思路
暴力枚举所有子串,转换为数值统计出现次数,预处理前缀和数组快速回答查询。子串数值超过查询上限1e5时提前终止,能过约80%数据。(洛谷过90%)
暴力代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int N, M;
cin >> N >> M;
string S;
cin >> S;
const int MAXV = 100000;
vector<long long> cnt(MAXV + 1, 0);
// 双重循环枚举所有子串,使用 substr + stoll
for (int i = 0; i < N; ++i) {
for (int len = 1; i + len <= N; ++len) {
string sub = S.substr(i, len);
// 避免转换超大数值(位数超过6位一定大于100000)
long long val = stoll(sub);
if (val > MAXV) break;
cnt[val]++;
}
}
vector<long long> pref(MAXV + 2, 0);
for (int i = 0; i <= MAXV; ++i) {
pref[i+1] = pref[i] + cnt[i];
}
for (int q = 0; q < M; ++q) {
int l, r;
cin >> l >> r;
if (l > MAXV) {
cout << 0 << '\n';
} else {
if (r > MAXV) r = MAXV;
cout << pref[r+1] - pref[l] << '\n';
}
}
return 0;
}
正解思路
题目要求统计所有非空连续子串对应的数值,并回答多个区间查询。
字符串中只有数字 0~9,但数值范围限制在 [0, 100000],因此我们只需统计数值不超过 100000 的子串个数(更大的数值不会影响查询)。
直接枚举所有子串(O(N²))不可行,但观察性质:
- 全零子串的数值一定为
0,连续的一段0内部所有子串都贡献给数值0。 - 含有非零数字的子串,其数值由第一个非零数字开始的一段决定;该非零数字前面连续的
0可以作为前导零附加到子串前面,从而产生多个起止位置不同但数值相同的方案。
所以我们可以把字符串划分成若干“连续 0 + 一个非零数字 + 后续数字”的片段,分别统计。
正解代码
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e6+10;
int pre[N],a[N];
signed main(){
int n,m;
string s;
cin>>n>>m>>s;
s="#"+s;
int len=0;//统计连续0的数量
for(int i=1;i<=n;i++){
if(s[i]=='0')len++;
else{
a[0]+=len*(len+1)/2;
string tmp="";
for(int j=i;j<=n;j++){
tmp+=s[j];
int x=stoll(tmp);
if(x>1000000)break;
a[x]+=len+1;
}
len=0;
}
}
a[0]+=len*(len+1)/2;
for(int i=1;i<=N;i++)pre[i]=pre[i-1]+a[i];
while(m--){
int l,r;
cin>>l>>r;
if(l<1)cout<<pre[r]-pre[0]+a[0]<<'\n';
else cout<<pre[r]-pre[l-1]<<'\n';
}
return 0;
}
代码分步讲解
1. 变量与读入
int n,m;
string s;
cin>>n>>m>>s;
s = "#" + s; // 使下标从1开始,方便遍历
int len = 0; // 记录当前连续 '0' 的个数
a[x] 表示数值 x 出现的方案总数;pre[i] 为 a[1..i] 的前缀和(注意 pre[0]=0,不包含 a[0])。
2. 统计所有子串数值
遍历字符串(从下标 1 到 n):
情况一:遇到 '0'
if (s[i]=='0') len++;
累积连续 0 的长度。
情况二:遇到非零数字 s[i](1~9)
第一步:处理之前累积的连续 0 段
a[0] += len * (len + 1) / 2;
长度为 len 的连续 0 段,内部任取非空连续子串,一共 len*(len+1)/2 个,它们的数值都为 0。
例如 "000" → 子串:"0"*3、"00"*2、"000"*1,共 6 个。
第二步:处理以当前非零数字开头的所有扩展子串
string tmp = "";
for (int j = i; j <= n; j++) {
tmp += s[j];
int x = stoll(tmp);
if (x > 1000000) break; // 超过数组范围或查询上限,停止扩展
a[x] += len + 1;
}
- 从
i开始,不断向后取字符组成临时字符串tmp,转成整数x。 - 由于前面有
len个连续的0,我们可以选择附加0~len个前导零到当前子串前面,得到len+1种不同的截取方案,但数值都是x,所以a[x]加上len+1。 - 当
x > 1000000时,继续扩展数值只会更大(非零数字开头,且后续全是数字),已经超出查询范围,直接跳出循环。
第三步:重置 len = 0
因为当前非零数字打断了连续的 0。
3. 处理末尾剩余的连续 0
遍历结束后,若 len > 0,说明字符串以若干个 0 结尾,同样累加:
a[0] += len * (len + 1) / 2;
4. 前缀和与查询
for (int i=1; i<=N; i++) pre[i] = pre[i-1] + a[i];
pre[i] 统计数值 1..i 的方案总数(不包含 0)。
对于每个询问 [l, r]:
- 若
l == 0,答案应为a[0] + (a[1]+...+a[r]) = a[0] + pre[r]。
你的代码中if(l<1)判断l=0的情况,输出pre[r] - pre[0] + a[0],等价于pre[r] + a[0],正确。 - 若
l > 0,直接输出pre[r] - pre[l-1]。
复杂度分析
- 时间:每个非零数字向后扩展的子串长度最多为
7(因为1000000是 7 位),所以总扩展次数约为O(6N),即O(N)级别,可满足N≤10^6。 - 空间:数组大小
1e6+10足够覆盖100000的查询范围
复盘
考场10分钟速通暴力代码,【2026.8.6补题】,利用连续零段和非零数字分段将子串计数转化为零段内部子串贡献 0和以非零数字开头的扩展子串 + 前导零方案数,再通过前缀和实现快速区间查询。
试题F:Token词元(15分)
考场思路(正解)
两遍贪心扫描即可:
- 先计算每个位置的 c[i]。
- 初始化 a a a 数组全为1。
- 从左到右遍历:若 c[i]>c[i-1],则 a[i]=a[i-1]+1
- 从右到左遍历:若 c[i]>c[i+1],则 a[i]=max(a[i],a[i+1]+1)
- 累加 a a a 数组得到最小总和。
代码
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> p(n);
for (int i = 0; i < n; ++i) cin >> p[i];
vector<int> c(n, 0);
for (int i = 0; i < n; ++i) {
if (i > 0 && p[i-1] < p[i]) c[i]++;
if (i < n-1 && p[i+1] < p[i]) c[i]++;
}
vector<int> a(n, 1);
for (int i = 1; i < n; ++i) {
if (c[i] > c[i-1]) a[i] = a[i-1] + 1;
}
for (int i = n-2; i >= 0; --i) {
if (c[i] > c[i+1]) a[i] = max(a[i], a[i+1] + 1);
}
long long sum = 0;
for (int x : a) sum += x;
cout << sum << endl;
return 0;
}
复盘
简单思维题
试题G:实验数据(20分)
考场思路
用前缀和暴力计算,单点修改时更新前缀数组, O ( n ) O(n) O(n) 修改、 O ( 1 ) O(1) O(1) 查询,能通过约50%数据。
暴力代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
int ksm(int a , int b) {
int res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
int f(int x) {
return ksm(x, MOD - 2);
}
signed main() {
int n, m;
cin >> n >> m;
vector<int> a(n + 1);
vector<long long> pre(n + 1, 0); // 前缀和数组
for (int i = 1; i <= n; ++i) {
cin >> a[i];
pre[i] = (pre[i-1] + a[i]) ;
}
while (m--) {
int op;
cin >> op;
if (op == 1) {
int l, r;
cin >> l >> r;
int sum = (pre[r] - pre[l-1] + MOD) % MOD;
int len = r - l + 1;
int avg = sum * f(len) % MOD;
// 计算方差
int var = 0;
for (int i = l; i <= r; ++i) {
int tmp = (a[i] - avg + MOD) % MOD;
var = (var + tmp * tmp) % MOD;
}
cout << avg << " " << var << "\n";
} else {
int k, x;
cin >> k >> x;
int m=x-a[k];
// 更新前缀和
for (int i = k; i <= n; ++i) {
pre[i]+=m;
}
a[k] = x;
}
}
return 0;
}
正解思路
线段树
复盘
未系统学习线段树只能拿暴力分,考场10分钟速通暴力代码
试题H:方和质数(20分)
考场思路
暴力遍历 L L L 到 R R R 的每个数,试除法判断质数,同时计算数位和判断是否为完全平方数,计数查找第 K K K 个。能通过约30%+数据(洛谷70%)
暴力代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
bool is_prime(ll n) {
if (n < 2) return 0;
for (int i = 2; i <= n/i; i++) {
if (n % i == 0) return 0;
}
return 1;
}
int digit_sum(ll x) {
int s = 0;
while (x) {
s += x % 10;
x /= 10;
}
return s;
}
bool ck(int x) {
int r = sqrt(x);
return r * r == x;
}
int main() {
ll L, R;
int K;
cin >> L >> R >> K;
int cnt = 0;
for (ll x = L; x <= R; ++x) {
if (ck(digit_sum(x)) && is_prime(x)) {
++cnt;
if (cnt == K) {
cout << x << '\n';
return 0;
}
}
}
cout << "-1\n";
return 0;
}
正解思路
先用线性筛(或埃氏筛)出[2,根号R]中所有质数
然后枚举筛出的质数,标记[L,R]中所有合数
最后枚举[L,R]即可
实现细节
线性筛时标记素数应防止下标越界超过1e9
标记合数时,枚举每个质数在[L,R]中起始位置应为
first=max(p*p,((L-1)/p+1)*p);
前者为线性筛定义的p筛出的最大合数,后者即为ceil(L/p)*p
防止标记合数越界,左平移L
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e7 + 9;
vector<int> primes;
bool st[N]; // 标记素数
void getp(int x) { // 线性筛模板
for (int i = 2; i <= x; i++) {
if (!st[i]) primes.push_back(i);
for (int t : primes) {
if (i * t > x) break; // 避免越界
st[i * t] = 1;
if (i % t == 0) break;
}
}
}
bool ck(ll x) { // 检查这个数的数位和是否为完全平方数
int sum = 0;
while (x) {
sum += x % 10;
x /= 10;
}
int s = sqrt(sum);
return s * s == sum;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
ll l, r;
int k;
cin >> l >> r >> k;
if (r < 2) {
cout << -1 << '\n';
return 0;
}
getp((int)sqrt(r));
int len = r - l + 1;
vector<char> vis(len, 0); // 使用char或bool标记合数
for (int t : primes) {
ll first = ((l - 1) / t + 1) * t; // ceil(L/p)*p
ll start = max((ll)t * t, first);
for (ll i = start; i <= r; i += t) {
vis[i - l] = 1; // 防越界
}
}
int cnt = 0;
for (ll i = max(2LL, l); i <= r; i++) {
if (vis[i - l]) continue;
if (ck(i)) {
cnt++;
if (cnt == k) {
cout << i << '\n';
return 0;
}
}
}
cout << -1 << '\n';
return 0;
}
复盘
考场10分钟速通暴力代码,【2026.8.5补题】该题属于数论+思维题,做法巧妙
试题I:货架换签(25分)
考场思路
无思考,直接输出原字符串,洛谷过10%的分。
复盘
本次国赛的难题,后续补题再更新,优先保证前面基础题拿分,战略性骗分
试题J:运动会(25分)
考场思路
DFS枚举每个班级的选取人数(0 ~ min(a[i], K)),累加组合数,能通过约30%的小数据。(洛谷过25%)
暴力代码
#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MOD = 998244353;
const int MAXA = 20; // 数据范围小
long long C[MAXA + 1][MAXA + 1];
void init() {
for (int i = 0; i <= MAXA; ++i) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; ++j)
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
int n, m, k;
vector<int> a;
long long ans = 0;
void dfs(int idx, int num, int cnt) {//下标 选的总人数 每个班选的人数
if (num > m) return;
if (idx == n) {
if (num == m) ans = (ans + cnt) % MOD;
return;
}
int mi = min(a[idx], k);
for (int x = 0; x <= mi; ++x) {
dfs(idx + 1, num + x, cnt * C[a[idx]][x] % MOD);
}
}
signed main() {
init();
cin >> n >> m >> k;
a.resize(n);
for (int i = 0; i < n; ++i) cin >> a[i];
dfs(0, 0, 1);
cout << ans << '\n';
return 0;
}
复盘
DFS+数论
备赛心得与后续规划
备赛过程
具体
26秋季开学就把牛客周赛、月赛当成了固定训练。周赛练短平快的解题节奏,强迫自己快速读题、想思路、写代码,改掉了以前磨磨蹭蹭、一道题抠半小时的坏习惯;月赛难度更高,用来检验专题学习效果,每次赛后都把不会的题对应的知识点补一遍。顺便写了6套秋季基础训练营。同期也同步打洛谷月赛,不同 OJ 的出题风格差异很大,多接触能避免思维固化,也能接触到更多题型变种。
寒假系统过算法基础:把二分,前缀和,DP、最短路、数论、图论、字符串,并查集,最优字段和等这些核心专题都认真学了一遍,每个专题刷 10~20 道题,确保基础算法都能熟练写出来。跟着6套牛客寒假算法训练营训练。
专项练技巧:专门练打表找规律、数学推导;编程题练骗分、写暴力拿部分分,确保不会的题也能抠点分下来。
春季开学之后重点打了两场正式比赛,用来对标自己的真实水平,也为蓝桥杯国赛攒赛场心态。
一场是 PTA 团体程序设计天梯赛,赛前集中刷了 PTA 官网的真题集,最后拿到了团体国家级三等奖。这场比赛主打模拟,树,最短路,并查集等也把我基础算法的代码实现练得更稳。(赛场具体思路与完整备赛经验后续单独更新)
另一场是 CCPC 邀请赛(可看我另一篇题解赛场思路与备赛经验),最终拿到了邀请赛铜牌。和蓝桥杯相比,CCPC 题型更灵活、码量更大,这场比下来明显感受到了和更高水平选手的差距,也学到了正式大赛的时间分配和心态调整方法,回来之后针对性补了码力和难题思维。
正式国赛前一个月,就不再乱打散赛了,完全回归蓝桥杯的出题风格和评分逻辑。主要刷历年真题和整理的专项题单,按题型分类突破;同时做模拟赛,练考场节奏和时间分配,具体的模拟赛清单和专项题单整理,在下面。
上考场之后明显稳了很多,最后拿了国二,也算对得起一年的努力。
整体感悟与建议
做题顺序远比死磕难题重要:蓝桥杯国赛不是按难度排序的,一定要先通览全卷,把会做的、好拿分的先写完,再去啃难题。第一次参赛就是吃了顺序做题的亏,白白丢了很多基础分。
暴力骗分是国赛底线:哪怕不会正解,也要把暴力写出来拿部分分。国赛很多题暴力就能拿 30~50 分,几道题加起来差距就拉开了,国优和国二往往就差这十几分的暴力分。
以赛代练提升非常快:只闷头刷题很容易陷入舒适区,定期打周赛、月赛能强制自己暴露问题。不用太在意排名,每次赛后把不会的知识点补上,打十场下来进步会非常明显。
基础算法是拿奖核心:蓝桥杯国赛 80% 的分数都是基础算法的变形,二分,前缀和,DP、最短路、数论、图论、字符串,并查集,最优字段和、模拟,把这些练熟,拿国二真的不难,压轴题可以适当放弃,性价比不高。
最好的备考资料:专项题单
省赛阶段:刷完4套模拟题+部分真题,跟着苯环哥哥的省赛题单系统训练,赛后认真补完了所有错题。
⌬杯”蓝桥杯大赛省赛模拟赛:https://ac.nowcoder.com/acm/contest/130222
蓝桥杯多校模拟赛1:https://ac.nowcoder.com/acm/contest/130226
蓝桥杯多校模拟赛2:https://ac.nowcoder.com/acm/contest/132303
洛谷蓝桥杯省赛模拟赛 2026:https://www.luogu.com.cn/contest/314564
⌬哥哥省赛题单(50题):https://www.luogu.com.cn/training/743042
国赛阶段:刷完⌬省赛题单后跟进⌬国赛题单,打了1套洛谷国赛模拟赛,日常保持刷题节奏积累手感,强化练习了弱项dp(结果没用到)。
⌬哥哥国赛题单(50题刷完):https://www.luogu.com.cn/training/759988
洛谷蓝桥杯国赛模拟赛 2026(34题写了10道左右):https://www.luogu.com.cn/contest/326698
成绩与感受
估分45左右
这是第二次参加蓝桥杯,第一次拿到国优,本次取得国二成绩已经达到预期,在学校可以拿到保研加分。整体发挥中规中矩,基础题基本都拿到分数,难题也骗到了部分分,符合平时训练水平。
后续规划
补完力所能及题目的正解,更新题解。
明年继续保持刷题节奏,多打模拟赛适应考场节奏,后续会持续更新题解与备赛经验。
更多推荐


所有评论(0)