A qc数数
知识点:数学
把两个和按十进制展开:
$$R=(10a_1+b_1)+(10a_2+b_2),\qquad C=(10a_1+a_2)+(10b_1+b_2).$$
相减后 $10a_1$ 与 $b_2$ 都抵消,只剩 $R-C=9(a_2-b_1)$,所以答案为 $9|a_2-b_1|$,只有反对角线上的两个数字有意义。
时间复杂度 $\mathcal O(1)$。
void solve() {
int a1, b1, a2, b2;
cin >> a1 >> b1 >> a2 >> b2;
cout << 9 * llabs(a2 - b1) << endl;
}
B qc的纸带
知识点:模拟
左端打孔的位置是 $0,a,2a,\dots$,右端是从 $L$ 开始往前每隔 $b$ 打一个,即 $L,L-b,L-2b,\dots$。两种打孔都落在这 $L+1$ 个位置上,而 $L\le100$,直接开数组记下每个位置被打了几次,统计次数恰好为 $2$ 的位置即可。
时间复杂度 $\mathcal O(L)$。
void solve() {
int l, a, b;
cin >> l >> a >> b;
vector<int> f(l + 1);
for (int i = 0; i <= l; i += a) ++f[i];
for (int i = l; i >= 0; i -= b) ++f[i];
cout << ranges::count(f, 2) << endl;
}
C qc染色
知识点:图论,思维
每次操作都是把一张纸条的颜色刷到它唯一的邻居上,所以颜色只会沿“被拿走的纸条 → 它的邻居”这一方向传递。记最后幸存的是 $u_k$,它的颜色来自最后一个被拿走的邻居 $u_{k-1}$,$u_{k-1}$ 的颜色又来自 $u_{k-2}$……顺着往回找就得到一条路径 $u_1\to u_2\to\cdots\to u_k$,其中 $u_i$ 被拿走时把颜色刷给 $u_{i+1}$,于是 $u_k$ 的最后颜色就是 $c_{u_1}$。
起点 $u_1$ 被拿走时颜色还是原来的 $c_{u_1}$:一张纸条被刷,前提是有邻居比它先被拿走,而 $u_1$ 被拿走时只剩 $u_2$ 这一个邻居,所以它在原树里的度数就是 $1$,是叶子。
反过来,任取叶子 $u$ 和它的邻居 $v$,把 $u$ 以外的部分一路剥到只剩 $v$,最后拿走 $u$,$v$ 的颜色就变成 $c_u$。$n=1$ 时没有操作,答案为 $1$。
所以答案就是叶子颜色的种类数,去重统计即可。
时间复杂度 $\mathcal O(n\log n)$。
void solve() {
int n;
cin >> n;
vector<int> c(n + 1), deg(n + 1);
for (int i = 1; i <= n; ++i) cin >> c[i];
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v, ++deg[u], ++deg[v];
}
if (n == 1) return cout << 1 << endl, void();
set<int> st;
for (int i = 1; i <= n; ++i) if (deg[i] == 1) st.insert(c[i]);
cout << st.size() << endl;
}
D qc的箱子
知识点:数学,分类讨论
设第一箱有 $x$ 颗小球,其余每箱都被 $b$ 唯一确定:$a_2=b_1-x$,$a_3=b_2-b_1+x$……把第 $i$ 箱写成
$$a_i=s_i+(-1)^{i+1}x,$$
其中 $s_i$ 是 $x=0$ 时的值,满足 $s_1=0,\ s_i=b_{i-1}-s_{i-1}$。于是每个 $a_i\ge1$ 都只是 $x$ 的单边限制:$i$ 为奇数时 $x\ge1-s_i$,$i$ 为偶数时 $x\le s_i-1$,取交得到可行区间 $[l,r]$,为空则输出 $-1$。
要最小化的是 $\max_i a_i=\max(P+x,\ Q-x)$,其中 $P=\max{s_1,s_3,s_5,\dots}$,$Q=\max{s_2,s_4,\dots}$。两条直线交于 $x_0=\frac{Q-P}{2}$,把 $x$ 卡进 $[l,r]$ 之后,答案就是
$$\max\left(P+l,\ Q-r,\ \left\lceil\frac{P+Q}{2}\right\rceil\right),$$
$x$ 向左越界时由 $P+l$ 取到,向右越界时由 $Q-r$ 取到,否则由中间那项取到。
时间复杂度 $\mathcal O(n)$。
void solve() {
int n;
cin >> n;
vector<int> b(n), s(n + 1);
for (int i = 1; i < n; ++i) cin >> b[i], s[i + 1] = b[i] - s[i];
int l = 1, r = s[2] - 1;
int p = 0, q = s[2];
for (int i = 3; i <= n; ++i) {
if (i & 1) l = max(l, 1 - s[i]), p = max(p, s[i]);
else r = min(r, s[i] - 1), q = max(q, s[i]);
}
if (l > r) return cout << -1 << endl, void();
cout << max({p + l, q - r, (p + q + 1) / 2}) << endl;
}
E qc的补给站
知识点:计数,双指针
枚举区间是 $\mathcal O(n^2)$ 的,但固定左端点 $l$ 之后,每个人剩下的要求都变成对 $r$ 的一个上界。第 $i$ 个人到左站的距离是 $i-l+1$,到右站的距离是 $r-i+1$,于是:
- 若 $l\ge i-a_i+1$,他在左边就够了,对 $r$ 没有要求;
- 否则必须 $r\le i+a_i-1$。
也就是说,所有满足 $i-a_i\ge l$ 的人一起把 $r$ 卡在 $\min(i+a_i)-1$ 以内。区间外的人不会带来多余的限制:$i<l$ 时不可能满足 $i-a_i\ge l$,而 $i>r$ 时 $i+a_i-1\ge r$ 自动成立。于是 $l$ 固定时合法的 $r$ 有 $\max\bigl(0,\ \min(n,\ \min(i+a_i)-1)-l+1\bigr)$ 个。
$l$ 从 $n$ 递减到 $1$ 的过程中,集合 ${i:i-a_i\ge l}$ 只增不减,把所有人按 $i-a_i$ 降序排序后用一个单调后移的指针加入,同时维护 $i+a_i$ 的最小值即可。
时间复杂度 $\mathcal O(n\log n)$。
constexpr int inf = 1E9 + 7;
void solve() {
int n;
cin >> n;
vector<pii> a(n + 1);
for (int i = 1, x; i <= n; ++i) cin >> x, a[i] = {i - x, i + x};
ranges::sort(a.rbegin(), a.rend());
int ans = 0, mn = inf, j = 0;
for (int l = n; l >= 1; --l) {
while (j < n && a[j][0] >= l) mn = min(mn, a[j][1]), ++j;
ans += max(0LL, min(n, mn - 1) - l + 1);
}
cout << ans << endl;
}
F qc的树
知识点:树形 DP,最大路径和
给每条边赋权:两端同色 $w=1$,异色 $w=-1$,原来的异色边数就是 $G=#{w=-1}$。
翻转一条路径只改变“恰好一个端点在路径上”的边,路径内部的边两端一起翻,颜色关系不变。被翻的同色边变成异色贡献 $+1$,异色边变成同色贡献 $-1$,所以总增益就是这些边界边的 $w$ 之和。而 $\sum_{u\in P}S_u$($S_u$ 为 $u$ 的相邻边权之和)把路径内部的边算了两遍、边界边只算了一遍,于是
$$\text{增益}=\sum_{u\in P}S_u-2\sum_{e\in\text{路径内部}}w_e .$$
这就成了一个最大路径和:每个点带权 $S_u$,从 $u$ 走进儿子 $v$ 时额外减去 $2w_{uv}$。设 $f_u$ 为从 $u$ 向某个儿子走的最大增益,
$$f_u=S_u+\max\Bigl(0,\ \max_{v\ \text{是}\ u\ \text{的儿子}}\bigl(f_v-2w_{uv}\bigr)\Bigr),$$
路径在 $u$ 处汇合时取 $S_u+m_1+m_2$,其中 $m_1,m_2$ 是 ${0}\cup{f_v-2w_{uv}}$ 的最大值与次大值($0$ 表示路径在 $u$ 处停下)。
答案就是 $G+\max_u\bigl(S_u+m_1+m_2\bigr)$。
时间复杂度 $\mathcal O(n)$。
void solve() {
int n;
cin >> n;
vector<int> c(n + 1);
for (int i = 1; i <= n; ++i) cin >> c[i];
vector<vector<int>> g(n + 1);
for (int i = 1; i < n; ++i) {
int u, v;
cin >> u >> v, g[u].push_back(v), g[v].push_back(u);
}
vector<int> S(n + 1);
int G = 0;
for (int u = 1; u <= n; ++u) {
for (auto v : g[u]) {
if (u > v) continue;
int w = (c[u] == c[v]) ? 1 : -1; // 同色 +1,异色 -1
S[u] += w, S[v] += w, G += (w < 0);
}
}
vector<int> f(n + 1);
int mx = 0;
auto dfs = [&](auto &&self, int u, int fa) -> void {
int m1 = 0, m2 = 0;
for (auto v : g[u]) {
if (v == fa) continue;
self(self, v, u);
int w = (c[u] == c[v]) ? 1 : -1, val = f[v] - 2 * w;
if (val > m1) m2 = m1, m1 = val;
else if (val > m2) m2 = val;
}
f[u] = S[u] + m1;
mx = max(mx, S[u] + m1 + m2);
};
dfs(dfs, 1, 0);
cout << G + mx << endl;
}
约定
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii array<int, 2>
#define endl "\n"
void solve() {}
signed main() {
ios::sync_with_stdio(0), cin.tie(0);
cout << fixed << setprecision(20);
int t = 1;
cin >> t;
for (int i = 0; i < t; ++i) {
solve();
}
return 0;
}
使用到的算法模板见 $\tt Github$ 仓库 林月的XCPC模板库