刷蓝桥杯历年考题(更新至15届~)

第十五届

C++A组省赛

训练士兵

AcWing5980.训练士兵

方法一：树状数组: $O(nlogn)$

• self-complete

/*先枚举组团，后分析每个士兵，有一个特点，组团费用是固定的，那当然是让所有士兵一块训练，训练完的士兵也不会有损失当还需要升级的士兵的金币之和小于组团时就各自训练，此时花费也已经固定了首先将经验按照从大到小排序，这样每次组团训练，会从后向前减少不需要训练的士兵，这样就能利用前缀和来判断是否需要单独训练每次组团先训练完一整类需要经验值相同的士兵再判断, 由于会对一整个区间进行修改求和，使用树状数组时间复杂度O(n)
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long longusing namespace std;const int N = 100010;struct Soldier{int coin, ep;bool operator< (const Soldier o) const{return ep > o.ep;}
}sl[N];int sc[N], tr[N];
int n, S;int lowbit(int x){return x & -x;
}void add(int x, int c){for (int i = x; i < N; i += lowbit(i))tr[i] += c;
}int sum(int x){int s = 0;for (int i = x; i; i -= lowbit(i))s += tr[i];return s;
}signed main(){scanf("%lld%lld", &n, &S);for (int i = 1; i <= n; i ++){scanf("%lld%lld", &sl[i].coin, &sl[i].ep);}sort(sl + 1, sl + n + 1);for (int i = 1; i <= n; i ++){sc[i] = sc[i - 1] + sl[i].coin;add(i, sl[i].ep - sl[i - 1].ep);}int res = 0;for (int i = n; i; i --){int cep = sum(i);if (cep > 0){if (sc[i] >= S){add(1, -cep);add(i, cep);res += S * cep;}else{res += sl[i].coin * cep;} }}printf("%lld\n", res);return 0;
}

方法二：哈希+整体操作（挖掘性质) $O(n)$

• 😦

/*由于组团训练肯定是所有士兵一起参加更好，所以可以把过程分为两种情况，一种是所有士兵组团训练，一种是所有士兵单独训练，而哪些已经训练完成的士兵就不用管了每次比较是组团和单独训练的花费金额来判断选用哪种情况
*/
#include <cstdio>
#include <cstring>
#include <algorithm>
#define int long longusing namespace std;const int N = 100010;int c[N], p[N];
int n, S;
int a[N * 100]; // a[k]哈希表，表示经过k轮后，完成训练后对应士兵的花费signed main(){scanf("%lld%lld", &n, &S);int maxt = 0;//一共只需要升maxt次所有士兵就能升满级int i_S = 0;//表示单独训练花费for (int i = 1; i <= n; i ++){scanf("%lld%lld", &c[i], &p[i]);maxt = max(maxt, p[i]);i_S += c[i];a[p[i]] += c[i];//训练多少轮后到达满级，此时对应的i_s将其去掉，未到满级是a[i]为0}int res = 0;for (int i = 1; i <= maxt; i ++){if (S < i_S){res += S;}else{res += i_S;}i_S -= a[i];}printf("%lld\n", res);return 0;
}

团建

AcWing5981. 团建

dfs+哈希 $O(n+m)$

最长公共子序列

/*求最长公共子序列，每次同时维护两个树
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <set>
#include <unordered_map>using namespace std;const int N = 200010, M = N * 2;int h[2][N], e[2][M], ne[2][M], idx;
int w1[N], w2[N];
int n, m;void add(int i, int a, int b){e[i][idx] = b, ne[i][idx] = h[i][a], h[i][a] = idx ++;
}int dfs(int u1, int u2, int fa1, int fa2){int res = 0;unordered_map<int, int> hs;//遍历第一个数，将其能到的子节点加入到集合Sfor (int i = h[0][u1]; ~i; i = ne[0][i]){int j = e[0][i];if (j == fa1) continue;hs[w1[j]] = j;//权值映射到点}for (int i = h[1][u2]; ~i; i = ne[1][i]){int j = e[1][i];if (j == fa2) continue;if (hs.count(w2[j])){//哈希表中有，就是有最长公共子序列res = max(dfs(hs[w2[j]], j, u1, u2), res);//取最长公共最长子序列}}return res + 1;//多了u，加一
}int main(){scanf("%d%d", &n, &m);memset(h, -1, sizeof h);for (int i = 1; i <= n; i ++) scanf("%d", &w1[i]);for (int i = 1; i <= m; i ++) scanf("%d", &w2[i]);for (int i = 0; i < n - 1; i ++){int a, b;scanf("%d%d", &a, &b);add(0, a, b); add(0, b, a);}for (int i = 0; i < m - 1; i ++){int a, b;scanf("%d%d", &a, &b);add(1, a, b); add(1, b, a);}int res = 0;if (w1[1] == w2[1]){res = dfs(1, 1, 0, 0);}printf("%d\n", res);return 0;
}

成绩统计

AcWing. 5982

二分+前缀和 $O(nlogn)$

$$\begin{gathered} 由于是求方差，就需要理解方差的性质：反应的是数之间的差异程度 \\ 方差越小，那么数之间的差越小 \\ 那么让我选k个数使其方差最小的话 \\ 我们首先将k个数排序，然后遍历求相邻k个数的方差，O(n) \\ 要求前x个数，就不能暴力枚举O(n)\to O(n^2) \\ 采用二分O(logn) \end{gathered}$$

$O(n)求方差最简单的办法：\to 将原式展开$
$${\sigma }^2=\frac{\sum _{i=1}^k{v}_i^2-\bar{v}\sum _{i=1}^{k}2\ast v_i+k\ast {\bar{v}}^2}{k}$$
$利用前缀和求各个和$

/*满足二分性质，当x越大，越能找到这样的k
*/
#include <iostream>
#include <algorithm>
#include <cstring>
#define int long long using namespace std;const int N = 100010;int a[N], bk[N], s[N], s2[N];
int n, k, T;bool check(int x){memcpy(bk, a, sizeof a);sort(bk + 1, bk + x + 1);//前缀和求k个数的和for (int i = 1; i <= x; i ++){s[i] = s[i - 1] + bk[i];s2[i] = s2[i - 1] + bk[i] * bk[i];}for (int i = k; i <= x; i ++){int spowvi = s2[i] - s2[i - k], svi = s[i] - s[i - k];double avg = (double)svi / k;if ((double)spowvi - avg * 2 * svi + k * avg * avg < (double)k * T) return true;}return false;
}signed main(){scanf("%lld%lld%lld", &n, &k, &T);for (int i = 1; i <= n; i ++) {scanf("%lld", &a[i]);}if (!check(n)){printf("%d\n", -1);return 0;}int l = 1, r = n;while (l < r){int mid = l + r >> 1;if (check(mid)) r = mid;else l = mid + 1;}printf("%lld\n", r);return 0;
}

零食采购

AcWing. 5984

LCA + 树状前缀和 $O(nlogn)$

$首先有n个节点，n-1条边，所以没有环是一颗树，而求任意两点之间的最短距离在算法提高课的图论中讲过$

AcWing.1171 距离

$$\begin{gathered} 方法是LCA，最近公共祖先，先求每个点到根节点的距离， \\ 那么两个点a,b之间的最短距离就是分别到最近公共祖先的距离之和 \\ 而这题就是上面简单扩展一下，加上经过了多少种类的糖果， \\ 由于糖果的种类较少，所以可以枚举每种糖果是否出现 \\ 事先求得每个节点到根节点的糖果i出现的次数（前缀和）， \\ 那么如果a,b分别到最近公共祖先之间糖果出现次数大于0的话就包含这个糖果 \end{gathered}$$

时间复杂度：

1. lca初始化$O(nlogn)$
2. lca查询$logn$

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int N = 100010, M = N * 2;int h[N], e[M], ne[M], idx;
int w[N], cnt[N][21];// cnt[i][j]表示从根节点到i的糖果j的数量
int depth[N], f[N][17]; //log2(100010) = 16.6
int n, m;void add(int a, int b){e[idx] = b, ne[idx] = h[a], h[a] = idx ++;
}void bfs(int root){memset(depth, 0x3f, sizeof depth);queue<int> q;q.push(root);depth[0] = 0, depth[root] = 1;while (q.size()){int u = q.front();q.pop();for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (depth[j] > depth[u] + 1){depth[j] = depth[u] + 1;f[j][0] = u;q.push(j);for (int k = 1; k <= 16; k ++){f[j][k] = f[f[j][k - 1]][k - 1];}}}}
}int lca(int a, int b){if (depth[a] < depth[b]) return lca(b, a);for (int i = 16; i >= 0; i --){if (depth[f[a][i]] >= depth[b])a = f[a][i];}if (a == b) return a;for (int i = 16; i >= 0; i --){if (f[a][i] != f[b][i]){a = f[a][i];b = f[b][i];}}return f[a][0];
}void dfs(int u, int fa){cnt[u][w[u]] ++;for (int i = h[u]; ~i; i = ne[i]){int j = e[i];if (j == fa) continue;for (int k = 1; k <= 20; k ++){cnt[j][k] = cnt[u][k] + (k == w[j]? 1 : 0);}dfs(j, u);}
}int main(){memset(h, -1, sizeof h);scanf("%d%d", &n, &m);for (int i = 1; i <= n; i ++) scanf("%d", &w[i]);for (int i = 0; i < n - 1; i ++){int a, b;scanf("%d%d", &a, &b);add(a, b); add(b, a);}bfs(1);dfs(1, -1);while (m --){int a, b;scanf("%d%d", &a, &b);int p = lca(a, b);int res = 0;for (int i = 1; i <= 20; i ++){if (cnt[a][i] + cnt[b][i] - 2 * cnt[f[p][0]][i] > 0) res ++;}printf("%d\n", res);}return 0;
}