2024.4.17
今天看到C语言网题库里有了蓝桥杯真题，可惜好像还没出研究生组的，就顺着刷了一下B组的，写了这篇题解。
交题链接: C语言网-蓝桥杯2024真题
思路和代码仅通过C语言网评测，并不代表绝对正确。
C题 好数
问题描述
思路简述
简单模拟
枚举从 1 1 1到 n n n每一个数，对每一个数按位判断是否为好数
代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e5+5;const int inf=0x3f3f3f3f;int n,cnt;bool check(int x) //判断x是否为好数{ int tmp=0; while(x) { int now=x%10; x/=10; tmp++; if(tmp%2!=now%2) return 0; } return 1;}int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) cnt+=check(i); printf("%d\n",cnt); return 0;}##过题记录
D题 R格式
问题描述
思路简述
模拟高精度
要求出 r e s = f ∗ 2 n res=f*2^n res=f∗2n，即求 n n n次 f = f ∗ 2 f=f*2 f=f∗2，也可以写成 f = f + f f=f+f f=f+f
注意数据溢出需要用到高精度，写高精度的时候需要注意小数点，记录小数点的位置。
记小数点的位置为 f d fd fd，小数的位数是不变的，比如初始是 3.14 3.14 3.14，不论乘几次 2 2 2，答案的小数位数一定还是 2 2 2位。
四舍五入的时候需要注意诸如 999.5 999.5 999.5这种情况，四舍五入之后应该是 1000 1000 1000。
代码
//模拟高精度，要求f乘2的n次方，即模拟n次f=f*2#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e6+5;const int inf=0x3f3f3f3f;int n,f[maxn],fd,lenf;char s[maxn];void add(){ int flag=0; for(int i=0;i<lenf;i++) { f[i]=f[i]+f[i]+flag; flag=(f[i]>=10); f[i]%=10; } if(flag) f[lenf++]=flag;}int main(){ scanf("%d %s",&n,s); int len=strlen(s); for(int i=len-1;i>=0;i--)//将字符串s转换成高精度数组f if(s[i]!='.') f[lenf++]=s[i]-'0'; else fd=len-1-i;//代表有fd位小数 while(n--) add();//f=f*2或者说f=f+f; if(f[fd-1]>=5) //四舍五入 { int flag=1; for(int i=fd;i<lenf;i++) { f[i]=f[i]+flag; flag=(f[i]>=10); f[i]%=10; } if(flag) f[lenf++]=flag; } for(int i=lenf-1;i>=fd;i--) printf("%d",f[i]); printf("\n"); return 0;}过题记录
E题 宝石组合
问题描述
思路简述
先整理简化 S S S
为方便起见用 a a a代表 H a H_a Ha， b b b代表 H b H_b Hb， c c c代表 H c H_c Hc
则有：
S = a b c ∗ l c m ( a , b , c ) l c m ( a , b ) l c m ( a , c ) l c m ( b , c ) S=abc*\frac{lcm(a,b,c)}{lcm(a,b)lcm(a,c)lcm(b,c)} S=abc∗lcm(a,b)lcm(a,c)lcm(b,c)lcm(a,b,c)
二元 l c m lcm lcm计算公式为 l c m ( a , b ) = a b g c d ( a , b ) lcm(a,b)=\frac{ab}{gcd(a,b)} lcm(a,b)=gcd(a,b)ab
但题目中出现了三元 l c m ( a , b , c ) lcm(a,b,c) lcm(a,b,c)，怎么计算呢？
我的第一反应是 l c m ( a , b , c ) = l c m ( l c m ( a , b ) , c ) lcm(a,b,c)=lcm(lcm(a,b),c) lcm(a,b,c)=lcm(lcm(a,b),c)，但大概推了一下发现简化的 s s s还是很复杂。
所以手写了三组样例 ( 2 , 3 , 5 ) , ( 2 , 3 , 10 ) , ( 2 , 6 , 10 ) (2,3,5),(2,3,10),(2,6,10) (2,3,5),(2,3,10),(2,6,10)，尝试推导，加上推测 (瞎猜)可以得到：
l c m ( a , b , c ) = a b c ∗ g c d ( a , b , c ) g c d ( a , b ) ∗ g c d ( a , c ) ∗ g c d ( b , c ) lcm(a,b,c)=\frac{abc*gcd(a,b,c)}{gcd(a,b)*gcd(a,c)*gcd(b,c)} lcm(a,b,c)=gcd(a,b)∗gcd(a,c)∗gcd(b,c)abc∗gcd(a,b,c)
带入整理一下 s s s就是
S = a b c ∗ a b c ∗ g c d ( a , b , c ) g c d ( a , b ) ∗ g c d ( a , c ) ∗ g c d ( b , c ) a ∗ a ∗ b ∗ b ∗ b ∗ c ∗ c g c d ( a , b ) ∗ g c d ( a , c ) ∗ g c d ( b , c ) = g c d ( a , b , c ) S=abc*\frac{\frac{abc*gcd(a,b,c)}{gcd(a,b)*gcd(a,c)*gcd(b,c)}}{\frac{a*a*b*b*b*c*c}{gcd(a,b)*gcd(a,c)*gcd(b,c)} }=gcd(a,b,c) S=abc∗gcd(a,b)∗gcd(a,c)∗gcd(b,c)a∗a∗b∗b∗b∗c∗cgcd(a,b)∗gcd(a,c)∗gcd(b,c)abc∗gcd(a,b,c)=gcd(a,b,c)
这时候观察数据范围 N = 1 e 5 N=1e5 N=1e5。
a b c abc abc三个变量分别枚举肯定超时， O ( N 3 ) O(N^3) O(N3)只能拿到30%的分。但观察到 H i H_i Hi本身比较小 ( 1 e 5 ) (1e5) (1e5)，所以我们可以直接枚举 S S S。但枚举每个 S S S，每次怎么检查 S S S是否满足条件呢？
这时需要引入set(可能有重复的所以需要multiset)，对于枚举的每个 S S S，再枚举其倍数 k S kS kS，用multiset查 k S kS kS是否存在，注意检查的同时满足字典序最小的条件。
总结一下时间复杂度： O ( H ∗ l o g H ∗ l o g n ) = 4 e 7 O(H*logH*logn)=4e7 O(H∗logH∗logn)=4e7。
代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e5+5;const int inf=0x3f3f3f3f;int n,a[maxn],res[4];multiset<int>s;int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]),s.insert(a[i]); for(int i=maxn-5;i>=1;i--)//枚举s { int cnt=0; for(int j=i;j<=maxn&&cnt<=2;j+=i)//枚举其倍数 for(int k=1;k<=s.count(j)&&cnt<=2;k++) res[++cnt]=j; if(cnt==3) break; } printf("%d %d %d\n",res[1],res[2],res[3]); return 0;}过题记录
F题 数字接龙
问题描述
思路简述
模拟+搜索，没什么好说的
好久没写了，熟悉的在垒屎山的感觉。
代码
//F#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e5+5;const int inf=0x3f3f3f3f;int f[15][15][8],a[15][15],vis[15][15],res[105],n,k,flag;int move1[8]={-1,-1, 0, 1, 1, 1, 0,-1};int move2[8]={0 , 1, 1, 1, 0,-1,-1,-1};bool check(int x,int y){ if(x<1||y<1||x>n||y>n||vis[x][y]) return 0; return 1;}void biaoji(int x,int y,int fx,int v){ if(fx==1) f[x][y+1][7]+=v,f[x-1][y][3]+=v; if(fx==3) f[x][y+1][5]+=v,f[x+1][y][1]+=v; if(fx==5) f[x][y-1][3]+=v,f[x+1][y][7]+=v; if(fx==7) f[x][y-1][1]+=v,f[x-1][y][5]+=v;}void dfs(int x,int y,int cnt){ if(x==n&&y==n&&cnt==n*n) { flag=1; for(int i=1;i<cnt;i++) printf("%d",res[i]); printf("\n"); } if(flag) return; for(int i=0;i<=7;i++) { int nx=x+move1[i],ny=y+move2[i]; if( check(nx,ny) && f[x][y][i]==0 && a[nx][ny]==((a[x][y]+1)%k) ) { res[cnt]=i; biaoji(x,y,i,1); vis[nx][ny]=1; dfs(nx,ny,cnt+1); biaoji(x,y,i,-1); vis[nx][ny]=0; } }}int main(){ scanf("%d %d",&n,&k); if(n==1) return 0*printf("-1\n");//特判n=1的情况 for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) scanf("%d",&a[i][j]); vis[1][1]=1; dfs(1,1,1); if(flag==0) printf("-1\n");//无解的情况 return 0;}过题记录
真坑啊
这个倒数第三个点好坑，一直就卡着这一个点过不去，我查了半天思路和代码都觉着没问题，。。。结果看着数据范围构造数据的时候，突然发现n=1的时候有问题，需要特判，此时应该是没路径的吧，直接输出-1，就能ac了。
G题 爬山（不会做，可以跳过不看）
问题描述
思路简述（不会，可以跳过）
打表可以得到
分析打表数据：山的高度是1的情况使用第二种魔法 H / 2 H/2 H/2，高度是2到5的时候使用两种魔法相同，大于等于6的时候优先使用第一种魔法 s q r t ( H ) sqrt(H) sqrt(H)
但这么写贪心可以很轻松的hack掉
给出两组hack数据
3 3 3
3 3 3
答案是0
2 1 1
8 9
答案是 9 2 + s q r t ( 8 ) = 4 + 2 = 6 \frac{9}{2}+sqrt(8)=4+2=6 29+sqrt(8)=4+2=6
写了个优先队列加贪心，但贪心贪的明显有问题
所以…没想出正解，不会
下面的代码倒是把这俩样例过了，但这个面向hack数据编程
像在垒屎，且连C语言网都没AC
未AC代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e5+5;const int inf=0x3f3f3f3f;int n,cnt1,cnt2,cnt3,ycnt1,ycnt2;struct node{ int x,y,z; node(){}; node(int xx,int yy,int zz) { x=xx; y=yy; z=zz;} friend bool operator < (node a,node b) { int mida1=a.x-a.y,mida2=a.x-a.z; int mxa=max(mida1,mida2); int midb1=b.x-b.y,midb2=b.x-b.z; int mxb=max(midb1,midb2); if(mxa==mxb) { if(mida1==0&&mida2==1) return 1; if(midb1==0&&midb2==1) return 0; if(mida1==midb1) { if(mida2==midb2) return a.x<b.x; return mida2>midb2; } return mida1<midb1; } return mxa<mxb; }};priority_queue<node>q;void ps(int x){ q.push(node(x,sqrt(x),x/2));}int main(){ scanf("%d%d%d",&n,&ycnt1,&ycnt2); for(int i=1,x;i<=n;i++) { scanf("%d",&x); ps(x); } while( cnt1+cnt2+cnt3<ycnt1+ycnt2 &&!q.empty()) { node qq=q.top(); q.pop(); int now=qq.x; int mid1=qq.y; int mid2=qq.z; if(cnt2==ycnt2) ps(mid1),cnt1++; else if(cnt1==ycnt1) ps(mid2),cnt2++; else//两种魔法都可以使用 { if(mid1>mid2) ps(mid2),cnt2++; else if(mid1<mid2) ps(mid1),cnt1++; else ps(mid1),cnt3++; } } LL res=0;//注意答案最大1e10，爆int while(!q.empty()) { res+=q.top().x; q.pop(); } printf("%lld\n",res); return 0;}得分记录
H题 拔河
问题描述
思路简述
思维题，主要的限制是：
（1）拉出来的队伍需要连续
（2）且有 l 1 ≤ r 1 < l 2 ≤ r 2 l_1\le r_1 <l_2\le r_2 l1≤r1<l2≤r2，字面理解就是拉出来的两队人不能有重合（不能有相同的人）
在这两个限制下，求两队伍力量值之和差距最小，第一个限制明显指向了前缀和，但第二个限制明显不好处理，暴力的话就是枚举四个数 l 1 , r 1 , l 2 , r 2 l_1,r_1,l_2,r_2 l1,r1,l2,r2，前缀和优化之后暴力枚举时间复杂度是 O ( n 4 ) O(n^4) O(n4)，但其实第二个限制完全没有用，因为是求差值，所以即使有重合的人也不影响结果（比如第一个队伍选1-4，第二个队伍选3-6，这俩队伍的差值其实和选1-2和5-6是一样的，因为3-4是重合的，对结果没有影响。
那么这个题就可以简化为：
给你n个数字，让你任选两个连续子序列（不完全相同），使俩子序列之和的差值最小，最小是多少。
解：O(n^2)预处理任意两点从i到j的连续子序列和s[i][j]，再把求出来的这些和排序，相邻相减取最小值即可。
注意开long long，爆int了
代码
#include<bits/stdc++.h>using namespace std;typedef long long LL;const int maxn=1e3+15;const int inf=0x3f3f3f3f;LL n,a[maxn],sum[maxn],mn=inf*inf;vector<LL>v;int main(){ scanf("%lld",&n); for(LL i=1;i<=n;i++) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i]; for(LL i=1;i<=n;i++) for(LL j=1;j<=i;j++) v.push_back(sum[i]-sum[j-1]); sort(v.begin(),v.end()); for(int i=1;i<v.size();i++) mn=min(mn,v[i]-v[i-1]); printf("%lld\n",mn); return 0;}过题记录
以上是C++B组的题，往下翻的时候看到了一道研究生组的题，顺道就做了，所以附带一道吊坠（暴力匹配+最小生成树）。
吊坠
问题描述
思路简述
暴力匹配+最小生成树（或者说最大生成树）
用 i , j i,j i,j两两枚举字符串，求 i i i到 j j j的边权值，然后跑最小生成树算法就行。
求边权值的时候，可以直接暴力匹配，思路就是你可以想象你现在枚举的这两个字符串变成两个环，然后一个不动，一个逐渐转圈，然后求匹配的权值，模拟的时候把每个字符串从后面复制一遍就可以。
时间复杂度 O ( n ∗ n ∗ 2 m ∗ 2 m ) = 1 e 8 O(n*n*2m*2m)=1e8 O(n∗n∗2m∗2m)=1e8
代码
#include<bits/stdc++.h>using namespace std;int n,m,f[205];;char s[205][205];struct node{ int u,v,w; node(int uu,int vv,int ww) { u=uu; v=vv;w=ww;}};bool cmp(node a,node b){ return a.w>b.w;}vector<node>g;int pp(int x,int y,int st){ int cnt=0,mx=0; for(int i=1;i<=m;i++) if(s[x][i]==s[y][i+st-1]) mx=max(++cnt,mx); else cnt=0; for(int i=1;i<=m;i++) if(s[x][i]==s[y][i+st-1]) mx=max(++cnt,mx); else cnt=0; return min(m,mx);}int solve(int x,int y){ int mx=0; for(int i=1;i<=m;i++) mx=max(mx,pp(x,y,i)); return mx;}int find(int x){ if(x==f[x]) return x; return f[x]=find(f[x]);}int main(){ scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%s",s[i]+1),f[i]=i; for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) s[i][j+m]=s[i][j]; for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) g.push_back(node(i,j,solve(i,j))); sort(g.begin(),g.end(),cmp); int cnt=0,ans=0; for(int i=0;i<g.size();i++) { int u=g[i].u,v=g[i].v,w=g[i].w; if(find(u)==find(v)) continue; f[find(u)]=find(v); cnt++;ans+=w; if(cnt==n-1) break; } printf("%d\n",ans); return 0;}过题记录
