2024西安铁一中集训DAY28 ---- 模拟赛（简单dp + 堆，模拟 + 点分治 + 神秘dp）

前言

T2好难，T4好难。T3写的好粪，T1好水。。

时间安排及成绩

• 7:40 开题。看题目说明好像有很签到的题？
• 7:40 - 7:45 T1看完了，为啥感觉有点难？？难道是容斥？但是数据规模也不可能啊。旁边有人叫T1真的水。就我秒不掉吗？
• 7:45 - 8:05 秉着T1就是签到题的想法，继续想T1。发现不用关心具体填什么数，只需保证相对关系逆序对数就不会变。所以直接暴力dp好像就做完了。写完一边过了所有样例。
• 8:05 - 8:10 看T2，woc这T2啥东西啊。看着像贪心，又好像模拟。但是这数据规模为啥这么逆天？？而且每个点都有牛好像不好搞。
• 8:10 - 8:50 又想了40minT2，还是只会20pts暴力。特殊性质都不知道该咋写。只好先放弃了。
• 8:50 - 8:55 T3题看懂了，就是树上每个节点都有一个括号，求树上一条路径，使括号匹配合法并且嵌套数最大。$n$ 的范围为啥是 $5\times 10^4$。难道要上根号或者 $log$ 特别多？？
• 8:55 - 9:30 太饿了，好像没啥劲思考。感觉只会 $n^2$ 的暴力。特殊性质最开始以为是菊花，后来发现还有可能是链或者蒲公英。那写起来就太粪了啊。。。
• 9:30 - 10:10 吃了个面包，然后嫌教室太吵了，出去想。想到了可以点分治。然后考虑怎样合并两条链。显然需要维护倒着看和正着看两种链，还要维护前缀最大值，最小值啥的。然后好像就可以单 $log$ ？？那这数据范围？？一度以为自己假了，后来想想感觉没啥问题。就回去写了。
• 10:10 - 11:10 写了好长时间，中间忘了点分治的板子了，还回去重新看了看。然后写的很丑，但是感觉思路很清晰。写完自信测样例。卧槽怎么都输出 $0$ 啊。打表发现我分治的根从第二次开始就都是 $0$，好逆天。
• 11: 10 - 11：30 终于看出了是我的变量重名了。改完之后每次分治的根不是 $0$ 了，但是输出还是不对。后来发现每次合并是左边链不能从根开始。改完之后怎么还不对？？推一下样例发现从子树到根的路径算错了。然后特殊处理了一下这样的路径就把样例都过了。
• 11:30 - 11:45 线上评测一下。woc，全部MLE了。但是数组只开到了 $5e4$ 啊，怎么会MLE？？后来尝试把代码注释一部分，一点一点找把哪里加上就会MLE。最后发现 void 函数打成了 int，没有返回值。然后就寄了？？！！
• 11:45 - 11:53 火速把T2暴力写了，一开始还一直错。后来发现没开long long。
• 11:53 - 12:00 尝试写T4 20分，但是由于题目看不懂失败了。。

估分：100 + 20 + 100 + 0 = 220
分数：100 + 20 + 100 + 0 = 220
rk6

点评为没挂分。。

题解

A. 江桥不会做的签到题（简单dp）

分析：

签到题。

设 $d{p}_{i,j}$ 表示前 $i$ 个位置，填 $1\sim i$，形成了 $j$ 个逆序对的方案数。注意这里的 $1\sim i$ 可以理解为 具有相对大小的 $i$ 个数字。

然后转移可以枚举第 $i$ 位填的是 相对顺序中第几的数字：

$d{p}_{i,j}={\sum }_{k=max(0,j-i+1)}^{j}d{p}_{i-1,k}$

前缀和随便优化一下。每个限制就是保留一个状态的方案数，其他状态赋值为 $0$。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 5010;
typedef long long LL;
const LL mod = 1e9 + 7;
LL f[N][N], S[N]; // f[i][j] 表示前i个逆序对数为j的方案数 
int n, m;
struct limit {int p, c;
}l[N];
bool cmp(limit x, limit y) {return x.p < y.p;
}
int main() {scanf("%d%d", &n, &m);for(int i = 1; i <= m; i ++ ) {scanf("%d%d", &l[i].p, &l[i].c);}sort(l + 1, l + m + 1, cmp);int k = 1;f[0][0] = 1LL; for(int i = 1; i <= n; i ++ ) {for(int j = 0; j <= 5000; j ++ ) {if(j == 0) S[j] = f[i - 1][j];else S[j] = (S[j - 1] + f[i - 1][j]) % mod;}for(int j = 0; j <= 5000; j ++ ) {f[i][j] = ((S[j] - (j - (i - 1) > 0 ? S[j - (i - 1) - 1] : 0LL)) % mod + mod) % mod;}if(k <= m && i == l[k].p) {for(int j = 0; j <= 5000; j ++ ) {if(j != l[k].c) f[i][j] = 0;}k ++;}}printf("%lld\n", f[n][l[m].c]); return 0;
}

B. 江桥树上逃（堆，模拟）

原题链接

分析：

感觉这题好难。。。

直接说正解：

首先有一个贪心的性质：如果一个点内还有人，并且它的父边流量还没满，那么把这条边流满肯定更优。也就是说一条边能够流满我们就让它流满。

然后我们假设当前是所有边都流满的状态，设为 $G_0$。那么这样的状态会在某个时刻发生改变，这是由于 某个点 $x$ 的流入量小于流出量，那么会在每秒流出时消耗它自己点内的人，直到点内的人都流走。这时这个点的父边就没办法流满了，这个点相当于变成了一个 中继站，由儿子流入的量会直接从父边流出，并且父边流不满。那么 $x$ 就是无用的，我们考虑这时 将 $x$ 和它的父亲合并成一个点。

也就是说边的流量集 $G$ 会发生变化，由 $G_0$ 变为 $G_1$，然后再由 $G_1$ 变成 $G_2$ 等。这样的变化是由于一个点内原来的人全部净流出去的结果，所以这样的变化应当不超过 $n$ 次。或者由于每次变化后我们都把两个点合成一个点，因此合并次数不会超过 $n$ 次。

那么我们考虑按照 时间顺序 维护这样的变化。对于一个点，记一个 $pas{s}_i$ 表示 $i$ 号点当前的 净流出量。那么 $pas{s}_i$ 的计算方式就是父边的流量减去儿子边的流量和。如果当前 $i$ 号点的人数为 $c_i$，那么前 $\lfloor \frac{c_i}{pas{s}_i}\rfloor$ 时刻显然 $i$ 号点都 有能力让父边满流。如果超出了这个时间，就可以把 $i$ 和 $f{a}_i$ 合成一个点。合并关系可以用 并查集 维护。

我们考虑把二元组 $(i$ ， $\lfloor \frac{c_i}{pas{s}_i}\rfloor )$ 插入堆中，堆里把 $\lfloor \frac{c_i}{pas{s}_i}\rfloor$ 小的放在堆顶。然后把询问按照时间顺序由小到大排序，用一个指针维护处理到哪一个询问了。

1. 拿出栈顶二元组，如果当前询问时间小于等于栈顶时间，那么这个询问的答案就是 $c_1-pas{s}_1\times t_i$。 $t_i$ 表示询问的时间。减号是由于 $pas{s}_i$ 等于 流出量减去流入量，那么 $-pas{s}_1$ 就表示流入量。
2. 如果当前询问时间大于栈顶时间，那么我们需要检验栈顶的节点 $x$ 是否已经合并过，即 $Find(i)$ 是否等于 $i$。如果合并过那么这个状态不能用，否则需要把 $i$ 合并到 $Find(f{a}_i)$ 的点集中。记 $Find(f{a}_i)$ 为 $Fa$，合并方法是让 $pas{s}_{Fa}$ 加上 $pas{s}_i$，让 $c_{Fa}$ 加上 $c_i$。($pas{s}_{Fa}$ 中减去了 $i$ 到父亲的流量，$pas{s}_i$ 中加上了 $i$ 到父亲的流量，正负抵消)。这个合并可以理解为 这个时刻之后 可以把 初始状态 看作 $x$ 和它的父亲缩成了一个点，它们两个之间的边不用管，这个点初始的人的数量就是 $c_i+c_{Fa}$。然后这个点的 净流量 就是 $pas{s}_x+pas{s}_{Fa}$。然后这个点能保持父边满流的时间就是 $\lfloor \frac{c_x+c_{Fa}}{pas{s}_x+pas{s}_{Fa}}\rfloor$。这样在上面算答案时 $c_1-pas{s}_1\times t_i$ 就可以对应成 点 $1$ 初始人数为 $c_1$，保持净流入量是 $-pas{s}_1$，持续了 $t$ 时刻 后点内的人数。

时间复杂度 $O(n\times lo{g}_{2}n)$。
代码不长。
CODE：

// 首先有一个贪心：能满流就让满流，这样一定不劣
// 考虑如果t时间内都是以 flow 的流量流入，那么t时间后这个点的人数就是 t * flow
// 但是一条边不可能一直满流，边的流量情况会出现变化，这个变化是由于某个点里的人为了让它的父边满流因此是负收入，在某一个时刻原来这个点里的人消耗完了
// 那么开一个堆维护这些变化时刻。如果一个点原来的人走完了，那么它实际上就是一个中继点，可以直接把它和它的父亲合并 
#include<bits/stdc++.h>  
using namespace std;
const int N = 1e5 + 10;
typedef long long LL;
int n, qc, fa[N], bin[N];
LL c[N], m[N], pass[N], ans[N], sum;
struct node {LL tim; int x;friend bool operator < (node a, node b) {return a.tim > b.tim;}
};
priority_queue< node > q;
struct Q {int t, idx;
}qq[N];
bool cmp(Q a, Q b) {return a.t < b.t;
}
int Find(int x) {return x == bin[x] ? x : bin[x] = Find(bin[x]);}
int main() {scanf("%d%d", &n, &qc);for(int i = 2; i <= n; i ++ ) {scanf("%d%lld%lld", &fa[i], &c[i], &m[i]);pass[i] += m[i], pass[fa[i]] -= m[i];sum += c[i];}for(int i = 1; i <= n; i ++ ) bin[i] = i;for(int i = 1; i <= qc; i ++ ) {scanf("%d", &qq[i].t);qq[i].idx = i;}for(int i = 1; i <= n; i ++ ) {if(pass[i] > 0) q.push((node) {c[i] / pass[i], i});}sort(qq + 1, qq + qc + 1, cmp);int p = 1;while(!q.empty() && p <= qc) {node Tp = q.top(); q.pop();LL tim = Tp.tim; int x = Tp.x;while(p <= qc && qq[p].t <= tim) {ans[qq[p].idx] = c[1] - pass[1] * (1LL * qq[p].t);p ++;}if(Find(x) != x) continue; //刚才被合并过了，那么这个状态不能用 // 可以合并 int Fa = Find(fa[x]); // 找到父亲所在的那个节点 pass[Fa] += pass[x]; c[Fa] += c[x]; bin[x] = Fa;if(pass[Fa] > 0) q.push((node) {c[Fa] / pass[Fa], Fa});}for(int i = p; i <= qc; i ++ ) {ans[qq[i].idx] = sum; // 合成1个点了 }for(int i = 1; i <= qc; i ++ ) printf("%lld\n", ans[i]); return 0;
}

总结：这类 把节点合并 来 简化状态 或者 减少决策 的思路还要多学习。

C. 括号平衡路径（点分治）

原题链接

分析：

感觉遇到这种 求所有路径中最优值 的题都可以往点分治上想。

对于当前根，考虑如何在 $O(子树大小)$ 的复杂度内求出所有 经过根 的路径的最优值。

还是按照点分治的套路，我们考虑 把两条在不同子树的路径 合起来。我们把左括号看作 $1$，右括号看作 $-1$。同时对于一个点 $x$ 到当前根 $rt$，维护这条路径 从 $x$ 往 $rt$ 看 的前缀最小值 $m{n}_1[x]$，前缀最大值 $m{x}_1[x]$ 以及 从 $rt$ 往 $x$看 的前缀最小值 $m{n}_2[x]$，前缀最大值 $m{x}_2[x]$。还需要维护 $x$ 到 $rt$ 的路径和 $s_x$。那么两条路径 $x\to rt$， $rt\to y$ 能够合并需要满足以下条件：

1. $s_x+s_y=0$
2. $m{n}_1[x]\ge 0$ 且 $s_x+m{n}_2[y]\ge 0$

如果满足，答案合并后的路径对答案的贡献就是 $max(m{x}_1[x],s_x+m{x}_2[y])$。

可以维护一个桶 $val$， $va{l}_i$ 表示已经加入的路劲中 $s_x=i$ 且满足 $m{n}_1[x]$ 的最大的 $m{x}_1[x]$。然后对一条路径 $rt\to y$ 找最优值就是查询 $va{l}_{-s_y}$。

注意：

1. 由于后加入的路径与前面的路径合并时只能作为后半段，但是实际上它还可以作为前半段，因此需要 正着做一遍，倒着做一遍。
2. 由于两条路径合并时不能都含根节点，因此可以让加入的路径含根节点，查询的路径不含根节点。这是一个边界的细节。

复杂度 $O(n\times lo{g}_{2}n)$

CODE：

#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N = 5e4 + 10;
const int INF = 2e6;
int n, fa, a[N], ans, res, root;
int val[N * 2]; // val[i + n]维护的是 sum = val[i + n] 的链，mx的最大值
int mx1[N], mx2[N], mn1[N], mn2[N], s[N]; // 分别表示倒着看的最大值，正着看的最大值，倒着看的最小值，正着看的最小值，和 
bool vis[N];
int sz[N], all, Maxn[N];
char ch[N];
vector< int > E[N];
void getrt(int x, int fa) {sz[x] = 1; Maxn[x] = 0;for(auto v : E[x]) {if(v == fa || vis[v]) continue;getrt(v, x);Maxn[x] = max(Maxn[x], sz[v]);sz[x] += sz[v];}Maxn[x] = max(Maxn[x], all - sz[x]);if(Maxn[x] < Maxn[root]) root = x;
}
void getsz(int x, int fa) {sz[x] = 1;for(auto v : E[x]) {if(v == fa || vis[v]) continue;getsz(v, x);sz[x] += sz[v];}
}
void add(int x) { // 加入 x 作为 倒着 if(mn1[x] >= 0) { // 大于0才加入 val[s[x] + n] = max(val[s[x] + n], mx1[x]);}
}
void del(int x) { // 删去 x 作为 倒着 val[s[x] + n] = -INF;
}
void ask(int x) { // x 为正 if(val[n - s[x]] >= 0 && (-s[x] + mn2[x] >= 0)) { // 存在 res = max(res, max(val[n - s[x]], -s[x] + mx2[x]));}
}
void calc(int x, int fa) { // x子树里作为正着 if(x == fa) {s[x] = mx2[x] = mn2[x] = a[x];}else {	s[x] = s[fa] + a[x];mx2[x] = max(mx2[fa], s[x]);mn2[x] = min(mn2[fa], s[x]);}ask(x);for(auto v : E[x]) {if(v == fa || vis[v]) continue;calc(v, x);}
}
void ins(int x, int fa) { // 插入x子树作为倒着 s[x] = s[fa] + a[x];mx1[x] = max(mx1[fa] + a[x], a[x]);mn1[x] = min(mn1[fa] + a[x], a[x]);if(s[x] == 0 && mn1[x] >= 0) res = max(res, mx1[x]);add(x);for(auto v : E[x]) {if(v == fa || vis[v]) continue;ins(v, x);}
}
void Clear(int x, int fa) {del(x);for(auto v : E[x]) {if(v == fa || vis[v]) continue;Clear(v, x);}
}
void query(int x, int fa) {s[x] = s[fa] + a[x];mx2[x] = max(mx2[fa], s[x]);mn2[x] = min(mn2[fa], s[x]);if(s[x] == 0 && mn2[x] >= 0) res = max(res, mx2[x]);for(auto v : E[x]) {if(v == fa || vis[v]) continue;query(v, x);} 
}
void sol(int rt) { // 以 rt 为根   1是倒着， 2是正着  拿正着和倒着匹配 vis[rt] = 1;mx1[rt] = mn1[rt] = s[rt] = a[rt];mx2[rt] = mn2[rt] = a[rt];add(rt); // 加入根 for(int i = 0; i < E[rt].size(); i ++ ) {int v = E[rt][i];if(vis[v]) continue;calc(v, v); // 解决v子树里的答案 ins(v, rt); // 加入 }for(int i = 0; i < E[rt].size(); i ++ ) { int v = E[rt][i];if(vis[v]) continue;Clear(v, rt); // 把它们的答案删去 }del(rt);for(int i = E[rt].size() - 1; i >= 0; i -- ) { // 倒着做一边 int v = E[rt][i];if(vis[v]) continue;calc(v, v);ins(v, rt);}for(auto v : E[rt]) {if(vis[v]) continue;query(v, rt); // 光处理根 }for(int i = 0; i < E[rt].size(); i ++ ) {int v = E[rt][i];if(vis[v]) continue;Clear(v, rt);}for(auto v : E[rt]) {if(vis[v]) continue;root = 0; all = sz[v];getrt(v, rt);getsz(root, 0);sol(root);}
}
void solve2() {all = n; root = 0; Maxn[0] = INF;getrt(1, 0);getsz(root, 0);sol(root);printf("%d\n", res);
}
int main() {for(int i = 0; i < N * 2; i ++ ) val[i] = -INF;scanf("%d", &n);for(int i = 2; i <= n; i ++ ) {scanf("%d", &fa);E[i].pb(fa); E[fa].pb(i);}for(int i = 1; i <= n; i ++ ) {scanf("\n%c", &ch[i]);if(ch[i] == '(') a[i] = 1;else a[i] = -1;} solve2();return 0;
}

D. 回到起始顺序（dp，组合数学）

原题链接

分析：

感觉是有很多trick结合的题。

实际上是问你所有 $n!$ 个 $1\sim n$ 的排列的权值的 乘积。一个排列的权值和计算方式：把 $i$ 往 $a_i$ 连一条有向边，所有点的出度为 $1$，入度为 $1$，形成了若干置换环。这个排列的权值就是 所有环大小的 $lcm$。

分析：

由于 $lcm$ 可能比较大，因此直接求某种 $lcm$ 对应的排列数不现实。我们考虑 每种质因数 的贡献。

设 $f_x$ 表示 $lcm$ 是 $x$ 的倍数的排列数。那么答案就是

${\prod }_{p^c\le n}{p}^{f_{p^c}}$（$p$ 为质数）

考虑一个排列的 $lcm$ 如果包含 $p^c$，那么这一部分贡献将会在 $p^{f_p}$，$p^{f_{p^2}}$,…, $p^{f_{p^c}}$ 分别被计算一次。那么总共会被计算 $c$，贡献不会少。 $p^c\le n$ 是因为一个 $lcm$ 中包含某个质因数 $p$ 的幂一定小于等于 $n$（任何一个环的长度都小于等于$n$，因此环长质因数分解后 $p$ 的幂肯定小于等于 $n$。那么 $lcm$ 中包含 $p$ 的幂一定也小于等于 $n$）。

考虑怎样求 $f_x$。我们发现如果 $x$ 是某个质数的幂，那么还有一个好处：满足 $lcm$ 是 $x$ 的倍数的排列一定至少存在一个置换环的长度是 $x$ 的倍数。这个性质很好想： $lcm$ 是每个环长质因数分解后每种质因数取幂次最大的那个。那么一定存在一个环长的质因数的幂次大于等于 $x$ 的幂次。这个环长就是 $x$ 的倍数。

我们考虑枚举 $x$，然后 $dp$：
设 $f_i$ 表示长度为 $i$ 的排列，满足所有置换环的长度都是 $x$ 的倍数的排列数。
$g_i$ 表示长度为 $i$ 的排列，没有一个置换环 的长度是 $x$ 的倍数的方案数。

那么有转移：

$f_i={\sum }_{j\le i,x|j}{C}_{i-1}^{j-1}\times f_{i-j}\times (j-1)!$
$g_i=i!-{\sum }_{j\le i,x|j}{C}_i^j\times f_j\times g_{i-j}$

最后 $n!-g_n$ 就是 $lcm$ 是 $x$ 的倍数的排列数。

$f_i$ 的转移可以理解为枚举 $1$ 号位置所在的置换环大小 $j$，然后这个置换环的其它位置需要在 $i-1$ 个位置里面选 $j-1$ 个，还要乘一个圆排列 $(j-1)!$ 表示这个环内的顺序。剩下 $i-j$ 个位置要接着划分为若干个大小是 $x$ 的倍数的置换环。

$g_i$ 的转移是一个容斥：总的排列数减去存在某些环的长度是 $x$ 的倍数的排列数。枚举这些长度是 $x$ 的倍数的置换环的总长度 $j$，这一部分的方案是 $f_j$，然后剩下 $i-j$ 个位置需要划分成长度都不是 $x$ 的倍数的环，方案是 $g_{i-j}$，最后还要乘上 $C_i^j$ 表示在 $i$ 个位置里选 $j$ 个位置去构建长度是 $x$ 的倍数的置换环。

还要注意一下由于求出的排列数要作为指数去算答案，因此它的计算过程中模数应该为 $mod-1$。这个数不一定是质数，因此需要避免逆元。上面的过程中组合数可以预处理求。

然后直接暴力 dp 复杂度是 $O(n^2\times lo{g}_{2}n)$ 的：
枚举 $x$ 是 $n$，枚举排列的长度 $i$ 加上转移是 ${\sum }_{i=1}^n\frac{i}{x}\le n\times \frac{n}{x}$。那么总复杂度是 ${\sum }_{x=1}^{n}n\times \frac{n}{x}=n\times {\sum }_{x=1}^n\frac{n}{x}=n^2\times lo{g}_{2}n$。

但是根据转移方程式我们发现：$f_i$ 的转移中只有 $i\equiv 0(modx)$ 的状态有用， $g_i$ 的转移中只有 $i\equiv n(modx)$ 的状态有用。因此不用全部转移，只需要转移 $\frac{n}{x}$ 个状态。每个状态转移 $\frac{n}{x}$ 次。

复杂度就是 ${\sum }_{x=1}^n\frac{n}{x}\times \frac{n}{x}={\sum }_{x=1}^n\frac{n^2}{x^2}\approx n^2$。

这个约等于可以让电脑打表输出一下，发现确实不会超过两倍。

CODE：

#include<bits/stdc++.h>
using namespace std;
const int N = 7550;
typedef long long LL;
bool vis[N];
int n;
LL m1, m2, c[N][N], f[N], g[N]; // f[i], g[i] 分别表示长度为i的置换所有环的长度都是x的倍数，所有环的长度都不是x的倍数的排列数 
LL res = 1LL, fac[N];
inline LL Pow(LL x, LL y, LL mod) {LL res = 1LL, k = x % mod;while(y) {if(y & 1) res = (res * k) % mod;y >>= 1;k = (k * k) % mod;}return res;
}
int main() {cin >> n >> m1;m2 = m1 - 1;for(int i = 0; i < N; i ++ ) for(int j = 0; j <= i; j ++ ) {if(!j) c[i][j] = 1LL;else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % m2;}fac[0] = 1LL;for(int i = 1; i < N; i ++ ) fac[i] = fac[i - 1] * (1LL * i) % m2;for(int i = 2; i <= n; i ++ ) {if(!vis[i]) {for(int j = i; j * i <= n; j ++ ) {vis[i * j] = 1;}}}for(int i = 2; i <= n; i ++ ) {if(vis[i]) continue;else { // 质数 int x = i; LL p = 1LL * i, cnt = 0; while(x <= n) { // 计算答案 g[0] = f[0] = 1LL;for(int j = 1; j <= n; j ++ ) {g[j] = f[j] = 0;if(j % x == 0 % x) { // 转移 f for(int k = x; k <= j; k += x) f[j] = (f[j] + f[j - k] * c[j - 1][k - 1] % m2 * fac[k - 1] % m2) % m2;}if(j % x == n % x) { // 转移 g g[j] = fac[j];for(int k = x; k <= j; k += x) g[j] = ((g[j] - g[j - k] * f[k] % m2 * c[j][k] % m2) % m2 + m2) % m2;}}cnt = (cnt + ((fac[n] - g[n]) % m2 + m2) % m2) % m2;x = x * p;}res = (res * Pow(p, cnt, m1)) % m1;}}printf("%lld\n", res);return 0;
}