# 试题 A: 九进制转十进制（数学）

``````#include <iostream>
#include <cmath>
using namespace std;

int main() {
cout << 2 * pow(9, 0) + 2 * pow(9, 1) + 0 * pow(9, 2) + 2 * pow(9, 3) << endl;
return 0;
}
``````

# 试题 B: 顺子日期（语文）

``````20220123
20220321
20221123
20221230
20221231
``````

``````20220123
20221123
20221230
20221231
``````

``````20220120
20220121
20220122
20220123
20220124
20220125
20220126
20220127
20220128
20220129
20221012
20221123
20221230
20221231
``````

orz

# 试题 C: 刷题统计（模拟）

### 【样例输入】

``````10 20 99
``````

### 【样例输出】

``````8
``````

``````#include <iostream>
using namespace std;

int main() {
int cnt = 1;
long long n;
int a, b;
cin >> a >> b >> n;
long long sum = 0;
while (sum < n) {
if (cnt % 7 == 0 || cnt % 7 == 6) {
sum += b;
}
else {
sum += a;
}
cnt++;
}
// 当超出时退出while循环，所以答案需要减一。
cout << cnt - 1 << endl;
return 0;
}
``````

``````#include <iostream>
using namespace std;

int main() {
long long a, b, n;
cin >> a >> b >> n;
int week = 5 * a + 2 * b;
long long ans = n / week * 7;
n %= week;
int sum = 0;
for (int i = 1; i <= 7 && sum < n; i++) {
if (i % 7 == 6 || i % 7 == 0) {
sum += b;
}
else {
sum += a;
}
ans++;
}
cout << ans << endl;
return 0;
}
``````

# 试题 D: 修剪灌木（找规律）

## 【样例输入】

``````3
``````

## 【样例输出】

``````4
2
4
``````

``````// 暴力代码：来回走两次。注意回的时候要把两个边界去掉。

#include <iostream>
#include <cstring>
using namespace std;

const int maxn = 1e4 + 100;
int a[maxn];
int maxHeight[maxn];

int main() {
int n;
while (cin >> n) {
memset(a, 0, sizeof(a));
memset(maxHeight, 0, sizeof(maxHeight));

// 来回走两次
for (int today = 0; today < n; today++) {
for (int i = 0; i < n; i++) {
a[i]++;
if (a[i] > maxHeight[i]) {
maxHeight[i] = a[i];
}
if (i == today) {
a[i] = 0;
}
}
}
for (int today = n - 2; today > 0; today--) {
for (int i = 0; i < n; i++) {
a[i]++;
if (a[i] > maxHeight[i]) {
maxHeight[i] = a[i];
}
if (i == today) {
a[i] = 0;
}
}
}
for (int today = 0; today < n; today++) {
for (int i = 0; i < n; i++) {
a[i]++;
if (a[i] > maxHeight[i]) {
maxHeight[i] = a[i];
}
if (i == today) {
a[i] = 0;
}
}
}
for (int today = n - 2; today > 0; today--) {
for (int i = 0; i < n; i++) {
a[i]++;
if (a[i] > maxHeight[i]) {
maxHeight[i] = a[i];
}
if (i == today) {
a[i] = 0;
}
}
}
for (int i = 0; i < n; i++) {
cout << maxHeight[i] << " ";
}
cout << endl << endl;
}
return 0;
}
``````

``````#include <iostream>
using namespace std;

int main() {
int n;
cin >> n;
for (int i = 0; i < n; i++) {
cout << max(i, n - i - 1) * 2 << endl;
}
return 0;
}
``````

# 试题 E: X 进制减法（数学）

## 【样例输入】

``````11
3
10 4 0
3
1 2 0
``````

## 【样例输出】

``````94
``````

① 看个位：个位为 1，那么只需数一次即可到 1，然后让结果加上 1，即 sum += 1
② 看十位：十位为 2，因为个位是二进制，所以十位要到 2 的话，就需要经过这样的变换：00 -> 01 -> 10 -> 11 -> 20。可以看出：十位每加 1，个位就需要变换 2 次，所以要使十位变成 2，则一共需要变换 2（十位的值） * 2（个位的进制） 次。然后让结果再加上它，即 sum += 2 * 2
③ 看百位：百位为 3，根据十位的分析，同理得：要使百位变成 3，则需要变换 3（百位的值） * 10（十位的进制） * 2（个位的进制）次。然后让结果再加上它，即 sum += 3 * 10 * 2

A = ( a[n - 1] * X[n - 2] * X[n - 3] * … * X[0] ) + ( a[n - 2] * X[n - 3] * X[n - 4] * … * X[0] ) + … + a[0]
B = ( b[n - 1] * X[n - 2] * X[n - 3] * … * X[0] ) + ( b[n - 2] * X[n - 3] * X[n - 4] * … * X[0] ) + … + b[0]
A - B = (( a[n - 1] - b[n - 1] ) * X[n - 2] * X[n - 3] * … * X[0] ) + (( a[n - 2] - b[n - 2] ) * X[n - 3] * X[n - 4] * … * X[0] ) + ( a[0] - b[0] )

A - B = ((( d[n - 1] * X[n - 2] + d[n - 2] ) * X[n - 3] + d[n - 3] ) * X[n - 4] + … d[0] ) …

``````#include <iostream>
#include <algorithm>
using namespace std;

const int MOD = 1e9 + 7;
const int maxn = 1e5 + 100;
int a[maxn];
int b[maxn];

int main() {
int n, m1, m2, m;
scanf("%d", &n);
scanf("%d", &m1);
// 逆序来存，确保让个位对齐，多余位置的值都是 0
for (int i = m1 - 1; i >= 0; i--) {
scanf("%d", &a[i]);
}
scanf("%d", &m2);
for (int i = m2 - 1; i >= 0; i--) {
scanf("%d", &b[i]);
}
m = max(m1, m2);
int res = 0;
for (int i = m - 1; i >= 0; i--) {
res = (res * max({ 2, a[i] + 1, b[i] + 1 }) % MOD + a[i] - b[i]) % MOD;
}
printf("%dn", res);
return 0;
}
``````

# 试题 F: 统计子矩阵（前缀和 + 双指针）

## 【样例输入】

``````3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
``````

## 【样例输出】

``````19
``````

``````#include <iostream>
using namespace std;

const int maxn = 505;
int s[maxn][maxn];

int main() {
memset(s, 0, sizeof(s));
int n, m, k;
scanf("%d %d %d", &n, &m, &k);
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
scanf("%d", &s[i][j]);
s[i][j] += s[i - 1][j];
}
}
int res = 0;
// 上下边界
for (int up = 1; up <= n; up++) {
for (int down = up; down <= n; down++) {
int sum = 0;
// 左右边界
for (int left = 1, right = 1; right <= m; right++) {
sum += s[down][right] - s[up - 1][right];
while (sum > k) {
sum -= s[down][left] - s[up - 1][left];
left++;
}
res += right - left + 1;
}
}
}
printf("%dn", res);
return 0;
}
``````

``````#include <iostream>
using namespace std;

int mat[550][550];

int main() {
int n, m;
long long k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> mat[i][j];
}
}
long long sum = 0;
long long cnt = 0;
for (int h1 = 1; h1 <= n; h1++) {
for (int h2 = h1; h2 <= n; h2++) {
for (int l1 = 1; l1 <= m; l1++) {
for (int l2 = l1; l2 <= m; l2++) {
sum = 0;
for (int h = h1; h <= h2; h++) {
for (int l = l1; l <= l2; l++) {
sum += mat[h][l];
}
}
if (sum <= k) {
cnt++;
}
}
}
}
}
cout << cnt << endl;
return 0;
}
``````

# 试题 G: 积木画（动态规划）

## 【样例输入】

``````3
``````

## 【样例输出】

``````5
``````

（是的，比如说，我倒数第二题就忘记取模了。。。。。

dp[n] 可以通过 dp[n - 1] 加上普通的一列得到

dp[n] 可以通过 dp[n - 2] 加上两块横的得到

dp[n] 可以通过 dp[n - 3] 加上两个三角形的堆起来得到，但要注意的是，这两个三角形的堆叠方式有两种，所以要加上两倍的 dp[n - 3]

dp[n]可以通过 dp[n - 4] 加上由左右两个各一个三角形，中间若干个横块的组合得到，同第三种情况，这个组合可以倒过来，即有两种堆叠方式，因此要加上两倍的 dp[n - 4]

``````#include <iostream>
using namespace std;

const long long MOD = 1e9 + 7;

const int maxn = 1e7 + 100;
long long dp[maxn];

int main() {
int n;
cin >> n;
dp[0] = 1;
dp[1] = 1;
dp[2] = 2;
dp[3] = 5;
for (int i = 4; i <= n; i++) {
// 注意每次相加后都要取余
dp[i] = (((((dp[i - 1] + dp[i - 2]) % MOD) + dp[i - 3] * 2) % MOD) + dp[i - 4] * 2) % MOD;
}
cout << dp[n] << endl;
return 0;
}
``````

# 试题 H: 扫雷（BFS）

## 【样例输入】

``````2 1
2 2 4
4 4 2
0 0 5
``````

## 【样例输出】

``````2
``````

``````#include <iostream>
#include <queue>
#include <cmath>
#include <map>
using namespace std;

const int maxn = 50100;
// 记录坐标和半径
int x_pos[maxn];
int y_pos[maxn];
bool vis[maxn]; // 用来记录这个点爆炸了没有

// 用于 bfs 的 struct，更方便处理
struct point {
int x, y, r;
// 将结构体放入 map 中，需要自己写一个 operator 来排序，因为 map 本身是有序的
bool operator < (const point& p) const {
if (x == p.x) {
if (y == p.y) {
return r < p.y;
}
return y < p.y;
}
return x < p.x;
}
};

map<point, int> all;

double getDis(int x1, int y1, int x2, int y2) {
return sqrt((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2));
}

int bfs(point begin, int n) {
int cnt = 0;
queue<point> q;
q.push(begin);
while (!q.empty()) {
point cur = q.front();
q.pop();
// 遍历以 2 倍半径为边长的正方形，找到其爆炸所涉及到的炸雷
for (int i = cur.y - cur.r; i <= cur.y + cur.r; i++) {
for (int j = cur.x - cur.r; j <= cur.x + cur.r; j++) {
if (getDis(j, i, cur.x, cur.y) > cur.r) {
continue;
}
point temp;
temp.y = i, temp.x = j;
for (int k = 0; k < n; k++) {
if (!vis[k] && x_pos[k] == temp.x && y_pos[k] == temp.y) {
q.push(temp);
cnt++;
all[temp]--;
vis[k] = true; // 标记为已爆炸
}
}
}
}
}
return cnt;
}

int main() {
int n, m;
cin >> n >> m;
for (int i = 0; i < n; i++) {
cin >> x_pos[i] >> y_pos[i] >> radius[i];
vis[i] = false; // 初始化都还没有爆炸
}
int cnt = 0;
for (int i = 0; i < m; i++) {
point p;
cin >> p.x >> p.y >> p.r;
// 我比赛时输出了 m 次结果，裂开了
// int cnt = 0;
cnt += bfs(p, n);
// cout << cnt << endl;
}
cout << cnt << endl;
return 0;
}
``````

# 试题 I: 李白打酒加强版（三维DP / 回溯）

## 【样例输入】

``````5 10
``````

## 【样例输出】

``````14
``````

``````#include <iostream>
using namespace std;

const int MOD = 1e9 + 7;
const int maxn = 105;
long long dp[maxn][maxn][maxn] = { 0 };

int main() {
int n, m;
cin >> n >> m;
// 初始化 dp
dp[0][0][2] = 1;
for (int i = 1; i <= n + m; i++) {
for (int j = 0; j <= i; j++) {
for (int k = 0; k <= 100; k++) {
// 遇到了花后抵达第 i 步
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k + 1]) % MOD;
// 遇到了酒馆后抵达第 i 步
// 当 k % 2 == 0 时才有可能是从酒馆走来的，因为经过酒馆后酒就加倍了
if (j != 0 && k % 2 == 0) {
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j - 1][k / 2]) % MOD;
}
}
}
}
cout << dp[n + m - 1][n][1] << endl;
return 0;
}
``````

① 一共必须要且仅要经过 N 次店，M 次花
② 最后一次遇到的必须是花
③ 最后遇到花后，酒必须喝光
④ 在中途遇到花时，酒不能为空

``````#include <iostream>
#include <string>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

void backTrack(vector<char>& temp, vector<vector<char> >& ans, int n, int m, int nn, int mm, int jiu) {
if (jiu < 0) return; // 如果遇到花却没酒了，则不符合条件
if (nn > n || mm > m) return; // 如果经过了多于 N 次店、M 次花，则不符合条件
if (temp.size() == n + m) {
if (jiu == 0 && temp.back() == '0') { // 如果最后到达的是店也不符合条件
ans.push_back(temp);
}
return;
}

temp.push_back('0');
backTrack(temp, ans, n, m, nn, mm + 1, jiu - 1);
temp.pop_back();
temp.push_back('1');
backTrack(temp, ans, n, m, nn + 1, mm, jiu * 2);
temp.pop_back();
}

int main() {
int n, m;
cin >> n >> m;
int jiu = 2;
vector<char> temp;
vector<vector<char> > ans;
backTrack(temp, ans, n, m, 0, 0, jiu);
cout << ans.size() % MOD << endl;
return 0;
}
``````

# 试题 J: 砍竹子

## 【样例输入】

``````6
2 1 4 2 6 7
``````

## 【样例输出】

``````5
``````

# 总结

① 注意题目要求，记得取模！
② 注意范围，可能要用 long long
③ 不要在一道题卡太长时间，比如我在 E 题卡了一个小时都没看懂题，就应该早早换题，最后换换思路再回来看或许反而能看懂了

THE END