©2020-2024 ioDraw All rights reserved
<>第十四届蓝桥杯大赛软件赛省赛 C/C++ 大学 B 组
注意！！！！！！！！！！这篇题解为赛时的个人做法，不代表是正确的，仅供参考。
更新：思路上应该都对，很多题都有细节错误，代码不用看了,太久没敲代码了(- -)
更新2：代码除了岛屿的都改好了，整数删除常数有点大，可能会t，赛时的代码一堆错误，还是对自己的文章负责，省赛打的太放松了，应该多自己造几组样例测得。最后两题lca，板子有一行脑抽了写错了居然没发现，然后求lca我是前一题复制到后一题，两题的样例都能过，结果两题都错了，把那一行代码改完就都a了，蓝桥杯给的样例是在是太水了。。。。。自己还是太久没敲代码，变菜了。(T
. T)
<>试题 A: 日期统计
dfs+剪枝即可，因为前四位一定是2023，五六位一定是1-12月，七八为也要满足条件，所以实际上搜索的范围比较少
最终答案:235
#include<bits/stdc++.h> using namespace std; const int N = 2e6+9; typedef long
long ll; int a[N]; int mon[] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; vector<
int> now; map<int,int> mp; int ans = 0; void dfs(int len,int dep){ if(len == 8){
int sum = 0; int m = now[4]*10 + now[5]; int d = now[6]*10 + now[7]; if(m < 1 ||
m> 12) return ; if(d < 1 || d > mon[m]) return ; for(int i = 0;i < 8;i++){ sum
*= 10; sum += now[i]; } if(!mp[sum]){ ans++; mp[sum] = 1; } return ; } for(int i
= dep;i <= 100;i++){ if(len == 0){ if(a[i] == 2){ now.push_back(a[i]); dfs(len+1
,i+1); now.pop_back(); } }else if(len == 1){ if(a[i] == 0){ now.push_back(a[i]);
dfs(len+1,i+1); now.pop_back(); } }else if(len == 2){ if(a[i] == 2){ now.
push_back(a[i]); dfs(len+1,i+1); now.pop_back(); } }else if(len == 3){ if(a[i]
== 3){ now.push_back(a[i]); dfs(len+1,i+1); now.pop_back(); } }else{ now.
push_back(a[i]); dfs(len+1,i+1); now.pop_back(); } } } void sol(){ for(int i = 1
;i <= 100;i++){ scanf("%d",&a[i]); } dfs(0,1); printf("%d",ans); } int main(){
sol(); return 0; }
<>试题 B: 01 串的熵
枚举0的个数,因为0个数比1小，所以遍历到23333333/2即可
最终答案：11027421
#include<bits/stdc++.h> using namespace std; const int N = 2e6+9; typedef long
long ll; void sol(){ int n = 23333333; for(int i = 0;i <= n/2;i++){ double ans =
-1.0*i*i/n*log2(1.0*i/n)-1.0*(n-i)*(n-i)/n*log2(1.0*(n-i)/n); if(abs(ans -
11625907.5798) <= 0.0001){ printf("%d",i); } } } int main(){ sol(); return 0; }
<>试题 C: 冶炼金属
数论分块知识，用二分也可以
#include<bits/stdc++.h> using namespace std; const int N = 2e6+9; typedef long
long ll; int main(){ int n; scanf("%d",&n); int maxx = 1000000000,minn = 0; for(
int i = 1;i <= n;i++){ int a,b; scanf("%d %d",&a,&b); maxx = min(maxx,a/b); minn
= max(minn,(a+b+1)/(b+1));//比赛时手快分子少加了个1，麻了(代码已改过) } printf("%d %d",minn,maxx);
return 0; }
<>试题 D: 飞机降落
因为N最多10，所以把所有飞机可能到达的顺序都检查一遍看看是否可行即可。复杂度O(T10!)
#include<bits/stdc++.h> using namespace std; const int N = 2e6+9; typedef long
long ll; struct node{ int t,d,l; }p[N]; int a[20]; void sol(){ int n; scanf("%d"
,&n); for(int i = 1;i <= n;i++){ scanf("%d %d %d",&p[i].t,&p[i].d,&p[i].l); a[i]
= i; } do{ int now = 0; int flag = 1; for(int i = 1;i <= n;i++){ int t = p[a[i]]
.t,d = p[a[i]].d,l = p[a[i]].l; if(now > t + d){ flag = 0; break; }else{ if(t >
now) now = t + l; else now = now + l; } } if(flag){ printf("YES\n"); return; } }
while(next_permutation(a+1,a+1+n)); printf("NO\n"); } int main(){ int t; scanf(
"%d",&t); while(t--){ sol(); } return 0; }
<>试题 E: 接龙数列
dp,dp[i]表示以i为结尾最长可以组成多长，那么答案就是n-max(dp[0-9])
复杂度O(n)
#include<bits/stdc++.h> using namespace std; const int N = 2e6+9; typedef long
long ll; struct node{ int t,w; }p[N]; int dp[20]; void sol(){ int n; scanf("%d",
&n); for(int i = 1;i <= n;i++){ int x; scanf("%d",&x); p[i].w = x % 10; while(x
>= 10){ x/=10; } p[i].t = x; } // for(int i = 1;i <= n;i++){ // printf("%d
%d\n",p[i].t,p[i].w); // } for(int i = 1;i <= n;i++){ dp[p[i].w] = max(dp[p[i].w
],dp[p[i].t] + 1); } int ans = 1000000000; for(int i = 0;i <= 9;i++){ ans = min(
ans,n-dp[i]); } printf("%d",ans); } int main(){ sol(); return 0; }
<>试题 F: 岛屿个数
首先dfs一次，把所有相连的岛屿都标上号。
一个个判断某一个岛屿是否被围住，如何判断，枚举所有的岛屿作为墙，当你从一个岛屿存在一个点，可以搜索走出n*m的棋盘就证明没有被围住，当所有其他岛屿作为墙，你都可以走出地图，那么这个岛屿就没有被围住。
复杂度O(n^4)
#include<bits/stdc++.h> using namespace std; const int N = 2e3+9; typedef long
long ll; int a[59][59]; int vis[59][59]; int dx[] = {0,0,1,-1}; int dy[] = {1,-1
,0,0}; int fobid = 0; int n,m; int ans[N]; int nc = 0; void dfs(int x,int y,int
co){ vis[x][y] = co; for(int i = 0;i <= 3;i++){ int xx = x + dx[i]; int yy = y +
dy[i]; if(xx < 1 || xx > n || yy < 1 || yy > m) continue; if(vis[xx][yy]||a[xx]
[yy] == 0){ continue; } dfs(xx,yy,co); } } int v[59][59]; void dfs2(int x,int y,
int co){ v[x][y] = 1; for(int i = 0;i <= 3;i++){ int xx = x + dx[i]; int yy = y
+ dy[i]; if(xx < 1 || xx > n || yy < 1 || yy > m){ ans[co] = 1; continue; } if(v
[xx][yy] || vis[xx][yy] == fobid){ continue; } dfs2(xx,yy,co); } } void sol(){
memset(vis,0,sizeof(vis)); memset(ans,0,sizeof(ans)); nc = 0; scanf("%d %d",&n,&
m); for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ scanf("%1d",&a[i][j]);
} } for(int i = 1;i <= n;i++){ for(int j = 1;j <= m;j++){ if(a[i][j]){ if(!vis[i
][j]){ dfs(i,j,++nc); } } } } for(fobid = 1;fobid <= nc;fobid++){ for(int i = 1;
i<= n;i++){ for(int j = 1;j <= m;j++){ if(vis[i][j] && fobid != vis[i][j]){ if(
ans[vis[i][j]]) continue; memset(v,0,sizeof(v)); dfs2(i,j,vis[i][j]); } } } }
int num = 0; for(int i = 1;i <= nc;i++){ num += ans[i]; } printf("%d\n",num); }
int main(){ int t; scanf("%d",&t); while(t--) sol(); return 0; }
<>试题 G: 子串简写
对结尾字符出现次数做前缀和，枚举a字符开头的位置，假设s[i]是a字符，那么i+k-1以后的出现的b都可以作为答案。
复杂度O(n)
#include<bits/stdc++.h> using namespace std; const int N = 2e6+9; typedef long
long ll; char s[N]; char a,b; ll sum[N]; void sol(){ int k,n; scanf("%d",&k);
scanf("%s",s+1); n = strlen(s+1); scanf(" %c",&a); scanf(" %c",&b); for(int i =
1;i <= n;i++){ if(s[i] == b) sum[i] = sum[i-1]+1; else sum[i] = sum[i-1]; } ll
ans= 0; for(int i = 1;i <= n;i++){ if(s[i] == a && i + k - 2 <= n){ ans += (sum[
n] - sum[i+k-2]); } } printf("%lld",ans); } int main(){ sol(); return 0; }
<>试题 H: 整数删除
维护两个set，一个set先对值再对位置大小排序，另一个则相反。然后模拟即可。
复杂度O(nlogn+klogn)
#include<bits/stdc++.h> using namespace std; const int N = 2e6+9; typedef long
long ll; struct nodevp{ int pos; ll val; bool operator < (const nodevp &p) const
{ if(val == p.val) return pos < p.pos; else return val < p.val; } bool operator
== (const nodevp &p) const{ return pos == p.pos && val == p.val; } }; struct
nodepv{ int pos; ll val; bool operator < (const nodepv &p) const{ if(pos == p.
pos) return val < p.val; else return pos < p.pos; } bool operator == (const
nodepv&p) const{ return pos == p.pos && val == p.val; } }; ll a[N]; set<nodevp>
svp; set<nodepv> spv; int n,k; void changepv(nodepv a,nodepv b){ spv.erase(a);
spv.insert(b); } void changevp(nodevp a,nodevp b){ svp.erase(a); svp.insert(b);
} void sol(){ scanf("%d %d",&n,&k); for(int i = 1;i <= n;i++){ scanf("%d",&a[i])
; nodevp v; v.val = a[i]; v.pos = i; svp.insert(v); nodepv p; p.val = a[i]; p.
pos= i; spv.insert(p); } for(int i = 1;i <= k;i++){ nodevp v = *svp.begin(); //
svp.erase(v); ll add = v.val; nodepv p; p.val = v.val; p.pos = v.pos; auto apv =
spv.find(p); if(apv != spv.begin()){ apv--; nodepv temp,nex; temp.pos = apv->
pos; temp.val = apv->val; nex.pos = temp.pos; nex.val = temp.val + add; nodevp
temp2,nex2; temp2.pos = apv->pos; temp2.val = apv->val; nex2.pos = temp2.pos;
nex2.val = temp2.val + add; changepv(temp,nex); changevp(temp2,nex2); // apv++;
} apv = spv.find(p); apv++; if(apv == spv.end()){ spv.erase(p); svp.erase(v);
continue; } nodepv temp,nex; temp.pos = apv->pos; temp.val = apv->val; nex.pos =
temp.pos; nex.val = temp.val + add; nodevp temp2,nex2; temp2.pos = apv->pos;
temp2.val = apv->val; nex2.pos = temp2.pos; nex2.val = temp2.val + add; changepv
(temp,nex); changevp(temp2,nex2); spv.erase(p); svp.erase(v); } while(spv.size()
){ nodepv p = *spv.begin(); printf("%lld ",p.val); spv.erase(p); } } int main(){
sol(); return 0; } // 5 3 // 4 1 2 8 7 // 5 4 // 1 4 2 8 7
<>试题 I: 景区导游
树上前缀和+lca。先算出不删除走完全称所需要的时间假设为asum。如何算，sum[i]代表从根走到i节点需要花多少时间，那么从u到v(后文表示为dis(u,v))则需要花sum[u]+sum[v]-sum[lca(u,v)]*2这么多时间，如果删去一个点i后，全程答案为
asum - dis(a[i],a[i+1]) - dis(a[i],a[i-1]) + dis(a[i-1],a[i+1]),删掉开头和结尾特判，入代码所示。
复杂度:O(nlogn)
#include<bits/stdc++.h> using namespace std; const int N = 2e5+9; typedef long
long ll; int n,k; int f[N][29]; int dep[N]; int a[N]; ll sum[N]; ll ans[N];
struct edge{ ll dis; int to; }; vector<edge> g[N]; int lca(int u,int v){ if(dep[
u] < dep[v]) swap(u,v); for(int i = 20;i >= 0;i--){ if(dep[f[u][i]] >= dep[v]) u
= f[u][i]; } if(u == v) return u; for(int i = 20;i >= 0;i--){ if(f[u][i] != f[v]
[i]){ u = f[u][i]; v = f[v][i]; } } return f[u][0]; } ll dis(int u,int v){
return (sum[u] + sum[v] - sum[lca(u,v)]*2); } void dfs(int now,int fa){ //
sum[now] = sum[now] + sum[fa]; f[now][0] = fa; dep[now] = dep[fa] + 1; for(int i
= 1;i <= 20;i++){ if(f[now][i-1]) f[now][i] = f[f[now][i-1]][i-1]; else break; }
for(auto j : g[now]){ if(j.to == fa) continue; sum[j.to] += sum[now] + j.dis;
dfs(j.to,now); } } void sol(){ scanf("%d %d",&n,&k); for(int i = 1;i <= n-1;i++)
{ int u,v; ll dis; scanf("%d %d %lld",&u,&v,&dis); edge p; p.dis = dis;p.to = v;
g[u].push_back(p); p.to = u; g[v].push_back(p); } dfs(1,0); ll asum = 0; for(
int i = 1;i <= k;i++){ scanf("%d",&a[i]); } for(int i = 2;i <= k;i++){ asum += (
sum[a[i-1]] + sum[a[i]] - sum[lca(a[i-1],a[i])]*2); } for(int i = 1;i <= k;i++){
if(i == 1){ ans[i] = asum - dis(a[i],a[i+1]); }else if(i == k){ ans[i] = asum -
dis(a[i],a[i-1]); }else{ ans[i] = asum - dis(a[i],a[i+1]) - dis(a[i],a[i-1]) +
dis(a[i-1],a[i+1]); } } for(int i = 1;i <= k;i++){ printf("%lld ",ans[i]); } }
int main(){ sol(); return 0; }
<>试题 J: 砍树
树上差分+lca。如果u到v想要断开，那么u到v路径上的任何一条边断开都可以，所以把u到v所经过的边权值加1，最后看那一条边的权值等于给出的无序对的个数，输出序号最大的那条边即可。
#include<bits/stdc++.h> using namespace std; const int N = 2e5+9; typedef long
long ll; int n,m; int f[N][29]; int dep[N]; ll sum[N]; int ans = -1; int fnum[N]
; struct edge{ ll dis; int to; }; vector<edge> g[N]; int lca(int u,int v){ if(
dep[u] < dep[v]) swap(u,v); for(int i = 20;i >= 0;i--){ if(dep[f[u][i]] >= dep[v
]) u = f[u][i]; } if(u == v) return u; for(int i = 20;i >= 0;i--){ if(f[u][i] !=
f[v][i]){ u = f[u][i]; v = f[v][i]; } } return f[u][0]; } void dfs(int now,int
fa){ // sum[now] = sum[now] + sum[fa]; f[now][0] = fa; dep[now] = dep[fa] + 1;
for(int i = 1;i <= 20;i++){ if(f[now][i-1]) f[now][i] = f[f[now][i-1]][i-1];
else break; } for(auto j : g[now]){ if(j.to == fa) continue; fnum[j.to] = j.dis;
dfs(j.to,now); } } void dfs2(int now,int fa){ for(auto j : g[now]){ if(j.to ==
fa) continue; dfs2(j.to,now); sum[now] += sum[j.to]; } if(sum[now] == m){ ans =
max(ans,fnum[now]); } } void sol(){ scanf("%d %d",&n,&m); for(int i = 1;i <= n-1
;i++){ int u,v; scanf("%d %d",&u,&v); edge p; p.dis = i;p.to = v; g[u].push_back
(p); p.to = u; g[v].push_back(p); } dfs(1,0); for(int i = 1;i <= m;i++){ int u,v
; scanf("%d %d",&u,&v); sum[u]++; sum[v]++; sum[lca(u,v)]-=2; } dfs2(1,0);
printf("%d",ans); } int main(){ sol(); return 0; }