2025年4月30日
从去年的11月份开始准备。刚开始刷题的时候，是从leetcode开始刷的题目。但是实在是太难了，很打击信心。所以我就开始转战洛谷和C语言网。难度小了很多，我本来准备在蓝桥杯官方网站买课，后来在B站里面找到了资源，但是根本听不进去。所以索性就直接刷题了。我刷题的步骤是先从几个大块去刷题。主要从一下几个板块去刷：动态规划，贪心，排列组合，深度/广度搜索，暴力枚举，递归，递推，回溯法，分治法。主要就是这几个板块去刷题。刷题真的很提升思维，我看到了各种各样抽象的题目，也看到了很多民间高手惊人的思维方式。在这个过程中，我对算法的认识更加深入。
因为是第一次参加算法比赛，所以心里没有底，因为我平时在图书馆一坐坐一天的时候，大脑真的会麻，而且蓝桥杯比赛时间就是4个小时，我也怕比赛那天有些知识点会想不起来，所以我先学的就是暴力。果不其然比赛那天我确实只有前几道编程是用了一些dp和其他的知识点，剩下的全是在那for for for ，哈哈哈。我们辽宁省有985，211和一些计算机强校，所以压力也不小。比赛获奖pdf出来的时候，我看到我在获奖名单上面的时候，我如释重负，努力没有白费。
下面是我的此次比赛具体过程
下面是第一题
第一题，说实话，当时我旁边的那个男生看到题目的时候，就已经在写敲键盘了，但是我没把这道题目当成编程题目，我把它看成一道数学题。我先在草纸上面把坐标轴画了出来，画出来之后我就已经有了想法，小明按照题目的说法走路，最小的移动距离就是一个正方向的X轴移动距离再加上一个弧长，难就难在这个弧长怎么求？我刚开始想了弧长的公式，发现解题的核心就在这个弧所对应的角度数，然后就可以解题了。
第二题
这道题我思考了很久，最后一点思路都没有，但是我根据刷题经验，发现了一些端倪。在题目的最后，给出了取余后的结果。我当时就在想，这个题本身就是让我们求有多少种可能。那么这个最终的答案肯定不会太小，而且还极有可能很大。当时我的心态就是尝试赌一下，把一个小一点的数写上去。所以我最后写的是7，虽然和答案不一样，但是我的思考方式对了。
第三题
这道题目不难发现，−1,0,1 三个数之和为 0，−2,−1,0,1,2 五个数之和也为 0。在这样的序列后面加一个数 x，该序列的和就为 x。因此除了 1 之外的任意正整数都是可分解的。边输入边判断即可。所以这个题目我还可以应对一下。
#include <stdio.h> int main() { int N; if (scanf("%d", &N) != 1) return 0; int count = 0; for (int i = 0; i < N; i++) { long long a; scanf("%lld", &a); if (a > 1) { count++; } } printf("%d\n", count); return 0; }第四题
当时我来到第四题的时候已经挺不住了，因为前三道题目就已经耗时1个多小时，大脑果然开始麻了，但是我还是能分析一下，由于每次是取平均，三个数会趋近于相同。当三个数相同之后，显然后面的全部操作都是无用的，三个数都不会有变化。因此在三个数相同之后，直接退出模拟，直接输出即可。这个我能分析出来，但是代码我遇到了问题，我写不出来具体的东西，这个思路我能想出来，但是代码我真的写不出来，但是Dev-C++一直出现报错，搞得我很焦灼，一时半会还解决不了，所以我索性就直接用暴力去写了，但是暴力运行之后，总是缺少几种情况，这几种就让我AC不了，我最后就只能拿几分。
#include <stdio.h> void solve() { long long a, b, c, k; scanf("%lld %lld %lld %lld", &a, &b, &c, &k); long long pa = a, pb = b, pc = c; for (long long i = 0; i < k; i++) { long long na = (pb + pc) / 2; long long nb = (pa + pc) / 2; long long nc = (pa + pb) / 2; if (na == pa && nb == pb && nc == pc) break; if (i > 200) break; pa = na; pb = nb; pc = nc; if (i > 100) { k = i + (k - i) % 2 + 2; } } printf("%lld %lld %lld\n", pa, pb, pc); } int main() { int t; if (scanf("%d", &t) != 1) return 0; while (t--) { solve(); } return 0; }第五题
#include <stdio.h> #include <stdlib.h> int compare(const void *a, const void *b) { long long arg1 = *(const long long *)a; long long arg2 = *(const long long *)b; if (arg1 < arg2) return -1; if (arg1 > arg2) return 1; return 0; } int main() { int n, m; if (scanf("%d %d", &n, &m) != 2) return 0; long long *a = (long long *)malloc(n * sizeof(long long)); for (int i = 0; i < n; i++) { scanf("%lld", &a[i]); } qsort(a, n, sizeof(long long), compare); long long min_l = -1; for (int i = 0; i <= n - m; i++) { long long current_l = a[i + m - 1] * a[i + m - 1] - a[i] * a[i]; if (min_l == -1 || current_l < min_l) { min_l = current_l; } } printf("%lld\n", min_l); free(a); return 0; }第六题
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 1000005 char s[2][MAXN]; int parent[MAXN * 2]; int find(int i) { if (parent[i] == i) return i; return parent[i] = find(parent[i]); } void unite(int i, int j) { int root_i = find(i); int root_j = find(j); if (root_i != root_j) parent[root_i] = root_j; } int main() { int n; if (scanf("%s %s", s[0], s[1]) == EOF) return 0; n = strlen(s[0]); for (int i = 0; i < 2 * n; i++) parent[i] = i; int first_col = -1, last_col = -1; for (int j = 0; j < n; j++) { for (int i = 0; i < 2; i++) { if (s[i][j] == '#') { if (first_col == -1) first_col = j; last_col = j; if (i == 1 && s[0][j] == '#') unite(j, j + n); if (j > 0 && s[i][j-1] == '#') unite(i * n + j, i * n + (j - 1)); } } } if (first_col == -1) { printf("0\n"); return 0; } int components = 0; int *comp_ids = (int *)malloc(2 * n * sizeof(int)); for (int i = 0; i < 2 * n; i++) { int r = i / n, c = i % n; if (s[r][c] == '#' && parent[i] == i) components++; } printf("%d\n", components > 0 ? components - 1 + (last_col - first_col - (components-1)) : 0); return 0; }第七题
#include <stdio.h> #include <stdlib.h> #define MAXN 1005 long long w[MAXN]; int head[MAXN], to[MAXN * 2], next[MAXN * 2], edge_cnt = 0; int is_leaf[MAXN]; void add_edge(int u, int v) { to[++edge_cnt] = v; next[edge_cnt] = head[u]; head[u] = edge_cnt; } long long dfs(int u, int p) { long long child_sum = 0; int has_child = 0; for (int i = head[u]; i; i = next[i]) { int v = to[i]; if (v == p) continue; child_sum += dfs(v, u); has_child = 1; } if (!has_child) return w[u]; return (child_sum < w[u]) ? child_sum : w[u]; } int main() { int n; if (scanf("%d", &n) != 1) return 0; for (int i = 1; i <= n; i++) scanf("%lld", &w[i]); for (int i = 0; i < n - 1; i++) { int u, v; scanf("%d %d", &u, &v); add_edge(u, v); add_edge(v, u); } printf("%lld\n", dfs(1, 0)); return 0; }第八题
#include <stdio.h> #define MOD 1000000007 long long power(long long base, long long exp) { long long res = 1; base %= MOD; while (exp > 0) { if (exp % 2 == 1) res = (res * base) % MOD; base = (base * base) % MOD; exp /= 2; } return res; } int main() { int n; if (scanf("%d", &n) != 1) return 0; long long a[n]; for (int i = 0; i < n; i++) scanf("%lld", &a[i]); long long total_sum = a[0] % MOD; long long last_block_sum = a[0] % MOD; long long pre_sum = 0; long long bit_counts[32][2] = {0}; for (int k = 0; k < 31; k++) { bit_counts[k][(a[0] >> k) & 1] = 1; } long long ways = 1; for (int i = 1; i < n; i++) { long long next_total = 0; long long next_last_block_sum = 0; long long next_pre_sum = 0; long long next_bit_counts[32][2] = {0}; next_total = (next_total + total_sum + ways * a[i]) % MOD; next_pre_sum = (next_pre_sum + total_sum) % MOD; next_last_block_sum = (next_last_block_sum + ways * a[i]) % MOD; for(int k=0; k<31; k++) next_bit_counts[k][(a[i] >> k) & 1] = (next_bit_counts[k][(a[i] >> k) & 1] + ways) % MOD; next_total = (next_total + total_sum - ways * (a[i] % MOD) + MOD) % MOD; next_pre_sum = (next_pre_sum + total_sum) % MOD; long long xor_last_sum = 0; for (int k = 0; k < 31; k++) { int bit = (a[i] >> k) & 1; next_bit_counts[k][0] = (next_bit_counts[k][0] + bit_counts[k][bit]) % MOD; next_bit_counts[k][1] = (next_bit_counts[k][1] + bit_counts[k][1 - bit]) % MOD; xor_last_sum = (xor_last_sum + (1LL << k) % MOD * next_bit_counts[k][1]) % MOD; } total_sum = (total_sum * 3) % MOD; ways = (ways * 3) % MOD; } printf("%lld\n", total_sum); return 0; }当我答第五题题的时候，时间已经过去2个多小时了，而且最难受的是，身边的一些高年级的学长，手里的键盘就没停下来，一直在敲，反正挺搞人心态的。再加上我越往后面几道题走，越觉得困难。实在是不知道怎么办的时候，就坐在座位上面傻待着。然后大概缓和了半个小时，这个时候已经距离考试结束还有40多分钟，我还是解决不了最后三个题，就是属于暴力都暴不出来的那种，不知道该怎么往里面套，挺难受的，当时就是想多拿几分，万一能冲击更高的奖，那不是更好。
待了大概3个小时50分钟，实在是没思路了，直接提交答案，离开考场。
这次蓝桥杯使我进步很多，假如不参加这次比赛，我可能都不会碰算法，我也不会感受算法的乐趣，我也不会有这么大的进步。这次比赛暂时告一段落，我还是要坚持学习算法。
