自学内容网 自学内容网
自学内容网 > 正文

蓝桥杯_B组_省赛_2022（用作博主自己学习）

🕗 发布于 2025-01-14 02:07 蓝桥杯  
 题目链接算法
11.九进制转十进制 - 蓝桥云课

进制转换

21.顺子日期 - 蓝桥云课

时间与日期

31.刷题统计 - 蓝桥云课

时间与日期

41.修剪灌木 - 蓝桥云课

思维

51.X 进制减法 - 蓝桥云课

贪心

61.统计子矩阵 - 蓝桥云课

二维前缀和

71.积木画 - 蓝桥云课

动态规划

82.扫雷 - 蓝桥云课

DFS / BFS

92.李白打酒加强版 - 蓝桥云课

动态规划 / 记忆化搜索

101.砍竹子 - 蓝桥云课

杂题

1. 九进制转十进制（简单题）

#include <iostream>
using namespace std;

int main(){
cout << 2 + 2 * 9 + 2 * 9 * 9 * 9;
return 0;
}

2. 顺子日期（简单题）

#include <iostream>
using namespace std;

int deadline[13] = {0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

int main(){
  int date[4];
  int count = 0;
  for(int m = 1; m <= 12; m ++){
    int daysize = deadline[m];
    for(int d = 1; d <= daysize; d ++){
      date[0] = m / 10;
      date[1] = m % 10;
      date[2] = d / 10;
      date[3] = d % 10;
      if((date[0] + 1 == date[1] && date[1] == date[2] - 1) || (date[1] + 1 == date[2] && date[2] == date[3] - 1) )
        count ++;
    }
  }
  cout << count;
  return 0;
}

3. 刷题统计（简单题）

#include <iostream>
using namespace std;


int main(){
long long a, b, n;cin >> a >> b >> n;
long long day = 0, week = 0;

week = n / (5 * a + 2 * b);
day = week * 7;
n -= week * (5 * a + 2 * b);

for(int i = 1; n > 0; i ++){
int num;
if(i >= 6) num = b;
else num = a;
n -= num;
day ++;
}

cout << day;

return 0;
}

4. 修剪灌木（找规律）

#include <iostream>
using namespace std;

int trees[10010];

int main(){
int n;cin >> n;

int first = 2 * n - 2;
int tmp = first;
int left = 1, right = n;
while(left <= right){
trees[left] = trees[right] = tmp;
tmp -= 2;
left ++;
right --;
}

for(int i = 1; i <= n; i ++)cout << trees[i] << endl;

return 0;
}

5. X 进制减法

#include <bits/stdc++.h>
using namespace std;

int A[100005] = {0};
int B[100005] = {0};
int Ans[100005] = {0};
int Carry[100005] = {0};


int main(){
    int N;    cin >> N;
    int Ma;    cin >> Ma;
    for(int i = Ma; i > 0; i --)    cin >> A[i];
    int Mb;    cin >> Mb;
    for(int i = Mb; i > 0; i --)    cin >> B[i];
    
    // 定进制
    for(int i = 1; i <= max(Ma, Mb); i ++)    Carry[i] = max((max(A[i], B[i]) + 1), 2);
     
    
    // 定各进位差值 
    for(int i = 1; i <= max(Ma, Mb); i ++)    Ans[i] = A[i] - B[i];
    //for(int i = 1; i <= max(Ma, Mb); i ++) cout << Ans[i] <<" ";
    
    // 计算差值
    
    /*
    long long a = 0, b = 0;//注意要long long 
    for(int i = Ma; i >= 1; i --){
        a = (a * Carry[i] + A[i]) % 1000000007;//注意取模 
    }
    for(int i = Mb; i >= 1; i --){
        b = (b * Carry[i] + B[i]) % 1000000007;
    }
    long long ans = (a - b + 1000000007) % 1000000007;//因为可能出现负数所以先+inf
    */
    
    
    long long ans = 0;
    for(int i = max(Ma, Mb); i >= 2; i --)
        ans = ((ans + Ans[i]) * Carry[i - 1]) % 1000000007;
        
    ans += Ans[1];
    ans %= 1000000007;
    
        
    cout << ans;
    
    return 0;
}

6. 统计子矩阵

【背模板、学习此题遍历矩阵的方式】

【70%】【二位前缀和】

#include <bits/stdc++.h>
using namespace std;


int a[505][505], s[505][505];




int main(){
    long long ans = 0;
    
    long long N, M, K;    cin >> N >> M >> K;
    // 存矩阵 
    for(int i = 1; i <= N; i ++)
        for(int j = 1; j <= M; j ++)
            scanf("%d", &a[i][j]);
    // 求二位前缀和 
    for(int i = 1; i <= N; i ++)
        for(int j = 1; j <= M; j ++)
            s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+a[i][j];
    
    // 统计所有矩阵
    int x1, x2, y1, y2;
    
    
    for(int x1 = 1; x1 <= N; x1 ++)
        for(int y1 = 1; y1 <= M; y1 ++)
            for(int x2 = x1; x2 <= N; x2 ++)
                for(int y2 = y1; y2 <= M; y2 ++)
                    if(s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1] <= K)    ans ++;
                    else break;
    
    cout << ans;
    
    return 0;
}

【100%】【二维前缀和 + 双指针】

#include <bits/stdc++.h>
using namespace std;


int a[505][505], s[505][505];

long long ans = 0;


int main(){
long long N, M, K;cin >> N >> M >> K;

// 求二位前缀和 
for(int i = 1; i <= N; i ++)
for(int j = 1; j <= M; j ++){
int a;cin >> a;
s[i][j] = s[i-1][j] + s[i][j-1] - s[i-1][j-1] + a;
}

// 统计所有矩阵

for(int x1 = 1; x1 <= N; x1 ++)
for(int x2 = x1; x2 <= N; x2 ++)
for(int y1 = 1, y2 = 1; y2 <= M; y2 ++){
while(y1 <= y2 && s[x2][y2] - s[x1-1][y2] - s[x2][y1-1] + s[x1-1][y1-1] > K)
y1 ++;
ans += y2 - y1 + 1;
}

cout << ans;

return 0;
}

7. 积木画

【普通二维动态规划】

#include <bits/stdc++.h>
using namespace std;


long long dp[10000005][3];
const int inf = 1000000007;


/*
dp[i][0] 刚好铺满
dp[i][1] 上面差一个 
dp[i][2] 下面差一个 

dp[i][0] = dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1] + dp[i - 1][2] 
dp[i][1] = dp[i - 2][0] + dp[i - 1][2]
dp[i][2] = dp[i - 2][0] + dp[i - 1][1]

*/


int main(){

long long N;cin >> N;

// 初始化 
dp[1][0] = 1;dp[1][1] = 0;dp[1][2] = 0;
dp[2][0] = 2;dp[2][1] = 1;dp[2][2] = 1;

// 递推 
for(int i = 3; i <= N; i ++){
dp[i][0] = (dp[i - 1][0] + dp[i - 2][0] + dp[i - 1][1] + dp[i - 1][2]) % inf; 
dp[i][1] = (dp[i - 2][0] + dp[i - 1][2]) % inf;
dp[i][2] = (dp[i - 2][0] + dp[i - 1][1]) % inf;
}


cout << dp[N][0];
return 0;
}

8. 扫雷

【bfs/dfs专项训练】

9. 李白打酒加强版

【记忆化搜索、dfs 专项训练】

【普通多维动态规划】

#include <bits/stdc++.h>
using namespace std;

long long dp[105][105][105];
const int inf = 1000000007;
/*
if(d == 0 && h == 0) continue;
if(h > 0)dp[d][h][w] = dp[d][h - 1][w + 1];
if(d > 0 && w != 0 && w % 2 == 0)dp[d][h][w] += dp[d - 1][h][w / 2];

*/

int main(){
int N, M; cin >> N >> M;

dp[0][0][2] = 1;

for(int d = 0; d <= N; d ++)
for(int h = 0; h <= M; h ++)
for(int w = 0; w <= M; w ++){
if(d == 0 && h == 0 && w != 2) dp[d][h][w] = 0;
if(h > 0)dp[d][h][w] = dp[d][h - 1][w + 1];
if(d > 0 && w % 2 == 0)dp[d][h][w] += dp[d - 1][h][w / 2];
dp[d][h][w] %= inf;
}

cout << dp[N][M - 1][1];

return 0;
}

10. 砍竹子

【未完全解决】

【未完待续ing】


原文地址：https://blog.csdn.net/2201_75769764/article/details/144851753

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！

相关文章

自学内容网
Copyright © 2015-2025