蓝桥杯2024省赛A组题解

前言

做下来的体感是，涉及的知识点比较基础，但需要写的细节并不少。难度略高于 CSP-J，低于 NOIP/CSP-S。

我给出的难度排序大致是：A<C<B=D<G<E<F<H，比较令人恶心的是E和F会爆 long long，考场上我肯定无情挂分。

H题初见没有明确的思路，写的玄学复杂度做法只有 20pts。不是一道好做的题。

只剩一个礼拜了，很难针对蓝桥杯的风格做专项复习了，稍微复习复习图论/数据结构的板子吧，再切几道推柿子题找找感觉，剩下的听天由命辽。

A

标签： 枚举

枚举区间内所有日期，统计笔画数大于 \(50\) 的天数即可。

Code: 略。

B

标签： DFS

笔者一开始考虑的错误做法是：枚举 \(13\) 个白子的位置，再判断是否为平局。复杂度是阶乘级别，难以在短时间内得到结果。

于是转变思路，考虑到平局要求棋盘被填满，那么最终状态一共只有 \(2^{25} = 33,554,432\) 种，时间可以接受。 直接枚举并判断每种情形是否符合平局标准（白子数目为 \(13\)，且不存在横、竖、斜连成一线）

Code:

void dfs(int k) {if (k == 26) {FOR(i, 1, 5) {if (sumx[i] == 0 || sumx[i] == 5) return;if (sumy[i] == 0 || sumy[i] == 5) return;}if (sec == 0 || sec == 5) return;if (fir == 0 || fir == 5) return;if (tot != 13) return;cnt++;return;} int i = (k - 1) / 5 + 1, j;if (k % 5 == 0) j = 5; else j = k % 5;sumx[i] += 1; // sumx[i] 为第 i 行中白子的个数sumy[j] += 1; // sumy[j] 为第 j 列中白子的个数if (i == j) fir += 1; // fir 为主对角线上白子个数if (i + j == 6) sec += 1; // sec 为副对角线上白子个数tot += 1; // tot 为白子总个数dfs(k + 1);tot -= 1;sumx[i] -= 1;sumy[j] -= 1;if (i == j) fir -= 1;if (i + j == 6) sec -= 1;dfs(k + 1);
}

C

标签： 前缀和，贪心

当训练进行到一定程度时，训练未完成的士兵一次训练所需的金币数可能会变得小于 \(S\) 。在这个时刻之前，选择组团训练，之后则仅对未完成的士兵训练。下面我们需要找到这个时刻。

根据需要的训练次数，对士兵进行升序排序。对其做后缀和，判断何时后缀和首次小于 \(S\)。然后根据上述的策略模拟即可。另外注意对 \(S\) 小于最后一位的情况进行判断。

Code:

struct person {int p, c;bool operator < (const person &x) const {return c < x.c;}
} y[N];int sum[N];void solve() {n = read(); m = read();FOR(i, 1, n) cin >> y[i].p >> y[i].c;sort(y + 1, y + n + 1);sum[n] = y[n].p;for (int i = n - 1; i >= 1; i--) {sum[i] = sum[i + 1] + y[i].p;}int pos = n + 1;for (int i = 1; i <= n; i++) {if (m > sum[i]) {pos = i;break;}}if (pos == n + 1) {cout << y[n].c * m << '\n';return;}int ans = y[pos - 1].c * m;FOR(i, pos, n) {ans += (y[i].c - y[i - 1].c) * sum[i];}cout << ans << '\n';
}

D

标签： DFS

在第一棵树上进行搜索，再设置一个指向第二棵树的指针。搜索过程中，先判断第二棵树上下一步能不能到达同样权值的点（使用 \(map\) 进行预处理），不能则跳过，能则继续搜索，并在搜索完成后回溯指针的位置。

Code:

int n, m, k, pos, ans;int a[N], b[N], dep[N];vector<int> e1[N], e2[N];map<int, int> mp[N];void pre(int u, int fa) {dep[u] = dep[fa] + 1;for (int v : e2[u]) {if (v == fa) continue;mp[u][b[v]] = v;pre(v, u);}
}void dfs(int u, int fa) {for (int v : e1[u]) {if (v == fa) continue;if (mp[pos][a[v]]) {int tmp = pos;pos = mp[pos][a[v]];dfs(v, u);pos = tmp;}}ans = max(ans, dep[u]);
}void solve() {n = read(); m = read();FOR(i, 1, n) a[i] = read();FOR(i, 1, m) b[i] = read();FOR(i, 1, n - 1) {int u = read(), v = read();e1[u].push_back(v);e1[v].push_back(u);}FOR(i, 1, m - 1) {int u = read(), v = read();e2[u].push_back(v);e2[v].push_back(u);}if (a[1] != b[1]) {cout << 0 << '\n';return;}pos = 1;pre(1, 0);dfs(1, 0);cout << ans << '\n';

E

标签： 二分

显然选出的最小方差随 \(x\) 的增大单调不增，考虑二分答案，将最优化问题转化为判定性问题。

对前 \(x\) 名同学的成绩进行排序，可以证明方差最小时选出的 \(k\) 名同学一定是连续的。

将方差的式子转化为在转移中便于维护的形式：

\[{\sigma^2}=\frac{1}{k}\sum_{i=1}^{k}{v_i}^2 - \frac{1}{k^2}(\sum_{i=1}^{k}v_i)^2 \]

转移时执行类似滑动窗口的操作修改 \(\sum_{i=1}^{k}v_i^2\) 和 \(\sum_{i = 1}^{k} v_i\) 的值，找出方差值的最小值，判断是否小于给定的 \(T\) 即可。

但此题似乎对浮点数的精度要求偏高，因此令上式两端同乘 \(k^2\) 转化为整数进行操作规避精度问题。注意到这样做过程中可能超出 long long 的范围，还需开 unsigned long long。

Code:

bool check(int x) {vector<int> vc;FOR(i, 1, x) vc.push_back(a[i]);sort(vc.begin(), vc.end());int sumsq = 0, sum = 0;FOR(i, 1, k) {sumsq += vc[i - 1] * vc[i - 1];sum += vc[i - 1];}int mn = sumsq * k - sum * sum;int pos = k;FOR(i, k + 1, x) {sumsq += vc[i - 1] * vc[i - 1];sumsq -= vc[i - 1 - k] * vc[i - 1 - k];sum += vc[i - 1];sum -= vc[i - 1 - k];int newans = sumsq * k - sum * sum;if (newans < mn) pos = i;mn = min(mn, newans);}if (mn < T * k * k) return true;return false;
}void solve() {n = read(); k = read(); T = read();FOR(i,1,n) a[i] = read();int L = k, R = n;if (!check(R)) {cout << "-1\n";return;}while (L < R) {int mid = (L + R) / 2;if (check(mid)) R = mid;else L = mid + 1;}cout << L << '\n';
}

F

标签： 容斥原理

先考虑前置问题：满足 \(a_j|a_i\) 的有序二元组 \((i,j)\) 有多少个。

由于 \(a_i\) 的数据范围并不大，我们先预处理出每个数的出现次数，然后用根号筛得到 \(a_i\) 的全部因数，对他们的出现次数求和，就可以得到对于当前的 \(i\) ，有多少满足条件的 \((i,j)\) 。注意，由于 \(i\ne j\) ，应将次数减一。

下面我们利用容斥原理，计算有序四元组 \((i,j,k,l)\) 的数量，其中 \(i,j,k,l\) 互异。

为了方便说明，下设：

满足条件且 \(i\ne j\) 的有序二元组数量是 \(N_0\) ；

满足条件但不限制互异性的有序四元组数量是 \(N_1\) ；

满足条件但 \((i=j) \wedge(k\ne l)\) 的有序四元组数量是 \(N_2\)；

满足条件但 \((i\ne j) \wedge(k=l)\) 的有序四元组数量是 \(N_3\)；

满足条件但 \((i=j) \wedge(k= l)\) 的有序四元组数量是 \(N_4\)；

满足条件但 \((i=l)\wedge(j\ne k)\) 的有序四元组数量是 \(N_5\)；

满足条件但 \((i\ne l)\wedge (j=k)\) 的有序四元组数量是 \(N_6\)；

满足条件但 \((i=l)\wedge(j=k)\) 的有序四元组数量是 \(N_7\)；

满足条件且满足互异性的有序四元组数量（也就是最终答案）是 \(N\) 。

那么根据容斥原理，有： \(N=N_1-N_2-N_3+N_4-N_5-N_6+N_7\) 。

由于未限制互异性，根据乘法原理，显然 \(N_1 = N_0^2\) 。另外可以注意到 \(N_4=N_0\)。

下面考虑怎样求 \(N_2\) 与 \(N_3\) ：

先说 \(N_2\)：假设除 \(a_i\) 自身之外，数列中 \(a_i\) 倍数的个数为 \(x_i\)。对于有序四元组而言，只需 \(a_k\) 和 \(a_l\) 互异且都为 \(a_i\) 倍数即可。易得 \(N_2=\sum x_i(x_i-1)\) 。

\(N_3\) 的求解方式同理：假设除 \(a_i\) 自身之外，数列中 \(a_i\) 因数的个数为 \(y_i\)，那么有 \(N_3=\sum y_i(y_i-1)\)。

\(x_1\) 和 \(x_2\) 都可以通过预处理获得。

下面求解 \(N_5\) 和 \(N_6\)：

根据对称性，显然两个值是相等的。以 \((i=l)\wedge (j \ne k)\) 的情形为例，则 \(a_j|a_i\) 且 \(a_i | a_k\) ，我们枚举这个作为 \(a_i\) 的数。沿用上文中的 \(x_i\) 与 \(y_i\) ，可以导出 \(N_5=N_6=\sum x_i y_i\) 。

至于 \(N_7\) 有且仅有一种情形：两个相等的数互为对方的倍数和因数。枚举 \(a_i\) 的取值，假设数列中共有 \(z_i\) 个取该值的数，那么有 \(N_7=\sum z_i(z_i - 1)\) 。

需要注意的是，在极端情况下（如数列中全是 \(1\) ）答案可能会超过 unsigned long long 的范围，因此需要用 __int128。

Code:

int n0, n1, n2, n3, n4, n5, n6, n7;
int cnt[N], times[N], res[N];void solve() {n = read();FOR(i, 1, n) {a[i] = read();cnt[a[i]]++;}FOR(i, 1, n) {for (int j = 1; j * j <= a[i]; j++) {if (j * j == a[i]) {res[i] += cnt[j];times[j] += 1;} else {if (a[i] % j == 0) {res[i] += cnt[j];res[i] += cnt[a[i] / j];times[j] += 1;times[a[i] / j] += 1;}}}n0 += (res[i] - 1);}n1 = n0 * n0;n4 = n0;FOR(i, 1, n) {n2 += (times[a[i]] - 1) * (times[a[i]] - 1);n3 += (res[i] - 1) * (res[i] - 1);n5 += (times[a[i]] - 1) * (res[i] - 1);n6 += (times[a[i]] - 1) * (res[i] - 1);}FOR(i, 1, N - 5) n7 += cnt[i] * (cnt[i] - 1);print(n1 - n2 - n3 + n4 - n5 - n6 + n7);
}

G

标签： LCA，树上差分

注意到零食的种类非常少，考虑对每种零食分别做树上前缀和。再以起点与终点的 \(lca\) 为分界点，将所求路径拆成两条链，借助前缀和求出路径上每种零食的数量，从而求得路径上零食的种类数。

Code：

int n, m, k, q;int a[N], b[N], c[N], dep[N];int sum[N][30], f[N][30];vector<int> e[N];void dfs1(int u, int fa) {dep[u] = dep[fa] + 1;for (int v : e[u]) {if (v == fa) continue;FOR(i, 1, 20) sum[v][i] = sum[u][i];sum[v][c[v]]++;dfs1(v, u);}
}void dfs2(int u, int fa) {f[u][0] = fa;for (int i = 1; (1 << i) <= dep[u]; i++) {f[u][i] = f[f[u][i - 1]][i - 1];}for (int v : e[u]) {if (v == fa) continue;dfs2(v, u);}
}int lca(int u, int v) {if (dep[u] < dep[v]) swap(u, v);for (int i = 20; i >= 0; i--)if (dep[u] - (1 << i) >= dep[v])u = f[u][i];if (u == v) return u;for (int i = 20; i >= 0; i--) {if (f[u][i] != f[v][i]) {u = f[u][i];v = f[v][i];}}return f[u][0]; 
}void solve() {n = read(); q = read();FOR(i, 1, n) c[i] = read();FOR(i, 1, n - 1) {int u = read(), v = read();e[u].push_back(v);e[v].push_back(u);}sum[1][c[1]] = 1;dfs1(1, 0);dfs2(1, 0);while (q--) {int u = read(), v = read();int fa = lca(u, v), ans = 0;vector<int> t(25);FOR(i, 1, 20) {t[i] += sum[u][i] - sum[fa][i];t[i] += sum[v][i] - sum[f[fa][0]][i];if (t[i] != 0) ans += 1;}cout << ans << '\n';}
}

H

标签： 贪心，线段树

所求为字典序最大的序列，那么每一步都应该选择能选的中最大的。当且仅当没有能放的宝石时，这一步放 \(-1\)。

体力值本质上是对选取范围做了限制。假设当前体力为 \(k\) ，当前位置是 \(i\) ，那么宝石的选取范围就是 \(\left[ i, i + k \right]\) 。当有多个宝石值相等时，显然我们应该选取位置最靠前的，因为越靠后越可能在后续过程中有机会被选取到。选取完成后我们将其修改为 \(0\) ，示意已经被选取过。

因而我们需要维护的是区间内的第一个最大值及其所在位置，并支持单点修改的操作，考虑用线段树维护。

在此基础上题目又增加了限制，相邻位置不能选取等大的数。那么当我们查询到的区间内最大值与上一位的取值相等时，应改为查询区间内的第一个严格次大值。这也可以使用线段树维护，只需修改一下线段树的信息结构和合并方式即可。

Code:

struct seg {int mx, mx2, mxpos, mx2pos;
} t[N << 2];void pushup(int p) {pii tmp[5];tmp[0] = make_pair(t[p << 1].mx, -t[p << 1].mxpos);tmp[1] = make_pair(t[p << 1].mx2, -t[p << 1].mx2pos);tmp[2] = make_pair(t[p << 1 | 1].mx, -t[p << 1 | 1].mxpos); tmp[3] = make_pair(t[p << 1 | 1].mx2, -t[p << 1 | 1].mx2pos);sort(tmp, tmp + 4);t[p].mx = tmp[3].first; t[p].mxpos = -tmp[3].second;for (int i = 2; i >= 0; i--) {if (tmp[i].first != tmp[3].first) {t[p].mx2 = tmp[i].first;t[p].mx2pos = -tmp[i].second;break;}}
}void build(int p, int l, int r) {if (l == r) {t[p].mx = a[l];t[p].mxpos = l;return;}int mid = (l + r) / 2;build(p << 1, l, mid);build(p << 1 | 1, mid + 1, r);pushup(p);
}void modify(int p, int l, int r, int x, int y) {if (l == r && l == x) {t[p].mx = y;return;}int mid = (l + r) / 2;if (x <= mid) modify(p << 1, l, mid, x, y);if (x > mid) modify(p << 1 | 1, mid + 1, r, x, y);pushup(p);
}seg querymx2(int p, int l, int r, int L, int R) {if (L <= l && r <= R) return t[p];if (L > r || R < l) return (seg){0, 0, 0, 0};int mid = (l + r) / 2;seg mxl = querymx2(p << 1, l, mid, L, R);seg mxr = querymx2(p << 1 | 1, mid + 1, r, L, R);pii tmp[5];tmp[0] = make_pair(mxl.mx, -mxl.mxpos);tmp[1] = make_pair(mxl.mx2, -mxl.mx2pos);tmp[2] = make_pair(mxr.mx, -mxr.mxpos); tmp[3] = make_pair(mxr.mx2, -mxr.mx2pos);sort(tmp, tmp + 4);seg ans = (seg){0, 0, 0, 0};ans.mx = tmp[3].first; ans.mxpos = -tmp[3].second;for (int i = 2; i >= 0; i--) {if (tmp[i].first != tmp[3].first) {ans.mx2 = tmp[i].first;ans.mx2pos = -tmp[i].second;break;}}return ans;
}void solve() {n = read(); k = read();FOR(i, 1, n) a[i] = read();build(1, 1, n);vector<int> ans(n + 1);FOR(i, 1, n) {seg now = querymx2(1, 1, n, i, min(i + k, n));if (now.mx == 0) {ans[i] = -1;} else if (i > 1 && now.mx == ans[i - 1]) {if (now.mx2 == 0) {ans[i] = -1;} else {ans[i] = now.mx2;modify(1, 1, n, now.mx2pos, 0);k -= now.mx2pos - i;}} else {ans[i] = now.mx;modify(1, 1, n, now.mxpos, 0);k -= now.mxpos - i;}}FOR(i, 1, n) cout << ans[i] << " ";
}