| 题目 | 链接 | 算法 |
|---|---|---|
| 1 | 1.九进制转十进制 - 蓝桥云课 | 进制转换 |
| 2 | 1.顺子日期 - 蓝桥云课 | 时间与日期 |
| 3 | 1.刷题统计 - 蓝桥云课 | 时间与日期 |
| 4 | 1.修剪灌木 - 蓝桥云课 | 思维 |
| 5 | 1.X 进制减法 - 蓝桥云课 | 贪心 |
| 6 | 1.统计子矩阵 - 蓝桥云课 | 二维前缀和 |
| 7 | 1.积木画 - 蓝桥云课 | 动态规划 |
| 8 | 2.扫雷 - 蓝桥云课 | DFS / BFS |
| 9 | 2.李白打酒加强版 - 蓝桥云课 | 动态规划 / 记忆化搜索 |
| 10 | 1.砍竹子 - 蓝桥云课 | 杂题 |
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. 砍竹子
【未完全解决】
