题目pdf下载：十三届蓝桥杯c++b组2022国赛题目pdf下载
G题没有写，J题是暴力的，其他好像都写出来，但是估计还是有错的。
目录
正文：
试题 A: 2022
题意： 2022分为不同十个不同的正整数的情况数。
思路：动态规划,我的答案是：379187662194355221。
以为挺简单的，但是dfs写完连100都跑不出来，这题难度不简单，估计卡了不少人时间
后面暴力出了答案，从55开始有答案（因为最小的十个不同的正整数是：1,2,3,4...10，和是55），根据前10个数很像哈代-拉马努金拆分数列，然后求出来和后面的不一样，而且会炸long long，所以这个数列应该是错的。
动态规划思路：
解释在下面动态规划代码的注释，大致就是dp[2022][10]=dp[1][9]+dp[2][9]+dp[3][9]....+dp[2021][9]的动态规划，用倒叙去实现每个整数只用一次（类似01背包）。
暴力代码：
-
#include<cstdio>
-
#include<cstring>
-
#include<iostream>
-
#include<algorithm>
-
using
namespace std;
-
int a=
55;
-
int ans=
0;
-
void dfs(int d,int sum,int pre){
//d是选的数量，sum是选的和，pre是上次选的点
-
if(d==
10){
-
if(sum==a)
-
ans++;
-
return;
-
}
-
for(
int i=pre+
1;i<=a;i++){
-
if(i+sum<=a){
-
dfs(d+
1,sum+i,i);
-
}
-
}
-
}
-
int main()
-
{
-
dfs(
0,
0,
0);
-
cout<<ans<<endl;
-
return
0;
-
}
动态规划代码：
-
#include<bits/stdc++.h>
-
using
namespace std;
-
long
long i,j,k,dp[
50000][
20];
-
//dp[i][j]表示选j个数总和为i的方案数
-
int main()
-
{
-
for(i=
2022;i>=
1;i--)
-
{
-
//这里i的顺序不影响结果
-
for(j=
2022;j>=
1;j--)
-
{
-
//为了dp不相互影响这里从大到小dp
-
//如果从小到大的话需要再开数组存结果
-
for(k=
1;k<=
9;k++)
-
{
-
dp[j+i][k+
1]+=dp[j][k];
-
//对于k个数总和为j的方案dp[j][j];
-
//可以选i使得k+1个数总和为j+i
-
}
-
}
-
dp[i][
1]=
1;
//表示选1个数总和为i的方法加1
-
}
-
for(i=
1;i<=
100;i++)
-
{
-
cout<<i<<
" "<<dp[i][
10]<<endl;
-
}
-
cout<<dp[
2022][
10]<<endl;
-
return
0;
-
}
试题 B: 钟表
题意：一个钟表的时针、分针的角度差==分针、秒针的角度差，求此时的时分秒。
思路：暴力，我的答案是：4 48 0
三个for起手不难，主要就是计算三个针的角度，
秒的角度就是：m/60
分的角度就是：f/60+(m/60)/*60，因为秒贡献的度数最多是1/60，贡献了m/60*(1/60)
时的角度就是：s/12+(f+m*60)/(60*12);，因为分钟贡献的度数最多是1/12，如果有res分钟，那么a=s/12+res/12
注意优弧劣弧的概念，小数的角度是<=0.5的。
代码：
-
#include<bits/stdc++.h>
-
using
namespace std;
-
#define dou double
-
#define EXP 1e-6
-
#define M 100010
-
int main()
-
{
-
for(dou s=
0;s<=
6;s++)
-
for(dou f=
0;f<
60;f++)
-
for(dou m=
0;m<
60;m++){
-
dou a=s/
12+(f+m*
60)/(
60*
12);
//时针在表上角度
-
dou b=f/
60+m/(
60*
60);
//分针在表上角度
-
dou c=m/
60;
//秒针在表上角度
-
dou x=
fabs(a-b)>
0.5?
1-
fabs(a-b):
fabs(a-b);
//x是时针和分针夹角
-
dou y=
fabs(b-c)>
0.5?
1-
fabs(b-c):
fabs(b-c);
//x是分针和秒针夹角
-
if(
fabs(x
-2*y)<EXP){
//如果A==2*B
-
cout<<s<<
" "<<f<<
" "<<m<<endl;
-
}
-
}
-
return
0;
-
}
试题 C: 卡牌
题意：a[i]数组是已有的 i 类手牌的数量，每个类（1-n类）的出1张可以组成一套，还有m张空白的，可以随便写成任意i类。b数组是该类最多被空白牌写成几张，求组成的最多套牌。
修改：这题比赛的时候被改成a,b<n*2了，不是原来的n*n了
思路：二分
容易知道是把空白牌用到少的类上，这题思路就是直接二分答案了
如果当前类牌不够mid张，当然是将空白的编变成该类牌，一是看是否超过了b数组的限制，二是看是否超过了最大空白牌数量。
直到最后也是没有被返回NO，那么返回YES
check函数：
-
int check(int mid){
//看看mid套行不行
-
LL sum=
0;
-
for(
int i=
1;i<=n;i++){
-
if(a[i]<mid){
//i类原来数量就超过mid张就不用考虑了
-
if(mid-a[i]>b[i])
return
0;
//如果需要的比限制多返回NO
-
sum+=mid-a[i];
-
if(sum>m)
return
0;
//如果使用空白牌多与m，返回NO
-
}
-
}
-
return
1;
-
}
代码：
-
#include<bits/stdc++.h>
-
using
namespace std;
-
#define LL long long
-
#define M 1000005
-
LL n,m;
-
LL a[M],b[M];
-
int check(int mid){
-
LL sum=
0;
-
for(
int i=
1;i<=n;i++){
-
if(a[i]<mid){
-
if(mid-a[i]>b[i])
return
0;
-
sum+=mid-a[i];
-
if(sum>m)
return
0;
-
}
-
}
-
return
1;
-
}
-
int main()
-
{
-
scanf(
"%lld%lld",&n,&m);
-
for(
int i=
1;i<=n;i++)
scanf(
"%lld",&a[i]);
-
for(
int i=
1;i<=n;i++)
scanf(
"%lld",&b[i]);
-
LL l=
0,r=n*
2,ans=
0;
-
while(l<=r){
-
LL mid=(l+r)/
2;
-
if(
check(mid)){
-
l=mid+
1;
-
ans=mid;
-
}
else{
-
r=mid
-1;
-
}
-
}
-
printf(
"%lld\n",ans);
-
return
0;
-
}
试题 D: 最大数字
题意：给一个小于1e18的数字，不超过a次可以给一位+1，9再+就变成0，
不超过b次可以给一位-1，0再-变成9。
思路：思维+暴力深搜（dfs）
使用肯定是从前面开始的，因为是不超过多少次使用，前面就是能省则省，但是但凡有用，必须使用，暴力出答案即可。
对于每种情况只能是暴力的搜答案，时间复杂度最坏应该是2^18了差不多。
然后一直纠结用字符串还是整数来表示，整数肯定更方便计算和简洁，字符串便于修改，后面用数量级还是实现了整数的修改。
dfs代码：
-
void dfs(LL a,LL ans,LL b,LL c){
//a表示当前的N，ans是10的某次方,表示数量级,b和c是剩余数量
-
if(ans==
0){
-
maxx=
max(maxx,a);
//更新答案
-
return;
-
}
-
int d=a/ans%
10;
-
if(b>
9-d){
//能变成9就变9,
-
int r=b-(
9-d);
-
dfs(a+(
9-d)*ans,ans/
10,r,c);
-
}
else{
//不能变成9就全用
-
dfs(a+b*ans,ans/
10,
0,c);
-
}
-
if(c!=
0){
-
if(c>=d+
1){
//能变成9就用，不能变就省着
-
int r=c-(d+
1);
-
dfs(a-d*ans+
9*ans,ans/
10,b,r);
-
}
-
}
-
}
代码：
-
#include<bits/stdc++.h>
-
using
namespace std;
-
#define fo(a,b) for(int i=a;i<=b;i++)
-
#define inf 0x3f3f3f3f
-
#define LL long long
-
#define M 100010
-
LL a,b,c;
-
LL maxx=
0;
-
void dfs(LL a,LL ans,LL b,LL c){
-
if(ans==
0){
-
maxx=
max(maxx,a);
-
return;
-
}
-
int d=a/ans%
10;
-
if(b>
9-d){
-
int r=b-(
9-d);
-
dfs(a+(
9-d)*ans,ans/
10,r,c);
-
}
else{
-
dfs(a+b*ans,ans/
10,
0,c);
-
}
-
if(c!=
0){
-
if(c>=d+
1){
-
int r=c-(d+
1);
-
dfs(a-d*ans+
9*ans,ans/
10,b,r);
-
}
-
}
-
}
-
int main()
-
{
-
cin>>a>>b>>c;
-
LL tmp=a;
-
LL ans=
1;
-
while(a){
-
a/=
10;
-
ans*=
10;
-
}
-
dfs(tmp,ans/
10,b,c);
-
cout<<maxx<<endl;
-
return
0;
-
}
试题 E: 出差
题意：n个点，m条边构成一个有边权的无向图，然后每个顶点都有自己的停留时间，即到达该点要停的时间，都是正数，求1到n点的最短时间
思路：最短路的贝尔曼-福特算法(Bellman-Ford)
这题就是最短路模板题，只是加上了顶点要停留，感觉迪杰斯特拉算法（Dijkstra）应该也行，但觉得贝尔曼-福特算法(Bellman-Ford)应该更合适。
只是在使用边的时候，将边权+终点停留时间，终点为n时不加
更新代码：
-
for(
int k=
1;k<=n;k++){
//n次更新
-
for(
int i=
1;i<=m;i++){
-
int res1=
0,res2=
0;
-
if(b[i]!=n) res1=x[b[i]];
//终点不为n，边权+停留时间
-
if(a[i]!=n) res2=x[a[i]];
-
dist[b[i]]=
min(dist[b[i]],dist[a[i]]+c[i]+res1);
-
dist[a[i]]=
min(dist[a[i]],dist[b[i]]+c[i]+res2);
-
}
-
}
代码：
-
#include<bits/stdc++.h>
-
using
namespace std;
-
#define fo(a,b) for(int i=a;i<=b;i++)
-
#define inf 0x3f3f3f3f
-
#define LL long long
-
#define M 100005
-
int n,m;
-
int x[M];
-
int dist[M],a[M],b[M],c[M];
-
int main(){
-
scanf(
"%d%d",&n,&m);
-
memset(dist,inf,
sizeof(dist));
-
dist[
1]=
0;
-
for(
int i=
1;i<=n;i++) cin>>x[i];
-
for(
int i=
1;i<=m;i++)
-
scanf(
"%d%d%d",&a[i],&b[i],&c[i]);
-
for(
int k=
1;k<=n;k++){
-
for(
int i=
1;i<=m;i++){
-
int res1=
0,res2=
0;
-
if(b[i]!=n) res1=x[b[i]];
-
if(a[i]!=n) res2=x[a[i]];
-
dist[b[i]]=
min(dist[b[i]],dist[a[i]]+c[i]+res1);
-
dist[a[i]]=
min(dist[a[i]],dist[b[i]]+c[i]+res2);
-
}
-
}
-
cout<<dist[n]<<endl;
-
return
0;
-
}
试题 F: 费用报销
题意：给同一年的一些天，这些天都一个或多个的钱，选一些天使金额最多且不超多m，其中所有相邻的天数相差不超过k（>=k）
思路：动态规划
比较简单得到动态规划，首先将天转变为一维数组，dp[i]表示该天最大的金额。
那么dp[i]=max(dp[i-1],dp[i-k]+a[i]) //对应的就是不选和选
核心代码：
-
-
for(
int i=
1;i<=
500;i++){
//一年365天，dp超过365就行
-
if(dp[i]+dp[
max(
0,i-k)]<=m)
-
dp[i]=
max(dp[i]+dp[
max(
0,i-k)],dp[i
-1]);
-
else
//如果选了会超过m，就不选了
-
dp[i]=dp[i
-1];
-
}
代码：
-
#include<bits/stdc++.h>
-
using
namespace std;
-
#define fo(a,b) for(int i=a;i<=b;i++)
-
#define inf 0x3f3f3f3f
-
#define LL long long
-
#define M 100005
-
int n,m,k;
-
int x,y,z;
-
int mp[
105][
105],dp[
10005];
-
int r[]={
0,
31,
28,
31,
30,
31,
30,
31,
31,
30,
31,
30,
31};
-
int main(){
-
int sum=
0;
-
for(
int i=
1;i<=
12;i++){
-
for(
int j=
1;j<=r[i];j++){
-
sum++;
-
mp[i][j]=sum;
//映射天数
-
}
-
}
-
scanf(
"%d%d%d",&n,&m,&k);
-
for(
int i=
1;i<=n;i++){
-
scanf(
"%d%d%d",&x,&y,&z);
-
dp[mp[x][y]]=
max(dp[mp[x][y]],z);
//k最小为1，当天的就选个最大的就行
-
}
-
for(
int i=
1;i<=
500;i++){
-
if(dp[i]+dp[
max(
0,i-k)]<=m)
-
dp[i]=
max(dp[i]+dp[
max(
0,i-k)],dp[i
-1]);
-
else
-
dp[i]=dp[i
-1];
-
}
-
cout<<dp[
500]<<endl;
-
return
0;
-
}
-
#include<bits/stdc++.h>
-
using
namespace std;
-
#define fo(a,b) for(int i=a;i<=b;i++)
-
#define inf 0x3f3f3f3f
-
#define LL long long
-
#define M 100005
-
int n,m,k;
-
int x,y,z;
-
int mp[
105][
105],dp[
10005];
-
int r[]={
0,
31,
28,
31,
30,
31,
30,
31,
31,
30,
31,
30,
31};
-
int main(){
-
int sum=
0;
-
for(
int i=
1;i<=
12;i++){
-
for(
int j=
1;j<=r[i];j++){
-
sum++;
-
mp[i][j]=sum;
//映射天数
-
}
-
}
-
scanf(
"%d%d%d",&n,&m,&k);
-
for(
int i=
1;i<=n;i++){
-
scanf(
"%d%d%d",&x,&y,&z);
-
dp[mp[x][y]]=
max(dp[mp[x][y]],z);
//k最小为1，当天的就选个最大的就行
-
}
-
for(
int i=
1;i<=
500;i++){
-
if(dp[i]+dp[
max(
0,i-k)]<=m)
-
dp[i]=
max(dp[i]+dp[
max(
0,i-k)],dp[i
-1]);
-
else
-
dp[i]=dp[i
-1];
-
}
-
cout<<dp[
500]<<endl;
-
return
0;
-
}
试题 G: 故障
题意：不知
思路：不知，题有点多，做不过来
代码：未有
试题 H: 机房
题意：给一颗无边权的树，查询m次两点路劲之间，所有点的直接连接点的数量和。
思路：LCA+树形DP
还是比较好想的，dfs处理出给个点的直接连接点的数量，再dfs，求出每个点到顶点的直接连接点的数量的前缀和，用dp[i]表示。
d表示两点x和y的LCA（共公祖先），pre[d]表示d的父点，结果就是dp[x]+dp[y]-dp[d]-dp[pre[d]]。
核心代码：
-
void dfs(int d,int pre,int sum)
-
{
-
for(
int i=
1;i<n+
5;i++) lg[i]=lg[i
-1]+(
1<<lg[i
-1]==i);
//LCA倍增
-
fa[d][
0]=pre;
//LCA倍增
-
h[d]=h[pre]+
1;
//LCA倍增
-
p[d]=pre;
//父点
-
for(
int i=
1;i<=lg[h[d]]+
1;i++)
//LCA倍增
-
fa[d][i]=fa[fa[d][i
-1]][i
-1];
-
int l=v[d].
size();
//l也是当前结点直接连接其他结点数量
-
dp[d]=l+sum;
//sum是之前父链的和
-
fo(
0,l
-1){
-
int now=v[d][i];
-
if(pre!=now){
-
dfs(now,d,dp[d]);
-
}
-
}
-
}
代码：
-
#include<bits/stdc++.h>
-
using
namespace std;
-
#define fo(a,b) for(int i=a;i<=b;i++)
-
#define inf 0x3f3f3f3f
-
#define LL long long
-
#define M 200005
-
int n,m,x,y;
-
int dp[M],p[M];
-
vector<
int>v[M];
-
int h[M],lg[M],fa[M][
35];
-
void dfs(int d,int pre,int sum)
-
{
-
for(
int i=
1;i<n+
5;i++) lg[i]=lg[i
-1]+(
1<<lg[i
-1]==i);
//LCA倍增
-
fa[d][
0]=pre;
//LCA倍增
-
h[d]=h[pre]+
1;
//LCA倍增
-
p[d]=pre;
//父点
-
for(
int i=
1;i<=lg[h[d]]+
1;i++)
//LCA倍增
-
fa[d][i]=fa[fa[d][i
-1]][i
-1];
-
int l=v[d].
size();
//l也是当前结点直接连接其他结点数量
-
dp[d]=l+sum;
//sum是之前父链的和
-
fo(
0,l
-1){
-
int now=v[d][i];
-
if(pre!=now){
-
dfs(now,d,dp[d]);
-
}
-
}
-
}
-
int LCA(int a,int b)
-
{
-
if(h[a]<h[b])
swap(a,b);
-
for(
int i=lg[h[a]]+
1;i>=
0;i--){
-
if(h[a]-(
1<<i)>=h[b])
-
a=fa[a][i];
-
}
-
if(a==b)
return a;
-
for(
int i=lg[h[a]]+
1;i>=
0;i--)
-
if(fa[a][i]!=fa[b][i]){
-
a=fa[a][i];
-
b=fa[b][i];
-
}
-
return fa[a][
0];
-
}
-
int main(){
-
cin>>n>>m;
-
fo(
1,n
-1){
-
cin>>x>>y;
-
v[x].
push_back(y);
-
v[y].
push_back(x);
-
}
-
dfs(
1,
0,
0);
-
while(m--){
-
int x,y;
-
cin>>x>>y;
-
int d=
LCA(x,y);
-
cout<<dp[x]+dp[y]-dp[d]-dp[p[d]]<<endl;
-
}
-
return
0;
-
}
试题 I: 齿轮
题意：给一个数组为齿轮大小，问能不能换顺序后，尾转的速度是首转的速度的qi倍，询问Q次。
思路：不难发现这个中间的没有用，就是首的半径=尾的半径*qi就可。而且这种排序是随便的，只需要找这个数组中有没有两个数相除==qi即可。
那么需处理出这个数组所有的可有倍数即可。具体看代码更容易理解，这个时间复杂度是n*logn的，对1e6也应该能用，注意倍数1的判断
预处理代码：
-
for(
int i=
1;i<=MAX;i++){
//MAX=2e5
-
if(vis[i]==
1){
//vis[i]表示i在该数组中
-
for(
int j=i*
2;j<=MAX;j+=i){
-
if(vis[j]==
1) ans[j/i]=
1;
//ans是结果数组
-
}
-
}
-
}
代码：
-
#include<bits/stdc++.h>
-
using
namespace std;
-
#define inf 0x3f3f3f3f
-
#define LL long long
-
#define M 1000005
-
int MAX=
400005;
-
int n,m,flag=
0;
-
int a[M];
-
int vis[M],ans[M];
-
int main(){
-
cin>>n>>m;
-
for(
int i=
1;i<=n;i++){
-
cin>>a[i];
-
if(vis[a[i]]==
1) flag=
1;
//单独判断ans[1]
-
vis[a[i]]=
1;
//表明数组有这个数
-
}
-
if(flag) ans[
1]=
1;
-
for(
int i=
1;i<=MAX;i++){
-
if(vis[i]==
1){
-
for(
int j=i*
2;j<=MAX;j+=i){
-
if(vis[j]==
1) ans[j/i]=
1;
-
}
-
}
-
}
-
int x;
-
while(m--){
-
cin>>x;
-
if(ans[x]) cout<<
"YES"<<endl;
-
else cout<<
"NO"<<endl;
-
}
-
return
0;
-
}
试题 J: 搬砖
题意：选取若干个从上到下放，重量不能小于上面的和，求总价值最大
思路：可能是动态规划，写差不多觉得和题意有点出入，就直接dfs暴力了
暴力挺简单的，先结构体排序，重量小的一定先选在上面，不然直接压垮了。然后同重量的价值大的一定先选。
dfs出所有的1-n排序，也就是：
1 2 3 4 5
1 2 3 4
3 4 5
2 4 5
这些
....
然后计算判断更新最后答案
代码：
-
#include<bits/stdc++.h>
-
using
namespace std;
-
#define fo(a,b) for(int i=a;i<=b;i++)
-
#define inf 0x3f3f3f3f
-
#define LL long long
-
#define M 200005
-
int n,maxx=
0;
-
struct
Node
-
{
-
int a,b;
-
bool
operator<(
const Node temp)
const{
-
if(a==temp.a)
return b>temp.b;
-
return a<temp.a;
-
}
-
}x[M];
-
-
//此代码是暴力代码，只能过30%
-
-
int q[M],v=
0;
-
void dfs(int d,int pre){
-
if(d==n){
//判断q数组中的顺序是否合法
-
int sum=
0,ans=
0;
-
for(
int i=
1;i<=v;i++){
-
if(x[q[i]].a<sum)
break;
-
sum+=x[q[i]].a;
-
ans+=x[q[i]].b;
-
if(i==v) maxx=
max(maxx,ans);
-
}
-
return;
-
}
-
for(
int i=pre+
1;i<=n;i++){
-
q[++v]=i;
-
dfs(d+
1,i);
-
v--;
-
}
-
if(v!=
0)
dfs(d+
1,pre);
-
}
-
int main(){
-
cin>>n;
-
for(
int i=
1;i<=n;i++)
-
cin>>x[i].a>>x[i].b;
-
sort(x+
1,x+n+
1);
-
dfs(
0,
0);
-
cout<<maxx<<endl;
-
return
0;
-
}
结尾：
看了下演草纸，才用了1页多，一般比赛要好几页的。不少题是算法及相关的题，总体acm选手估计是叫好，但是对其他选手不清楚了，这题个人觉得难度适中，因为往年很多题不能暴力，而且到现在，那些题也没有题解（csdn上）。今年只有一题没看，一个暴力，难度肯定是降了不少的。
转载：https://blog.csdn.net/m0_58177653/article/details/125345906