试题A: 九进制转十进制本题总分:5分【问题描述】九进制正整数 (2022), 转换成十进制等于多少?【答案提交】这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。题解：进制转换2 * 9^0 + 2 * 9^1 + 0 + 2 * 9^3 = 1478
试题B: 顺子日期本题总分:5分【问题描述】小明特别喜欢顺子。顺子指的就是连续的三个数字:123、456等。顺子日期指的就是在日期的 yyyymmdd 表示法中，存在任意连续的三位数是一个顺子的日期。例如20220123就是一个顺子日期，因为它出现了一个顺子: 123; 而20221023则不是一个顺子日期，它一个顺子也没有。小明想知道在整个2022年份中，一共有多少个顺子日期。【答案提交】这是一道结果填空的题，你只需要算出结果后提交即可。本题的结果为一个整数，在提交答案时只填写这个整数，填写多余的内容将无法得分。题解：日历很多人在讨论 012 算不算顺子，因为题目里说 0123 中的顺子是 123，我是算了的，不算的话答案应该是 4年份 2022 是不变的，而且不可能搭上顺子，所以只考虑后四位即可
可能搭上顺子的月份有：
1月：0120 ~ 0129 共 10 个，顺子是 012 (其中 0123 可以认为顺子是 123)
10月：1012，顺子是 012
11月：1123，顺子是 123
12月：1230，1231，顺子是 123
一共 14 个
蓝桥杯题意表达含糊不清真的有一套的试题C: 刷题统计时间限制:1.0s 内存限制:256.0MB 本题总分:10分【问题描述】小明决定从下周一开始努力刷题准备蓝桥杯竞赛。他计划周一至周五每天做α道题目，周六和周日每天做b道题目。请你帮小明计算,按照计划他将在第几天实现做题数大于等于n题?【输入格式】输入一行包含三个整数a, b和n.【输出格式】输出一个整数代表天数。【样例输入】10 20 99
【样例输出】8
【评测用例规模与约定】对于 50% 的评测用例，1 ≤ a, b, n ≤ 10^5.对于 100% 的评测用例，1≤ a, b, n ≤ 10^15.题解：取余看 1E15 的数据规模，暴力模拟的话稳稳超时可以先算出每周可以做多少题，然后利用除法和取余，就能把取余后的做题量控制在一周内，再判断一下一周内的五天能不能做完，就比较简单了#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a, b, n, k;
ll ans = 0;
int main() {
cin >> a >> b >> n;
k = a * 5 + b + b;
ans += n / k * 7;
n %= k;
if (n <= a * 5) {
ans += n / a + (n % a != 0);
}
else {
n -= a * 5;
ans += 6 + (n > b);
}
cout << ans << endl;
return 0;
}
刷这么多题，小明好卷……试题D: 修剪灌木时间限制:1.0s 内存限制: 256.0MB 本题总分:10分【问题描述】爱丽丝要完成一项修剪灌木的工作。有N棵灌木整齐的从左到右排成一排。爱丽丝在每天傍晚会修剪一棵灌木，让灌木的高度变为0厘米。爱丽丝修剪灌木的顺序是从最左侧的灌木开始,每天向右修剪一棵灌木。当修剪了最右侧的灌木后，她会调转方向，下一天开始向左修剪灌木。直到修剪了最左的灌木后再次调转方向。然后如此循环往复。灌木每天从早上到傍晚会长高1厘米，而其余时间不会长高。在第一天的早晨，所有灌木的高度都是0厘米。爱丽丝想知道每棵灌木最高长到多高。【输入格式】一个正整数N，含义如题面所述。【输出格式】输出N行，每行一个整数，第i行表示从左到右第i棵树最高能长到多高。【样例输入】3
【样例输出】4
2
4
【评测用例规模与约定】对于 30% 的数据，N ≤ 10.对于 100% 的数据，1< N ≤ 10000.题解：贪心注意每棵灌木在被修剪得那天还会先长高 1 厘米，然后再被修剪对于每棵灌木，长到最高的时间段有两种可能：被剪后往右剪再拐回来，和被剪之后往左剪再拐回来假设某个灌木左侧有 x 棵灌木，右侧有 y 棵，容易发现这颗灌木的最大高度是 max(x, y) * 2，它的左(右)侧每有一颗灌木被剪前它都会长高 1 厘米，包括它自己被剪之前#include <bits/stdc++.h>
using namespace std;
int n;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
int x = max(i, n - i - 1);
cout << x * 2 << endl;
}
return 0;
}
种得下这么多灌木，艾丽丝家还蛮大的！试题E: X进制减法时间限制: 1.0s 内存限制:256.0MB 本题总分:15分【问题描述】进制规定了数字在数位上逢几进一。X 进制是一种很神奇的进制，因为其每一数位的进制并不固定!例如说某种 X 进制数，最低数位为二进制，第二数位为十进制，第三数位为八进制，则X进制数 321 转换为十进制数为 65。现在有两个 X 进制表示的整数 A 和 B，但是其具体每一数位的进制还不确定，只知道 A 和 B 是同一进制规则，且每一数位最高为 N 进制，最低为二进制。请你算出 A-B 的结果最小可能是多少。请注意，你需要保证A和B在X进制下都是合法的，即每一数位上的数字要小于其进制。【输入格式】第一行一个正整数 N，含义如题面所述。第二行一个正整数 Ma，表示 X 进制数 A 的位数。第三行 Ma 个用空格分开的整数，表示 X 进制数 A 按从高位到低位顺序各个数位上的数字在十进制下的表示。第四行一个正整数 M, 表示X进制数 B 的位数。第五行 Mb 个用空格分开的整数，表示 X 进制数 B 按从高位到低位顺序各个数位上的数字在十进制下的表示。请注意，输入中的所有数字都是十进制的。【输出格式】输出一行一个整数，表示X进制数 A - B 的结果的最小可能值转换为十进制后再模1000000007的结果。【样例输入】11
3
10 4 0
3
1 2 0
【样例输出】94
【样例说明】当进制为:最低位2进制，第二数位5进制，第三数位11进制时,减法得到的差最小。此时A在十进制下是108，B在十进制下是 14，差值是94.【评测用例规模与约定】对于30%的数据，N≤ 10; Ma, Mb ≤ 8.对于100%的数据，2 < N ≤ 1000; 1 ≤ Ma, Mb, ≤ 100000; A ≥ B.题解：贪心本想深搜，一看数据范围还是算了假设 A 和 B 都是三位数，分别是 a2a1a0 和 b2b1b0每位的进制数 (pi) 分别是 p2p1p0那么可以知道 A 的十进制应为：a0 * 1 + a1* p0 + a2 * (p0 * p1)，B 为：b0 * 1 + b1* p0 + b2 * (p0 * p1)那么就有 A - B = (a0 - b0) + (a1 - b1) * p0 + (a2 - b2) * (p0 * p1)这么看的话，每一位进制数 (pi) 都取尽可能小的进制就好（最小是 2 进制）此时有个猜想，(ai - bi) 是负数时要不要抬高进制数？注意题目中说 A >= B，如果存在 ai < bi 的情况，那么在更高位肯定存在有 aj > bj拿上面的 A - B 式说明，假设 (a1 - b1) 小于0，因此使 p0 变大，以此来使结果变小但是 p0 变大的同时也一定使 (a2 - b2) * (p0 * p1) 的结果变大，而且比 (a1 - b1) * p0 变小的程度更大，因为它还乘了个 p1，而 p1 作为 a1 和 b1 的进制数，肯定比 a1 和 b1 大，也肯定比 (b1 - a1) 要大#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int MAXM = 100005;
int n, ma, mb;
int a[MAXM], b[MAXM];
ll ans = 0, bac = 1;
int main() {
cin >> n;
cin >> ma;
for (int i = 1; i <= ma; i++) {
cin >> a[i];
}
cin >> mb;
for (int i = 1; i <= mb; i++) {
cin >> b[i];
}
int i = ma, j = mb;
while (i > 0) {
ans += (a[i] - b[j]) * bac;
ans %= MOD;
ll p = max(a[i], b[j]) + 1;
bac *= max(p, 2LL);
bac %= MOD;
i--;
if (j) j--;
}
cout << ans << endl;
return 0;
}
说实话我也不知道这对不对，做蓝桥的题经常会有一种朦朦胧胧的感觉，不清楚思路可行不可行试题F: 统计子矩阵时间限制:1.0s 内存限制: 256.0MB 本题总分:15分【问题描述】给定一个N×M的矩阵A，请你统计有多少个子矩阵(最小1×1，最大NxM)满足子矩阵中所有数的和不超过给定的整数K?【输入格式】第一行包含三个整数N,M和K.之后N行每行包含M个整数，代表矩阵A.【输出格式】一个整数代表答案。【样例输入】3 4 10
1 2 3 4
5 6 7 8
9 10 11 12
【样例输出】19
【样例说明】满足条件的子矩阵一共有19，包含:大小为1×1的有10个。大小为1×2的有3个。大小为1×3的有2个。大小为1×4的有1个。大小为2×1的有3个。【评测用例规模与约定】对于30%的数据, N, M ≤ 20.对于70%的数据，N, M ≤ 100.对于100%的数据，1 ≤ N,M ≤ 500; 0 ≤ Aij ≤1000;1 ≤ K ≤ 250000000.题解：二维前缀和+二分一看题就想到前缀和了，不过暴力枚举的话肯定超时了，想了个半枚举+二分查找的歪点子，时间复杂度大概 是O(n^3 * log(n))，大概有 10^9 了，再加上一点剪枝，能不能过看运气了假设 (i, j) 是子矩阵的起点坐标，(x, y) 是终点坐标，枚举 i, j, x，二分查找符合条件的最大 y，就是找起点为 (i, j) ，终点在第 x 行最多有多少个矩阵#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int N = 505;
ll m, n, k;
ll a[N][N];
ll ans = 0;
ll getsum(int i, int j, int x, int y) {
return a[x][y] - a[i - 1][y] - a[x][j - 1] + a[i - 1][j - 1];
}
int main() {
cin >> m >> n >> k;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
a[i][j] += a[i - 1][j] - a[i - 1][j - 1] + a[i][j - 1];
}
}
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
if (getsum(i, j, i, j) > k) continue;
for (int x = i; x <= m; x++) {
int l = j, r = n;
while (l < r) {
int mid = (l + r + 1) >> 1;
if (getsum(i, j, x, mid) > k) r = mid - 1;
else l = mid;
}
if (getsum(i, j, x, l) > k) break;
ans += l - j + 1;
}
}
}
cout << ans << endl;
return 0;
}
真·题解：前缀和 + 连续子段个数这题有解了，其实是个套路题先确定子矩阵的两个列边界，然后做一次行遍历，就是求符合条件的连续子段个数（双指针滑动窗口），复杂度缩小到 O(n^3)由于每次只需拿到某一行内的和，只做一维前缀和即可#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int N = 505;
ll m, n, k;
ll a[N][N];
ll ans = 0;
int main() {
cin >> m >> n >> k;
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
a[i][j] += a[i][j - 1];
}
}
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
int left = 1;
ll cur = 0;
for (int right = 1; right <= m; right++) {
cur += a[right][j] - a[right][i - 1];
while (cur > k) {
cur -= a[left][j] - a[left][i - 1];
left++;
}
ans += right - left + 1;
}
}
}
cout << ans << endl;
return 0;
}
试题G: 积木画时间限制: 1.0s 内存限制:256.0MB 本题总分:20分【问题描述】小明最近迷上了积木画，有这么两种类型的积木，分别为Ⅰ型(大小为2个单位面积)和L型(大小为3个单位面积):同时，小明有一块面积大小为2×N的画布，画布由2×N个1×1区域构成。小明需要用以上两种积木将画布拼满，他想知道总共有多少种不同的方式? 积木可以任意旋转,且画布的方向固定。【输入格式】输入一个整数N,表示画布大小。【输出格式】输出一个整数表示答案。由于答案可能很大，所以输出其对1000000007取模后的值【样例输入】3【样例输出】5【样例说明】五种情况如下图所示，颜色只是为了标识不同的积木;【评测用例规模与约定】对于所有测试用例，1 ≤ N ≤ 10000000.题解：动态规划（错解）要摆出 n 列方格，可以在 n - 1 列方格后加一个竖着的 I 形积木，也可以在 n - 2 方格后加两个横着的 I 形积木，也可以在 n - 3 列方格上后加 两个 L 形积木的两种摆法用 dp[i] 表示 i 列方格的摆法则有，当 i >= 3 时 dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] * 2;#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int N = 10000005;
int n;
ll dp[N];
int main() {
cin >> n;
dp[0] = dp[1] = 1;
dp[2] = 2;
for (int i = 3; i <= n; i++) {
dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] * 2;
dp[i] %= MOD;
}
cout << dp[n] << endl;
return 0;
}
思路想的太简单了，寄！题解：动态规划看过别人说的，可以先放一个 L 形，再连续放若干个横着的 I 形积木，末尾再放一个 L 形，直接一记重锤打脑门上然而还有另一种情况：话说蓝桥故意只放一个小样例是不是不太好（虽然确实考验思维就是了）那么在上面错解的基础上，要摆出 n 列方格，还可以由（n - 4, n - 5, n - 6, n - 7, ……）转换而来也就有：① dp[i] = dp[i - 1] + dp[i - 2] + dp[i - 3] * 2 + dp[i - 4] * 2+ dp[i - 5] * 2 + …… + * dp[1] * 2② dp[i - 1] = dp[i - 2] + dp[i - 3] + dp[i - 4] * 2 + dp[i - 4] * 2+ dp[i - 5] * 2 + …… + * dp[1] * 2① - ② 得出 dp[i] - dp[i - 1] = dp[i - 1] + dp[i - 3] 即 dp[i] = dp[i - 1] * 2 + dp[i - 3]#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int N = 10000005;
int n;
ll dp[N];
int main() {
cin >> n;
dp[1] = 1;
dp[2] = 2;
dp[3] = 5;
for (int i = 4; i <= n; i++) {
dp[i] = (dp[i - 1] * 2 + dp[i - 3]) % MOD;
}
cout << dp[n] << endl;
return 0;
}
试题H:扫雷时间限制: 1.0s 内存限制:256.0MB 本题总分:20分【问题描述】小明最近迷上了一款名为《扫雷》的游戏。其中有一个关卡的任务如下，在一个二维平面上放置着 n 个炸雷，第i个炸雷 (xi, yi, ri) 表示在坐标 (xi, yi) 处存在一个炸雷，它的爆炸范围是以半径为 ri 的一个圆。为了顺利通过这片土地，需要玩家进行排雷。玩家可以发射m个排雷火箭，小明已经规划好了每个排雷火箭的发射方向，第 j 个排雷火箭 (xj, yj, rj) 表示这个排雷火箭将会在 (xj, yj) 处爆炸，它的爆炸范围是以半径为 rj 的一个圆，在其爆炸范围内的炸雷会被引爆。同时，当炸雷被引爆时，在其爆炸范围内的炸雷也会被引爆。现在小明想知道他这次共引爆了几颗炸雷?你可以把炸雷和排雷火箭都视为平面上的一个点。一个点处可以存在多个炸雷和排雷火箭。当炸雷位于爆炸范围的边界上时也会被引爆。【输入格式】输入的第一行包含两个整数 n、m.接下来的 n 行，每行三个整数xi, yi, ri，表示一个炸雷的信息。再接下来的 m 行，每行三个整数xj, yj, rj，表示一个排雷火箭的信息。【输出格式】输出一个整数表示答案。【样例输入】2 1
2 2 4
4 4 2
0 0 5
【样例输出】2
【样例说明】示例图如下，排雷火箭1覆盖了炸雷1，所以炸雷1被排除;炸雷1又覆盖了炸雷2，所以炸雷2也被排除。【评测用例规模与约定】对于40%的评测用例: 0 ≤ x, y ≤ 10^9, 0 ≤ n, m ≤ 10^3, 1 < r ≤ 10.对于100%的评测用例: 0 ≤ x, y ≤ 10^9, 0 ≤ n,m ≤ 5 × 10^4, 1 ≤ r ≤ 10.题解：广搜比赛时没看到题里说一个点可以有多个雷，又寄！坐标的范围 10^9 太大了，于是用哈希表放 pair，同一个点上的多个雷，可以状态压缩一下，用百位开始放雷的个数，个位放最大半径队列里放将要爆炸的雷，集合放已经被扫描到的雷还是比较偏暴力的，不知道行不行#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct point {
int x, y, r;
point(int xx, int yy, int rr) : x(xx), y(yy), r(rr) {}
};
double get_len(int i, int j, int
x, int y) {
return sqrt((i - x) * (i - x) + (j - y) * (j - y));
}
map<pair<int, int>, int> mp;
queue<point> q;
set<pair<int, int> > s;
int m, n;
ll ans = 0;
int main() {
cin >> n >> m;
int x, y, r;
for (int i = 0; i < n; i++) {
cin >> x >> y >> r;
int tmp = mp[make_pair(x, y)] + 100;
mp[make_pair(x, y)] = max(tmp, tmp / 100 * 100 + r);
}
for (int i = 0; i < m; i++) {
cin >> x >> y >> r;
q.push(point(x, y, r));
}
while (!q.empty()) {
point po = q.front();
x = po.x, y = po.y, r = po.r;
q.pop();
for (int i = x - r; i <= x + r; i++) {
for (int j = y - r; j <= y + r; j++) {
pair<int, int> pir(i, j);
if (s.count(pir)) continue;
if (!mp.count(pir)) continue;
if (get_len(i, j, x, y) > r) continue;
s.insert(pir);
q.push(point(i, j, mp[pir] % 100));
ans += mp[pir] / 100;
}
}
}
cout << ans << endl;
return 0;
}
试题:李白打酒加强版时间限制: 1.0s 内存限制: 256.0MB 本题总分:25分【问题描述】话说大诗人李白，一生好饮。幸好他从不开车。一天，他提着酒壶，从家里出来，酒壶中有酒2斗。他边走边唱:无事街上走，提壶去打酒。逢店加一倍，遇花喝一斗。这一路上，他一共遇到店 N 次，遇到花 M 次。已知最后一次遇到的是花，他正好把酒喝光了。请你计算李白这一路遇到店和花的顺序，有多少种不同的可能?注意: 壶里没酒（0斗) 时遇店是合法的，加倍后还是没酒，但是没酒时遇花是不合法的。【输入格式】第一行包含两个整数 N 和 M.【输出格式】输出一个整数表示答案。由于答案可能很大，输出模 1000000007 的结果。【样例输入】5 10
【样例输出】14
【样例说明】如果我们用 0 代表遇到花，1代表遇到店，14种顺序如下:010101101000000010110010010000011000110010000100010110010000011001000110000100011000110000100100010110000010110100000100011001001000100100011001000100100100011000100011010000010100100100100010100101000001010100【评测用例规模与约定】对于40%的评测用例: 1 ≤ N, M ≤ 10。对于100%的评测用例: 1 ≤ N, M ≤ 100。题解：记忆化搜索+剪枝比较容易想到的是深搜，取令 n - 1 和令 m - 1 的结果相加，在此基础上有几个规则用来剪枝用 k 来表示酒的数量：假如 k == 0，必须有 m == n == 0，结果为 1，否则无解，因为最后一次遇到的必须是花，而且没酒时遇花是不合法的假如 k > m, 一定无解假如 k != 0 且 n >= m ，一定无解假如 n == 0，必须有 k == m，结果为 1，否则无解因为 n 和 m 最大为 100，剪枝之后 k 的值又不会大于 m，所以可以用三维数组做记忆化（然而我比赛时用的哈希表，而且好像少判了 n == 0 时的条件……）#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1000000007;
const int N = 105;
ll mp[N][N][N];
ll dfs(int n, int m, int k) {
if (k == 0) return (m == 0 && n == 0);
if (k > m
n >= m) return 0;
if (n == 0) return k == m;
if (mp[n][m][k] != -1) return mp[n][m][k];
ll ans = dfs(n, m - 1, k - 1) + dfs(n - 1, m, k + k);
ans %= MOD;
mp[n][m][k] = ans;
return ans;
}
int main() {
memset(mp, -1, sizeof mp);
int m, n;
cin >> n >> m;
cout << dfs(n, m, 2) << endl;
return 0;
}
也是可以动态规划的，不过不写了试题J:砍竹子时间限制: 1.0s 内存限制:256.0MB 本题总分:25分【问题描述】这天，小明在砍竹子，他面前有 n 棵竹子排成一排，一开始第 i 棵竹子的高度为 hi .他觉得一棵一棵砍太慢了，决定使用魔法来砍竹子。魔法可以对连续的一段相同高度的竹子使用，假设这一段竹子的高度为 H，那么使用一次魔法可以把这一段竹子的高度都变为 [ sqrt( [H / 2] + 1 ) ] ，其中 [x] 表示对 x 向下取整。小明想知道他最少使用多少次魔法可以让所有的竹子的高度都变为 1。【输入格式】第一行为一个正整数n，表示竹子的棵数。第二行共n个空格分开的正整数h，表示每棵竹子的高度。【输出格式】一个整数表示答案。【样例输入】6
2 1 4 2 6 7
【样例输出】5
【样例说明】其中一种方案: 2 1 4 2 6 7→2 1 4 2 6 2→2 1 4 2 2 2→2 1 1 2 2 2→1 1 1 2 2 2→1 1 1 1 1 1共需要5步完成【评测用例规模与约定】对于20%的数据，保证 n ≤ 1000, hi ≤ 10^6。对于100%的数据，保证 n ≤ 2 × 10^5, hi ≤ 10^18。题解：贪心骗分一看到成段修改就想到线段树了，但还是没有思路，而且 10^18 实在是太大了看样例猜一个贪心，每次找最大值修改，如果连续相同的话就一起修改然后暴力模拟，能骗两个样例就算成功#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 200005;
int n;
ll a[N], ans = 0;
int main() {
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
while (true) {
int idx = 0;
for (int i = 0; i < n; i++) {
if (a[i] > a[idx]) idx= i;
}
if (a[idx] == 1) break;
ll val = a[idx];
for (int i = idx; a[i] == val; i++) {
a[i] = sqrt(a[i] / 2 + 1);
}
ans ++;
}
cout << ans << endl;
return 0;
}
总结下来就是：寄了吗？又寄了吗？答案是寄！这届比赛最大的变动就是填空题变成了两道，不过总体难度还是不算太高的（只说C++ B组）感觉这次蓝桥杯是想往代码能力和思维能力上靠，但是连着这么多编程题挺消磨意志的，八道大题，到后面连题都不想读了还有希望蓝桥杯出题再优化一下题目吧，让题意表达确切些，最好再精简一下B题顺子日期给我的感觉就是玩了一个游戏，但让我自己来猜游戏规则是什么，而且只能玩一次}

什么是蓝桥杯？官方解释是：蓝桥杯大赛是工信部人才交流中心举办的全国性专业信息技术赛事。这个比赛最早是针对大学生群体的编程赛事。自从2016年第八届蓝桥杯开始，在原有的大学生数个专业编程组别的基础上增加了中小学创意编程组，简称【青少组】，第11届竞赛，超过4万名中小学参加了青少年组的比赛，第12届起，STEMA评测考试替代了青少年组的地区选拔赛，主要是评测学生的【科技素养】、【逻辑思维】、【编程能力】按照省份给出综合评测成绩。简单讲就是这是一个编程领域专业性的全国比赛，初赛选拔是考STEMA（科学（Science）、技术（Technology）、工程（Engineering）、数学（Mathematics）、艺术（Arts））对的，除了考编程还需要考一些“课外知识”，两部分分数占比是五比五，同等重要。
先给大家说说蓝桥杯的大概比赛时间吧：比赛分为初赛（STEMA选拔赛）——省赛——国赛初赛一年五到六次，一般是每年8,10,11,1,3这几个月份进行。四月份省赛，五月份国赛。然后是晋级规则：一等奖晋级机制：初赛一等奖可以直接进国赛；初赛二等奖，三等奖，优秀奖，需要参加第二轮的省赛；省赛一等奖才能晋级国赛。总的来说，如果想走到全国总决赛，要么初赛是一等奖，要么省赛是一等奖，相当于给了每个考生2次机会。第一题:结点选择题干：有一棵 n 个节点的树，树上每个节点都有一个正整数权值。如果一个点被选择了， 那么在树上和它相邻的点都不能被选择。求选出的点的权值和最大是多少？解题思路： 这题模型是树形动态规划入门题目， dp[i][0]表示该节点不被选择，dp[i][1]表示该结点被选择。 转移方程为: dp[u][1]+=dp[v][0];//选择了 u 结点，则与它邻接的结点不选； dp[u][0]+=max(dp[v][0]，dp[v][1]);不选择 u 结点，则与它邻接的结点选择结果最 大的； 应该特别注意：该题结点数量较大，应该选用邻接表存储边的关系。#include<cstdio>
#include<cstring>
#define max(a,b) ((a)>(b)?(a):(b))
#define maxn 100010
bool vis[maxn];
int dp[maxn][2];
int father[maxn];
int head[maxn];
int n;
int cnt;
struct Edge
{
int to,next;
}edge[2*maxn];
void add(int u,int v)
{
edge[cnt].to=v;
edge[cnt].next=head[u];
head[u]=cnt++;
}
void treedp(int u)
{
vis[u]=1;
for(int i=head[u];i!=-1;i=edge[i].next)
{
int v=edge[i].to;
if(!vis[v])
{
treedp(v);
dp[u][1]+=dp[v][0];
dp[u][0]+=max(dp[v][1],dp[v][0]);
}
}
}
void init()
{
cnt=0;
memset(dp,0,sizeof(dp));
memset(father,0,sizeof(father));
memset(vis,0,sizeof(vis));
memset(head,-1,sizeof(head));
}
int main()
{
init();
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%d",&dp[i][1]);
int root=0;
int begin=1;
for(int i=0;i<n-1;i++)
{
int a,b;
scanf("%d%d",&a,&b);
add(a,b);
add(b,a);
father[b]=a;
if(root==b
begin)
{
root=a;
}
}
while(father[root])
root=father[root];
treedp(root);
int ans;
ans=max(dp[root][0],dp[root][1]);
printf("%d\n",ans);
}
第二题:K 好数题干：如果一个自然数 N 的 K 进制表示中任意的相邻的两位都不是相邻的数字，那么我们就 说这个数是 K 好数。求 L 位 K 进制数中 K 好数的数目。例如 K = 4，L = 2 的时候，所有 K好数为 11、13、20、22、30、31、33 共 7 个。由于这个数目很大，请你输出它对 1000000007 取模后的值。解题思路：dp[i][j]表示第 i 位为 j 的时候的个 I 好数个数；因此有转移方程：dp[i][j]=dp[i-1][m]+dp[i][j];m 为上一位的值，满足的条件应为 m-j 的绝对值不为 1.即不相邻；应当注意的是：最后在求和的时候不能简单的统计 dp[l][m] 0<=m<k;因为首位如果是 0 的话，其实不足 L 位了，所以 0<m<k,也许有人会疑问这是不统计 L 位的 0，不是第一位 呀。。。。。。其实仔细想想，是等效的。#include<cstdio>
#include<cstring>
#define mod 1000000007
#define abs(a,b) ((a)>(b)?(a-b):(b-a))
int dp[110][110];
int main()
{
int k,l;
memset(dp,0,sizeof(dp));
scanf("%d%d",&k,&l);
for(int i=0;i<k;i++)
dp[1][i]=1;
for(int i=2;i<=l;i++)
{
for(int j=0;j<k;j++)
{
for(int m=0;m<k;m++)
{
if(abs(m,j)!=1)
dp[i][j]=(dp[i][j]%mod+dp[i-1][m]%mod)%mod;
}
}
}
int ans=0;
for(int i=1;i<k;i++)
ans=(ans%mod+dp[l][i]%mod)%mod;
printf("%d\n",ans);
}
第三题:K 好数题干：有 n 个格子，从左到右放成一排，编号为 1-n。共有 m 次操作，有 3 种操作类型： 1.修改一个格子的权值， 2.求连续一段格子权值和， 3.求连续一段格子的最大值。 对于每个 2、3 操作输出你所求出的结果。解题思路： 这是线段树的入门题目。直接建立线段树，求解就 OK 了#include<cstdio>
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define N 100010
#define L(a) (a)<<1
#define R(a) (a)<<1|1
struct node
{
int l,r,maxn,minn,sum;
}line[3*N];
int num[N];
int first,second;
void create(int k,int x,int y)
{
line[k].l=x;line[k].r=y;
if(x==y)
{
line[k].sum=num[x];
line[k].maxn=line[k].minn=num[x];
return;
}
int mid=(x+y)>>1;
create(L(k),x,mid);
create(R(k),mid+1,y);
line[k].maxn=max(line[L(k)].maxn,line[R(k)].maxn);
//line[k].minn=mymin(line[L(k)].minn,line[R(k)].minn);
line[k].sum=line[L(k)].sum+line[R(k)].sum;
}
void updata(int k,int a,int b)
{
if(line[k].l==line[k].r)
{
line[k].maxn=b;
line[k].sum=b;
return ;
}
int mid=(line[k].l+line[k].r)>>1;
if(a<=mid)
updata(L(k),a,b);
else
updata(R(k),a,b);
line[k].sum=line[L(k)].sum+line[R(k)].sum;
line[k].maxn=max(line[L(k)].maxn,line[R(k)].maxn);
}
void quary(int k,int x,int y)
{
if(line[k].l==x&&line[k].r==y)
{
second+=line[k].sum;
first=max(first,line[k].maxn);
return;
}
int mid=(line[k].l+line[k].r)>>1;
if(y<=mid)
quary(L(k),x,y);
else if(x>mid)
quary(R(k),x,y);
else
{
quary(L(k),x,mid);
quary(R(k),mid+1,y);
}
}
int main()
{
int n,m;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
scanf("%d",&num[i]);
create(1,1,n);
for(int i=1;i<=m;i++)
{
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
if(a==1)
{
updata(1,b,c);
}
else if(a==2)
{
first=-10000;
second=0;
quary(1,b,c);
printf("%d\n",second);
}
else
{
first=-10000;
second=0;
quary(1,b,c);
printf("%d\n",first);
}
}
}
}