2019 第十届蓝桥杯大赛软件赛决赛，国赛，C/C++大学B组题解

编程入门行业动态更新时间:2024-10-21 16:23:57

2019 第十届蓝桥杯大赛软件赛决赛，国赛，C/C++大学B组<a href=https://www.elefans.com/category/jswz/34/1769599.html style= 题解"/>

2019 第十届蓝桥杯大赛软件赛决赛，国赛，C/C++大学B组题解

文章目录

- - 第1题——平方序列（5分）
  - 第2题——质数拆分（5分）
  - 第3题——拼接（10分）
  - 第4题——求值（10分）
  - 第5题——路径计数（15分）
  - 第6题——最优包含（15分）
  - 第7题——排列数（20分）
  - 第8题——解谜游戏（20分）
  - 第9题——第八大奇迹（25分）
  - 第10题——燃烧权杖（25分）

官方题目链接：
/?id=70881

第1题——平方序列（5分）

题目：
思路：
2x^2 = 2019^2+y^2, 从2020开始枚举x, 用公式算出y，如果是个正数就是最小的。
答案为7020

#include<bits/stdc++.h>
using namespace std;int main(){for(int x = 2020; x <= 9999; x++){int y2 = 2*x*x-2019*2019;int y = sqrt(y2);if(y*y==y2){cout<<x+y<<"\n";return 0;}}return 0;
}

第2题——质数拆分（5分）

题意：
思路：
先把1-2019的质数都筛出来，然后作为体积Vi，跑容量为2019的背包。
fij表示到第i个素数为止，拼成j的方法数。
记得不开ll会爆。

答案是55965365465060

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn = 5050;//线性筛
LL vis[maxn], primes[maxn], cnt;
void get_primes(int n){for(int i = 2; i <= n; i++){if(!vis[i])primes[++cnt]=i;for(int j = 1; primes[j] <= n/i; j++){vis[primes[j]*i] = 1;if(i%primes[j]==0)break;}}
}LL f[maxn][maxn];int main(){get_primes(maxn-10);f[0][0] = 1;for(LL i = 1; i <= cnt; i++){for(LL j = 0; j <= 2019; j++){f[i][j] = f[i-1][j];if(j>=primes[i])f[i][j] += f[i-1][j-primes[i]];}}cout<<f[cnt][2019];return 0;
}

第3题——拼接（10分）

题目
思路：
找规律，发现除了沿右边界分割的情况，右上角那一个必选。
然后第一行可以选1-7的格子，第二行能选1-6，后面依次类推
且右端一定靠近对角线，下一行不能多余上一行，上下两行要连续。
然后dfs

所以答案是128

#include<bits/stdc++.h>
using namespace std;int a[50], n = 7;
int dx[] = {0,0,1,-1};
int dy[] = {1,-1,0,0};
int ans = 1;void dfs(int cur, int now){if(cur>=n || now==0){ans++;for(int i = 1; i <= n; i++)cout<<a[i]<<' '; cout<<"\n";return ;}for(int i = 0; i<now && i<=n-cur; i++){a[cur+1] = i;dfs(cur+1, i);a[cur+1] = 0;}
}int main(){for(int i = 1; i <= n; i++){memset(a,0,sizeof(a));a[1] = i;dfs(1,i);}cout<<ans;return 0;
}

第4题——求值（10分）

题意：
思路
数字有点小，，才100，暴力枚举每个数，求约数个数，第一个有100个约数的数肯定很小呀，然后输出就好了

答案是45360

#include<bits/stdc++.h>
using namespace std;int main(){for(int i = 100; ;i++){int cnt = 0;for(int j = 1; j <= i; j++){if(i%j==0)cnt++;}if(cnt==100){cout<<i<<"\n";return 0;}}return 0;
}

第5题——路径计数（15分）

题意：
思路：
直接0，0开始往外dfs走12步看看有没有回来即可。
对于自交的情况，因为走过的路不会往回走，所以不需要考虑。
！！！但是有一个特判没考虑到，因为vis是回溯当前的点不能走，但是我往右走一步可以直接往回走到起点，这个时候vis是不会影响到原点的，所以会炸，要减去这两个值。

所以答案是206

#include<bits/stdc++.h>
using namespace std;int ans = 0;
int ok = 0;
int dx[] = {0,0,-1,1};
int dy[] = {1,-1,0,0};
int vis[10][10];
void dfs(int x, int y, int s){if(s>12)return ;if(x==0 && y==0){ok++;if(ok==2 && s<=12){ok = 1;ans++;return ;}}for(int i = 0; i < 4; i++){int nx = x+dx[i], ny = y+dy[i];if(nx>=0&&nx<=7&&ny>=0&&ny<=7 && vis[nx][ny]==0){vis[nx][ny] = 1;dfs(nx,ny,s+1);vis[nx][ny] = 0;}}
}int main(){dfs(0,0,0);cout<<ans-2<<"\n";return 0;
}

第6题——最优包含（15分）

题意：
思路：给出字符串S和T，求S修改多少个字母能包含T。

类似于LCS，令f[i][j]表示S串前i个字符,包含T串前j个字符所需要的最小修改次数。
分四种情况转移。反正nm范围小，随便操作。

#include<bits/stdc++.h>
using namespace std;
int f[1010][1010];
int main(){string a, b;  cin>>a>>b;int n = a.size(), m = b.size();a = "0"+a, b = "0"+b;memset(f,0x3f,sizeof(f));f[0][0] = 0;for(int i = 1; i <= n; i++){f[i][0] = 0;for(int j = 1; j <= m; j++){f[i][j] = f[i-1][j]; //s[i-1]改到t[j]的最值，不用s[i]这个字符if(a[i]==b[j])f[i][j] = min(f[i][j], f[i-1][j-1]);//s[i-1]改到t[j-1]，s[i]与t[j]配对else f[i][j] = min(f[i][j], f[i-1][j-1]+1);//修改一个，增加一次次数}}cout<<f[n][m]<<"\n";return 0;
}

第7题——排列数（20分）

题意：
思路：
求1-n的排列中，有多少个是k单调的，k单调指的是有k-1个数比两边的大或小。
dp，记f(i,j)表示第i个数，j个折点的方案数。
转移时考虑将第i个数放入1~i-1的排列中，对折点数量的影响。
分类讨论插入的情况。
如果插入单调序列中，折点数量+2，波峰和波谷各一个。
如果插入波峰或波谷的两端，折点数量不变。
如果插入波峰或波谷的重心，折点数量+2。
如果插入区间端点(0或i-1)，折点数量+1。

所以f[i][j]=f[i−1][j]∗x+f[i−1][j−1]∗y+f[i−1][j−2]∗z
x,y,z分别为放弃后折点数量+0，+1，+2的方案数。
所以f[i][j]=f[i−1][j]∗j+f[i−1][j−1]∗2+f[i−1][j−2]∗(i−j).

#include<bits/stdc++.h>
using namespace std;
const int mod = 123456;
int f[550][550];int main(){int n, k;  cin>>n>>k;f[1][1] = 1;  f[2][1] = 2;for(int i = 3; i <= n; i++){for(int j = 1; j<=k && j<=i; j++){f[i][j] = (f[i][j]+f[i-1][j]*j%mod+f[i-1][j-1]*2%mod)%mod;if(j>1)f[i][j] = (f[i][j]+f[i-1][j-2]*(i-j))%mod;}}cout<<f[n][k]<<"\n";return 0;
}

第8题——解谜游戏（20分）

题意：
思路：多组样例，每次三个字符串，可以旋转或者交换内外圈0点，求能否外圈绿色，中圈红色，内圈黄色。
模拟转圈的过程，可以发现，内圈转完4次（转完一圈），中圈转半圈，大圈转三分之一圈，那么可以知道，内圈0号位置对应中圈有两个位置（0号和4号），外圈有三个位置（0号、4号、8号，即可以发生换圈位置的情况）。

可以分成四个组，只有在组内才能发生跨圈的操作，所以只要每个的条件都满足1个Y、2个R、3个G就可以达成目标输出YES。

#include<bits/stdc++.h>
using namespace std;int main(){int T;  cin>>T;while(T--){string a, b, c;  cin>>a>>b>>c; //外，中，内int z[200] = {0}, ok = 1;for(int i = 0; i < 4; i++){ //四组z[c[(i+4)%4]-'A']++;//内z[b[(i+4)%4]-'A']++;//中z[b[(i+4)%8]-'A']++;z[a[(i+4)%4]-'A']++;//外z[a[(i+4)%12]-'A']++;z[a[(i+8)%12]-'A']++;if(z['R'-'A']==2 && z['G'-'A']==3 && z['Y'-'A']==1){memset(z,0,sizeof(z));}else{// cout<<z['R'-'A']<<" "<<z['G'-'A']<<"\n";ok = 0;  break;}}if(ok==1)cout<<"YES\n";else cout<<"NO\n";}return 0;
}

第9题——第八大奇迹（25分）

题意：

【样例输入】
10 15
C 1 10
C 2 20
C 3 30
C 4 40
C 5 50
C 6 60
C 7 70
C 8 80
C 9 90
C 10 100
Q 1 2
Q 1 10
Q 1 8
C 10 1
Q 1 10
【样例输出】
0
30
10
20
思路：
1-1e5的数组，初始为0，单点修改，查询区间第8大的值。
emmm，众所周知的动态区间第k小问题。
静态主席树：可持久化权值线段树。×
动态主席树：树套树。√

主席树或者线段树维护10个节点（区间最大的8个值，每次更新从左右子树排序过的最大的8个值pushup）吧，虽然板子不好敲，但还是挺板的
所以我选线段树（）

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e5+10;
int val[maxn<<2][8], sum[maxn<<2];//区间长度//线段树
#define lch (p<<1)
#define rch (p<<1|1)
void pushup(int p){//按从大到小合并左右区间到当前区间（类似于归并）int a = 0, b = 0, cc = 0;while(a < sum[lch] && b < sum[rch] && cc < 8){if(val[lch][a] > val[rch][b]){val[p][cc++] = val[lch][a++];}else{val[p][cc++] = val[rch][b++];}}while(a<sum[lch] && cc < 8)val[p][cc++] = val[lch][a++];while(b<sum[rch] && cc < 8)val[p][cc++] = val[rch][b++];sum[p] = min(8, sum[lch]+sum[rch]);
}
void add(int p, int l, int r, int x, int v){if(l==r){val[p][0] = v;sum[p] = 1;return ;}int mid = l+r>>1;if(x <= mid){add(lch, l, mid, x, v);}else{add(rch, mid+1, r, x, v);}pushup(p);
}
int tmp[100];
void merge(int kk[], int k1[], int k2[]){int a = 0, b = 0, cc = 0;while(a < 8 && b < 8){if(k1[a]>=k2[b])tmp[cc++]=k1[a++];else tmp[cc++]=k2[b++];}while(a<8)tmp[cc++]=k1[a++];while(b<8)tmp[cc++]=k2[b++];for(int i = 0; i < 8; i++)kk[i]=tmp[i];
}
int* query(int p, int l, int r, int ql, int qr){if(ql<=l && r<=qr)return val[p];int mid = l+r>>1;if(qr <= mid)return query(lch, l, mid, ql, qr);else if(ql>mid)return query(rch,  mid+1, r, ql, qr);int* k1 = query(lch, l, mid, ql, qr);int* k2 = query(rch,  mid+1, r, ql, qr);int* kk = new int[9];merge(kk, k1, k2);return kk;
}int main(){int n, m;  cin>>n>>m;for(int i = 1; i <= m; i++){string op;  cin>>op;if(op=="C"){int p, x;  cin>>p>>x;add(1,1,n,p,x);}else{int a, b;  cin>>a>>b;cout<<query(1,1,n,a,b)[7]<<"\n";}}return 0;
}