真题卷001——算法备赛

蓝桥杯2024年C/C++B组国赛卷

1.合法密码

问题描述

小蓝正在开发自己的OJ网站。他要求用户的密码必须符合一下条件：

1. 长度大于等于8小于等于16
2. 必须包含至少一个数字字符和至少一个符号字符

请计算一下字符串，有多少个子串可以当作合法密码。字符串为：

kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th

原题链接

思路分析

这题打卡题还是简单的，直接按题意暴力枚举判断即可。题目要求子串需要包含一个符号字符，而原字符中符号只有'#'，只需判断枚举的子串是否包含'#'即可。

代码

#include <bits/stdc++.h>
using namespace std;
bool check(string k){bool isNum=false,isSymbol=false;for(int i=0;i<k.size();i++){if(k[i]=='#') isSymbol=true;else if(k[i]>='0'&&k[i]<='9') isNum=true;}return isNum&&isSymbol;
}
int main()
{string s;     s="kfdhtshmrw4nxg#f44ehlbn33ccto#mwfn2waebry#3qd1ubwyhcyuavuajb#vyecsycuzsmwp31ipzah#catatja3kaqbcss2th";int n=s.size();int ans=0;for(int i=0;i<=n-8;i++){for(int j=8;j<=16;j++){if(n-i>=j){string sub=s.substr(i,j);if(check(sub)) ans++;}else break;}}cout<<ans;return 0;
}

2.选数概率

问题描述

一个数组中有a个1，b个2，和c个3.
$$设p_{i,j}表示从数组中随机取两个数，其中一个数为i，另一个数为j的概率。比如p_{1,2}=\frac{ab}{C_{(a+b+c)}^2}。$$

$$当a,b,c等于多少时，满足p_{1,2}=\frac{517}{2091},p_{2,3}=\frac{2632}{10455},p_{1,3}=\frac{308}{2091}，且a+b+c最小。题目保证最小的解是唯一的。$$

你需要提交一个a,b,c格式的字符串，例如a=12,b=34,c=54，那么你需要提交的字符串为12,34,56。

原题链接

思路分析
$$题目意思就是\frac{ab}{n}=\frac{517}{2091},\frac{bc}{n}=\frac{2632}{10455},\frac{ac}{n}=\frac{308}{2091}，求a，b，c的分别为多少时，a+b+c最小。$$
首先通分，将三个分数的分母都化为一个值，设三个分子分别为s1,s2,s3.
$$可以得到\frac{ab}{bc}=\frac{a}{c}=\frac{s1}{s2}，\frac{ac}{bc}=\frac{a}{b}=\frac{s3}{s2}$$
进而可得a:b:c=s3:s2:(s2s3)/s1化简得:a:b:c=s1s3:s1s2:s2s3，求出满足这个比值的最小的三个整数即可。设s1s3，s1s2，s2s3的公因数为d，对应的a，b，c就是s1*s3/d，s1*s2/d，s2*s3/d，要使a，b，c尽量小，d就要尽量大，求出最大公因数即可。

代码

#include <bits/stdc++.h>
using namespace std;
int main()
{int s1=517*5;int s2=2632;int s3=308*5;int d=gcd(s1*s3,gcd(s2*s3,s1*s2));cout<<s1*s3/d<<','<<s1*s2/d<<','<<s2*s3/d;return 0;
}

3.蚂蚁开会

问题描述

二维平面上有n只蚂蚁，每只蚂蚁有一条线段作为活动范围，第i只蚂蚁的活动范围的线段的两个端点为(x1,y1),(x2,y2)。现在考虑在这些线段的交点处设置会议中心，它们决定在所有交点为整点（x偏移量和y偏移量都是整数）的地方设置会议中心，问需要设置多少个会议中心？

数据规模

• n<=500
• 0<=x1,x2,y1,y2<=10000
• 任意蚂蚁的活动范围不会退化为一个点，不保证任意两条线段之间的交点数量有限

原题链接

思路分析

本题如果考虑直接求交点的方法，计算会非常繁琐，而且注意数据规模提示最后一个信息，说明两条线段可能重合，那么求交点就更难了。

重新仔细思考一下，其实可以考虑枚举整点的方式来统计是交点的整点数量。具体思路如下：

1. 根据每条直线，通过gcd将所有在该线段上的整点都添加进map
2. 统计map集合，所有出现两次以上的整点数量就是答案

根据数据规模信息，map可以存储点的进制哈希值。

时间复杂度O(nk)k为线段上整点的平均数，最坏的情况数量级在5*10^6左右。

代码

#include<bits/stdc++.h>
using namespace std;
int N = 10001;
int main() {ios::sync_with_stdio(0);cin.tie(0);int n; cin >> n;unordered_map<int, int>mp;for (int i = 0; i < n; i++) {int x1, y1, x2, y2;cin >> x1 >> y1 >> x2 >> y2;int xMin = min(x1, x2), xMax = max(x1, x2);int yMin = min(y1, y2), yMax = max(y1, y2);int d = gcd(xMax - xMin, yMax - yMin);int dx = (x2 - x1) / d, dy = (y2 - y1) / d;int x = x1, y = y1;for (int i = 0; i <= d; i++) {mp[x * N + y]++;x += dx;y += dy;}}int ans = 0;for (auto& [k, v] : mp) {if (v >= 2) ans++;}cout << ans;
}

4.立定跳远

问题描述

在运动会上，小明从数轴的原点开始向正方向立定跳远。项目设置了 n个检查点a1,a2,…, an 且 ai > ai-1 > 0。小明必须先后跳跃到每个检查点上且只能跳跃到检查点上。同时，小明可以自行再增加 m 个检查点让自己跳得更轻松。小明单次跳跃的最远距离达到L，并且学会一个爆发技能可以在运动会时使用一次，使用时可以在该次跳跃时的最远距离变为 2L。小明想知道，L的最小值是多少可以完成这个项目?

原题链接

思路分析

首先看到题目，是求最优值的问题，这类题常用的解法有1.动态规划，2.贪心，3.暴力模拟，4.二分答案+贪心判断。

在由构造过程推出答案不好做的时候，从答案倒推过程是个不错的选择，本题就是如此。由题给信息可知，增设的检查点越多，L就可以越小，反之，L越小，需要增设的检查点就要更多。问题具有单调性，可以二分猜答案x，再根据x贪心地判断该x需要的最少检查点是否大于m。最后那个最小的x就是正确答案。

现在考虑子问题，已知x，求最小的增设检查点数量。

枚举每个间距di（已知的相邻检查点间距离），如果di大于x，那肯定需要增设检查点，增设的数量最少的方案就是每隔x放一个，为：(di-1)/x，单次跳跃最远距离可以变为一次2*x，也就是可以少放置一个检查点。最小增设检查点数量就是cnt-1(cnt为实际放置的最少数量)，这个值为负数也没关系，最后只是拿来与m做比较。

代码

#include <bits/stdc++.h>
using namespace std;
int n,m;
vector<int>d;
bool check(int x){int cnt=0;for(int di:d){if(di>x){cnt+=(di-1)/x;}}if(cnt-1<=m) return true;return false;
}
int solve(){cin>>n>>m;d.resize(n);int l=1,r=0;int pre=0,next;for(int i=0;i<n;i++){cin>>next;d[i]=next-pre;pre=next;r=max(d[i],r);}while(l<r){int mid=(l+r)/2;if(check(mid)) r=mid;else l=mid+1;}return r;
}
int main()
{cout<<solve();return 0;
}

5.最小字符串

问题描述

给定一个长度为 N 且只包含小写字母的字符串 S，和 M个小写字母 c1,c2,…,c。

现在你要把 M 个小写字母全部插入到字符串 S 中，每个小写字母都可以插入到任意位置。请问能得到的字典序最小的字符串是什么?

原题链接

思路分析

字符串的字典序大小取决于靠前的字符的大小，越靠前的字符越小，字符串的字典序就越小。

先将M个字符统计到一个频数字典中，再贪心地枚举s中的每个字符ch，若能使当前的ch变得更小，那整个字符串的字典序就能更小。

依次将ch与频数字典中最小的字符t比较,只要t更小，就将s(s是t的频数)个t都插入到ch的位置。

注意：在插入s后，s的长度会改变，枚举指针i要调整。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{int n, m; cin >> n >> m;string s; cin >> s;vector<int>d(26);for (int i = 0; i < m; i++) {char ch; cin >> ch;d[ch - 'a']++;}int cnt = -1;while (cnt < 26) if (d[++cnt] != 0) break;for (int i = 0; i < s.size(); i++) {if (s[i] > 'a' + cnt) {s.insert(i, d[cnt], 'a' + cnt);i += d[cnt] - 1;while (cnt < 26) if (d[++cnt] != 0) break;if (cnt == 26) break;}}while (cnt < 26) {  //处理数据残留if (d[cnt] != 0) {s.insert(s.size(), d[cnt], 'a' + cnt);}cnt++;}cout << s;return 0;
}

6.数位翻转

蓝桥杯2024年国赛题

问题描述

小明创造了一个函数f(x)用来翻转x的二进制的数位（无前导0）。比如f(11)=13，小明随机出了一个长度为n的整数数组{a1,a2,,...an}，他想知道在这个数组中最多选m个不相交的区间，将这些区间内的二进制数位翻转（将ai变为f(ai)）后，整个数组的最大和是多少？

原题链接

思路分析

首先将数组中的所有数都预处理，计算出一个d数组，d[i]存储的是f[ai]-ai。

原问题转化一个子问题：从d[i]中选最多m个不相交的区间，这些区间内所有数的和最大为多少？该问题的值再加上sum(sum为a数组的总和)就是原问题答案。

现在来思考这个子问题：如果贪心或者模拟来求具体是哪几个区间是不容易的，因为区间不能重叠，要考虑的细节很多。可以使用动态规划来解决。

定义dp[i][j]表示前 i 个数取最多 j 个不相交的区间的最大总和。枚举到i时，计算dp[i][j],有两种选择：

• 不选最后一个下标i的后缀区间，dp[i][j]=dp[i-1][j]
• 选最后一个下标i的后缀区间，dp[i][j]=max(dp[k-1][j-1]+suffix(k,i) ，suffix(k,i)表示d的子数组[k,i]的区间和。

状态转移方程为：dp[i][j]=max(dp[i-1][j],max(dp[k-1][j-1]+suffix(k,i)))。

时间复杂度O(mn^2)。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll getDiff(int x) {int p = x;int tr = 0;while (x) {tr <<= 1;if (x & 1) tr |= 1;x >>= 1;}return tr - p;
}int main()
{int n, m;cin >> n >> m;vector<ll>d(n + 1);vector<vector<ll>>dp(n + 1, vector<ll>(m+1));  //dp[i][j]表示前i个数取最多j个不相交的区间的最大总和ll sum = 0;for (int i = 1; i <= n; i++) {int t; cin >> t;sum += t;d[i] = getDiff(t);}for (int i = 1; i <= n; i++) {for (int j = 1; j <= m; j++) dp[i][j] = dp[i - 1][j];  //不选从i开始的后缀子数组for (int j = 1; j <= m; j++) {ll suffix = 0;for (int k = i; k >= 1; k--) {suffix += d[k];dp[i][j] = max(dp[i][j], dp[k - 1][j - 1] + suffix);  //选从i开始的后缀子数组}}}cout << sum + dp[n][m];return 0;
}

7.数星星

问题描述

小明正在一棵树上数星星，这棵树有n个节点1,2,3...,n。他定义树上的一个子图G是一颗星星需要满足以下所有条件：

1. G是一课树。
2. G中存在某个节点，其度数为|VG|-1。其中|VG|表示这个子图含有的节点数。

当且仅当两颗星星包含的节点集合不完全相同，两颗星星不相同。小明想知道这棵树上有多少颗不同的星星包含的节点数在[L,R]范围内。答案对1e9+7取余

原题链接

思路分析

本题看似是一道图论题，实际只是借用了图的概念的排列组合的数学题。

直观图

由题意可知，子图G是一棵星星，其实就是说G是一棵所有叶子都是根节点的孩子的树，如上图，子图[1,2,3,4]，子图[1,3,5]都是星星。

首先统计每个节点的邻接节点数量（具体是哪些节点不用关系），edges[i]存储了节点i的邻接点的数量（也就是以i为根节点，它的孩子节点的数量）。依次枚举节点，统计以它为根节点的星星中（子节点数量为n），子节点数在[L-1,R-1]范围内的星星数量。这就是一个组合的问题，答案为:
$$C_n^{L-1}+...+C_n^{min(n,R-1)}$$

$$单个计算C_n^x=\frac{n!}{x!\ast (n-x)!}$$

因为需要多次计算组合数，暴力计算是要超时的，可以预处理计算出所有的x！的结果，C(n,x)就能在O(1)的时间复杂度内计算出结果。

在计算过程中需要不断对mod取余，而除法是不能直接除，这里可以用逆元处理。

前置知识：

逆元：给定整数a，m，满足gcd(a,m)=1(a与m互质)，ax%m=1的一个解为a模m的逆元，记为a^-1。

注：求解x/y%m的值可以转化为x*y^-1%m的值，（y^-1为y模m的逆元）。

费马小定理：当m是质数时，对于任意的a（a不能被m整除），其逆元为a^m-2%m。

注：求解a^m-2可以通过快快速幂求解。

更多详情请读者查阅资料。

根据前置知识可以得出求解C(n,x)的计算公式：
$$C_n^x\%mod=\frac{n!}{x!\ast (n-x)!}\%mod=fac[n]\ast inv[n-k]\ast inv[k]\%mod$$
其中fac[x]表示x！，inv[x]表示x！模mod的逆元。

自此其实还没完（只能通过16个测试用例），仔细想想，当L<=2<=R时，统计节点数为2的星星数量时是有重复统计的，直观图中子图[1,2]，和子图[2,1]是同一个子图。解决方法就是节点为1（星星数为原图中节点的数量）和2（星星数为原图边的数量）的星星数提前计算出来，枚举时只统计节点数大于等于max(3,L)的星星,具体实现见代码。

代码

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int mod = 1e9 + 7;
vector<int>fac;  //预处理阶乘
vector<int>inv;  //预处理阶乘的逆元
int pow(int x, int n) {  //快速幂求解(x^n)%mint s = 1;while (n) {if (n & 1) {s = (ll)x * s % mod;}x = (ll)x * x % mod;n >>= 1;}return s;
}
void init(int n) {  //初始化fac.resize(n + 1);inv.resize(n + 1);fac[0] = inv[0] = 1;//阶乘的初始化for (int i = 1; i <= n; i++) {fac[i] = (ll)fac[i - 1] * i % mod;inv[i] = pow(fac[i], mod - 2);  //费马小定理求解阶乘的逆元}
}
int cal(int n, int x) {  //求解C(n,x)的值return (ll)((ll)fac[n] * inv[x] % mod) * inv[n - x] % mod;
}
int main()
{int n; cin >> n;init(n);vector<int>edges(n+1);for (int i = 1; i < n; i++) {int u, v; cin >> u >> v;edges[u]++;edges[v]++;}int L, R; cin >> L >> R;int ans = 0;int sum1=n,sum2=n-1;  //节点为1的星星数量为n，节点为2的星星数量为n-1for (int i = 1; i <= n; i++) {int s = edges[i];if (s < max(L-1,2)) continue;  //子节点数量不合格直接退出for (int j = max(L-1,2); j < R; j++) {  //从至少j=2开始遍历，j小于2的星星统计会有重复计算，先预处理好ans = (ans + cal(s, j)) % mod;if (j >= s) break;}}if(L==1) ans=(ans+sum1)%mod;if(L<=2&&2<=R) ans=(ans+sum2)%mod;cout << ans;return 0;
}

8.套手镯

问题描述

小蓝在 LQ 集市上发现一个套手镯的游戏，在一个大小为10⁸ * 10⁸矩形平面上摆放着 N 个圆形的手镯。

玩家可以将一个大小为 w*h 的矩形方框放置在这个平面上(玩家只可以沿着水平/垂直方向放置方框，即可以将方框旋转 90度，但不可以旋转至其他角度)，位于这个矩形方框内部的手镯就是玩家获得的奖励。可以将这个矩形平面看作是一个二维坐标系，左下角的坐标为(0,0)。手镯和方框的厚度可以忽略不计，允许多个手镯重叠放置。小蓝想要尝试一次，请问他最多可以获得多少手镯?

示例：

数据规模

1<=N<=10⁵，1<=w,h,x,y,r<=10⁸，1<=min(w,h)<=200.

原题链接

思路分析

一个圆形如何判断它是否在矩形中内，只要它最高点，最低点，最左点，最右点在矩形内即可，所以对于一个圆形，我们主要关注的就是它的四个边界点（题目要是改成其他形状也是如此）。

先将圆的四个边界点作为一个整体（可以自定义数据结构，也可以使用pair,为方便后面排序，可直接使用pair）装入一个数据容器，将矩形方框作为滑窗让其装入尽量多的圆。滑动的过程可以枚举底线，让矩形在底线上水平左右滑动。具体滑动时要将尽可能多的圆包含在矩形中，为方便计算，将圆按照右边界点大小排序，固定底线，每次将当前枚举到的圆的右边界作为矩形的右边界，来统计装入的圆的数量最多为多少。

图示过程：

在单次水平滑动过程中需要用一个容器来维护矩形范围内的圆的左边界，常用的是队列，因为左边界不保证有序，可以用优先队列来存储，头节点维护的是最小的左边界，圆的左边界超出矩形的左边界都需要剔除（详见代码）。

因为矩形可以旋转90度，交换矩形的长宽然后再重复滑动过程就行。

代码

#include <bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
int n,w,h;
vector<pair<pii,pii>>c;
int getCnt(int bottom){   priority_queue<int,vector<int>,greater<int>>pq;  //维护矩形内的圆，头节点记录左边界最小的圆的左边界值int cnt=0;for(int i=0;i<n;i++){auto cur=c[i];if(cur.s.s<bottom||cur.s.f>bottom+h) continue;  //y坐标不合格pq.push(cur.f.s);  //左边界x坐标入队while(!pq.empty()&&pq.top()<cur.f.f-w) pq.pop();  //左边界不在矩形范围内的圆删除队列cnt=max(cnt,(int)pq.size());}return cnt;
}
int main()
{ios::sync_with_stdio(0); cin.tie(0);cin>>n>>w>>h;c.resize(n);for(int i=0;i<n;i++){int x,y,r; cin>>x>>y>>r;c[i].f.f=x+r;c[i].f.s=x-r;c[i].s.f=y+r;c[i].s.s=y-r;}sort(c.begin(),c.end());int ans=0;for(int i=0;i<n;i++){ans=max(ans,getCnt(c[i].s.s));}swap(w,h);  //将方框旋转90度for(int i=0;i<n;i++){ans=max(ans,getCnt(c[i].s.s));}cout<<ans;return 0;
}

9.跳石头

问题描述

小明正在和朋友们玩跳石头的小游戏，一共有 块石头按 1到 n 顺序排成一排，第讠块石头上写有正整数权值 C。如果某一时刻小明在第 j块石头，那么他可以选择跳向第j + c 块石头(前提j+ ci<n )或者跳向第 2j块石头(前提 2j<n)，没有可跳跃的目标时游戏结束。

假如小明选择从第 x 块石头开始跳跃，如果某块石头有可能被小明经过("经过"指存在某一时刻小明在这个石头处)，则将这块石头的权值纳入得分集合 S，那么小明从第 x 块石头开始跳跃的得分为|S|(|S|表示S中不同元素的数量)。

比如如果小明从第 x 块石头出发，所有可能经过的石头上的权值分别为 5,3,5,2,3，那么 S=[ 5,3,2 ] 得分为|S|=3。小明可以任选一块石头开始跳跃，请求出小明最多能获得的分数。

原题链接

思路分析

这是一个常见的跨步问题，可以用动态规划求解，记录原数组到nums，从下标 i 出发，可能到达i+nums[i]和i*2的位置，可以定义dp[i]记录从i出发可能到达的节点权值集合，要求解dp[i]就得先知道dp[i+nums[i]]或dp[i*2],可以采用记忆化搜索的方式求解，也可以从后往前遍历，先求解出后面的dp值。

代码

#include<bits/stdc++.h>
using namespace std;
int main()
{int n; cin>>n;vector<int>nums(n+1);vector<unordered_set<int>>dp(n+1);for(int i=1;i<=n;i++) cin>>nums[i];int ans=0;for(int i=n;i>=1;i--){int to1=i+nums[i];int to2=i*2;if(to1<=n){dp[i].insert(dp[to1].begin(),dp[to1].end());}if(to2<=n){dp[i].insert(dp[to2].begin(),dp[to2].end());}dp[i].insert(nums[i]);ans=max((int)dp[i].size(),ans);}cout<<ans;return 0;
}

10.最长回文前后缀

问题描述

小明特别喜欢回文串，然而回文串太少见了，因此他定义：字符串的相同长度的，不相交的前缀和后缀是"回文前后缀"，当且仅当这个前缀和后缀拼起来是个回文串。对于一个给定的字符串 S，小明希望对其进行改造使得L(S)(S的最长前后缀长度)尽可能大。改造允许将字符串中一个任意长度的子串删除。比如删除S=abcdebijbba 中的子串 S[3,5]后S变成了 abbijbba 。

小明想知道改造后的新字符串 S’的最长回文前后缀”的长度L(S')最大是多少?

原题链接

思路分析

在判断一个字符串是否是回文串时，常用双指针往中心靠拢的方式来枚举判断，在本题中，我么也可以先这样统计出最小的回文前后缀的长度ans，第一个不相同的位置为l,r。

此时，如果不进行删除，那答案就是ans，如果进行删除，那肯定是删除以L为开头的前缀子串或者删除以R为结尾的后缀子串，只有这样才能使ans更大。因为只能删除一次，那直接暴力枚举删除具体那个子串就好，当然也不用真的删除，只是模拟一下，计算出值就行。

因为需要两次模拟操作，可以定义一个函数来实现代码复用。

代码

#include<bits/stdc++.h>
using namespace std;
int getMax(string str){int l=0,r=str.size()-1;int cnt=0;while(l<r){if(str[l]==str[r]){  //删除[0,l-1]int lt=l,rt=r;while(lt<rt&&str[lt]==str[rt]) lt++,rt--;cnt=max(lt-l,cnt);}l++;}return cnt;
}
int main()
{ios::sync_with_stdio(0); cin.tie(0);string s; cin>>s;int n=s.size();int l=0,r=n-1;int ans=0;while(l<r&&s[l]==s[r]) l++,r--;ans=l;string t=s.substr(l,r-l+1);string rt=t; reverse(t.begin(),t.end());ans+=max(getMax(t),getMax(rt));cout<<ans;return 0;
}

总结

这张国赛卷涉及的知识点还挺多，包括：1.暴力法，2.几何数学，3.数论，4.动态规划，5.滑动窗口，6.图的定义，7.二分法，8.贪心。

总体看来涉及的算法过程并不复杂，但要想到用哪种方法求解就不是易事了，像第四题，开始时总想着要贪心还是动态规划来求解最优方案，其实二分答案+贪心判断才是正解，当然这也启示我在解题时不能一棵树上吊死，一种方法不好做，要积极尝试转换思维寻找其他方法，有时需要重新读题来寻找其他方法。

本卷的最难题其实不是最后一道，相比之下，我觉得第7,8题难一点，当然冷静分析，仔细读题，将一个复杂困难的问题分解为几个简单问题，难题也能迎刃而解。最后祝愿大家能在后面的竞赛中取得好成绩，AC连连！