题解|第十三届蓝桥杯大赛软件赛省赛B组(个人思路) c++|算法

个人思路，全靠口嗨，就图一乐
如果哪里错了，评论或者私信告诉我/(ㄒoㄒ)/~~
如果代码锅了，就锅了吧 (╥﹏╥)

- 简单思路
- - 试题 A: 九进制转十进制
  - 试题 B: 顺子日期
  - 试题 C: 刷题统计
  - 试题 D: 修剪灌木
  - 试题 E: X 进制减法
  - 试题 F: 统计子矩阵
  - 试题 G: 积木画
  - 试题 H: 扫雷
  - 试题 I: 李白打酒加强版
  - 试题 J: 砍竹子
- 参考代码
- - A: 九进制转十进制
  - B: 顺子日期（这里012是算顺子的....）
  - C: 刷题统计
  - D: 修剪灌木
  - E: X 进制减法
  - F: 统计子矩阵 (二分写法，双指针写法回头补)
  - G: 积木画
  - H: 扫雷 (暴力混分版)
  - I: 李白打酒加强版
  - J: 砍竹子
- 总结

简单思路试题 A: 九进制转十进制
手算或者程序跑，res = 1478

文章图片

试题 B: 顺子日期
手数日历或者写个程序跑一下都行，我写的是 14。
但是，对于012是不是顺子这件事，我也不晓得呀 ((lll￢ω￢))。

20220120
20220121
20220122
20220123
20220124
20220125
20220126
20220127
20220128
20220129
20221012
【题解|第十三届蓝桥杯大赛软件赛省赛B组(个人思路)】20221123
20221230
20221231

试题 C: 刷题统计
先r e s = n 5 ? a + 2 ? b res = \frac{n}{5*a+2*b} res=5?a+2?bn? ,n = n % ( 5 ? a + 2 ? b ) n = n \%(5*a+2*b) n=n%(5?a+2?b)
再看一下剩下的 n 要写几天。
试题 D: 修剪灌木
对于第 i 课树， r e s = m a x ( i ? 1 , n ? i ) ? 2 res = max(i-1,n-i)*2 res=max(i?1,n?i)?2
试题 E: X 进制减法
我愿称它为最恶心的一个题。
如果A ? B > = 0 A - B >= 0 A?B>=0, 对于每一位选中的进制为m a x ( a i + 1 , b i + 1 , 2 ) max(a_i+1,b_i+1,2) max(ai?+1,bi?+1,2)
如果A ? B < 0 A - B < 0 A?B<0, 对于每一位选中的进制为n n n
试题 F: 统计子矩阵
我的写法是：二维前缀和+二分枚举，时间复杂度O ( n 3 ? l o g 2 ( n ) ) O(n^3*log_2(n)) O(n3?log2?(n))

具体写法：
枚举每一个点(i,j)作为矩阵的左上角，再遍历右下角点(x,y) 中的 x，最后二分找合法的最大的 y。

但是，大佬们说，会超时。更优的写法是：双指针，时间复杂度O ( n 3 ) O(n^3) O(n3)

具体写法：
枚举矩阵的所在行x 和 i (上边界和下边界)，双指针分别表示矩阵的两个列 y 和 j。

试题 G: 积木画
本人的DP写法。
状态定义：
d p i , 1 dp_{i,1} dpi,1? 表示前i-1列摆满，第 i 列第一行放了积木的方案数
d p i , 2 dp_{i,2} dpi,2? 表示前i-1列摆满，第 i 列第二行放了积木的方案数
d p i , 3 dp_{i,3} dpi,3? 表示前i列摆满的方案数
初始化：
d p 0 , 3 = 1 dp_{0,3} = 1 dp0,3?=1
d p 1 , 3 = 1 dp_{1,3} = 1 dp1,3?=1
d p 2 , 1 = d p 2 , 2 = 1 dp_{2,1} = dp_{2,2} = 1 dp2,1?=dp2,2?=1
转义状态( i > 1)：
d p i + 1 , 1 = d p i , 2 + d p i ? 1 , 3 dp_{i+1,1} = dp_{i,2} + dp_{i-1,3} dpi+1,1?=dpi,2?+dpi?1,3?
d p i + 1 , 2 = d p i , 1 + d p i ? 1 , 3 dp_{i+1,2} = dp_{i,1} + dp_{i-1,3} dpi+1,2?=dpi,1?+dpi?1,3?
d p i , 3 = d p i ? 1 , 1 + d p i ? 1 , 2 + d p i ? 1 , 3 + d p i ? 2 , 3 dp_{i, 3} = dp_{i-1,1} + dp_{i-1,2} + dp_{i-1, 3} + dp_{i-2,3} dpi,3?=dpi?1,1?+dpi?1,2?+dpi?1,3?+dpi?2,3?
最后r e s = d p n , 3 res = dp_{n,3} res=dpn,3?
ps：应该有更简单的DP思路，我这里想复杂了
试题 H: 扫雷
几何题咱不会呀，大佬们说 leetcode 上有类似的。
写了个暴力代码，每次给出一个手雷就去暴力统计，混百分之四十没问题。
试题 I: 李白打酒加强版
依然是DP。
状态定义：
d p i , j , k dp_{i,j,k} dpi,j,k? 表示前 i 个操作中有 j 次喝酒并且酒还有 k 斗的方案数
初始化：
d p 0 , 0 , 2 = 1 dp_{0,0,2} = 1 dp0,0,2?=1
转义状态：
当k ? 2 < = m k*2 <= m k?2<=m 时， d p i + 1 , j , k = d p i + 1 , j , k + d p i , j , k dp_{i+1,j,k} = dp_{i+1,j,k} + dp_{i,j,k} dpi+1,j,k?=dpi+1,j,k?+dpi,j,k?
当k > 0 k > 0 k>0 时， d p i + 1 , j + 1 , k + 1 = d p i + 1 , j + 1 , k + 1 + d p i , j , k dp_{i+1,j+1,k+1} = dp_{i+1,j+1,k+1} + dp_{i,j,k} dpi+1,j+1,k+1?=dpi+1,j+1,k+1?+dpi,j,k?
ps：注意最后一次操作必须是喝酒
最后r e s = d p n + m , m , 0 res = dp_{n+m,m,0} res=dpn+m,m,0?
试题 J: 砍竹子
并查集实现区间合并，同时维护双链表。
分析题目给出的操作可得：每次操作后竹子都会变短，并且竹子变矮的路线是唯一的，故而每次选择最高的竹子操作即可。
参考代码 A: 九进制转十进制

#include #include #define ll long long #define IOS ios::sync_with_stdio(false) using namespace std; const int maxn = 2e5 + 5; int main(){ IOS; int n = 2022; int res = 2*9*9*9 + 0*9*9 + 2*9 + 2; // 1478 cout << res << endl; while(res){ cout << res%9; res /= 9; } cout << endl; return 0; }

B: 顺子日期（这里012是算顺子的…）

#include #define ll long long #define IOS ios::sync_with_stdio(false) using namespace std; const int maxn = 2e5 + 5; int a[100] = {0,2,0,2,2}; int day[15] = {0,31,28,31,30,31,30,31,31,30,31,30,31}; int main(){ IOS; int res = 0; for(int i = 1; i <= 12; i++){ a[5] = i / 10; a[6] = i % 10; for(int j = 1; j <= day[i]; j++){ a[7] = j / 10, a[8] = j % 10; for(int k = 3; k <= 8; k++){ if(a[k-2]+1 == a[k-1] && a[k-1]+1 == a[k]){ printf("%3d2022%02d%02d\n", ++res, i, j); break; } } } } cout << res << endl; // 14 return 0; }

C: 刷题统计

#include #define ll long long #define IOS ios::sync_with_stdio(false) using namespace std; const int maxn = 2e5 + 5; int main(){ IOS; ll a, b, n; cin >> a >> b >> n; ll res = n / (a*5+b*2) * 7; n %= (a*5+b*2); for(int i = 1; i <= 5; i++) if(n > 0) res++, n -= a; for(int i = 1; i <= 2; i++) if(n > 0) res++, n -= b; cout << res << endl; return 0; }

D: 修剪灌木

#include #define ll long long #define IOS ios::sync_with_stdio(false) #define endl "\n" using namespace std; const int maxn = 2e5 + 5; int main(){ IOS; int n; cin >> n; for(int i = 1; i <= n; i++){ int tmp = max(i-1, n-i) * 2; cout << tmp << endl; } return 0; }

E: X 进制减法

#include #define ll long long #define IOS ios::sync_with_stdio(false) #define endl "\n" using namespace std; const ll mod = 1e9 + 7; const int maxn = 2e5 + 5; ll a[maxn], b[maxn], c[maxn]; int main(){ IOS; int n; cin >> n; int m1, m2; cin >> m1; for(int i = 1; i <= m1; i++) cin >> a[m1-i+1]; cin >> m2; for(int i = 1; i <= m2; i++) cin >> b[m2-i+1]; int len = max(m1, m2) + 1; for(int i = 1; i < len; i++) c[i] = a[i] - b[i]; ll res = 0, last = 1; for(int i = 1; i < len; i++){ int tmp = max(a[i], b[i]) + 1; tmp = max(tmp, 2); if(c[i] < 0){ c[i] = c[i] + tmp; c[i+1]--; } res = res + c[i] * last % mod; res %= mod; last *= tmp; } if(c[len] == -1){ // 如果为负数 for(int i = 1; i <= n; i++) swap(a[i], b[i]); swap(m1, m2); for(int i = 1; i < len; i++) c[i] = a[i] - b[i]; res = 0, last = 1; for(int i = 1; i < len; i++){ int tmp = n; if(c[i] < 0){ c[i] = c[i] + tmp; c[i+1]--; } res = res + c[i] * last % mod; res %= mod; last *= tmp; }res = (-1*res+mod) % mod; } cout << res << endl; return 0; }/* 11 3 10 4 0 3 1 2 08 4 4 3 2 1 4 5 3 2 1 */

F: 统计子矩阵 (二分写法，双指针写法回头补)

#include #define ll long long #define IOS ios::sync_with_stdio(false) #define endl "\n" using namespace std; const ll mod = 1e9 + 7; const int maxn = 2e5 + 5; ll a[505][505], b[505][505]; ll sum(int i, int j, int x, int y){ ll res = b[x][y] - b[i-1][y] - b[x][j-1] + b[i-1][j-1]; return res; }int main(){ IOS; ll n, m, k; cin >> n >> m >> k; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ cin >> a[i][j]; b[i][j] = a[i][j] + b[i][j-1] + b[i-1][j] - b[i-1][j-1]; } } ll res = 0; for(int i = 1; i <= n; i++){ for(int j = 1; j <= m; j++){ for(int x = i; x <= n; x++){ int l = j, r = m, y = -1; while(l <= r){ int mid = l + r >> 1; if(sum(i, j, x, mid) <= k){ y = mid; l = mid + 1; } else r = mid - 1; } if(y != -1) res += y-j+1; } } } cout << res << endl; return 0; }/* 3 4 10 1 2 3 4 5 6 7 8 9 10 11 12 */

G: 积木画

#include #define ll long long #define IOS ios::sync_with_stdio(false) #define endl "\n" using namespace std; const ll mod = 1e9 + 7; const int maxn = 1e7 + 5; ll dp[maxn][4]; int main(){ IOS; int n; cin >> n; dp[0][3] = 1; dp[1][3] = 1; dp[2][1] = dp[2][2] = 1; for(int i = 2; i <= n; i++){ dp[i+1][1] = (dp[i+1][1] + dp[i-1][3] + dp[i][2]) % mod; dp[i+1][2] = (dp[i+1][2] + dp[i-1][3] + dp[i][1]) % mod; dp[i][3] = (dp[i][3] + dp[i-1][1] + dp[i-1][2] + dp[i-2][3] + dp[i-1][3]) % mod; } cout << dp[n][3] << endl; return 0; }/* 3 5 */

H: 扫雷 (暴力混分版)

#include #define ll long long #define IOS ios::sync_with_stdio(false) #define endl "\n" using namespace std; const ll mod = 1e9 + 7; const int maxn = 1e6 + 5; typedef struct Node{ double x, y, r; int flag; } node; int n, m; node a[maxn]; bool check(node A, node B){ double len = (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y); len = sqrt(len); if(A.r + B.r > len) return 1; return 0; }void solve(int id){ a[id].flag = 0; for(int i = 1; i <= n; i++){ if(a[i].flag == 0) continue; if(check(a[i], a[id])){ solve(i); } } }int main(){ IOS; cin >> n >> m; for(int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y >> a[i].r, a[i].flag = 1; node b; for(int i = 1; i <= m; i++){ cin >> b.x >> b.y >> b.r; for(int j = 1; j <= n; j++){ if(a[i].flag == 0) continue; if(check(a[i], b)){ solve(i); } } } int res = n; for(int i = 1; i <= n; i++) res -= a[i].flag; cout << res << endl; return 0; }/* 2 1 2 2 4 4 4 2 0 0 5 2 */

I: 李白打酒加强版

#include #define ll long long #define IOS ios::sync_with_stdio(false) #define endl "\n" using namespace std; const ll mod = 1e9 + 7; const int maxn = 1e7 + 5; ll dp[205][105][105]; // res = dp[n+m][m][0] int main(){ memset(dp, 0, sizeof(0)); IOS; int n, m; cin >> n >> m; dp[0][0][2] = 1; for(int i = 0; i <= n+m; i++){ for(int j = min(i, m); j >= 0; j--){ for(int k = m; k >= 0; k--){ if(k*2 <= m && i+1 != n+m) dp[i+1][j][k*2] = (dp[i+1][j][k*2] + dp[i][j][k]) % mod; if(k > 0) dp[i+1][j+1][k-1] = (dp[i+1][j+1][k-1] + dp[i][j][k]) % mod; } } } cout << dp[n+m][m][0] << endl; return 0; } /* 5 10 14 */

J: 砍竹子

#include #define ll long long #define IOS ios::sync_with_stdio(false) #define endl "\n" using namespace std; const ll mod = 1e9 + 7; const int maxn = 1e6 + 5; priority_queue > qu; int f[maxn]; int l[maxn], r[maxn]; int find(int x){ if(x == f[x]) return x; else return f[x] = find(f[x]); }void join(int x, int y){ int fx = find(x); int fy = find(y); if(fx != fy){ f[fx] = fy; l[fy] = min(l[fy], l[fx]); r[fy] = max(r[fy], r[fx]); } }ll a[maxn]; int main(){ IOS; int n; cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; for(int i = 1; i <= n; i++) f[i] = i; for(int i = 1; i <= n; i++) l[i] = i-1; for(int i = 1; i <= n; i++) r[i] = i+1; for(int i = 2; i <= n; i++){ if(a[i] == a[i-1]){ join(i, i-1); } } for(int i = 1; i <= n; i++) if(f[i] == i) qu.push(make_pair(a[i], i)); int res = 0; while(!qu.empty()){ int id = qu.top().second, h = qu.top().first; qu.pop(); if(id != find(id)) continue; if(a[id] != h || a[id] == 1) continue; res++; a[id] = sqrt(h/2+1); //cout << res << ' ' << id << ' ' << h << " " << a[id] << endl; if(l[id] != 0 && a[id] == a[l[id]]) join(id, l[id]); if(r[id] != n+1 && a[id] == a[r[id]]) join(id, r[id]); if(a[id] != 1) qu.push(make_pair(a[id], find(id))); } cout << res << endl; return 0; }/* 6 2 1 4 2 6 7 5 */

总结题目涉及到的算法多为常见算法，个人感觉难度比不上XCPC省赛。
怀念可以让学弟敲代码，我自己口嗨的日子~~~