下面的代码都是远古代码，不打算重写了。
CSP-S 2023
T1 密码锁
题意：一个密码锁上有 \(5\) 个位置，每个位置上的数字是 \(0 \sim 9\) 的循环，每次打乱会选择一或两个相邻位置同时循环移动。
给定 \(n\) 个打乱后的状态，求有多少种可能的原状态。
\(n \le 8\)。
容易发现可能的状态数只有 \(10^5\) 种，全部搜出来，然后一一暴力校验合不合法即可。
Code
#include <iostream>
using namespace std;
const int N = 9;
int n, ans;
int a[N][6], b[6];
int dif[6], cnt;
bool check (int *a, int *b) {
cnt = 0;
for (int i = 1; i <= 5; ++i) {
if (a[i] != b[i]) {
dif[++cnt] = i;
}
}
if (!cnt || (cnt == 2 && dif[1] + 1 != dif[2]) || cnt > 2) return 0;
if (cnt == 1) return 1;
return !((a[dif[1]] + b[dif[2]] - a[dif[2]] - b[dif[1]]) % 10);
}
void dfs (int x) {
if (x == 6) {
bool fl = 1;
for (int i = 1; fl && i <= n; ++i) {
fl &= check(a[i], b);
}
ans += fl;
return;
}
for (int i = 0; i <= 9; ++i) {
b[x] = i, dfs(x + 1);
}
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int i = 1; i <= n; ++i) {
for (int j = 1; j <= 5; ++j) {
cin >> a[i][j];
}
}
dfs(1);
cout << ans << '\n';
return 0;
}
T2 消消乐
我们称一个字符串 \(a\) 是可消除的，当且仅当每次删去 \(a\) 中相邻的两个字符，经过若干次操作后能将 \(a\) 删空。
给定一个长度为 \(n\) 的字符串 \(s\)，求 \(s\) 有多少个非空子串是可消除的。
\(1 \le n \le 2 \times 10^6\)。
注意到可消除串与括号序列非常相似。我们为每一个字符指定一个左方向或右方向，那么字符串构成一个括号序列（括号的种类可能有很多）。
所以我们引入类似括号序列的判定方法：依次将所有元素压入栈中，若栈顶的两个元素相同则消去，最终如果得到空串，则原串是可消除的。
于是我们有了一个 \(O(n^2)\) 的做法。枚举左端点，然后将后面的元素依次加入，只需计数有多少个时刻栈为空。
进一步发掘可消除串的性质，我们发现在任意栈中加入一个可消除串，这个栈是不会改变的。具体证明考虑还是看成区分左右括号的括号序列，对于一个可消除串先进行括号匹配，对于一对匹配的括号 \(a, b\)，若 \(a\) 压入栈中成为左括号则可以直接消除，否则 \(a\) 作为右括号和栈中的一个元素 \(c\) 匹配，此时考虑数学归纳，\([a + 1, b - 1]\) 中的元素也是可消除串，则它们不会使栈该边，则 \(b\) 加入栈时会取代 \(c\)，整体还是不变。
我们发现上面的结论反过来也成立，若一个栈加入串 \(a\) 后不变，则 \(a\) 一定是可消除串，证明类似。
所以我们用两端前缀 \([1, l - 1], [1, r]\) 的栈来刻画一个可消除串 \([l, r]\)，若 \([1, l - 1]\) 和 \([1, r]\) 的栈相同，则 \([l, r]\) 时可消除的。所以我们按前缀栈对于 \([0, n]\) 中每一个位置划分等价类，对于一个等价类 \(C\)，答案为 \(|C| \choose 2\)。等价类的划分可以直接哈希。
时间复杂度 \(O(n)\)。
Code
#include <iostream>
#include <map>
using namespace std;
using Pr = pair<int, int>;
using LL = long long;
const int N = 2e6 + 5;
const int Mod = 1e9 + 7;
int n, tp;
int w[N], v[N];
char s[N], st[N];
int wp[N], vp[N];
map<Pr, int> p;
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
w[0] = v[0] = 1;
for (int i = 1; i <= n; ++i) {
cin >> s[i];
w[i] = (w[i - 1] * 1145141ll) % Mod;
v[i] = (v[i - 1] * 903607ll) % Mod;
}
p[{0, 0}] = 1;
for (int i = 1; i <= n; ++i) {
if (tp && s[i] == st[tp]) {
wp[i] = ((wp[i - 1] - 1ll * st[tp] * w[tp]) % Mod + Mod) % Mod;
vp[i] = ((vp[i - 1] - 1ll * st[tp] * v[tp]) % Mod + Mod) % Mod;
--tp;
}
else {
st[++tp] = s[i];
wp[i] = (wp[i - 1] + 1ll * st[tp] * w[tp]) % Mod;
vp[i] = (vp[i - 1] + 1ll * st[tp] * v[tp]) % Mod;
}
++p[{wp[i], vp[i]}];
}
LL ans = 0;
for (auto i : p) {
ans += 1ll * i.second * (i.second - 1) / 2;
}
cout << ans << '\n';
return 0;
}
T3 结构体
题意：写一个程序，模拟 C++ 中的结构体，变量，和它们的地址。
大模拟。注意仔细读题（特别是对其规则的部分）。
Code
#include <iostream>
#include <vector>
#include <map>
using namespace std;
using LL = long long;
const int N = 1e2 + 10;
const LL Inf = 1e18 + 1;
int n, tot = 4, cnt;
struct type {
LL siz, mx;
vector<int> e;
} t[N] = {{0, Inf}, {1, 1}, {2, 2}, {4, 4}, {8, 8}};
map<string, int> p{{"byte", 1}, {"short", 2}, {"int", 3}, {"long", 4}};
struct element {
int ty;
string na;
} a[N * N];
string ans;
void align (LL &x, LL y) {
if (x % y) x += y - x % y;
}
LL query_id (int k, string s) {
if (s.empty() || a[k].ty && a[k].ty <= 4) return 0;
string p = "";
for (int i = 0; i < s.size(); ++i) {
if (s[i] == '.') break;
p += s[i];
}
LL res = 0;
for (auto i : t[a[k].ty].e) {
align(res, t[a[i].ty].mx);
if (a[i].na == p) {
return res + query_id(i, s.substr(p.size() + 1, s.size() - p.size() - 1));
}
res += t[a[i].ty].siz;
}
}
void query_s (int k, LL x) {
if (a[k].ty && t[a[k].ty].e.empty() && x <= t[a[k].ty].siz) {
ans.pop_back();
return;
}
LL now, nex = 0;
for (auto i : t[a[k].ty].e) {
align(now = nex, t[a[i].ty].mx);
nex = now + t[a[i].ty].siz;
if (x >= now && x < nex) {
ans += a[i].na + ".";
return (void)query_s(i, x - now);
}
}
ans = "ERR";
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n;
for (int o; n--; ) {
cin >> o;
string s;
if (o == 1) {
cin >> s;
p[s] = ++tot;
int l; cin >> l;
for (int i = 1; i <= l; ++i) {
cin >> s;
a[++cnt].ty = p[s];
cin >> a[cnt].na;
t[tot].e.push_back(cnt);
t[tot].mx = max(t[tot].mx, t[a[cnt].ty].mx);
}
for (auto i : t[tot].e) {
align(t[tot].siz, t[a[i].ty].mx);
t[tot].siz += t[a[i].ty].siz;
}
align(t[tot].siz, t[tot].mx);
cout << t[tot].siz << ' ' << t[tot].mx << '\n';
}
else if (o == 2) {
cin >> s;
a[++cnt].ty = p[s];
cin >> a[cnt].na;
t[0].e.push_back(cnt);
align(t[0].siz, t[a[cnt].ty].mx);
cout << t[0].siz << '\n';
t[0].siz += t[a[cnt].ty].siz;
}
else if (o == 3) {
cin >> s;
cout << query_id(0, s + ".") << '\n';
}
else {
LL x; cin >> x;
ans = "", query_s(0, x);
cout << ans << '\n';
}
}
return 0;
}
T4 种树
题意：有 \(n\) 个地块，用 \(n - 1\) 条道路连接，构成一个有根树结构。
你需要在这些地块上种树，第 \(i\) 个地块上的树需要生长到 \(a_i\) 的高度，它在第 \(x\) 天会生长 \(\max(1, b_i + c_ix)\) 的高度。每天只能在一个地块上种树。
并且我们要求种树的顺序必须满足，若将 \(n\) 个地块看成有根树，那么一个点可以种树当且仅当它的所有祖先已经种了树，求最少多少天可以使得 \(\forall i \in [1, n]\)，第 \(i\) 棵树长到了 \(a_i\) 的高度。
\(1 \le n \le 10^5, 1 \le a_i \le 10^{18}, 1 \le b_i, c_i \le 10^9\)。
显然正着不太好做。考虑二分答案为 \(w\)，问题变成判定 \(w\) 的合法性。
我们希望计算一个 \(t_i\)，表示位置 \(i\) 最晚要在第 \(t_i\) 天种树，这样可以转化成一个纯正的树上问题。
然而 \(t_i\) 还是不好计算，我们考虑再二分它，问题就变成对于一个位置 \(i\)，算它生长时间为 \([l, r]\) 是否可行。这个我们可以直接用数学方法算出生长的高度，然后和 \(a_i\) 比较即可。
考虑求出 \(t_i\) 后怎么做。显然 \(t_i\) 越小的位置限制越严格，所以我们贪心地处理 \(t_i\) 小的位置，并给每一个位置分配一个种树的日期 \(num_i\)，那么一个方案可行当且仅当 \(\forall i \in [1, n], num_i \le t_i\)。
具体而言，我们将所有位置 \(i\) 按照 \(t_i\) 从小到大排序后分别考虑。假设我们当前考虑一个位置 \(i\)，并且 \(num_i\) 未确定。我们跳到 \(i\) 的最高级祖先 \(r\) 满足 \(num_r\) 也未确定，然后从 \(r\) 开始向下走，依次贪心分配最小标号即可。
时间复杂度 \(O(n \log n \log V)\)。
Code
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
using i128 = __int128;
const int N = 1e5 + 5;
int n, b[N], c[N], t[N], q[N], cnt[N], fa[N], num[N];
LL a[N];
vector<int> e[N];
void Init (int u) {
for (auto v : e[u]) {
if (v != fa[u]) {
fa[v] = u, Init(v);
}
}
}
bool Valid (int i, LL l, LL r) {
i128 d;
if (!c[i]) {
LL p = max(b[i], 1);
d = i128(p) * (r - l + 1);
}
else if (c[i] > 0) {
LL p = min(r + 1, max(l, 0ll + (c[i] - b[i]) / c[i]));
i128 dy = min(i128(1ll << 60), i128(p + r) * (r - p + 1) / 2);
d = (p - l) + (i128(b[i]) * (r - p + 1) + dy * c[i]);
}
else {
LL p = max(l - 1, min(r, 0ll + (1 - b[i]) / c[i]));
d = (r - p) + (i128(b[i]) * (p - l + 1) + i128(p + l) * (p - l + 1) / 2 * c[i]);
}
return d >= a[i];
}
bool Check (LL w) {
for (int i = 1; i <= n; ++i) {
LL l = 1, r = n;
while (l <= r) {
LL mid = (l + r) >> 1;
if (Valid(i, mid, w)) {
l = mid + 1;
}
else {
r = mid - 1;
}
}
t[i] = r;
if (!t[i]) return 0;
}
fill(cnt, cnt + n + 1, 0);
for (int i = 1; i <= n; ++i) {
++cnt[t[i]];
}
for (int i = 1; i <= n; ++i) {
cnt[i] += cnt[i - 1];
}
for (int i = 1; i <= n; ++i) {
q[cnt[t[i]]--] = i;
}
fill(num, num + n + 1, 0);
int cur = 0;
bool fl = 1;
for (int i = 1; i <= n; ++i) {
int u = q[i];
if (num[u]) continue;
vector<int> vec;
for (int v = u; v && !num[v]; v = fa[v]) {
vec.push_back(v);
}
while (!vec.empty()) {
int v = vec.back();
vec.pop_back();
num[v] = ++cur;
}
fl &= (num[u] <= t[u]);
}
return fl;
}
int main () {
cin.tie(0)->sync_with_stdio(0);
cin >> n;
LL lim = 0;
for (int i = 1; i <= n; ++i) {
cin >> a[i] >> b[i] >> c[i];
LL l = n, r = LL(1e18) + n;
while (l <= r) {
LL mid = (l + r) >> 1;
if (Valid(i, n, mid)) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
lim = max(lim, l);
}
for (int i = 1, u, v; i < n; ++i) {
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
Init(1);
LL l = n, r = lim;
while (l <= r) {
LL mid = (l + r) >> 1;
if (Check(mid)) {
r = mid - 1;
}
else {
l = mid + 1;
}
}
cout << l << '\n';
return 0;
}
CSP-S 2022
T1 假期计划
题意：给定一张 \(n\) 个顶点 \(m\) 条边的图，\(1\) 是家，\(2 \sim n\) 是景点，每个景点有一个价值 \(v_i\)。
要求选 \(4\) 个不同的景点 \(x_1, x_2, x_3, x_4\) 使得它们的总价值最大，要求五段行程 \(1 \rightarrow x_1, x_1 \rightarrow x_2, x_2 \rightarrow x_3, x_3 \rightarrow x_4, x_4 \rightarrow 1\) 中的每段 \(u \rightarrow v\)，都需要满足存在一条 \(u\) 到 \(v\) 的路径，且 \(u\) 到 \(v\) 的最短路径长度 \(\le k + 1\)。
求这个最大总价值。
\(1 \le n \le 2.5 \times 10^3, 1 \le m \le 10^4\)。
考虑先从每个点开始 \(\text{bfs}\) 一遍，求出任意两点的最短路 \(dis(u, v)\)，对于 \(dis(u, v) \le k + 1\) 的点对连一条边构成一张新图。题意转化为求经过 \(1\) 的最大权五元环。
假设答案形如 \(1 \rightarrow x_1 \rightarrow x_2 \rightarrow x_3 \rightarrow x_4 \rightarrow 1\)。最朴素暴力就是枚举 \(x_1, x_2, x_3, x_4\)，时间复杂度 \(O(n^4)\)。
接下来考虑类似 \(\text{Meet in the middle}\)，我们枚举 \(x_2, x_3\)，考虑一种贪心是选存在边 \((1, v), (v, x_2)\) 的权值最大的 \(v\) 作为 \(x_1\)，\(x_4\) 同理，这样显然可以保证权值和最大。
但直接这样做会出问题。假设 \(x_2\) 选出了一个 \(x_1\)，\(x_3\) 选出了一个 \(x_4\)，有可能出现 \(x_1 = x_3, x_1 = x_4, x_2 = x_4\) 这三种不合法情况。所以我们在位置 \(x_2\) 时保留前 \(4\) 大的 \(x_1\) 即可，\(x_4\) 的选择同理。
Code
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int cosk = 4;
const int N = 2505;
int n, m, k;
ll a[N];
vector<int> w[N];
int dis[N];
bool ed[N][N];
vector<int> e[N];
void Bfs (int s) {
fill(dis, dis + n + 1, N);
queue<int> Q;
dis[s] = 0; Q.push(s);
while (!Q.empty()) {
int x = Q.front();
Q.pop();
for (auto y : e[x]) {
if (dis[y] == N) {
dis[y] = dis[x] + 1;
Q.push(y);
}
}
}
}
void bsort (vector<int> &v) {
for (int k = min(cosk, (int)v.size() - 1); k > 0; ) {
if (a[v[k]] > a[v[k - 1]]) {
swap(v[k], v[k - 1]);
k--;
}
else break;
}
}
int main () {
cin >> n >> m >> k;
for (int i = 2; i <= n; i++) {
cin >> a[i];
}
for (int i = 1, x, y; i <= m; i++) {
cin >> x >> y;
e[x].push_back(y);
e[y].push_back(x);
}
for (int i = 1; i <= n; i++) {
Bfs(i);
for (int j = 1; j <= n; j++) {
if (j != i && dis[j] <= k + 1) {
ed[i][j] = 1;
}
}
}
for (int i = 2; i <= n; i++) {
for (int j = 2; j <= n; j++) {
if (i != j && ed[i][j] && ed[1][j]) {
if (w[i].size() <= cosk) {
w[i].push_back(j);
}
else {
w[i][cosk] = j;
}
bsort(w[i]);
}
}
}
ll ans = LONG_LONG_MIN;
for (int i = 2; i <= n; i++) {
for (int j = 2; j <= n; j++) {
if (i != j && ed[i][j]) {
for (auto x : w[i]) {
for (auto y : w[j]) {
if (i != y && j != x && x != y) {
ans = max(ans, a[i] + a[j] + a[x] + a[y]);
}
}
}
}
}
}
cout << ans;
return 0;
}
T2 策略游戏
给定一个长度为 \(n\) 的数组 \(a\) 和一个长度为 \(m\) 的数组 \(b\)，有 \(q\) 次询问：
- 给定 \(l_1, r_1, l_2, r_2\)，现在 \(\text{Alice}\) 会先选一个 \(i \in [l_1, r_1]\)，然后 \(\text{Bob}\) 会选一个 \(j \in [l_2, r_2]\)。此时得分为 \(a_i \times b_j\)。
- \(\text{Alice}\) 想让得分尽量大，\(\text{Bob}\) 想让得分尽量小。假设双方都用最优策略，求得分是多少。
\(1 \le n, m, q \le 10^5\)。
考虑贪心。我们站在 \(\text{Alice}\) 的角度，看她第一步会如何选择：
- 若 \([l_1, r_1]\) 中存在正数，而 \([l_2, r_2]\) 中只有正数，则 \(\text{Alice}\) 的一种策略是选 \([l_1, r_1]\) 中的最大正数，而 \(\text{Bob}\) 会选 \([l_2, r_2]\) 中的最小正数。
- 若 \([l_1, r_1]\) 中存在负数，而 \([l_2, r_2]\) 中只有负数，则 \(\text{Alice}\) 的一种策略是选 \([l_1, r_1]\) 中绝对值最大的负数，而 \(\text{Bob}\) 会选 \([l_2, r_2]\) 中绝对值最小的正数。
- 若 \([l_1, r_1]\) 中有 \(0\)，则 \(\text{Alice}\) 的一种策略是直接选 \(0\)。
- 若 \([l_1, r_1]\) 中有正数，且 \([l_2, r_2]\) 中的最小值为 \(0\)。或 \([l_1, r_1]\) 中有负数，且 \([l_2, r_2]\) 中的最大值为 \(0\)。则 \(\text{Alice}\) 可以逼 \(\text{Bob}\) 选 \(0\)。
- 若 \([l_1, r_1]\) 中存在正数，则 \(\text{Alice}\) 的一种策略是选最小的正数。
- 若 \([l_1, r_1]\) 中存在负数，则 \(\text{Alice}\) 的一种策略是选绝对值最小的负数。
可以证明答案一定是上面的情况之一。对于 \(\text{Alice}\) 的策略取 \(\max\) 即可。
接下来就是 \(\text{RMQ}\) 了，这个大家都会。
时间复杂度 \(O(n \log n + q)\)。
Code
#include <iostream>
#include <cmath>
using namespace std;
using LL = long long;
const int N = 1e5 + 5;
const int M = 18;
int n, m, q;
int x[N], y[N];
struct ST {
int len;
int a[N], v[N], Min[N][M], Max[N][M];
void Input (int *arr) {
for (int i = 1; i <= len; i++) {
a[i] = arr[i];
Min[i][0] = a[i];
Max[i][0] = a[i];
v[i] = v[i - 1] + (a[i] == 0);
}
}
void Init () {
for (int k = 1; k < M; k++) {
for (int i = 1; i + (1 << k) - 1 <= n; i++) {
Min[i][k] = min(Min[i][k - 1], Min[i + (1 << (k - 1))][k - 1]);
Max[i][k] = max(Max[i][k - 1], Max[i + (1 << (k - 1))][k - 1]);
}
}
}
bool Fzero (int l, int r) {
return (v[r] - v[l - 1] > 0);
}
int Query_Max (int l, int r) {
int k = log2(r - l + 1);
return max(Max[l][k], Max[r - (1 << k) + 1][k]);
}
int Query_Min (int l, int r) {
int k = log2(r - l + 1);
return min(Min[l][k], Min[r - (1 << k) + 1][k]);
}
} a, b, c, d;
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
a.len = n, b.len = m;
for (int i = 1; i <= n; i++) {
cin >> x[i];
}
for (int i = 1; i <= m; i++) {
cin >> y[i];
}
a.Input(x), b.Input(y);
a.Init(), b.Init();
c.len = n, d.len = n;
for (int i = 1; i <= n; i++) {
y[i] = x[i];
if (x[i] <= 0) {
x[i] = 1e9;
}
if (y[i] >= 0) {
y[i] = -1e9;
}
}
c.Input(x), d.Input(y);
c.Init(), d.Init();
for (int al, ar, bl, br; q--; ) {
cin >> al >> ar >> bl >> br;
LL ans = -1e18;
int aMax = a.Query_Max(al, ar);
int aMin = a.Query_Min(al, ar);
int bMax = b.Query_Max(bl, br);
int bMin = b.Query_Min(bl, br);
if (aMax > 0 && bMin > 0) {
ans = max(ans, 1ll * aMax * bMin);
}
if (aMin < 0 && bMax < 0) {
ans = max(ans, 1ll * aMin * bMax);
}
if (a.Fzero(al, ar) || (aMax > 0 && bMin == 0) || (aMin < 0 && bMax == 0)) {
ans = max(ans, 0ll);
}
if (aMax > 0 && bMin < 0) {
ans = max(ans, 1ll * c.Query_Min(al, ar) * bMin);
}
if (aMin < 0 && bMax > 0) {
ans = max(ans, 1ll * d.Query_Max(al, ar) * bMax);
}
cout << ans << '\n';
}
return 0;
}
T3 星战
给定一张 \(n\) 个点 \(m\) 条边的有向图，每条边都有激活和失活两种状态，初始时所有边都为激活。有四种操作共 \(q\) 次：
- 激活某条边。
- 激活以某个点作为终点的所有边。
- 失活某条边。
- 失活以某个点作为终点的所有边。
然后每次操作后询问，如果只考虑激活的边，是否满足：
- 所有点出度均为 \(1\)。
- 所有的点都满足，从这个点出发，可以走到一个环中。
\(1 \le n, m \le 5 \times 10^5\)。
首先题目中的条件等价为所有点出度为 \(1\)。因为此时你从一个点开始不断走出边，肯定是能到环的。
但是我们发现题目中的 \(2\) 和 \(4\) 操作很难直接维护出度。所以考虑哈希。
具体而言，我们称一条边的权值 \((u, v)\) 为 \(u\)，那么你可以近似的认为，当所有激活边的权值之和为 \(\frac{(n + 1)n}{2}\) 时，所有点出度就是 \(1\)。
此时对于单边的修改仍然是容易的，现在考虑我们修改以 \(v\) 为终点的所有边的状态。若此时所有边的状态是一样的话，我们可以维护 \(s_v\) 表示所有以 \(v\) 为终点的边的权值和。
那如果有些边的状态会被单点修改呢？也很好办，在做单点修改的时候更新 \(s_u\) 就好了。
最后我们可以将前面所述一条边 \((u, v)\) 的权值修改为与 \(u\) 有关的任意随机函数 \(f(u)\)，对后面的步骤不影响，这样可以保证正确性。
时间复杂度 \(O(n + m + q)\)。
Code
#include <iostream>
#include <numeric>
using namespace std;
using LL = long long;
const int N = 5e5 + 5;
int n, m, q;
int w[N];
LL r[N], s[N], sum, now;
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m;
for (int i = 1; i <= n; ++i) {
w[i] = rand() * rand();
sum += w[i];
}
for (int i = 1; i <= m; ++i) {
int u, v;
cin >> u >> v;
s[v] = (r[v] += w[u]);
}
now = accumulate(r + 1, r + n + 1, 0ll);
cin >> q;
while (q--) {
int o, u, v;
cin >> o >> u;
if (o == 1) {
cin >> v;
r[v] -= w[u], now -= w[u];
}
if (o == 2) {
now -= r[u], r[u] = 0;
}
if (o == 3) {
cin >> v;
r[v] += w[u], now += w[u];
}
if (o == 4) {
now += s[u] - r[u], r[u] = s[u];
}
cout << (now == sum ? "YES" : "NO") << '\n';
}
return 0;
}
T4 数据传输
题意：给定一棵 \(n\) 个结点的树和一个整数 \(k\)，第 \(i\) 个点有权值 \(v_i\)，\(q\) 次询问；
- 给出两个点 \(s\) 和 \(t\)，你需要选出一个顶点序列 \(c_1 = s, c_2, c_3, \ldots, c_{m - 1}, c_m = t\)，满足 \(\forall i \in [1, n)\)，\(c_i\) 和 \(c_{i + 1}\) 在树上的距离不超过 \(k\)，最小化 \(\sum\limits_{i = 1}^{m} v_{c_i}\)。
\(1 \le n, q \le 2 \times 10^5, k \le 3, v_i \ge 1\)。
先考虑 \(k = 3\) 的情况。对于一次询问 \(s, t\)，我们将 \(s\) 到 \(t\) 这条路径拉出来，写成 \(s \rightarrow u_1 \rightarrow u_2 \rightarrow u_3 \rightarrow \ldots \rightarrow u_m \rightarrow t\)。
观察最终的点序列长什么样，对于一个点 \(v\)，若它到这条路径的距离 \(\ge 2\)，则我们断言它一定不会用到。因为若存在 \(c_i \rightarrow v \rightarrow c_{i + 2}\)，则显然可以直接从 \(c_i\) 走到 \(c_{i + 2}\)，而这题点权为正，所以这样一定不优。
所以对于一个路径上的点 \(u_i\)，我们只关系它点权最小的，且不在路径上的邻居 \(t\)。甚至我们连这个邻居是什么也不关心，而只关心它的点权 \(w_{u_i} = v_t\)。
而每次询问求出 \(w_{u_i}\) 显然是不现实的。我们发现 \(t\) 在不在路径上无所谓，因为如果 \(t\) 在路径上只会更优，这显然合法。所以我们对于每个点 \(i\)，预处理它的点权最小的邻居，权值记作 \(w_i\)。
然后我们开始 \(\text{DP}\)，设 \(f_{j}\) 表示我们考虑了路径上的一段前缀 \(s \rightarrow \ldots \rightarrow u_i\)，选出的最后一个点距离 \(u_i\) 为 \(j\) 的方案数，显然 \(j = 0/1/2\)。这样可以 \(O(1)\) 转移，我们就得到时间复杂度为 \(O(nq)\) 的算法。
正解也很简单，考虑将 \(\text{DP}\) 的过程写成 \((\min, +)\) 矩阵乘法的形式。然后树上倍增维护一条路径上转移矩阵的并即可。
然后 \(k = 1/2\) 的情况显然非常简单。并且在写完 \(k = 3\) 后，也可以直接通过修改转移矩阵的方式通过。
时间复杂度 \(O((n + q) \log n)\)，此处忽略矩阵乘法的常数。
Code
#include <iostream>
#include <vector>
using namespace std;
using LL = long long;
const int N = 2e5 + 5;
const int M = 19;
const LL Inf = 1e18;
struct Mat {
LL a[3][3];
void clear () { fill(a[0], a[2] + 3, Inf); }
void init () { clear(); a[0][0] = a[1][1] = a[2][2] = 0; }
};
Mat operator* (Mat A, Mat B) {
Mat res; res.clear();
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
for (int k = 0; k < 3; k++) {
res.a[i][j] = min(res.a[i][j], A.a[i][k] + B.a[k][j]);
}
}
}
return res;
}
int n, m, k;
LL num[N], val[N];
int fa[N][M], dep[N];
Mat p[N][M], s[N][M];
vector<int> e[N];
Mat Init (int u) {
Mat res; res.clear();
res.a[0][0] = val[u];
if (k >= 2) {
res.a[0][1] = val[u], res.a[1][0] = 0;
}
if (k >= 3) {
res.a[0][2] = val[u], res.a[2][1] = 0, res.a[1][1] = num[u];
}
return res;
}
void Dfs (int u) {
dep[u] = dep[fa[u][0]] + 1;
num[u] = Inf;
for (auto v : e[u]) {
num[u] = min(num[u], val[v]);
if (v != fa[u][0]) {
fa[v][0] = u;
Dfs(v);
}
}
p[u][0] = s[u][0] = Init(u);
}
Mat Gets (int u, int v) {
Mat us, vs; us.init(), vs.init();
if (dep[u] < dep[v]) {
vs = p[v][0], v = fa[v][0];
}
for (int k = M - 1; k >= 0; k--) {
if (dep[u] - dep[v] >= (1 << k)) {
us = s[u][k] * us;
u = fa[u][k];
}
}
if (u == v) return vs * p[u][0] * us;
for (int k = M - 1; k >= 0; k--) {
if (fa[u][k] != fa[v][k]) {
us = s[u][k] * us, u = fa[u][k];
vs = vs * p[v][k], v = fa[v][k];
}
}
return vs * p[v][1] * p[u][0] * us;
}
LL Query (int u, int v) {
if (u == v) return val[u];
if (dep[u] < dep[v]) swap(u, v);
Mat trs = Gets(fa[u][0], v);
Mat base; base.clear();
base.a[0][0] = val[u];
return (trs * base).a[0][0];
}
int main () {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
cin >> val[i];
}
for (int i = 1; i < n; i++) {
int u, v;
cin >> u >> v;
e[u].push_back(v);
e[v].push_back(u);
}
Dfs(1);
for (int k = 1; k < M; k++) {
for (int i = 1; i <= n; i++) {
fa[i][k] = fa[fa[i][k - 1]][k - 1];
p[i][k] = p[i][k - 1] * p[fa[i][k - 1]][k - 1];
s[i][k] = s[fa[i][k - 1]][k - 1] * s[i][k - 1];
}
}
while (m--) {
int u, v;
cin >> u >> v;
cout << Query(u, v) << '\n';
}
return 0;
}