7 月下.
先别羡慕了，再这么摆明年省队都没你了
LOJ 2769 「ROI 2017 Day 1」前往大都会
某国有编号为 \(1\) 到 \(n\) 的 \(n\) 座城市，还有编号为 \(1\) 到 \(m\) 的 \(m\) 条单向铁路线。\(i\) 号铁路线被沿途 \((s_i+1)\) 座城市分为 \(s_i\) 段。\(i\) 号铁路线从起点到终点依次经过 \(v_{\large i,1}, v_{\large i,2}, \dots, v_{\large i,s}\) 号城市，城市 \(v_{\large i,j}\) 通过这条线路到城市 \(v_{\large i,j+1}\) 花费的时间为 \(t_{\large i,j}\)。
现在你位于 \(1\) 号城市，你想要坐火车前往 \(n\) 号城市，途中可以换乘。求最少花费时间，及在花费时间最少的情况下，任意相邻两次换乘所花费时间的平方和的最大值，初始和结束也算换乘。
\(n,\sum s_i \leq 10^6\)。
建出最短路树，现在变成在 DAG 上做第二问。考虑 DP，设 \(f_{i}\) 表示在 \(i\) 号点进行了换乘的最大答案，转移枚举一个能不换乘到达 \(i\) 的点 \(j\)，有 $f_i \gets f_j + (s_i - s_j)^2$，其中 \(s_i\) 为 DAG 上 \(1\) 到 \(i\) 的路径长度。
注意到在 DAG 上每条铁路会被划分成若干段，每段是一条链。我们可以对段考虑，转移时改为枚举 \(i\) 所在的每个段，把这个段内所有 \(j\) 一起转移。这当然是可以做到的，考虑把平方拆开斜率优化：\(f_i = f_j + s_i^2 - 2s_is_j + s_j^2 \Rightarrow \underline{2s_i}_k \cdot \underline{s_j}_x + \underline{f_i - s_i^2}_b = \underline{f_j + s_j^2}_y\)
最大化截距，对每个段维护 \((s_j,f_j+s_j^2)\) 的上凸包即可，决策时在凸包上二分，总时间复杂度 \(\mathcal{O}(n \log n)\)。
注意全部转移完了再依次更新凸包。
code
#include <bits/stdc++.h>
using namespace std;
#define int long long
typedef long long LL;
typedef pair <int, int> pi;
constexpr int N = 2e6 + 5;
int n, m; LL d1[N], d2[N], ans1, ans2;
struct dat { int v, w, col; };
vector <dat> e[N], E[N], t[N];
bool vis[N];
priority_queue <pi> q;
int all, d[N]; LL f[N], sum[N];
vector <int> que[N], bel[N]; int hd[N], tl[N];
vector <pi> buk[N];
LL X(int i) { return sum[i]; }
LL Y(int i) {
return f[i] + sum[i] * sum[i];
}
signed main() {
// freopen("railway.in", "r", stdin);
// freopen("railway.out", "w", stdout);
cin >> n >> m;
for (int i = 1, s; i <= m; i++) {
cin >> s;
static int q[N];
for (int j = 1; j <= 2 * s + 1; j++) cin >> q[j];
for (int j = 1, x, y, z; j <= s; j++) {
x = q[2 * j - 1], y = q[2 * j + 1], z = q[2 * j];
e[x].push_back(dat{y, z, i});
E[y].push_back(dat{x, z, i});
}
}
for (int i = 1; i <= n; i++) d1[i] = 1e9 + 5;
d1[1] = 0;
q.push({-d1[1], 1});
while (!q.empty()) {
pi cur = q.top(); q.pop();
int u = cur.second;
if (vis[u] == true) continue;
vis[u] = true;
for (int j = 0; j < (int)e[u].size(); j++) { int v = e[u][j].v, w = e[u][j].w;
if (d1[v] > d1[u] + w) {
d1[v] = d1[u] + w;
if (vis[v] == false) q.push({-d1[v], v});
}
}
}
for (int i = 1; i <= n; i++) d2[i] = 1e9 + 5, vis[i] = 0;
d2[n] = 0;
q.push({-d2[n], n});
while (!q.empty()) {
pi cur = q.top(); q.pop();
int u = cur.second;
if (vis[u] == true) continue;
vis[u] = true;
for (int j = 0; j < (int)E[u].size(); j++) { int v = E[u][j].v, w = E[u][j].w;
if (d2[v] > d2[u] + w) {
d2[v] = d2[u] + w;
if (vis[v] == false) q.push({-d2[v], v});
}
}
}
ans1 = d1[n];
// cerr << ans1 << "\n";
// for (int i = 1; i <= n; i++) cerr << d1[i] << " \n"[i == n];
// for (int i = 1; i <= n; i++) cerr << d2[i] << " \n"[i == n];
for (int u = 1; u <= n; u++) {
for (int j = 0; j < (int)e[u].size(); j++) { int v = e[u][j].v, w = e[u][j].w, i = e[u][j].col;
if (d1[u] + w + d2[v] == ans1) {
t[u].push_back({v, w, i});
buk[i].push_back({u, v});
d[v]++;
// cerr << "add : " << u << " -> " << v << ", val = " << w << ", col = " << i << "\n";
}
}
}
for (int i = 1; i <= n; i++) sum[i] = d1[i];
for (int i = 1; i <= m; i++) {
vector <int> tmp;
static int c[N], to[N];
for (int j = 0; j < (int)buk[i].size(); j++) { int u, v; tie(u, v) = buk[i][j];
tmp.push_back(u), tmp.push_back(v);
to[u] = v;
c[v]++;
}
tmp.erase(unique(tmp.begin(), tmp.end()), tmp.end());
for (int j = 0; j < (int)tmp.size(); j++) { int x = tmp[j];
if (c[x] == 0) {
++all;
bel[x].push_back(all);
while (to[x]) x = to[x], bel[x].push_back(all);
}
}
for (int j = 0; j < (int)tmp.size(); j++) { int x = tmp[j];
c[x] = 0, to[x] = 0;
}
}
// for (int i = 1; i <= n; i++) {
// cerr << i << " belongs : ";
// for (auto x : bel[i]) cerr << x << " "; cerr << "\n";
// }
f[1] = 0;
queue <int> Q;
Q.push(1);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int j = 0; j < (int)bel[u].size(); j++) { int x = bel[u][j];
if (hd[x]) {
// if (u == 4 && x == 3 || u == 6 && x == 3) for (int i = hd[x]; i <= tl[x]; i++) cerr << que[x][i] << " \n"[i == tl[x]];
// while (hd[x] < tl[x] && sum[u] * (X(que[x][hd[x] + 1]) - X(que[x][hd[x]])) < (Y(que[x][hd[x] + 1]) - Y(que[x][hd[x]]))) hd[x]++;
// int v = que[x][hd[x]];
int v = que[x][tl[x]];
if (hd[x] != tl[x]) {
int l = hd[x], r = tl[x] - 1;
while (l <= r) {
int m = ((l + r) >> 1);
if (1LL * 2 * sum[u] * (X(que[x][m + 1]) - X(que[x][m])) > (Y(que[x][m + 1]) - Y(que[x][m]))) r = m - 1, v = que[x][m];
else l = m + 1;
}
}
f[u] = max(f[u], f[v] + (sum[u] - sum[v]) * (sum[u] - sum[v]));
}
}
for (int j = 0; j < (int)bel[u].size(); j++) { int x = bel[u][j];
if (hd[x] == 0) {
que[x].push_back(0);
que[x].push_back(u);
hd[x] = tl[x] = 1;
} else {
while (hd[x] < tl[x] && 1LL * (Y(u) - Y(que[x][tl[x] - 1])) * (X(u) - X(que[x][tl[x]])) < 1LL * (Y(u) - Y(que[x][tl[x]])) * (X(u) - X(que[x][tl[x] - 1]))) que[x].pop_back(), tl[x]--;
que[x].push_back(u), tl[x]++;
}
}
for (int j = 0; j < (int)t[u].size(); j++) { int v = t[u][j].v;
if (--d[v] == 0) Q.push(v);
}
}
// for (int i = 1; i <= n; i++) cerr << f[i] << " \n"[i == n];
// for (int i = 1; i <= n; i++) cerr << "(" << X(i) << ", " << Y(i) << ")\n";
cout << ans1 << " " << f[n] << "\n";
return 0;
}
/*
7 5
1 1 10000 3
1 1 9999 2
4 2 1 3 1 6 1 4 1 5
1 4 10000 7
1 5 9999 7
*/
ARC 093F Dark Horse
有 \(2^n\) 个人，按照满二叉树的形态进行淘汰赛。给定 \(m\) 个人 \(a_1 \sim a_m\)，表示这 \(m\) 个人能赢 \(1\) 号，对于其它的情况，编号小的赢。求在所有 \((2^n)!\) 种情况中，有多少种 \(1\) 号能取得最终的胜利。答案对 \(10^9+7\) 取模。\(n,m \leq 16\)，保证 \(a_i\) 升序给出。
钦定 \(1\) 号在第一个位置，最后再将答案乘上 \(2^n\)。合法只需要保证 \([2,2],[3,4],\cdots,[2^{k-1}+1,2^k],\cdots,[2^{n-1}+1,2^n]\) 这些区间中不存在任何一个的最小值在 \(a_1 \sim a_m\) 中。
任意一个都不在 \(a_1 \sim a_m\) 中的限制有点不好算，考虑容斥，设 \(F(i)\) 为钦定了 \(i\) 个 \(a_j\) 是区间的最小值，剩下随便填的方案数，答案即为 \(\sum\limits_{i=1}^n F(i)\)。
接下来考虑如何求 \(F(i)\)。考虑状压 DP，设 \(f_{i,j}\) 表示考虑了 \(a_1 \sim a_i\)，二进制数 \(j\) 的 \(2^k\) 为 \(1\) 当且仅当长度为 \(2^k\) 的区间的最小值已经被钦定为 \(a_1 \sim a_i\) 中的某个值。当我们发现这样并不好转移，因为钦定一个 \(a_i\) 相当于一个 \(\geq a_i\) 的限制，如果我们先考虑松的限制，那么我们无法确定更紧的限制是否能被满足。倒过来 DP 即可，设 \(f_{i,j}\) 为了 \(a_{m-i+1} \sim a_m\)，那么每次转移时填入的数一定 \(\geq a_{m-i+1}\)，枚举 \(a_{m-i}\) 填入的区间长度 \(2^k\)，相当于在 \((a_{m-i},2^n]\) 中没被用过的 \(2^n - a_{m-i} - j\) 个数中选 \(2^k-1\) 个并排列，方案数为 \(\dbinom{2^n - a_{m-i} - j}{2^k-1} \times (2^k)!\)，预处理组合数即可，总时间复杂度 \(\mathcal{O}(n^22^n)\)。
code
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 18, mod = 1e9 + 7;
int n, m, a[N], f[N][1 << 17], fc[1 << 17], ifc[1 << 17];
int ksm(int a, int b) {
int ret = 1;
for (; b; b >>= 1, a = 1LL * a * a % mod) if (b & 1) ret = 1LL * ret * a % mod;
return ret;
}
void init(int n) {
fc[0] = 1;
for (int i = 1; i <= n; i++) fc[i] = 1LL * fc[i - 1] * i % mod;
ifc[n] = ksm(fc[n], mod - 2);
for (int i = n; i >= 1; i--) ifc[i - 1] = 1LL * ifc[i] * i % mod;
}
int bin(int n, int m) {
if (n < m || m < 0) return 0;
return 1LL * fc[n] * ifc[m] % mod * ifc[n - m] % mod;
}
signed main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= m; i++) cin >> a[i];
init(1 << n);
f[m + 1][0] = 1;
for (int i = m; i >= 1; i--) {
for (int j = 0; j < (1 << n); j++) {
f[i][j] = (f[i][j] + f[i + 1][j]) % mod;
for (int k = 0; k < n; k++) if (((j >> k) & 1) == 0) {
f[i][j + (1 << k)] = (f[i][j + (1 << k)] + 1LL * f[i + 1][j] * bin((1 << n) - j - a[i], (1 << k) - 1) % mod * fc[1 << k] % mod) % mod;
}
}
}
int ans = 0;
for (int s = 0; s < 1 << n; s++) {
int coef = ((__builtin_popcount(s) & 1) == 1 ? mod - 1 : 1);
ans = (ans + 1LL * coef * f[1][s] % mod * fc[(1 << n) - s - 1] % mod) % mod;
}
ans = 1LL * ans * (1 << n) % mod;
cout << ans << "\n";
return 0;
}
ARC 058F 文字列大好きいろはちゃん
给定 \(n\) 个字符串，选出若干个顺次连接，要求得到的字符串长度为 \(k\)。求字典序最小的最终串，保证有解。
\(n \leq 2000\)，\(k \leq 10^4\)，\(\sum s_i \leq 10^6\)。
首先用背包对每个后缀算出后 \(i\) 个字符串能拼成的所有长度。
考虑从前往后 DP，设 \(f_{i,j}\) 为前 \(i\) 个字符串拼成的长度为 \(j\) 的字典序最小的串。显然如果后缀拼不出长度 \(k-j\)，这个状态就可以直接扔掉了。
注意到，对于两个合法的 \(j_1,j_2\) 满足 \(j_1 < j_2\)，且 \(f_{i,j_1}\) 不为 \(f_{i,j_2}\) 的前缀，那么它们两个中字典序较大的一个也一定可以扔掉，所以 \(f_i\) 一定形如一个母串，和它的一些前缀。考虑直接维护这些东西，转移 \(f_{i,j} \gets \min(f_{i-1,j},f_{i-1,j-|s_i|} + s_i)\)，比较字典序可以用 Z 函数，可惜我不会，于是写了二分哈希，额外维护每个长度是从哪个 \(j\) 转移来的即可。时间复杂度 \(\mathcal{O}(nk \log k)\)。
然后就被小卡了一下，但是发现这个东西跑的最慢的时候所有字符都相同，我们特判一手，然后就过了。
code
#include <bits/stdc++.h>
using namespace std;
typedef vector <char> vc;
typedef vector <int> vi;
constexpr int N = 3e3 + 5, K = 1e4 + 5, B = 233, mod = 1e9 + 7;
int ksm(int a, int b) {
int ret = 1;
for (; b; b >>= 1, a = 1LL * a * a % mod) if (b & 1) ret = 1LL * ret * a % mod;
return ret;
}
int n, k, suf[N][K], hav[K], L[N], pw[K], inv[K], pos[K], stk[K], tp;
vc str[N], cur; int curL;
vi h[N];
int getH(int t, int i, int j) {
if (i > j) return 0;
return 1LL * (h[t][j] + mod - h[t][i - 1]) % mod * inv[i - 1] % mod;
}
int main() {
// ios :: sync_with_stdio(false);
// cin.tie(nullptr);
cin >> n >> k;
pw[0] = 1;
for (int i = 1; i <= k; i++) pw[i] = 1LL * pw[i - 1] * B % mod;
inv[k] = ksm(pw[k], mod - 2);
for (int i = k; i >= 1; i--) inv[i - 1] = 1LL * inv[i] * B % mod;
for (int i = 1; i <= n; i++) {
string s;
cin >> s;
L[i] = s.length();
str[i].resize(L[i] + 1);
h[i].resize(L[i] + 1);
for (int j = 1; j <= L[i]; j++) str[i][j] = s[j - 1];
h[i][0] = 0;
for (int j = 1; j <= L[i]; j++) h[i][j] = (h[i][j - 1] + 1LL * str[i][j] * pw[j] % mod) % mod;
}
bool allsame = true;
char c = str[1][1];
for (int i = 1; i <= n; i++) for (int j = 1; j <= L[i]; j++) if (c != str[i][j]) allsame = false;
if (allsame == true) {
for (int i = 1; i <= k; i++) cout << c;
cout << "\n";
return 0;
}
suf[n + 1][0] = 1;
for (int i = n; i >= 1; i--) {
for (int j = 0; j <= k; j++) {
suf[i][j] = suf[i + 1][j];
if (j >= L[i]) suf[i][j] |= suf[i + 1][j - L[i]];
}
}
// for (int i = 1; i <= n; i++) cerr << L[i] << " \n"[i == n];
cur.resize(k + 1);
h[0].resize(k + 1);
hav[0] = 1;
for (int i = 1; i <= n; i++) {
if (L[i] > k) continue;
h[0][0] = 0;
for (int j = 1; j <= curL; j++) h[0][j] = (h[0][j - 1] + 1LL * cur[j] * pw[j] % mod) % mod;
for (int j = 1; j <= k; j++) pos[j] = -1;
for (int j = 1; j <= k; j++) {
// if (i == 5 && j == 9) cerr << suf[i + 1][k - j] << "\n";
if (suf[i + 1][k - j] == 0) continue;
if (hav[j]) pos[j] = j;
if (j >= L[i] && hav[j - L[i]] == 1) {
if (pos[j] == -1) {
pos[j] = j - L[i];
continue;
}
int l = 1, r = L[i], ns = 0;
while (l <= r) {
int m = (l + r) >> 1;
if (getH(i, 1, m) == getH(0, (j - L[i]) + 1, (j - L[i]) + m)) ns = m, l = m + 1;
else r = m - 1;
}
// if (i == 5 && j == 9) cerr << getH(i, 1, 1) << " " << getH(0, 6, 6) << " " << ns << "\n";
if (ns == L[i]) pos[j] = j - L[i];
if (cur[(j - L[i]) + ns + 1] > str[i][ns + 1]) pos[j] = j - L[i];
}
}
// for (int j = 1; j <= k; j++) cerr << pos[j] << " \n"[j == k];
for (int j = 1; j <= tp; j++) hav[stk[j]] = 0;
tp = 0;
for (int j = 1; j <= k; j++) if (pos[j] >= 0) {
if (tp == 0) {
stk[++tp] = j;
continue;
} else {
while (tp) {
int t = stk[tp];
int l = 1, r = t, ns = 0;
while (l <= r) {
int m = (l + r) >> 1;
int H1, H2;
if (m <= pos[t]) {
H1 = getH(0, 1, m);
} else {
H1 = (getH(0, 1, pos[t]) + 1LL * getH(i, 1, m - pos[t]) * pw[pos[t]] % mod) % mod;
}
if (m <= pos[j]) {
H2 = getH(0, 1, m);
} else {
H2 = (getH(0, 1, pos[j]) + 1LL * getH(i, 1, m - pos[j]) * pw[pos[j]] % mod) % mod;
}
if (H1 == H2) l = m + 1, ns = m;
else r = m - 1;
}
// if (t == 5) {
// cerr << j << " " << t << " " << ns << "\n";
// }
if (ns == t) {
stk[++tp] = j;
break;
} else {
char c1, c2;
ns++;
if (ns <= pos[t]) c1 = cur[ns];
else c1 = str[i][ns - pos[t]];
if (ns <= pos[j]) c2 = cur[ns];
else c2 = str[i][ns - pos[j]];
if (c1 > c2) tp--;
else break;
}
}
if (tp == 0) stk[++tp] = j;
}
}
// cerr << stk[tp] << "\n";
curL = stk[tp];
for (int j = curL + 1; j <= k; j++) cur[j] = 0;
if (pos[curL] < curL) {
for (int j = 1; j <= L[i]; j++) cur[pos[curL] + j] = str[i][j];
}
for (int j = 1; j <= tp; j++) hav[stk[j]] = 1;
hav[0] = 1;
// for (int j = 1; j <= curL; j++) cerr << hav[j];
// cerr << "\n";
// for (int j = 1; j <= curL; j++) putchar(cur[j]);
// cerr << "\n";
}
for (int i = 1; i <= k; i++) cout << cur[i];
cout << "\n";
return 0;
}
/*
10 21
baabb
ba
ba
bbaaaa
baab
a
baa
aaa
bb
aaa
*/
ABC 219H Candles
有 \(n\) 支蜡烛放在数轴上，第 \(i\) 支的坐标为 \(x_i\)。在 \(0\) 时刻，蜡烛的长度为 \(a_i\)。点燃的蜡烛每 \(1\) 时刻长度短 \(1\)，当长度为 \(0\) 时，蜡烛就会燃烧殆尽，之后长度不变。另外，被熄灭的蜡烛的长度不变。
你 \(0\) 时刻在坐标 \(0\)，每个时刻可以移动 \(1\) 单位长度。你在与自己所在坐标相同的坐标上有蜡烛的情况下，能够将蜡烛的火熄灭。同一坐标中有多个蜡烛的情况下可以一起吹灭，熄灭蜡烛所需的时间可以忽略不计。
求经过 \(10^{100}\) 时刻后剩下的蜡烛长度之和的最大值。\(n \leq 300\)，\(|x_i|,a_i \leq 10^9\)。
显然任意时刻被熄灭的蜡烛形成一段区间。考虑区间 DP。
先对所有蜡烛排序，使 \(x_i\) 单调不降。一个朴素的想法是设 \(f_{i,j,k,0/1}\) 为取了 \([i,j]\) 内的蜡烛，花费了 \(k\) 的时间，最终走到左或右端点，取到蜡烛长度的最大值，容易写出转移。但 \(k\) 的值域太大，这个角度似乎没什么救，考虑能不能把 \(k\) 给去掉。
我们称一个蜡烛有效当且仅当我们取到它时长度仍大于 \(0\)。假设取某一个区间内有效蜡烛的顺序是 \(t_1 \sim t_c\)，那么总贡献是 \(\sum\limits_{i=1}^c a_{t_i} - (c-i+1) \times |x_{t_i} - x_{t_{i-1}}|\)。虽然转移时我们并没有办法确定 \(c\)，但可以发现只需要倒着 DP 就可以把 \((c-i+1)\) 变成 \(i\) 了。具体来说我们设 \(f_{i,j,k,0/1}\) 表示当前在区间 \([i,j]\) 的左或右端点，当前这个蜡烛是倒数第 \(k\) 个，容易写出转移。如果有蜡烛得分为负数，那么最优解中一定不会包含它，因此这么 DP 是正确的。
总时间复杂度 \(\mathcal{O}(n^3)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
constexpr int N = 305;
int n; LL f[N][N][N][2];
struct dat {
LL x, y;
dat (LL _1 = 0, LL _2 = 0) : x(_1), y(_2) {}
} a[N];
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
a[++n] = dat(0, 0);
sort(a + 1, a + n + 1, [&](dat i, dat j) { return i.x < j.x; });
int p = -1;
for (int i = 1; i <= n; i++) if (!a[i].y) { p = i; break; }
memset(f, -0x3f, sizeof(f));
for (int i = 0; i <= n; i++) f[p][p][i][0] = f[p][p][i][1] = 0;
for (int L = 2; L <= n; L++) {
for (int i = 1, j = L; j <= n; i++, j++) {
for (int k = 0; k <= n; k++) {
f[i][j][k][0] = max({f[i + 1][j][k][0] - (a[i + 1].x - a[i].x) * k, f[i + 1][j][k + 1][0] - (a[i + 1].x - a[i].x) * (k + 1) + a[i].y, f[i + 1][j][k][1] - (a[j].x - a[i].x) * k, f[i + 1][j][k + 1][1] - (a[j].x - a[i].x) * (k + 1) + a[i].y});
f[i][j][k][1] = max({f[i][j - 1][k][0] - (a[j].x - a[i].x) * k, f[i][j - 1][k + 1][0] - (a[j].x - a[i].x) * (k + 1) + a[j].y, f[i][j - 1][k][1] - (a[j].x - a[j - 1].x) * k, f[i][j - 1][k + 1][1] - (a[j].x - a[j - 1].x) * (k + 1) + a[j].y});
}
}
}
LL ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = i; j <= n; j++) {
for (int k = 0; k <= n; k++) {
ans = max(ans, max(f[i][j][k][0], f[i][j][k][1]));
}
}
}
cout << ans << "\n";
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) solve();
return 0;
}
QOJ 1878 No Rest for the Wicked
有 \(n\) 个国家通过 \(m\) 条双向边连接，每个国家有先进度 \(s_i\)，危险度 \(c_i\)，控制阈值 \(t_i\)。如果想要到达国家 \(j\)，那么需满足：对于所有之前到过的国家 \(i\)，有 \(c_i \leq t_j\)。对每个 \(i\) 求出：从 \(i\) 出发，能到达的先进度最大的国家所对应的先进度。\(n,m \leq 2 \times 10^5\)，\(c_i,t_i,s_i \leq 10^9\)，\(c_i \leq t_i\)。
设 \(f(x,v)\) 为以危险度 \(x\) 从国家 \(v\) 出发，能到达的最大先进度。考虑怎么求这个东西。
假设我们已经确定了初始危险度 \(x\)，那么那些 \(t_i < x\) 的国家就可以直接扔了。我们称一条边 \(u \Leftrightarrow v\) 是自由边当且仅当 \(c_u\) 和 \(c_v\) 都 \(\leq x\)，此时从哪边通过这条边都不会改变 \(x\) 的值。如果 \(c_u \leq x < c_v\)，我们则称之为单向边，通过它会使得 \(x\) 的值增大。记从 \(v\) 只通过自由边能到达的点集为 \(FC(v)\)。
如果我们以危险度 \(x\) 从国家 \(v\) 出发，那么走法大概有两种：通过若干自由边，到达 \(FC(v)\) 内先进度最大的国家，或者至少通过一条单向边。对于 \(FC(v)\) 内的点 \(u\)，记其单向边的出点集合为 \(T(u)\)，则可以写出转移：\(f(x,v) = \max(\{s_u : u \in FC(v)\} \cup \{f(c_w,w) : u \in FC(v), w \in T(u)\})\)。
然后我们就发现有用的其实只有 \(f(c_u,u)\) 这样的东西，一个暴力的做法是从大到小枚举危险度 \(x\)，建出图转移，但这样复杂度显然不太行。注意到无论是单向边还是自由边，一条边都会在一段区间内的危险值对应的图中出现，线段树分治一下，用可撤销并查集维护一下 \(FC(v)\) 和点集内 \(\max s_i\) 即可。
总时间复杂度 \(\mathcal{O}(n \log^2 n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef tuple <int, int, int> ti3;
constexpr int N = 4e5 + 5;
int n, m, c[N], t[N], u[N], v[N], fa[N], siz[N], ans[N], mx[N], tp;
int gf(int x) { while (x != fa[x]) x = fa[x]; return x; }
struct dat {
int x, y, val;
dat(int _1 = 0, int _2 = 0, int _3 = 0) : x(_1), y(_2), val(_3) {}
} stk[N << 1];
void merge(int x, int y) {
x = gf(x), y = gf(y);
if (x == y) return;
if (siz[x] < siz[y]) swap(x, y);
fa[y] = x, siz[x] += siz[y];
stk[++tp] = dat(x, y, mx[x]);
mx[x] = max(mx[x], ans[y]);
ans[x] = max(ans[x], mx[x]);
}
void work(const vector <ti3> &vc, int L, int R) {
if (vc.empty()) return;
vector <ti3> vl, vr;
int m = L + R >> 1, lst = tp;
for (auto [l, r, id] : vc) {
if (l <= L && r >= R) {
if (id > 0) merge(u[id], v[id]);
else {
id = -id;
stk[++tp] = dat(u[id], 0, mx[u[id]]);
mx[u[id]] = max(mx[u[id]], ans[v[id]]);
ans[u[id]] = max(ans[u[id]], mx[u[id]]);
}
} else {
if (l <= m) vl.emplace_back(l, r, id);
if (r > m) vr.emplace_back(l, r, id);
}
}
work(vr, m + 1, R), work(vl, L, m);
while (tp > lst) {
int x = stk[tp].x, y = stk[tp].y;
if (y) {
siz[x] -= siz[y], fa[y] = y, ans[y] = max(ans[y], ans[x]);
}
mx[x] = stk[tp].val, tp--;
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> c[i] >> t[i] >> mx[i], fa[i] = i, siz[i] = 1, ans[i] = mx[i];
vector <ti3> E;
for (int i = 1; i <= m; i++) {
cin >> u[i] >> v[i];
if (c[u[i]] > c[v[i]]) swap(u[i], v[i]);
int l = c[v[i]], r = min(t[u[i]], t[v[i]]);
if (l <= r) E.emplace_back(l, r, i);
l = c[u[i]], r = min(t[u[i]], c[v[i]] - 1);
if (l <= r) E.emplace_back(l, r, -i);
}
work(E, 1, 1000000000);
for (int i = 1; i <= n; i++) cout << ans[i] << " \n"[i == n];
return 0;
}
QOJ 6745 Delete the Tree
给定一颗 \(n\) 个点的树。每次操作形如：选择一个独立集 \(S\) 将其及相关的边删去，然后对于所有 \(u \in S\)，\(u\) 所有不同邻居两两连边。要求在 \(10\) 次之内把树删空，并构造方案。\(n \leq 500\)。
比较神秘的观察：简化条件，假设最后一步只删一个点，那么无论怎么删都是合法的，并且能划分成若干个子问题。按点分治那样递归 \(\mathcal{O}(\log n)\) 次就行了。
CF 1806E Tree Master
给定一颗 \(n\) 个点的树，每个点都有权值 \(a_i\)。规定 \(f(x,y)=\begin{cases}0&(x=y=0)\\f(p_x,p_y)+a_x\cdot a_y&(x,y\neq0)\end{cases}\)，\(q\) 次询问，每次给定两个相同深度的节点 \(x,y\)，求 \(f(x,y)\)。\(n,q \leq 10^5\)，时限 \(\text{3.0s}\)。
这个形式一看就不太能 polylog，结合数据范围我们直接考虑根号分治：取 \(B = \sqrt n\)，称节点个数 \(\geq B\) 的深度为关键层，其余层为非关键层。对于非关键层我们预处理出两两点权乘积，每次询问不断跳到最近的关键层，关键层间的贡献可以用前缀和快速计算，总时间复杂度 \(\mathcal{O}((n+q)\sqrt n)\)。
CF 1805E There Should Be a Lot of Maximums
定义一颗树的权值为其出现次数大于一次的点权最大值。给定一颗 \(n\) 个点的树，对于每一条边求出将其删除后形成的两颗新树的权值的最大值。\(n \leq 10^5\)。
经典套路了，支配点对状物，先把只出现一次的扔了，然后考虑全局的最大权值：出现了至少三次，那么答案都是它，否则设出现在 \(x,y\)，那么除了 \((x,y)\) 这条链上答案都是它，把链拉出来随便做一做就行了。时间复杂度 \(\mathcal{O}(n \log n)\)。
CF 1801D The way home
一个人在一张有向图的 \(1\) 号结点，他要去到 \(n\) 结点。每条边 \((a_i,b_i)\) 有边权 \(s_i\)，表示走过这条边需要花 \(s_i\) 元。这个人一开始有 \(p\) 元，到了一个点 \(u\)，他可以进行若干次演出，每次演出收获 \(w_u\) 元。问到达 \(n\) 的最小演出次数，若无解输出 -1。\(n \leq 800\)，\(m \leq 3000\)，\(p,w_i,s_i \leq 10^9\)。
关键性质：在城市 \(i\) 表演之后，不会在城市 \(w_j \leq w_i\) 的城市 \(j\) 再表演了。否则把表演提到 \(i\) 一定不劣。
设 \(f_i\) 表示到达城市 \(i\) 最少需要多少次表演，\(g_i\) 对应剩余钱数。按 \(w_i\) 从小到大转移，现在的问题是，考虑从 \(u\) 到 \(v\) 的路径，对于两组 \((f_1,g_1)\) 和 \((f_2,g_2)\)，若满足 \(f_1<f_2\) 和 \(g_1<g_2\)，我们如何判断哪一组是更优的。
我们可以断言，\((f_1,g_1)\) 比 \((f_2,g_2)\) 更优。事实上，\(f_1\) 只要在 \(v\) 处再表演一次，所剩余的钱数就能比 \(g_2\) 多。这是因为，从 \(u\) 到 \(v\) 的路径，到达 \(v\) 点后所有方案所剩的钱数不会超过 \(w_u\)，否则我们可以少表演一次，且有 \(w_u < w_v\)。则 \(g_2 - g_1 < w_u\)，\(w_u < w_v\)，即 \(g_1 + w_v > g_2\)。
综上：演出次数越少，方案越优。如果演出次数相等，则剩余的钱数越多越优。Floyd 预处理最短路然后直接转移即可。时间复杂度 \(\mathcal{O}(n^3)\)，也可以用 \(n\) 次 Dijkstra 做到 \(\mathcal{O}(nm \log n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <LL, int> pi;
#define fi first
#define se second
constexpr int N = 8e2 + 5, M = 3e3 + 5;
int n, m; LL p, w[N], d[N][N], f[N], g[N]; pi a[N];
LL min(LL x, LL y) {
return x < y ? x : y;
}
void upd(int x, LL nf, LL ng) {
if (nf < f[x]) f[x] = nf, g[x] = ng;
else if (nf == f[x] && ng > g[x]) g[x] = ng;
}
void solve() {
cin >> n >> m >> p;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == j) d[i][j] = 0;
else d[i][j] = 1e18;
}
}
for (int i = 1; i <= n; i++) cin >> w[i], a[i].fi = w[i], a[i].se = i;
sort(a + 1, a + n + 1);
for (int i = 1, x, y, z; i <= m; i++) {
cin >> x >> y >> z;
d[x][y] = min(d[x][y], z);
}
for (int k = 1; k <= n; k++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}
}
}
for (int i = 1; i <= n; i++) f[i] = 1e18, g[i] = 0;
f[1] = 0, g[1] = p;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
int x = a[i].se, y = a[j].se;
if (d[x][y] != 1e18 && x != y) {
LL tmpf = f[x], tmpg = g[x];
if (tmpg >= d[x][y]) upd(y, tmpf, tmpg - d[x][y]);
else {
LL dlt = d[x][y] - tmpg;
LL sum = (dlt + w[x] - 1) / w[x];
tmpf += sum, tmpg += sum * w[x];
upd(y, tmpf, tmpg - d[x][y]);
}
}
}
}
if (f[n] <= 3e12) cout << f[n] << "\n";
else cout << "-1\n";
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; cin >> t;
while (t--) solve();
return 0;
}
CF 1801E Gasoline prices
给定一个 \(n\) 个节点的树，每个点上有一个数，取值范围为 \([l_i,r_i]\)。\(q\) 次询问，每次会新增一个限制，每次给出四个整数 \(a,b,c,d\)，保证 \(a\rightarrow b\) 和 \(c\rightarrow d\) 的长度相同，对于每个 \(i\) 要求两条路径上的第 \(i\) 个点的取值相同。每次询问后输出写数字的方案数，对 \(10^9+7\) 取模。\(n,q \leq 2 \times 10^5\)。
其实就是把 P3295 [SCOI2016] 萌萌哒 搬到了树上。
做法一：树链剖分一下，把 DFS 序 reverse 一份拼在后面，这样每次只需要做 \(\mathcal{O}(\log n)\) 次区间合并。考虑将区间 \([l, r]\) 类似 ST 表地拆成两个长为 \(2^t\) 的区间，现在只需要维护长为 \(2\) 的幂的区间合并。
考虑分治，对 \([x,x+2^t-1],[y,y+2^t-1]\) 的合并，若 \(t=0\)，我们在底层并查集上直接合并，否则在 \(t\) 这层操作，如果成功合并，则把操作传到 \((x,y,t-1),(x+2^{t-1},y+2^{t-1},t-1)\) 继续合并即可。总时间复杂度 \(\mathcal{O}((n+q)\log^2n)\)。
做法二：注意到只有 \(\mathcal{O}(n)\) 次有效的合并，只要每一次合并的两个点原来不在一个集合，这部分的复杂度就是正确的。于是我们只要找到 \(a\to b\) 路径上和 \(c\to d\) 路径上第一个不是同一个集合的。并查集用按秩合并就能知道每一个点现在是哪一个集合，找到第一个不同的直接二分+哈希即可。链求和用树状数组，总时间复杂度 \(\mathcal{O}((n+q) \log^2 n)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
constexpr int N = 5e5 + 5, mod = 1e9 + 7;
int n, m, k, l[N], r[N], L[N], R[N], ans = 1;
int t[N][25], par[N], dep[N], sz[N], son[N], dfn[N], tim, top[N];
vector <int> e[N];
int ksm(int a, int b) {
int ret = 1;
for (; b; b >>= 1, a = 1LL * a * a % mod) if (b & 1) ret = 1LL * ret * a % mod;
return ret;
}
void dfs1(int u) {
dep[u] = dep[par[u]] + 1, sz[u] = 1;
for (auto v : e[u]) {
dfs1(v);
sz[u] += sz[v];
if (son[u] == 0 || sz[son[u]] < sz[v]) son[u] = v;
}
}
void dfs2(int u, int tp) {
dfn[u] = ++tim, top[u] = tp;
if (son[u] != 0) {
dfs2(son[u], tp);
for (auto v : e[u]) if (v != son[u]) dfs2(v, v);
}
}
int gf(int x, int k) {
return x == t[x][k] ? x : t[x][k] = gf(t[x][k], k);
}
void merge1(int x, int y, int k) {
int tx = gf(x, k), ty = gf(y, k);
if (tx != ty) {
t[tx][k] = ty;
if (k == 0) {
ans = 1LL * ans * ksm(1LL * max(R[tx] - L[tx] + 1, 0) * max(R[ty] - L[ty] + 1, 0) % mod, mod - 2) % mod;
L[ty] = max(L[ty], L[tx]);
R[ty] = min(R[ty], R[tx]);
ans = 1LL * ans * max(R[ty] - L[ty] + 1, 0) % mod;
} else {
k--;
merge1(x, y, k);
merge1(x + (1 << k), y + (1 << k), k);
}
}
}
void merge2(int x, int y, int k) {
int t = log2(k);
merge1(x, y, t);
merge1(x + k - (1 << t), y + k - (1 << t), t);
}
vector <pi> get_seg(int u, int v, int n) {
int _ = 0;
vector <pi> ret, buk[2];
while (top[u] != top[v]) {
if (dep[top[u]] < dep[top[v]]) {
swap(u, v);
_ ^= 1;
}
buk[_].emplace_back(dfn[top[u]], dfn[u]);
u = par[top[u]];
}
if (dep[u] < dep[v]) {
swap(u, v);
_ ^= 1;
}
buk[_].emplace_back(dfn[v], dfn[u]);
for (int i = 0; i < (int)buk[0].size(); i++) {
ret.emplace_back(n - buk[0][i].second + 1, n - buk[0][i].first + 1);
}
for (int i = (int)buk[1].size() - 1; i >= 0; i--) {
ret.emplace_back(buk[1][i]);
}
return ret;
}
void solve() {
cin >> n, k = n * 2;
for (int i = 1; i <= k; i++) for (int j = 0; j <= log2(k); j++) t[i][j] = i;
for (int i = 2; i <= n; i++) {
cin >> par[i];
e[par[i]].emplace_back(i);
}
dfs1(1), dfs2(1, 1);
for (int i = 1; i <= n; i++) {
cin >> l[i] >> r[i];
ans = 1LL * ans * (r[i] - l[i] + 1) % mod * (r[i] - l[i] + 1) % mod;
}
for (int i = 1; i <= n; i++) {
int t = k - dfn[i] + 1;
L[dfn[i]] = L[t] = l[i];
R[dfn[i]] = R[t] = r[i];
merge1(dfn[i], t, 0);
}
cin >> m;
for (int i = 1, a, b, c, d; i <= m; i++) {
cin >> a >> b >> c >> d;
vector <pi> v1 = get_seg(a, b, k), v2 = get_seg(c, d, k);
while (!v1.empty() && !v2.empty()) {
int len1, len2, len3;
pi &z1 = v1.back(), &z2 = v2.back();
len1 = z1.second - z1.first + 1;
len2 = z2.second - z2.first + 1;
len3 = min(len1, len2);
merge2(z1.second - len3 + 1, z2.second - len3 + 1, len3);
if (len1 == len3) {
v1.pop_back();
} else {
z1.second -= len3;
}
if (len2 == len3) {
v2.pop_back();
} else {
z2.second -= len3;
}
}
cout << ans << "\n";
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) solve();
return 0;
}
CF 1801F Another n-dimensional chocolate bar
给定两个正整数 \(n,k\) 和一个长度为 \(n\) 的正整数序列 \(a\)，你需要找一个一个长度为 \(n\) 的正整数序列 \(b\) 满足 \(\prod\limits_{i=1}^nb_i\geq k\)，求 \(k\times\prod\limits_{i=1}^n\lfloor\dfrac{a_i}{b_i}\rfloor\times\dfrac{1}{a_i}\) 的最大值。
\(n\leq 100\)，\(a_i\leq10^7\)，\(k\leq10^7\)。
考虑 DP，设 \(f_{i,j}\) 表示 \(b_1 \sim b_i\) 已经确定，后面的数的限制为 \(\prod\limits_{p>i}b_p \geq j\) 的前提下，\(\prod\limits_{p=1}^i \lfloor \frac{a_p}{b_p}\rfloor \times \frac{1}{a_p}\) 的最大值。枚举 \(b_i\) 的值 \(x\) 暴力转移，则有 \(f_{i,\lceil \frac{j}{x} \rceil} \gets f_{i-1,j} \times \lfloor \frac{a_p}{x} \rfloor \times \frac{1}{a_p}\)。
考虑怎么优化这个东西，注意到 \(\lceil \frac{k}{a} \rceil= \lfloor \frac{k-1}{a}\rfloor +1\)，且 \(\lceil \frac{\lceil \frac{k}{a} \rceil}{b} \rceil = \lceil \frac{k}{ab} \rceil\)，于是我们可以把上取整变成下取整。
此时对于 \(\lfloor \frac{k}{x} \rfloor\) 相同的 \(x\)，它们本质相同，并且为了最大化 \(\lfloor \frac{a_p}{x} \rfloor\)，我们一定会选择最小的 \(x\) 转移。这样只会有 \(\mathcal{O}(\sqrt k)\) 个有用的位置，提前数论分块预处理出来即可。根据杜教筛的结论，总时间复杂度为 \(\mathcal{O}(nk^{\frac{3}{4}})\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
constexpr int N = 105, M = 7e3 + 5, V = 1e7 + 5;
int n, m, k, a[N], v[M], id[V]; double f[N][M];
void solve() {
cin >> n >> k;
for (int i = 1; i <= n; i++) cin >> a[i];
if (k == 1) {
double ans = 1.0;
cout << fixed << setprecision(20) << ans << "\n";
return;
}
for (int l = 1, r = 0; l <= k - 1; l = r + 1) {
r = (k - 1) / ((k - 1) / l);
v[++m] = (k - 1) / l;
id[v[m]] = m;
}
v[++m] = 0, id[0] = m;
f[0][1] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) if (f[i - 1][j]) {
for (int l = 1, r = 1; l <= v[j]; l = r + 1) {
r = v[j] / (v[j] / l);
f[i][id[v[j] / l]] = max(f[i][id[v[j] / l]], (a[i] / l) / (double)a[i] * f[i - 1][j]);
}
f[i][m] = max(f[i][m], (a[i] / (v[j] + 1)) / (double)a[i] * f[i - 1][j]);
}
}
cout << fixed << setprecision(20) << f[n][m] * k << "\n";
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) solve();
return 0;
}
CF 1801G A task for substrings
给你一个字符串 \(t\) 和 \(n\) 个字符串 \(s_1 \sim s_n\)。\(m\) 个询问，第 \(i\) 个询问给你 \(l_i,r_i\)，统计满足 \(t[a,b]\) 在 \(s_1 \sim s_n\) 中出现过且 \(l_i \leq a \leq b \leq r_i\) 的 \((a,b)\) 的个数。
\(|t| \leq 5 \times 10^6\)，\(n,m \leq 5 \times 10^5\)，\(\sum |s_i| \leq 10^6\)。
相比于区间，我们更喜欢前后缀。如果只要求右端点在区间 \([l,r]\) 内就好了，我们直接 ACAM 预处理出每个前缀的答案，但现实是残酷的。
做法一：考虑先按上面说的做，容斥减掉左端点在 \([1,l-1]\)，右端点在 \([l,r]\) 内的串。对正反串分别建 ACAM，对于每个询问，记录 \([1,l-1]\) 在正 ACAM 上的节点和 \([l,r]\) 在反 ACAM 上的节点，后者需要先处理后缀的节点然后倍增跳祖先。问题转化成：两个节点在对应 ACAM 的 fail 树上的祖先中，有多少对能拼成一个完整的 \(s_i\)，利用数据结构容易做到 \(\mathcal{O}((S+q) \log S + |t|)\)。
做法二：有点人类智慧地，考虑一个不合法的串 \(S[L,R]\)，满足 \(L\in[1,l),R\in[l,r]\)，我们发现结尾在 \([l,R]\) 的合法的串一定是这个串的子串。也就是说，如果我们找到了一个 \(R\) 最大的不合法的串，那么结尾比 \(R\) 大的没有不合法的串，结尾不大于 \(R\) 的都是这个串的子串。更具体地，是这个串一个后缀的子串，对于一个串计算其一个后缀有多少个合法子串是容易的，建反串 ACAM 即可。最大的 \(R\) 可以先在 ACAM 上预处理出以每个位置结尾的最长的合法串，每次询问线段树二分，时间复杂度 \(\mathcal{O}(S + |t| + m \log |t|)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
constexpr int N = 1e6 + 5, M = 5e6 + 5, S = 26;
struct ACAM {
int tot, ch[N][S], fa[N], ed[N], ml[N];
void ins(string s, int id) {
int p = 0;
for (auto c : s) {
if (!ch[p][c - 'a']) ch[p][c - 'a'] = ++tot;
p = ch[p][c - 'a'];
}
ed[p] = 1, ml[p] = id;
}
void build() {
queue <int> q;
for (int i = 0; i < S; i++) if (ch[0][i]) q.push(ch[0][i]);
while (!q.empty()) {
int u = q.front(); q.pop();
ed[u] += ed[fa[u]];
if (!ml[u]) ml[u] = ml[fa[u]];
for (int i = 0; i < S; i++) {
if (ch[u][i]) q.push(ch[u][i]), fa[ch[u][i]] = ch[fa[u]][i];
else ch[u][i] = ch[fa[u]][i];
}
}
}
} tr, rev;
char t[M];
string s[N], rs[N];
int n, m, c, mch[M];
LL pre[M];
vector <LL> f[N];
int val[M << 2];
#define m ((l + r) >> 1)
void build(int x, int l, int r) {
if (l == r) {
if (mch[l]) val[x] = l - s[mch[l]].size();
else val[x] = M;
return;
}
build(x << 1, l, m);
build(x << 1 | 1, m + 1, r);
val[x] = min(val[x << 1], val[x << 1 | 1]);
}
int qry(int x, int l, int r, int ql, int qr, int v) {
if (val[x] >= v) return -1;
if (l == r) return l;
if (m < qr) {
int ret = qry(x << 1 | 1, m + 1, r, ql, qr, v);
if (ret != -1) return ret;
}
if (ql <= m) return qry(x << 1, l, m, ql, qr, v);
return -1;
}
#undef m
void solve() {
cin >> n >> m >> t + 1;
c = strlen(t + 1);
for (int i = 1; i <= n; i++) {
cin >> s[i], tr.ins(s[i], i);
rs[i] = s[i], reverse(rs[i].begin(), rs[i].end()), rev.ins(rs[i], i);
}
tr.build(), rev.build();
int p = 0;
for (int i = 1; i <= c; i++) {
p = tr.ch[p][t[i] - 'a'];
mch[i] = tr.ml[p];
pre[i] = pre[i - 1] + tr.ed[p];
}
for (int i = 1; i <= n; i++) {
f[i].resize(s[i].size());
for (int j = 0, p = 0; j < s[i].size(); j++) {
if (j) f[i][j] = f[i][j - 1];
p = rev.ch[p][rs[i][j] - 'a'], f[i][j] += rev.ed[p];
}
}
build(1, 1, c);
for (int i = 1; i <= m; i++) {
int l, r;
cin >> l >> r;
int p = qry(1, 1, c, l, r, l);
if (p == -1) cout << pre[r] - pre[l - 1] << " ";
else {
int mc = mch[p];
cout << pre[r] - pre[p] + f[mc][p - l] << " ";
}
}
cout << "\n";
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t = 1;
while (t--) solve();
return 0;
}
QOJ 6501 Graph Partitioning
给定一张图，将其划分成两棵有根树，第一棵树每个节点的编号小于父亲的编号，第二棵树每个节点的编号大于父亲的编号，求方案数，对 \(998244353\) 取模。\(n \leq 5 \times 10^5\)。
树可以看成给每个点确定一个父亲，那么原题可以看成给 \([1, n − 1]\) 的每个点找一个更大的父亲，\([2, n]\) 找一个更小的父亲。一条连接 \(x, y(x ≤ y)\) 的边可成为 \(x\) 在第一棵树上到父亲的边，或者成为 \(y\) 在第二棵树上到父亲的边。整个题目可以看成每条边匹配一棵树上的某一个点的问题。
把每个点拆成两个点，分别表示在第一棵树中或第二颗树中。这样总共有 \(2n − 2\) 个需要确定父亲的点，且输入中有 \(2n − 2\) 条边。可以发现有解当且仅当是一个基环树森林，即每一个连通块边数 = 点数，此时的答案为 \(2^C\)。总时间复杂度 \(\mathcal{O}(n)\)。
code
#include <bits/stdc++.h>
using namespace std;
constexpr int N = 1e6 + 5, mod = 998244353;
int n, ans, vis[N], cn, ce;
vector <int> e[N];
void dfs(int u) {
if (vis[u]) return;
vis[u] = true, cn++;
for (int v : e[u]) ce++, dfs(v);
}
int main() {
cin >> n;
ans = 1;
for (int i = 1, x, y; i <= 2 * n - 2; i++) {
cin >> x >> y;
if (x > y) swap(x, y);
e[x + n].push_back(y);
e[y].push_back(x + n);
if (x == y) ans = 0;
}
for (int i = 2; i < 2 * n; i++) if (!vis[i]) {
cn = 0, ce = 0;
dfs(i);
ce /= 2;
if (cn != ce) ans = 0;
ans = 2LL * ans % mod;
}
cout << ans << "\n";
return 0;
}
QOJ 6502 Disjoint Set Union
给定一个路径压缩并查集的起始状态，问是否能到达另一个状态，并构造方案。要求步数不超过 \(2n^2\)。
\(n \leq 1000\)，\(\sum n^2 \leq 5 \times 10^6\)。
先判掉成环或者初始时连通，但最终不连通的情况，这一定无解。
设初始时有 \(k\) 颗树 \(T_1\sim T_k\)，根分别为 \(r_1 \sim r_k\)。假设最终状态只由一颗树构成，考虑由这 \(k\) 个根在最终状态构成的树的结构：如果 \(x\) 是 \(y\) 的父亲，那么必定是某一步 \(y\) 直接合并到 \(x\)。这是因为，find 操作只会将具有祖先后代关系的一组点的祖先后代关系破坏，而不会增加新的祖先后代关系。所以，如果最终时刻有限制 \(x\) 必须是 \(y\) 的祖先，那么在任意时刻该限制都需要满足。
接下来考虑，如果最终某个 \(r_x\) 的子树内存在点 \(u\)，使得 \(u\) 在初始时位于另一棵子树 \(r_y\) 中，那么在某一时刻 \(r_x\) 是 \(r_y\) 的祖先。因此我们可以得到若干形如 \(r_x\) 必须是 \(r_y\) 祖先的限制。如果限制成环，显然无解。否则跑出任意一组拓扑序，按照拓扑序来构造方案。
注意到如果 \(x\) 是根，\(y\) 是 \(x\) 的某一个儿子，\(z\) 是 \(y\) 的某一个儿子，那么我们可以通过操作 \(z\) 来将 \(z\) 所在子树提到 \(x\) 的儿子，而其他结构没有影响。同时，注意到，对于初始时非根节点 \(t\)，\(t\) 与 \(fa\) 在最终具有父子关系，当且仅当 \(t\) 没有被操作过。于是我们可以据此判定是否要在某个时刻操作 \(x\)。因此我们可以知道在初始时需要对哪些点先进行 find，在初始时便进行这样的操作一定是最优的。
因此我们直接按照拓扑序依次复原即可。由于做到一个点时至多进行 \(n\) 次操作，因此操作次数不会超过 \(n^2+n\)。时间复杂度 \(\mathcal{O}(n^2)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef tuple <int, int, int> ti3;
constexpr int N = 1e3 + 5;
int n, f[N], g[N], d[N], pre[N], ed[N], to[N], q[N], c; bool root[N];
vector <int> e[N];
vector <ti3> ns;
int gf(int x) { return x == f[x] ? x : f[x] = gf(f[x]); }
struct dsu {
int t[N];
int gf(int x) { return x == t[x] ? x : t[x] = gf(t[x]); }
} F, G;
void clr() {
ns.clear();
c = 0;
for (int i = 1; i <= n; i++) e[i].clear(), root[i] = d[i] = to[i] = ed[i] = 0;
}
void solve() {
cin >> n;
clr();
for (int i = 1; i <= n; i++) cin >> f[i], F.t[i] = f[i];
for (int i = 1; i <= n; i++) cin >> g[i], G.t[i] = g[i];
for (int i = 1; i <= n; i++) pre[i] = i, root[i] = i == f[i];
for (int i = 1; i <= n; i++) {
if (f[i] != g[i] && root[f[i]] == false) {
gf(i);
ns.emplace_back(1, i, 0);
}
}
for (int i = 1; i <= n; i++) if (f[i] != g[i]) {
if (root[g[i]] == false) {
cout << "NO\n";
return;
}
if (f[g[i]] == g[g[i]]) ed[f[i]] = g[i];
else {
e[f[i]].push_back(g[i]), d[g[i]]++;
}
}
queue <int> que;
for (int i = 1; i <= n; i++)
if (root[i] && f[i] != g[i] && d[i] == 0) que.push(i);
while (!que.empty()) {
int u = que.front(); que.pop();
q[++c] = u;
for (auto v : e[u]) {
if (--d[v] == 0) que.push(v);
}
}
for (int i = 1; i <= n; i++) if (d[i]) {
cout << "NO\n";
return;
}
for (int i = c; i >= 1; i--) {
int u = q[i];
for (auto v : e[u]) ed[u] = ed[v];
to[u] = pre[ed[u]], pre[ed[u]] = u;
}
for (int i = 1; i <= c; i++) {
int u = q[i];
f[u] = to[u];
ns.emplace_back(2, u, to[u]);
for (int j = 1; j <= n; j++) if (f[j] != g[j] && f[j] == u) {
gf(j);
ns.emplace_back(1, j, 0);
}
}
for (int i = 1; i <= n; i++) {
for (int j = i + 1; j <= n; j++) {
if (F.gf(i) == F.gf(j) && G.gf(i) != G.gf(j)) {
cout << "NO\n";
return;
}
}
}
cout << "YES\n";
cout << (int)ns.size() << "\n";
for (auto [ty, x, y] : ns) {
if (ty == 1) {
cout << 1 << " " << x << "\n";
} else {
cout << 2 << " " << x << " " << y << "\n";
}
}
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; cin >> t;
while (t--) solve();
return 0;
}
QOJ 6503 DFS Order 3
给定一棵树中以每个点为起点的 DFS 序，复原这棵树。\(n \leq 1000\)，\(\sum n^2 \leq 2 \times 10^6\)。
注意到，DFS 序中最后一个点一定是叶子节点，且 DFS 序中第二个点一定与第一个点直接相邻。于是我们不停的删除叶子节点，删叶子的时候找它的父亲即可。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef pair <int, int> pi;
constexpr int N = 1e3 + 5;
int n, a[N][N], vis[N], hd[N];
vector <pi> ns;
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) for (int j = 1; j <= n; j++) cin >> a[i][j];
ns.clear();
for (int i = 1; i <= n; i++) vis[i] = 0, hd[i] = 2;
for (int j = n; j >= 2; j--) {
for (int i = 1; i <= n; i++) if (vis[a[i][j]] == false) {
vis[a[i][j]] = true;
int x = a[i][j];
while (hd[x] < n && vis[a[x][hd[x]]]) hd[x]++;
if (vis[a[x][hd[x]]] == false)
ns.emplace_back(x, a[x][hd[x]]);
}
}
for (auto [x, y] : ns) cout << x << " " << y << "\n";
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; cin >> t;
while (t--) solve();
return 0;
}
QOJ 6504 Flower's Land 2
维护一个 \(012\) 串 \(s\)，支持区间加 \(1\) 模 \(3\)，或区间询问能否通过删除两个相邻相等元素删成空串。\(n,q \leq 5 \times 10^5\)。
神秘题。构造三个随机可逆矩阵 \(M_0, M_1, M_2\)。对于每个 \(i\)，如果 \(i \bmod 2 = 0\)，则令 \(A_i = M_{s_i}\)，否则 \(A_i = M^{−1}_{s_i}\)。一个区间可以消空当且仅当 \(\prod\limits_{i=l}^r A_i = I\)。用线段树树维护区间加 \(1\) 模 \(3\) 与区间矩阵乘积，时间复杂度 \(\mathcal{O}(n \log n \times k^3)\)，其中 \(k\) 是矩阵大小，实战取 \(k=2\) 就够了。
code
#include <bits/stdc++.h>
typedef long long LL;
using namespace std;
constexpr int N = 5e5 + 5, mod = 998244353;
int ksm(int a, int b) {
int ret = 1;
for (; b; b >>= 1, a = 1LL * a * a % mod) if (b & 1) ret = 1LL * ret * a % mod;
return ret;
}
int n, q; string str;
struct Mat {
LL a[2][2];
Mat operator ~() {
Mat z;
LL det = (1LL * a[0][0] * a[1][1] % mod + mod - 1LL * a[0][1] * a[1][0] % mod) % mod, inv = ksm(det, mod - 2);
z.a[0][0] = 1LL * a[1][1] * inv % mod;
z.a[1][1] = 1LL * a[0][0] * inv % mod;
z.a[0][1] = 1LL * (mod - a[0][1]) * inv % mod;
z.a[1][0] = 1LL * (mod - a[1][0]) * inv % mod;
return z;
}
Mat operator * (const Mat &y) {
Mat z;
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
z.a[i][j] = 0;
for (int k = 0; k < 2; k++) z.a[i][j] += 1LL * a[i][k] * y.a[k][j];
z.a[i][j] %= mod;
}
}
return z;
}
bool isI() {
return a[0][0] == 1 && a[0][1] == 0 && a[1][0] == 0 && a[1][1] == 1;
}
} M[10];
struct SGT {
int tg[N << 2];
Mat val[N << 2][3];
#define m ((l + r) >> 1)
void push_up(int x) {
for (int i = 0; i < 3; i++) val[x][i] = val[x << 1][i] * val[x << 1 | 1][i];
}
void ptag(int x, int v) {
tg[x] = (tg[x] + v) % 3, rotate(val[x], val[x] + v, val[x] + 3);
}
void push_down(int x) {
if (tg[x]) ptag(x << 1, tg[x]), ptag(x << 1 | 1, tg[x]), tg[x] = 0;
}
void build(int x, int l, int r) {
if (l == r) {
if (l % 2 == 0) {
val[x][0] = M[str[l] - '0'];
val[x][1] = M[(str[l] - '0' + 1) % 3];
val[x][2] = M[(str[l] - '0' + 2) % 3];
} else {
val[x][0] = M[str[l] - '0' + 3];
val[x][1] = M[(str[l] - '0' + 1) % 3 + 3];
val[x][2] = M[(str[l] - '0' + 2) % 3 + 3];
}
return;
}
build(x << 1, l, m), build(x << 1 | 1, m + 1, r);
push_up(x);
}
void mdf(int x, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) return ptag(x, 1);
push_down(x);
if (ql <= m) mdf(x << 1, l, m, ql, qr);
if (qr > m) mdf(x << 1 | 1, m + 1, r, ql, qr);
push_up(x);
}
Mat qry(int x, int l, int r, int ql, int qr) {
if (ql <= l && qr >= r) return val[x][0];
push_down(x);
if (qr <= m) return qry(x << 1, l, m, ql, qr);
if (ql > m) return qry(x << 1 | 1, m + 1, r, ql, qr);
return qry(x << 1, l, m, ql, qr) * qry(x << 1 | 1, m + 1, r, ql, qr);
}
#undef m
} t;
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
srand(time(NULL));
cin >> n >> q >> str;
str = ' ' + str;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 2; j++) {
for (int k = 0; k < 2; k++) {
M[i].a[j][k] = rand() % mod;
}
}
M[i + 3] = ~M[i];
}
t.build(1, 1, n);
while (q--) {
int ty, l, r;
cin >> ty >> l >> r;
if (ty == 1) {
t.mdf(1, 1, n, l, r);
} else {
Mat Z = t.qry(1, 1, n, l, r);
if (Z.isI()) cout << "Yes\n";
else cout << "No\n";
}
}
return 0;
}