-
2022年6月第十三届蓝桥杯大赛软件赛全国决赛C++A组题解
试题 A: 小蓝与钥匙
C(28,14)*错排
错排可以容斥或者递推
1286583532342313400
代码如下：
#include<bits/stdc++.h> using namespace std; const int N = 16; long long dp[N]; int main() { long long ans = 1; int ct = 2; for(int i =15;i<=28;i++) { ans =ans*i; while(ans%ct==0&&ct<=14) ans/=ct,ct++; } dp[2]=1,dp[3]=2; for(int i = 3;i<=14;i++) dp[i]=1ll*(i-1)*(dp[i-1]+dp[i-2]); cout<<ans*dp[14]<<endl; return 0 ; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
试题 B: 排列距离
康托展开，注意是循环排列。
试题 C: 内存空间
预计得分：100%
模拟即可
代码如下：
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const long long mod = 1e9 + 7; string str; void solve() { int n; scanf("%d", &n); getchar(); long long ans = 0; for (int i = 1; i <= n; i++) { getline(cin, str); string TP = ""; int m = str.size(); bool f = 0; for (int i = 0; i < m; i++) { if (!f) { TP += str[i]; if (TP == "int" || TP == "long" || TP == "String") f = 1; continue; } if (TP == "String") { bool flag = 0; for (int j = i; j < m; j++) { if (!flag) { if (str[j] == '\"') flag = 1; continue; } if (str[j] == '\"') { flag = 0; continue; } ans++; } break; } if (str[i] == '[') { bool flag = 0; long long res; for (int j = i + 2; j < m; j++) { if (!flag) { if (str[j] == '[') flag = 1, res = 0; continue; } if (str[j] == ']') { flag = 0; ans += res * (TP == "int" ? 4 : 8); continue; } res = res * 10 + str[j] - '0'; } break; } for (int j = i; j < m; j++) { if (str[j] == ',' || str[j] == ';') ans += (TP == "int" ? 4 : 8); } break; } } long long B = ans % 1024; long long KB = ans / 1024 % 1024; long long MB = ans / 1024 / 1024 % 1024; long long GB = ans / 1024 / 1024 / 1024 % 1024; if (GB) printf("%lldGB", GB); if (MB) printf("%lldMB", MB); if (KB) printf("%lldKB", KB); if (B) printf("%lldB\n", B); } int main() { solve(); return 0; } /* 1 long[] nums=new long[131072]; 4 int a=0,b=0; long x=0,y=0; String s1=??hello??,s2=??world??; long[] arr1=new long[100000],arr2=new long[100000]; */- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
试题 D: 最大公约数
预计得分：100%
如果数组中已经有 1 1 1，那么直接用 1 1 1平铺即可。
否则找出最小区间满足区间 G C D = 1 GCD=1 GCD=1，用这个 1 1 1进行平铺。
寻找方法可以使用二分+RMQ。
代码如下：
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const long long mod = 1e9 + 7; const long long INF = 0x3f3f3f3f; int a[N]; struct node { int l, r, g; } tr[N << 2]; void pushup(int k) { tr[k].g = __gcd(tr[k * 2].g, tr[k * 2 + 1].g); } void build(int k, int l, int r) { tr[k].l = l, tr[k].r = r; if (l == r) { tr[k].g = a[l]; return; } int mid = l + r >> 1; build(k * 2, l, mid); build(k * 2 + 1, mid + 1, r); pushup(k); } int query(int k, int L, int R) { if (tr[k].l == L && tr[k].r == R) { return tr[k].g; } int mid = (tr[k].l + tr[k].r) >> 1; if (R <= mid) return query(k * 2, L, R); else if (L > mid) return query(k * 2 + 1, L, R); else return __gcd(query(k * 2, L, mid), query(k * 2 + 1, mid + 1, R)); } void solve() { int n; scanf("%d", &n); int ct = 0; for (int i = 1; i <= n; i++) { scanf("%d", &a[i]); ct += a[i] == 1; } if (ct) //有1直接平铺 { printf("%d\n", n - ct); return; } build(1, 1, n); if (query(1, 1, n) != 1) //肯定不行 { puts("-1"); return; } int min_step = INF; for (int i = 1; i <= n; i++) { int l = i + 1, r = n, res = INF; while (l <= r) { int mid = l + r >> 1; if (query(1, i, mid) == 1) { res = mid - i; r = mid - 1; } else l = mid + 1; } min_step = min(min_step, res); } printf("%d\n", min_step + n - 1); } int main() { solve(); return 0; } /* 3 4 6 9 5 6 4 6 10 5 */- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
试题 E: owo
预计得分：10%
应该是个DP，刚开始没什么思路，后面也没时间想了，交了暴力。
代码如下：
#include <bits/stdc++.h> using namespace std; const int N = 1e6 + 5; int ans = 0; string s[N]; int ct = 0; int func() { int r = 0; for (int i = 1; i <= 1e3; i++) { random_shuffle(s + 1, s + 1 + ct); string tmp; for (int i = 1; i <= ct; i++) tmp += s[i]; int n = tmp.size(); int res = 0; for (int i = 2; i < n; i++) res += tmp[i - 2] == 'o' && tmp[i - 1] == 'w' && tmp[i] == 'o'; r = max(r, res); } return r; } void solve() { srand(time(NULL)); int n; cin >> n; for (int i = 1; i <= n; i++) { string str; cin >> str; if (str[0] != 'o' && str[0] != 'w' && str[(int)str.size() - 1] != 'o' && str[(int)str.size() - 1] != 'w') //剪枝 { printf("%d\n", ans); continue; } else { s[++ct] = str; ans = func(); printf("%d\n", ans); } } } int main() { solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
试题 F: 环境治理
预计得分：100%
比较简单的一个题，二分+FLOYD求最短路。时间复杂度 n 3 l o g m n^3logm n3logm，其中m为把所有路径清理到下限的所需天数（开个 1 e 8 、 1 e 9 1e8、1e9 1e8、1e9都行）。
代码如下：
#include<bits/stdc++.h> using namespace std; const int N = 105; const long long mod = 1e9+7; const int INF= 0x3f3f3f3f; int w[N][N]; int ww[N][N]; int minn[N][N]; int n , q; int check(int day) { int ans =0 ; for(int i =0; i<n; i++) for(int j =0; j<n; j++) ww[i][j]=w[i][j]; for(int i =0; i<n; i++) { int val = day/n+(day%n>=i+1?1:0); for(int j =0 ; j<n; j++) ww[i][j]-=val,ww[j][i]-=val; } for(int i =0; i<n; i++) for(int j =0 ; j<n; j++) ww[i][j]=max(minn[i][j],ww[i][j]); for(int k =0 ; k<n; k++) for(int i =0 ; i<n; i++) for(int j =0 ; j<n; j++) ww[i][j]=min(ww[i][j],ww[i][k]+ww[k][j]); for(int i =0; i<n; i++) for(int j =0; j<n; j++) ans+=ww[i][j]; return ans ; } void solve() { scanf("%d %d",&n,&q); for(int i =0; i<n; i++) for(int j =0 ; j<n; j++) scanf("%d",&w[i][j]); for(int i =0; i<n; i++) for(int j =0 ; j<n; j++) scanf("%d",&minn[i][j]); int l =0,r= 100000*n,ans =-1; while(l<=r) { int mid = l+r>>1; if(check(mid)<=q) { r= mid -1; ans = mid; } else l=mid+1; } cout<<ans<<endl; } int main() { solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
试题 G: 选素数
预计得分：30%
数学废物，没思路，交了暴力。
代码如下：
#include <bits/stdc++.h> using namespace std; const int N = 5005; const long long mod = 1e9 + 7; const int INF = 0x3f3f3f3f; bool f[N]; int prime[N]; int ct; void init() { f[0] = f[1] = 1; for (int i = 2; i < N; i++) if (!f[i]) { prime[++ct] = i; for (int j = i + i; j < N; j += i) f[j] = 1; } } void solve() { init(); int n; cin >> n; for (int x = 2; x <= n; x++) { for (int p1 = 1; p1 <= ct && prime[p1] < x; p1++) { int xx = x; int a = prime[p1]; if (x % a) xx = (xx / a + 1) * a; if (xx > n) //剪枝 continue; for (int p2 = 1; p2 <= ct && prime[p2] < xx; p2++) { a = prime[p2]; int xxx = xx; if (xx % a) xxx = (xx / a + 1) * a; if (xxx == n) { cout << x << endl; return; } } } } puts("-1"); } int main() { solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
试题 H: 替换字符
预计得分：40%
感觉需要神奇的数据结构来维护，并不会，交了暴力。
#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 5; const long long mod = 1e9 + 7; const long long INF = 0x3f3f3f3f; char s[N]; int l, r; char a[3], b[3]; void solve() { scanf("%s", s + 1); int n = strlen(s + 1); int m; scanf("%d", &m); while (m--) { scanf("%d %d %s %s", &l, &r, a, b); for (int i = l; i <= r; i++) if (s[i] == a[0]) s[i] = b[0]; } printf("%s", s + 1); } int main() { solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
试题 I: 三角序列
预计得分：40%
单独维护每个三角形， 类似于分块的思想，边界单独维护一下。
时间复杂度： n m l o g n l o g n nmlognlogn nmlognlogn
代码如下：
#include <bits/stdc++.h> using namespace std; const int N = 2e5 + 5; const long long mod = 1e9 + 7; const long long INF = 0x3f3f3f3f; struct tri { int typ, len, l, r; } a[N]; long long pre[N]; //前缀列数量之和 int n, m; long long cal2(int len, int h) //计算边长为len的三角形 高度<=h的贡献 { long long sum = 1ll * len * (len + 1) / 2; long long len2 = max(0, len - h); long long res = 1ll * len2 * (len2 + 1) / 2; return sum - res; } long long cal(int col, int idx, int h) //计算 第idx个三角形，从第col列开始， 高度<=h的贡献 { if (col > a[idx].r) return 0; if (a[idx].typ == 0) { long long s1 = cal2(a[idx].len, h); long long len2 = col - a[idx].l; long long s2 = cal2(len2, h); return s1 - s2; } else { long long len2 = a[idx].r - col + 1; return cal2(len2, h); } } int check(int l, int r, int h) { int left_idx = lower_bound(pre + 1, pre + 1 + n, l) - pre; int right_idx = lower_bound(pre + 1, pre + 1 + n, r) - pre; if (left_idx == right_idx) //只有一个三角形 return cal(l, left_idx, h) - cal(r + 1, left_idx, h); else { long long ans = 0; ans += cal(l, left_idx, h); ans += cal(a[right_idx].l, right_idx, h) - cal(r + 1, right_idx, h); for (int i = left_idx + 1; i < right_idx; i++) //计算中间的三角形贡献 ans += cal(a[i].l, i, h); return ans; } } void solve() { scanf("%d %d", &n, &m); int max_h = 0; for (int i = 1; i <= n; i++) { scanf("%d %d", &a[i].len, &a[i].typ); pre[i] = pre[i - 1] + a[i].len; a[i].l = pre[i - 1] + 1; a[i].r = pre[i]; max_h = max(max_h, a[i].len); } for (int i = 1; i <= m; i++) { int L, R, v; scanf("%d %d %d", &L, &R, &v); int l = 1, r = max_h, h = -1; while (l <= r) { int mid = l + r >> 1; if (check(L, R, mid) >= v) { h = mid; r = mid - 1; } else l = mid + 1; } printf("%d\n", h); } } int main() { solve(); return 0; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
试题 J: 括号序列树
树的最大匹配的定义？
-
相关阅读:
CesiumJS 2022^ 源码解读[6] - 三维模型（ModelExperimental）新架构
【光学】基于矩阵法和等效界面法分析光学薄
LeetCode二叉树系列——107.二叉树的层序遍历II
openproject在docker下的安装
Python 中的日期和时间
【密码学相关】常用的期刊，会议，实验室
「南凌科技SASE DAY」助力企业数字化转型的挑战和应对实践
算法-第几个幸运数
ARM可用的可信固件项目简介
Qt窗口无标题栏拖动放大
- 原文地址：https://blog.csdn.net/hesorchen/article/details/125345898