南外集训
NOIP模拟赛44
A. K 近查询
给定序列 $a_n$, 对每个 $k\le lim$ 求 $j$ 使得 $j$ 是 $j < i, a_j\ge a_i$ 中第 $k$ 大的.
$n\le 10^7, lim=1$ 或 $n\le 3\times 10^6, lim=5$
简单题, 对 $10^7$ 的部分直接单调栈, 对 $lim=5$ 的部分建出链表, 然后从小到大删元素并统计答案.
B. 树上流水
给一棵 $n$ 个点的外向树, 根有无限水, 边有容量限制, 每秒可以把水延边推动, 求最少几秒使得叶子处总水量至少为 $K$.
$K\le 10^9$, $n\le 1000$
容易想到dp, 设 $f_{u, i}$ 表示点 $u$ 发出 $fw_u=w_{fa_u\to u}$ 的流量在 $i$ 秒后最多有多少到叶子, 转移大概是 $f_{u, i}=\min (\sum f_{v, i}, fw_u)$, 然后求出 $1$ 的就可以算答案了.
然而赛时一开始没看到 $n\le 1000$(它写 $\sum n\le 5\times 10^4$), 所以可以写线段树合并加速转移. 或者动态dp每次删最底下的东西, 或者可并堆, 都能做到单log.
当然也容易想到贪心, 因为你一定优先流深度低的叶子.
C. 逆序对
给定一长为 $2^n$ 的序列 $p_1, p_2, . . . , p_{2^n}$, $m$ 次操作, 每次操作给出三个整数 $q_i$, $l_i$, $r_i$, 然后对序列作如下变换:
- 将序列分为 $2^{q_i}$ 个大小为 $2^{n-q_i}$ 的块.
- 选择第 $l_i$ 到第 $r_i$ 个块.
每次操作后, 输出整个序列的逆序对数.
直接线段树维护就行了. 建线段树后, 每个点记录 $w_x$ 为左儿子对右儿子的逆序对数, 发现翻转这个节点(交换左右子树, 子树内不变)只影响本节点的 $w$ 且可以预处理, 而题目所要求的翻转一个区间就是翻转区间对应节点的所有子树. 于是要打懒标记, 记录 $s_x$ 表示 $x$ 子树中集合 $s$ 中的层都要翻转, $c_{x, i}$ 表示 $x$ 子树中深度为 $i$ 的那层节点翻转后的 $w$ 减去翻转前的 $w$ 就做完了就能合并标记和处理变化了. 复杂度2log.
D. 净土裁断
在一棵 $n$ 点树上随机游走, 在点 $u$ 有 $p_u$ 概率停留 $1s$, 有 $1-p_u$ 概率等概率走到相邻一点, 走到 $1$ 停止, 求每个点走到 $1$ 的步数的 $k$ 次方的期望.
$n\le 10^5, k\le 10^3$
先考虑 $k=1$ 怎么做, 那么
$$
f_u=p_u(f_u+1)+(1-p_u)\sum_{u\to v}(f_v+1)
$$
然后这个有后效性, 学到一个树上高消: 依赖关系成树之后叶子的式子可以写成 $f_u=a_uf_{fa}+b_u$, 然后把这个式子带入父亲的式子就消掉自己, 于是父亲最后也表示成关于爷爷的一次函数, 以此类推, 最后推到根, 再用根的值算出整棵树的dp值.
遇到 $k$ 次方常见套路是EGF和斯特林数.
斯特林数, 则 $x^k=\sum_{i=0} \binom{n}{i}{k\brace i}i!$, 于是要算 $\sum \binom{l}{i}$, 于是
$$
f_{u, k}=p_u(f_{u, k}+f_{u, k-1})+(1-p_u)\sum_{u\to v}(f_{v, k}+f_{v, k-1})
$$
于是仍然套刚才的树上高消, 复杂度 $nk+k^2$
假设我们一开始选择EGF, 则设 $F_u(x)$ 表示 $\sum_{l\in S} p_le^{xl}$, 其中 $S$ 是所有方案下到根步数的多重集, 那么列出 $F_u(x)=p_ue^xF_u(x)+\sum_{u\to v}(1-p_u)e^xF_v(x), F(1)=1$ 并仍然套用刚才树上高消的转移, 这个转移不动因为卷 $e^x$ 复杂度是 $k\log k$ 的, 考虑换元 $t=e^x$ 则 $F_u(t)=p_utF_u(t)+\sum_{u\to v}(1-p_u)tF_v(t)$, 此时卷上单个 $t$ 复杂度就 $O(k)$ 了.
USACO 2018 铂金
A. Balance Beam
想到dp $dp_i=\max (f_i, \dfrac{1}{2}(dp_{i-1}+dp_{i+1}))$, 但这个转移不了.
考虑一些点 $dp_i=f_i$, 那么这些点就把序列分成若干段, 每一段内的点的dp值就由两边的断点决定. 而发现走到左右断点中的哪一个的概率是能求的: 和距离成正比.
然后最厉害的地方在于, 考虑把它们以 $i$ 为横坐标, $f$ 为纵坐标画到平面上, 则中间的点就是断点连线在这个横坐标的值. 现在把 $i, v_i$ 画到平面上, 选择若干个点使得对应横坐标最大, 发现这是凸包. 于是最后只要求个凸包就做完了.
[think] 想出一个最优策略
[trick] 在 $[1, l]$ 的线段上, 每步随机走到 $-1+1$ 的位置, 点 $x$ 从 $0$ 出来的概率是 $\dfrac{x}{l+1}$
B. Sort It Out
集合外的点相对顺序不变, 于是集合外的点必然是升序的, 在此基础上发现集合内的每个点都会到正确的位置上. 那么剩下的是一个LIS, 发现若两个LIS的字典序关系和它们的补的大小关系相反(考虑其第一个不相同的元素前都相同, 第一个不相同的元素 $B$ 大则补中 $B$ 缺一个大的 $A$ 缺一个小的). 于是求第 $k$ 大LIS, 设 $f_i, g_i$ 表示以 $i$ 结尾的 $LIS$ 长度和个数, $g$ 的转移一定是 $f_j=f_i-1$ 的一个后缀转移过来, 如果对每种 $f$ 的值开一棵线段树, 那么就是区间查, 最后求第 $k$ 大也就是在线段树上面二分. 复杂度单log. 好吧实际上求 $g$ 可以直接维护最大值对应元素之和, 二分也可以直接二分, 但这样是先确定尾不断往头走, 所以应该翻过来找下降序列.
[think] 寻找不变性, 排除一定不合法的情况分析充分性. 这里先要求集合外升序, 而集合外不升序的情况下集合内的点最终目标没有好的性质.
C. The Cow Gathering
容易想到建成根向有根树, 把限制边连上就是问每个点开始有没有环.
发现对于限制 $u\to v$, 所有以 $v$ 为根的 $u$ 的子树都不能当根了. 于是ban掉 $O(1)$ 个dfs区间.
[think] 考虑每个限制的贡献
D. Lifeguards
看到 $k=100$ 直接dp, 显然有包含关系可以全杀了, 然后按 $r$ 排序, $f_{i, j}$ 表示前 $i$ 个区间删 $j$ 个的最大值转移不了, 不知道转移过来时那里有没有删, 那么钦点 $i$ 必选, 考虑前面一段没有选, 然后从 $f_{k, j-1}$ 转移来, 此时若 $r_k>l_i$ 则贡献就是 $f_{i, j}=f_{k, j-(i-k+1)}+(r_i-r_k)$, 否则是 $f_{i, j}=f_{k, j-{i-k+1}}+(r_i-l_i+1)$, 对 $k$ 的限制就是前后缀, 发现其实是要知道 $f_{k, k+(j-i-1)}$, 对每个差维护单调队列即可 $O(1)$ 转移.
[think] 钦点状态加强性质帮助转移, 困难是不知道最后一个被删的是谁那可以钦点成自己
E. Cow at Large
Bessie通过一个点的条件是这个点最近的叶子到它的距离小于根到这个点的距离, 所有不能通过的点中父亲能通过的就是你会用来堵死bessie的点(农民会走到这些位置).
考虑怎么不依赖父亲, 考虑此时先拿出所有Bessie不能通过的点, 容斥出答案, 我们值希望让每个子树的和为 $1$ 即可, 于是叶子贡献 $1$, 每个点贡献负的度数减 $1$ 即可.
于是统计答案, 要对每个点 $u$ 求所有 $dis_{u, v}>p_v$ 的 $v$ 的权值和, 点分治就可以了.
[think] 容斥点权使得子树和为 $1$ 相当于最上层点个数
F. Sprinklers
显然水和废料覆盖的分别是一个阶梯状, 要数两个阶梯状的交里放下几个矩形. 考虑直接扫描线, 因为值域 $O(n)$, 维护纵向的扫描线上每个 $y$ 坐标在扫描线有多长一段合法的, 每次移动区间加, 发现答案贡献要再维护下标和值的乘积就做完了.
G. Out of Sorts
考虑每个位置什么时候出现分隔点, 因为每次冒泡都让右边比 $i$ 小的元素向左移动一格, 于是可以求出冒泡次数. 于是每个位置的贡献就是两边分隔出现时间中的较大值. 于是就结束了.
不会做就拆贡献!
H. Train Tracking
咕咕
I. Disruption
这不是模板题吗! 直接并查集就能做到 $n\alpha (n)$
NOIP2023模拟赛45
A. 树上删边
有一棵 $n$ 个结点的树, 每个结点有一个权值, 删除一条边的费用为该边连接子树中结点权值最大值之和. 问以任意顺序删除树中所有边的最小花费.
$n\le 10^5$
容易发现, 应该按照边的两个端点中大的一个排序然后依次删除. 然后为了维护这个可以倒过来加边并查集.
B. 欧几里得
定于
$$
R(a, b)=
\begin{cases}
R(b, a)\ if\ a<b\
R(\lfloor\dfrac{a}{b}\rfloor, b)\ if\ 1<b\le a\
a\ if\ b=1\end{cases}
$$
给定 $g, h$, 求任意一组 $a, b\le 10^{18}, R(a, b)=\gcd(a, b)$
考虑 $\gcd$ 的限制是精确的, 而 $R$ 每次是给一个范围, 于是想到从 $R(1, h)$ 往回倒退 $a, b$ 的范围, 往前一组肯定是 $R(h, x), x\in [h^2, 2h^2)$, 于是发现你可以不断对 $[h^2, 2h^2)$ 乘一个 $h$ 扩大它的范围, 然后让我们的答案分别是 $ag, bg(a>b)$, 那么经过一次递归之后变成 $R(\dfrac{a}{b}, bg)$, 于是只要能找到 $bg\in [h^k, 2h^k)$, 则能算出 $ag=hb+i(i\in (0, b))$ 使得 $gcd(ag, bg)=g$, 容易发现 $gcd(ag, bg)=gcd(i, bg)$, 于是直接让 $i=(b-1)g$ 即可. 赛时没细想最后一步直接写了个 $0, b$ 范围内随也过了.
C. 没有上司的涨薪舞会
一个公司有 $n$ 名员工, $1$ 没有直接上司, 其余员工都有一个直接上司. 这样的直接上司关系构成以 $1$ 为根的有根树. 已知这颗树. 一个员工的直接下属, 指以他为直接上司的所有员> 工. 一个员工的下属, 指他子树内除他以外的所有员工.
这些员工都十分渴望涨薪, 所以有些人会要求涨薪. 记 $s_i$ 为第 $i$ 个员工是否要求涨薪, “是”为 $1$, “否”为 $0$. 不知道序列 $s$.
现在所有员工都被邀请去了一个舞会. 但是并不是所有人都十分想去, 而且他们是否参加会以自己的直接下属参加情况为参考. 每个人 $u$ 都会等待自己所有下属都决定完, 然后:
若不存在直接下属决定参加舞会, 则以 $p_u$ 的概率参加舞会;
否则, 一定不参加舞会.
已知序列 $p$.
这个公司里, 每位员工都有权力和义务给自己的下属涨薪/降薪. 在这个舞会上, 每位参加舞会的员工 $u$ 会对每个要求涨薪并且参加舞会的下属都涨薪 $a_u$. 这个值可以是负的, 因为有些人心情很差, 专门给要求涨薪的人降薪. 已知序列 $a$.
求使公司所有员工涨薪量之和期望最大的序列 $s$. 不用输出序列 $s$, 只用输出期望的大小. 保证答案在 $10^{11}$ 以内.
期望的线性性说可以对每个点分别求祖先到它的期望. 此时你可以智慧的直接设 $f_{u, 0/1}$ 表示 $u$ 一定来或不来时祖先造成的贡献去dp, 或者直接看成每次修改 $a_u$, 上一个矩阵优化的静态动态dp, 只要维护到根的矩阵连乘积.
D. 最大子段和
给定 ${a_n}$, 每次可以选择 $p$ 让 $a_p: =a_p-1$, 定义 $g(i)$ 表示操作 $i$ 次后最大子段和的最小值, $q$ 次求 $\sum_{i=l}^r g(i) \pmod {10^9+7}$
$l, r\le 10^{15}, n, q\le 5\times 10^5$
看到这个询问可以直接猜答案是 $O(n)$ 段一次函数的区间和. 但问题是一个子段和可能随着减小突然裂开成两个.
考虑二分答案转为求让答案减少到 $V$ 需要操作多少次, , 线性规划形式为
$$
\min_c \sum_i x_i\
s. t. \forall l, r\ \sum_{i=l}^r a_i-x_i\le V\
x_i\ge 0
$$
标准型
$$
\min 1\cdot x\
Ax\ge c\
x\ge 0
$$
$A$ 是 $\dfrac{n(n-1)}{2}\times n$ 的矩阵, 每行对应一个区间, 这一行中属于这个区间的位置是 $1$ 其他是 $0$, $x$ 是长 $\dfrac{n(n-1)}{2}$ 的数组每个位置为 $sum-V$. 对偶之后变成
$$
\max c\cdot y\
A^Ty\ge 1\
y\ge 0
$$
那这个的意思是, 每个区间有一个 $01$ 权值, 最大化区间的权乘 $sum-V$, $y$ 中不能有两个相交的区间权值都不为 $0$. 于是转化成了 $\max t_k-kV$, 其中 $t_k$ 表示选 $k$ 个不相交的区间的和最大是多少.
此时能求出 $t$, 考虑 $k$ 个区间一定是若干个最大子段和, 用线段树维护最大子段和, 有个经典技巧是每次取走一个子段然后把它取负作为如果交上的反悔, 求出 $t$ 之后因为函数取 $\max$ 可以求一个下凸壳, 那么 $g(x)$ 表示最大子段和为 $x$ 最少需要操作几次就是这个下凸壳函数了, 而 $f$ 是 $g$ 的反函数, 对 $f$ 预处理前缀和, 区间求和即可.
NOIP2023模拟赛46
A. 完美主义
你在电脑上发现了一个长度为 $a$ 的字符串, 根据你的完美主义你需要将其长度变成 $b$.
你可以执行任意顺序, 任意多次的以下 $5$ 种操作:
- A. . . Z , 即花费一个按键的代价在字符串尾部添加一个字符, 此时所有选中会被撤销, 这与你的生活经验
或许有所不同, 因为平时使用时若全选了则会将字符串整个删除后添加该字符.- Ctrl + A , 即花费两个按键的代价全选所有字符.
- Ctrl + C , 即花费两个按键的代价复制当前选择的字符到剪贴板, 即剪贴板中的内容是当前字符串.
- Ctrl + V , 即花费两个按键的代价粘贴当前剪贴板中的内容.
- Backspace , 即若全选了当前的所有字符, 则删除所有字符, 否则删除最后一个字符.
现在你想知道长度从 $a$ 变到 $b$ 至少需要按几次按键.
直接建图记录剪贴板长度是 $n^2$ 的.
考虑把按下剪贴板之后的一系列操作(剪贴加若干次粘贴)一起维护, 枚举这次复制之后粘贴了几次, 那么复杂度就成了 $n\ln n$
B. 挑战哈密顿
给定一张 $n$ 点完全图, 顶点编号 $1\ldots n$, 每条边是红色或蓝色, 你要以每个点为起点, 找一条尽量短的路径满足以 $u$ 为起点经过每个点至少一次, 且边的颜色最多变化一次.
$n\le 2000$
猜测一定有恰好为 $n$ 的解.
考虑增量构造哈密顿路, 如果目前所有颜色都相同直接放到链的最后, 于是现在已经有一条链 $1\ldots x\ldots u$, 其中 $1\ldots x$ 的边颜色为 $c_1$, $x\ldots y$ 为 $c_2$, $c_1\ne c_2$, 考虑分类讨论新的点 $i$ 和原来 $p\to x\to q$ 三个点的关系.
若 $i\to q$ 为 $c_2$, 那么你可以把 $i$ 插入到 $x, q$ 之间, 不管 $x\to i$ 为什么都满足条件, 然后移动 $x$(分界点). 同理有 $i\to p$ 为 $c_1$, 于是现在只剩下 $i\to p$ 为 $c_2$, $i\to q$ 为 $c_1$, 发现若 $i\to x$ 为 $c_1$ 可以 $p\to x\to i\to q$, 为 $c_2$ 可以 $p\to i\to x\to q$, 然后移动端点.
然后有一个容易WA的点在于如果当前 $x$ 为链首或链尾, 说明整条链都是一个颜色, 要处理一下, 不然可能会把新的点插入到起点前面.
C. 装备
$n\le 10^5$, $a_i$ 互不相同
首先这个 $c_i\le n$ 说明你从后往前贪心满足是对的. 然后考虑如果要翻转 $i$ 不行, 那一定是 $b_i=a_j$, 那么若有这种情况就连一条边 $i\to j$, 则形成一个基环树森林, 但有环的连通块都动不了, 所以只要考虑森林. 同时, $i$ 翻过去之后会让所有 $b_k=b_i$ 不能翻.
于是你就建图找环, 然后对每个点维护 $s_i$ 表示翻转它需要再翻转几个点, 维护 $fixed_i$ 表示 $i$ 是否已经确定, 维护 $flip_i$ 表示 $i$ 是否被翻转, 模拟上面的东西即可. 维护 $s$ 要查点到根的和, 可以BIT维护dfs序.
然而这题有线性做法, 注意到一棵树只有一个装备没被使用, 而你翻转就是把没有使用的空位移动, 而 $k$ 就是移动步数.
D. 灵活性
好难啊
我要把这个7k代码放在这/oh
考虑你要求一个一开始的答案, 一个当前答案. 那么路径应该放到 $lca$ 上dp(完整包含路径的点): 设 $f_u$ 为子树内的答案, 那么考虑转移就说枚举 $u$ 上一条路径, 然后 $f_u=\sum_{fa_i\in Path_{u, v}} i\notin Path_{u, v}+w$, 考虑维护 $s_u$ 表示 $\sum_{v\in son_u} f_v$, 那么就只要求链的 $\sum s_u-f_u+f_{lca}$ 了. 最后 $f_1$ 就是答案.
而询问的答案由两部分构成, 显然建虚树, 然后一部分是虚树上所有点的 $s_u-f_u$, 另一部分是虚树根子树外的答案, 于是考虑如何处理每个点子树外的答案 $g_u$, 发现经过点 $u$ 的路径 $x\to l\to y$ 可以被用来更新 $v$, 当且仅当不经过 $v$ 的子树, 此时 $g_v=\max g_{l}+\sum_{i\in path_{x, y}} s_i-f_i + f_l$, 则可以把这个值插入到 $x$ 和 $y$ 上, 更新一个点的儿子时就只要用子树最大值更新了.
复杂度 $n\log n$
1 |
|
USACO2020 铂金
剩下的大黑题要不鸽了吧!
A. Non-Decreasing Subsequences
值域很小?
可以写成dp, 预处理前缀矩阵和矩阵逆的乘积, $(n+q)k^3$.
考虑矩阵长什么样: $f_{i, a_i}=\sum f_{i-1, k}, k<a_i$, 哦所以矩阵的样子是对角线全是 $1$ 加上第 $k$ 列有一些 $1$, 那其实乘上这个矩阵是 $n^2$ 的, 因为你只需要对每个 $1$ 贡献就行了.
然后求答案的时候向量乘矩阵也是 $n^2$ 的.
B. Falling Portals
画出每个地方关于时间的纵坐标图像, 容易想到对着出发点分类, 考虑如果出发点比目的地高, 那你就要尽量快的下降, 也就是每次走到比自己下的快的直线就下的策略. 于是你走的一定是一个凸壳. 同时, 每条直线转移到的下一跳直线是唯一的, 考虑 $l$ 如果在 $0$ 时进入转移到 $p$, 那么如果它可以从 $q\to l$ 时不走 $p$ 而走 $q$ 只能因为 $p$ 与 $l$ 的交点在 $q$ 与 $l$ 交点之前, 但此时根据斜率关系, 发现 $p$ 与 $q$ 交点一定在 $p$ 与 $l$ 之前, 于是每条直线的转移时唯一的, 预处理后倍增的跳即可.
C. Delegation
难蚌, 读成了每个点在一个路径里. (不看样例的吗! )
直接multiset去把里面的都匹配起来传一个剩下的上去. 那应该把哪一个放上去是需要考虑的, 考虑如果自己这层全都匹配了放上去的是 $1$ 是最不好的, 所以如果可以就不要全部匹配, 如果当前点有偶数个儿子(可能全部匹配), 那么因为全部自己匹配是最劣的所以如果可以先把最大的能放走的的单独放走. 如果是奇数那么不可能全部匹配直接做就行了.
D. Help Yourself
设 $f_i$ 表示最后所有线段的并的右端点是 $i$ 的答案, 此时的困难是, 如果用区间 $[l, r]$ 转移, 对于 $i\ge l$ 我们不会做: 新的区间可能会覆盖两个原区间, 使得 $f_i$ 中两个连通块合并成一个. 此时考虑钦点一个转移顺序避免这种情况, 如果出现合并, 一定与其中至少一个区间有交, 那么考虑按 $l$ 从小到大转移, 此时可以做了, 对于区间 $[l, r]$, 所有 $f_i, i<l$ 都要连通块数加 $1$ 贡献过来, $i\in [l, r]$ 直接贡献过来, $f_i, i>r$ 无影响(方案数乘 $2$). 那么线段树维护即可, 次幂用斯特林数转组合数.
E. Sprinklers 2: Return of the Alfalfa
容易发现这些中间只有一条分割线, 分割线转角处要放洒水器, 好像接下来直接dp, 设 $f_{i, j, 0/1}$ 表示在 $i, j$ 处放一个洒水器, 分割线最后一次方向, 每次可以由往上或往左一条线求和转移过来.
F. Exercise
好厉害的容斥数数.
首先它肯定是让你求所有环的 $lcm$ 的积. 那你肯定要转成求指数, 又因为直接求指数不好求, 考虑算有多少种方案 $lcm$ 是 $p^k$ 的幂, $p$ 为质数.
考虑怎么在已有若干个环长 $n$ 的排列数上在添加一个长 $i$ 的环, 那么这 $i$ 个数自己有 $(i-1)!$ 种, 再拼进去有 $\binom{n}{i}$ 种.
考虑先枚举一个 $p^k=D$, 那么是算有多少种方案包含一个大小为 $D$ 的倍数的环, 但包含太难算了考虑变成不包含的排列数 $f_n$, 但只用不包含的环大小去背包是 $n^2$ 的, 考虑再次容斥计算仅有 $D$ 的倍数构成的排列数 $g_n$, 因为这样的 $g$ 只有 $\dfrac{n}{D}$ 个, 然后容斥出 $f_n=n! -\sum_i \binom{n}{i}f_ig_{n-i}$(总数减去包含的), 同时发现 $f$ 也只有 $\dfrac{n}{D}$ 个, 因为你要算 $f_n$ 的时候只用到 $f_i, i=n-kD$, 再往下递归也始终是这个形式, 于是复杂度成了 $\dfrac{n^2}{d^2}$, 而 $\sum \dfrac{1}{d^2}$ 是收敛的!
最后按照之前写的拼接方式计算 $g$, 枚举包含第一个点的环长 $i$, 则方案数是 $g_n=g_{n-i}\binom{n-1}{i-1}(i-1)!$.
G. Circus
H. Sleeping Cows
上来先对 $a, b$ 排序, 这个题 $a$ 和 $b$ 匹配是对称的, 考虑从 $b$ 这一维做, 则能匹配 $b_i$ 的 $a$ 是一个前缀 $p_i$, 那么当前这个 $b$ 可以匹配一个 $a$, 也可以留空, 留空要求前面没有必须留空的 $a$, 于是可以设 $f_{i, j, 0/1}$ 表示前 $i$ 个 $b$, $1\ldots p_i$ 中有 $j$ 个 $a$ 还没匹配但该匹配, 是否有被钦定不匹配的 $a$, 每次转移枚举这 $[p_i-p_{i-1}]$ 中的牛有多少加入匹配即可. 注意这里 $\sum p_i-p_{i-1}=n$ 所以复杂度其实是 $n^2$ 而不是 $n^3$
更好的做法可能是把 $a$ 和 $b$ 一起排序, 一次只转移一个.
I. Spaceship
见鬼数数
J. Cowmistry
NOIP2023模拟赛47
A. 药品试验
你在数轴上, 有 $a$ 的概率往左走一步, $b$ 的概率停在当前位置, $c$ 的位置往右走一步, 你一开始在 $n$, 走到 $0$ 或 $2n$ 停止, 求走到 $2n$ 的概率.
$n\le 10^7$
直接写主元高消会因为求逆元爆炸掉.
考虑中间的部分可以矩阵快速转移, 那么直接用矩阵算出 $f_{2n}$ 关于 $f_0, f_1$ 的概率那个矩阵然后解出 $f_1$, 再直接递推 $n$ 即可.
B. 小猫钓鱼
模拟
C. 模拟旅行
给定一张 $n$ 个点的图, 询问集合 $s$ 中的点两两距离的最小值.
$n\le 3\times 10^5, m\le 10^6$
首先容易想到多源dij求每个点正着/反着到最近的两个 $S$ 中点的距离然后做完了.
一个很好写的方法是, 考虑如果是 $S$ 中到 $T$ 中的你直接跑一遍最短路就行了, 那每次随机划分重复 $\log$ 次即可.
找到原题: P5304
D. 迷雾华光
求树链上众数
$n\le 8\times 10^4, q\le 10^5$
树分块模板. 分完了就是蒲公英那个题的做法.
王氏联邦分块比随机撒点跑的快得多.
NOIP2023模拟赛48
A. Chefina 与区间
简单题
B. 小 G 的布料
给定 $01$ 矩阵, 求面积 $\ge k$ 的全 $0$ 矩形个数.
$n, m\le 2000$
预处理每个点往下连续 $0$ 的个数 $f_{i, j}$, 枚举每一行, 对 $f_i$ 建笛卡尔树, 在上面数数, 就只要算包含在一个矩形中的面积大于 $k$ 的个数了, 这个列出式子预处理即可.
C. Easy Data Structure
模板ddp
D. LCM Game
随机生成 $[1, n]$ 的数 $k$ 次, 求所有方案下生成的数的 $lcm$ 的和/积.
$n\le 500, k\le 100$
积是好做的, 直接对每个素数的幂分别算即可.
有一个经典技巧(寿司晚宴)说的是大于 $\sqrt n$ 的质数每个数只能有一个, 在最终的答案要么出现要么不出现, 而小于 $sqrt n$ 的数在这题里只有 $8$ 个, $lcm$ 有大约 $6\times 10^4$ 种. 于是考虑对每个数分解成 $lp\times bp$, 其中 $bp=p\ge sqrt n$ 或 $bp=1$. 则考虑对 $lp$ 的 $lcm$ 算 $bp$ 部分的lcm的乘积. 但限制 $lp$ 的 $lcm=x$ 恰好为一个数困难, 限制 $lcm\vert x$ 的答案 $g_x$ 只要选的每个数的小质数部分都是 $x$ 的因数, 于是先算后面这种再一遍狄利克雷差分就能得到答案.
枚举 $x$ 计算 $g$, 先预处理能选的数($lp\vert x$)中 $bp=p_i$ 的数的个数 $cnt_i$, 那么现在要求在 $[1, n]$ 中选 $k$ 个数的所有方案权值和, 一个方案的权值是它选的数中包含的 $bp$ 的乘积. 限制出现过是困难的(只能一次转移相同 $bp$ 的所有数, 复杂度 $nm$), 考虑容斥, 原来一个 $bp$ 的贡献可以看成 $([have]p+[nothave]1)=(p+[nothave]\cdot (1-p))$, 于是把方案算成钦定 $bp$ 可以出现则乘 $bp$, 不能出现则乘 $1-bp$, 算出有 $i$ 个被钦定可以出现的方案数 $f_i$, 则答案为 $\sum f_i i^k$.
另一种容斥的理解是, 考虑原来要求的是 $\prod (p(e^{x\cdot cnt}-1)+1)$, 它可以变成 $\prod (pe^{x\cdot cnt}+(1-p))$, 这个就能算了, 对每个最后的 $e^{kx}$ 算前面的系数, 而 $n! [z^n]e^{kx}=k^n$, 后面算每个 $e$ 前面系数的部分就是那个dp.
复杂度是 $l n^2$ 其中 $l$ 为 $lp$ 部分 $lcm$ 个数, 发现过不了, 但发现如果只看 $bp\ne 1$ 的数的 $lcm$ 就只剩不到 $1000$ 种, 于是把dp分成 $bp\ne 1$ 和 $bp=1$ 两部分, 前面的记忆化就能过了.
一些构造题
A. 人生的经验
猜测答案是 $c^l+l-1$, 考虑如果把字符串建成点, 相邻两个字符串转移建成边, 那要求哈密顿路不会, 于是考虑把字符串表示成边, 那么可以建 $l-1$ 长度的字符串为点, 这样就是要求欧拉路径了, 而且此时可以发现一定有解.
B. 矩阵
有一个 $n\times n$ 的 $01$ 矩阵, 每次选择一个 $i\in [1, n]$, 然后记录 $c_j=a_{i, j}$, 然后赋值 $a_{j, i}=c_j$, 要求最后全 $1$. 最小化操作次数或判断无解.
$n\le 1000$
如果有 $1$ 一定有解, 容易想到一定是先把一行全 $1$ 然后再把每列操作, 而全 $1$ 一行的代价首先是这行 $0$ 个数, 但是如果这行对应的列没有 $1$ 就在加上 $1$.
C. Divide
$n$ 个元素分成两组, 每个元素有属性 $a_i$, 最大化不在一组的元素 $i, j$ 满足 $a_i+a_j>m$ 的对数, 求方案数
$n\le 2000, m\le 2\times 10^6$
这谁想得到啊!
考虑直接dp不行因为你大概需要前面知道在不在一组的点中有多少能匹配. 于是你把 $a$ 重排, 使得要么前面每个元素都不可能和它构成贡献, 要么都能和它构成贡献, 于是dp只要记录前面有多少个点在A组. 但这个序列为什么一定存在呢? 考虑把原序列排序, 若 $a_1+a_n\ge m$ 则 $a_n$ 可以和中间所有元素构成贡献, 可以把 $a_n$ 拿出来放到序列最后, 若 $a_1+a_n<m$ 则 $a_1$ 不能和中间任何元素构成贡献, 可以把 $a_1$ 拿出来放最后, 递归下去就构造出来了.
[trick] 可以排序序列使得对常数 $m$ 和任意 $i$, 有 $a_i+a_j>m, \forall j<i$ 或 $a_i+a_j<m, \forall j<i$
有更厉害的做法!
D. Hby的旅游之都
给定 $DAG(n, m)$, 给边三染色使得不存在一条路径可以连续经过 $42$ 条相同颜色的边.
$n, m\le 2\times 10^5$
考虑把点分成 $42$ 组, 组之间全染色成 $0$. 再把每组分成 $42$ 组递归下去, 发现 $42^3$ 成功的大于了 $n$. 这个要想对要求你走出一个组之后没有可能回到组中, 于是你可以按拓扑序上的区间分组.
E.
首先根据它给的结论, 猜测答案为 $n-1$.
考虑把边分为 $n-1$ 组, 则每组有 $\dfrac{n}{2}$ 条边, 每组内连续编号则一定是对的. 于是只要找完全图的 $n-1$ 组不交的匹配.
可以构造成这幅图的 $n-1$ 次旋转
F.
定义一个 $n\times n$ 的矩阵称为 $n$ 阶皇后矩阵, 当且仅当矩阵中的元素都取自集合 $S=1, 2\ldots 2n-1$, 且对于每个 $i=1, 2\ldots n$, 它的第 $i$ 行和第 $i$ 列中所有元素合起来恰好是 $S$ 中的所有元素. 请你对于给定的 $n$ 给出一个边长为 $n$ 的皇后矩阵. 当然如果你不想回答这个问题, 或确实无法构造, 你也可以退而求其次, 回答是否存在 $m$ 阶皇后矩
$n\le 1500$
NOIP2023模拟赛49
B. 括号串
构造 $n\times n$ 的空矩阵, 值域 $1\ldots n$ 使得行, 列, 主对角线中元素互不相同.
$n\le 300$
奇数时直接 $a_{i, j}=(i+j)\pmod n$
偶数先构造出奇数的再在上面补充.
我才不会告诉你我直接瞪着100的大样例找规律.
B. 括号串
一开始, 一个仅包含一对括号的串即 $()$, 接下来有 $3$ 个操作, 操作分为三类:
- 操作 $1$ , 在字符串的末尾加上一对括号, 即由 $S$ 变为 $S()$;
- 操作 $2$ , 在字符串的最外面套上一对括号, 即由 $S$ 变为 $(S)$;
- 操作 $3$ , 是撤销之前的某个操作, 清除它造成的一切影响.
每次操作后, 你需要输出当前字符串能够括号匹配的非空子串数量.
考虑把括号之间的嵌套关系建树, 顶层建一个超级根, 那么操作 $1$ 是给当前根挂一个儿子, 操作 $2$ 是给当前根挂一个父亲并成为新的根. 若只有操作 $1, 2$, 则某一时刻的答案就是每个点的 $\sum \dfrac{s_u(s_u+1)}{2}$, 其中 $s_u$ 为 $u$ 的儿子个数. 那现在有了操作 $3$, 把最终的整棵树建出来, 让被撤销的/还没加入的点为白点, 其余点为黑点, 则显然一个点的 $s_u$ 应该指的是 $u$ 子树中到 $u$ 的路径上没有其他黑点的黑点数量, 而答案是所有黑点的贡献之和. 那么用dfs+BIT维护 $s_u$ 支持链加单点查, 再上一个数据结构支持查一个点往上最近的黑点即可. 查这个在普通树上不用lct类科技应该只能2log? 但是这个树上直接树剖就是单log.
然而不树剖直接二分+bit也过了.
C. 博弈
是Topcoder SRM700 AnyNumber
有一个棋盘, 第 $i$ 行有 $l_i$ 个格子, 给定字符串序列 $s_n$, 你会按顺序依次把字符串放到一个随机的空格子中, 当有一行被填满时结束, 定义一个操作序列的权值为操作后这一行满格子上的字符串顺次拼接后形成的数字, 求权值期望.
$n, m, \sum s_i\le 300, \sum l_i\le n+m$
一开始疑惑为什么要按照顺序, 因为看起来先放这个再放那个最后局面概率是一样的. 但发现有终止局面就不一样了. 于是考虑枚举结束的时间.
这个权值看起来很奇怪, 先看它怎么处理, 假设我们会处理一行的权值, 那么接下来就只要乘上 $cnt_{i, j}$ 表示没有第 $i$ 行的情况下放 $j$ 个字符串, 没有填满任何一行的方案数, 就可以合并答案了.
再枚举最后满的一行, 现在要算权值, 这个权值直接看很见鬼, 考虑把每个数字的贡献拆开算, 设字符串 $s_i$ 的实际值为 $v_i$, 长度为 $q_i$. 我们可以把其贡献表示成 $v_i\sum 10^{x}$, 那么看看能不能dp这个 $x$ 出来, 设加入 $i$ 个字符串, 其中有 $j$ 个放在当前这一行的情况下, 把这 $j$ 个拿出拼成一个序列, $\sum_T 10^{s_{T, k}}$, 其中 $s_{T, k}$ 表示方案 $T$ 下最后 $k$ 个数的 $q_i$ 之和为 $f_{i, j, k}$(换句话说, 如果新加一个字符串插入在从右往左数第 $k$ 个字符串的右边, 它应该乘上多少). 转移就是新来的字符串的位置, 其中 $(1)$ 表示这个字符被放到其它行, $(2)$ 是放在后 $k$ 个之前, $(3)$ 是放在后 $k$ 个中
$$
\begin{align}
f_{i, j, k}=&f_{i-1, j, k}\tag{1}\
+&(j-k)f_{i-1, j-1, k}\tag{2}\
+&k\cdot f_{i-1, j-1, k-1}\cdot 10^{q_i}\tag{3}
\end{align}
$$
此时已经可以写答案了吧, 就是你枚举一个数, 枚举它的位置, 但这样复杂度应该是 $n^4$ 的. 考虑再dp, 设 $g_{i, j}$ 表示前 $i$ 个字符串, 有 $j$ 个在当前行, 发现此时加入一个数不好转移, 因为当你向这 $j$ 个数中间插入一个数时, 会让一个前缀乘上 $10^{q_i}$, 于是考虑把前缀也设进去: $g_{i, j, k}$ 表示前 $i$ 个字符串, 有 $j$ 个在当前行, 把它们拼成一个序列, 在所有方案下, 前 $k$ 个元素的贡献和是多少(比如前 $k$ 个元素种有一个元素在一种方案下为 $x$, 它后面总长为 $y$, 那么它会产生 $x10^y$ 贡献), 此时就可以列转移了.
$$
\begin{align}
g_{i, j, k}&=g_{i-1, j, k}\tag{1}\
&+kg_{i-1, j-1, k-1}\tag{2}\
&+\sum_{l<k} k{i-1, j-1, l}(10^{q_i}-1)\tag{3}\
&+\sum_{l\in [j-k, j)} f_{i-1, j-1, l}v_i\tag{4}
\end{align}
$$
$(1)$ 表示不选, $(2)$ 是去掉这个元素的贡献, $(3)$ 是选上这个元素后, 有一些元素的贡献因为插入了它变大, $(4)$ 是这个元素自身在每个位置的贡献之和.
$f, g$ 用滚动数组优化都是 $n^3$, 前面那个枚举处理 $cnt$ 也是 $n^3$, 合并答案 $n^2$, 总复杂度 $n^3$, 注意合并答案时要强制当前元素在这一行被选(只要在贡献 $g_i$ 时差分掉 $g_{i-1}$ 的即可).
D. 平面树
$n\le 3\times 10^5, q\le 6\times 10^6$
考虑先预处理, 把一条边的代价重置为从这条边左边到这条边右边的最小代价, 这个可以两遍dfs实现, 跨过一条边的方式包括跨过子树的所有儿子, 跨过它, 跨过所有兄弟和父亲三种.
然后设状态为 $f_{u, 0/1, 0/1}$ 表示从这条边的左右侧转移到父边的左右侧要加的代价, 这个转移可以写成矩阵, 然后查询时你就从两个点先转移到lca, 然后合并答案即可.
复杂度是单log吧.
NOIP2023模拟赛50
A. 点分治
容易发现从小到大排列后, $v_i$ 就是祖先分别是 $solve$ 几级别的树.
那么设 $f(u, d)$ 表示级别 $u$ 的树中深度为 $x$ 的点有多少, 发现它就是组合数. 那就简单了, 显然答案就是这个点为根的答案加上祖先们到它的距离, 而 $u$ 的祖先的答案 $g(u, d)=g(fa, d-1)+f(fa, d-1)-f(fa, d-2)$.
没特判 $f(u, d), d<0$ 的情况挂成5分.
B. 塔
这个是CF354D
怎么是黑的啊
感觉dp基本功不行啊, 上来先想到你看设计成 $S+2$ 而不是 $aS+b$ 肯定有点意义吧, 于是如果你要用第二种法术, 必然要保证 $S+2\le 3k$, 于是你可能用第二种法术的高度是根号级的. 然后就不会了?
好吧可以直接dp的啊, 但你应该从左往右dp而不是见鬼的按行做或按点做, 因为把三角形摆正后, 这个修改是直角三角形, 然后就直接 $n\sqrt n$ 了.
C. 军队
$n, m, c\le 3\times 10^5, k\le 10$
什么缝合破题.
第一部分显然直接线段树维护前 $k$ 小个数. 算出每一行的.
第二行显然按照每行中雌雄个数中较小的排序, 前缀和.
D. 最优化
$n\le 300, q\le 10^5$
感觉这个是现有算法后有题类.
考虑你要求一个图的链覆盖, 先考虑dag最小链覆盖怎么做, 就拆点跑网络流, 也就是 $s\to u, u+n\to v$, 若 $u\to v$ 则连 $u\to v+n$, 去跑匹配. 这个是不允许路径有交的, 如果允许有则先传递闭包(对任意 $u\Longrightarrow v$(可到达)则连边 $u\to v+n$).
然后这个为什么不能做一般图链覆盖呢? 因为一般图下会成环, 但这个题允许成环, 且这个 $+C$ 的共线可以看成(点数减边数), 于是发现这简直是为这个算法量身定做的, 于是你直接暴力求出流量为 $i=1\ldots n$ 的答案 $f_i$ 然后对每个 $c$ 计算 $\min (n-i)c+f_i$ 即可.
CCPC Online 2023
大多数题都不难啊/fn
其中比较有趣的:
C. Clique Challange
$Graph(n, m)$ 求团个数, $n, m\le 1000$
NPC, 但是复杂度是 $\sqrt m1. 414^{\sqrt {2m}}$
J. Find the Gap
给 $50$ 个点, 求最近的两个平面把它们夹住
以为一定是与某三个点平行的, 但不对
考虑正四面体, 其最优情况是两条对角线.
于是正解是异面直线的情况和三个点确定的情况.
特判所有点在一条直线上(叉乘总为 $0$)
H. Hurricane
给定稀疏图, 求补图上长度分别为 $1$ 到 $n-1$ 的简单路径数
$n, m\le 2\times 10^5$
考虑如果两个点度数之和小于 $n$, 那么答案不超过 $2$ 啊.
于是把点分成度数超不超过 $n/2$ 的两类, 第一类的直接答案填 $2$, 第二类对每个点bfs. bfs的话可以维护两个集合, 一个和当前点相连一个不相连就行了.
I. Monster Generator
你要打 $m$ 天怪, 有 $n$ 个怪, 每天独立(你都要把它们打一遍), 第 $k$ 天打第 $i$ 个怪会失去 $a+bk$ 点体力, 打完了会获得 $c+dk$ 点体力, 你的体力不能小于 $0$. 问你每天开始时的最小体力.
$n\le 100, m\le 10^{18}$
长得一脸贪心, 考虑一天的怎么做, 把怪分成两类, 一类是打完体力上升, 一类是打完下降, 那么你显然上升的从小往大打, 下降的从小往大打即可.
那么当 $m$ 很大的时候, 你就直接处理情况变化的时间即可.
L. Partially Free Meal
给定 $n$ 对 $(a_i, b_i)$, 对每个 $k$ 最小化 $\sum_{i\in S} a_i+\max_{i\in S} b_i\ s. t. \ \vert S\vert = k$.
$n\le 2\times 10^5, a, b\le 10^9$
按 $b$ 排序, 对于一个固定的 $k$ 显然答案是某个位置前的前 $k-1$ 小, 可以主席树.
当要对每个 $k$ 做时, 发现决策单调性, 更大的 $b$ 只在更大的 $k$ 时有用, 于是上个分治即可.
K. Sequence Shift
给定 $a_1\ldots a_n, b_1\ldots b_n$, 每次操作为把 $b$ 循环左移并设置 $b_n$, 询问 $\max a_i+b_i$.
$n, q\le 10^6$, 数据随机
好强悍的东西.
说的是, 离线, 然后你选择一个 $k$, 记录 $a_k+b_k=lim$, 然后每次移动后先枚举 $a_i+b_n\ge lim$ 的数算贡献更新对应的 $ans$, 那么吸纳然如果一个询问更新到了答案就是对的, 否则你暴力计算. 那 $k$ 选大了更新的复杂度爆炸, 选小了暴力的复杂度爆炸, 于是它开始平衡复杂度: 先算期望对数 $E=\dfrac{k^2(n+m^2)}{2nm}$, 然后算暴力的复杂度 $(m-n+1)n(1-\dfrac{E}{nm})^n$, 然后加起来求导, 最后接出来 $k=\dfrac{m}{n+m}\sqrt {2n\log \dfrac{nq}{m}}$
NOIP2023模拟赛51
A.
是AGC027E
给定一个只含小写字母 $\mathtt{a}, \mathtt{b}$ 的字符串 $s$, 每次你可以执行以下两种操作:
- 选取 $s$ 中连续的两个字符 $\mathtt{aa}$, 把它们删去, 替换成一个字符 $\mathtt{b}$.
- 选取 $s$ 中连续的两个字符 $\mathtt{bb}$, 把它们删去, 替换成一个字符 $\mathtt{a}$.
请你求出执行若干次操作后, 能够得到的本质不同的字符串有多少个, 答案对 $({10}^9 + 7)$ 取模.
- $1 \le \vert s\vert \le {10}^5$.
考虑赋权看操作不改变什么, $v(a)=1, v(b)=2$, 则不改变模 $3$ 的值, 且若 $s$ 不是 $ab$ 交替的串, 则任意一段可以合并成等于它的和模 $3$ 的一个字符. 于是直接dp就行了.
B.
给定简单图 $Graph(n, m)$, 保证 $1$ 不为割点且每个点到 $1$ 有连边, 对每个 $k$ 求 $1$ 的度数为 $k$ 时的答案.
$n\le 3\times 10^5$
最容易想到的是按照每条边对答案的贡献(权值减换掉的那条的权值)排序后替换, 但问题是替换前面的会影响后面的, 暴力更新复杂度也是错的.
另一种方法是在 $n-1$ 个点 MST 上dp, 设 $f_{u, i}$ 表示 $u$ 内选 $i$ 个点和 $1$ 连通的答案, 这个 $v$ 转移到 $u$ 只要枚举是否连 $1\to u, 1\to v, u\to v$. 直接做复杂度是树上背包 $n^2$, 但经典结论是它是凸的, 于是闵和合并+分治+树上启发式合并.
最简单的方法是考虑kruskal重构树, 两个点之间的最大值是它们的lca, 那么某一次你会删掉 $u\to v$, 然后剩下的情况你不会删掉跨过 $u, v$ 的连通块的边, 也就是kruskal重构树的子树内的子问题, 于是就不用考虑删边影响未删的边的贡献了.
C.
一棵 $n$ 点树, 每个点上有一个BST, 每次给一条路径上插入一个值 $k$ 或询问单个节点中查询 $k$ 时 $k$ 到BST中根的点的权值和.
$n, q\le 2\times 10^5, k$ 互不相同
碰到这种数据结构你第一反应应该是枚举扫描线方向和把BST结构搞清楚, 这种问题肯定是扫序列维维护时间的.
于是你发现把权值排序后, BST中一个点的父亲是前驱/后继中晚插入的那个, 另外会发现两边对 $x$ 的贡献是独立的, 就是左边的答案就是不断跳比当前节点早插入的节点中的前驱, 右边同理.
对于序列上, 问题变成插入删除点 $(k, time_k)$ 和求答案, 答案是跟前缀后缀min相关的, 所以上一个值域上的楼房重建线段树. 假设要求往右跳的贡献, 设 $calc(l, r, k)$ 表示区间 $l, r$ 中 $time<k$ 的 $time$ 前缀min的 $k$ 之和, 则若 $d=\min_{i\le mid} time_i, d>k$ 那直接跳到右边了, 否则就是 $calc(l, mid, k)+calc(mid+1, r, d)$, 维护 $calc(mid+1, r, d)$ 即可.
现在求树上, 线段树合并就行了.
D.
就是 UOJ Round#6 懒癌
好难todo
NOIP2023模拟赛52
A. 区间
给定 $n$ 个区间 $[l_i, r_i]$, 要求选出尽可能多的区间对使得任意每对中两个区间不交, 区间只能被选一次.
$n\le 4\times 10^5$
就是让你求一个图的匹配, 方法是如果一个点
B. 排序
给定排列 $p_n$, 每次可以把 $a_l, a_{l+1}, \ldots a_r$ 重排成 $a_{l+1}, a_{l+3}\ldots a_l, a_{l+2}\ldots$, 构造在 $2n$ 次内使排列升序.
$n\le 3000$
首先你会冒泡, 然后你会看怎么能快速移动一个节点的位置, 原问题上不好考虑, 考虑操作反过来做后问题是等价的(对排列置换), 那么反过来后你可以把 $\dfrac{n}{2}$ 左边的元素 $x$ 最大移动到 $2x$, 否则你可以移动到最后, 然后移动一个数需要 $\log {n}-\log i+1$ 次, 而这个期望是常数. 所以你先随机操作打乱排列然后去做即可.
[trick] $\log n-\log i+1$ 期望 $O(1)$
C
给定字符串 $S$. 对于一个字符串, 你可以选择一个起点然后每次走到相邻的点, 不能走出字符串, 你必须走出一个回文且不能回到起点. 一个字符串合法当且仅当可以走任意次使路径把字符串覆盖, 区间询问子串是否合法.
$n, q\le 10^6$
首先看什么样的字符串是合法的, 发现包含长度为 $3$ 的回文合法(走 $a_1ba_2xx\ldots a_2ba_2$ 可以覆盖掉一边, 再来一次可以覆盖掉另一边), 而如果不包含发现奇回文不能令你回头, 那么如果只有偶回文你只能一直走, 也就是另一种合法是字符串被回文覆盖.
那么第一种显然好判断, 考虑怎么判第二种, 对于一个点 $i$, 处理出它左右最近的覆盖到它的回文中心, 那么一个点被覆盖是限制(左端点小于某个值或右端点大于某个值), 那么不能覆盖的就是一个2side矩形, 发现于是每个点给区间的限制是一个 $4side$ 矩形不能选, 就是矩形加单点查了.
D
求有多少个 $a_n$ 满足 $\forall i\in[1, m], \mathrm{lcm}(a_{x_i}, a_{y_i})=b_i$.
$n\le 38$
首先观察到对每个质因子独立.
现在对于单个质因子就是给你一张图, 然后要求每条边连的两个点中的最大值等于某值, 那么显然如果一个点连了好几个边不是最小值的都可以直接确定另一个点是几, 然后形成若干连通块, 每个连通块边权相等设为 $v$, 那么没取到 $v$ 的点必须构成独立集, 一个独立集 $S$ 的权值为 $(v-1)^{\vert S\vert}$, 那么预处理每个点的相邻点集合, 折半 $2^{\frac{n}{2}}$ 搜一边, 合并就是 FWT 的或卷积.
div1-杂题
[SNOI2019] 纸牌
有一副纸牌. 牌一共有 $n$ 种, 分别标有 $1, 2, . . . , n$ , 每种有 $C$ 张. 故这副牌总共有 $nC$ 张.
三张连号的牌 $(i, i+1, i+2)$ 或三张相同的牌 $(i, i, i)$ 可以组成一叠. 如果一组牌可以分成若干(包括零)叠, 就称其为一组王牌.
你从牌堆中摸了一些初始牌. 现在你想挑出一些牌组成一组王牌, 请问有多少种可能组成的王牌呢? 答案对 $998244353$ 取模.
两组牌相同当且仅当它们含有的每一种牌数量都相同.
对于所有数据, $1\leq n\leq 10^{18}, 0\leq a_i\leq C\leq 1000, 0\leq X\leq 1000$ . 注意 $a_i$ 和 $C$ 可能为 $0$ .
直接想dp, 假设覆盖你要怎么做? 你发现以 $i$ 为右端点的操作你需要知道 $i-1$ 和 $i-2$ 都多少, 然后丢给下一位, 于是就dp $f_{i, j, k}$ 表示前 $i$ 种牌, $i, i-1$ 分别有多少, 矩阵加速一下即可.
upd: 感觉这么设状态不如设 $f_{i, j, k}$ 表示 $j, k$ 分别被操作了多少, 因为这个只用关于第 $i$ 位考虑, 而之前那种和前两位也有关.
[SNOI2019] 字符串
给定字符串 $s_n$, 求删掉第 $i$ 位的字符串 $s_i$ 按字典序排序后的序列.
$n\le 10^6$
直接sort, 那你只要想怎么比较两个字符串, 则删掉 $i$ 的和删掉 $j$ 的你就要比较 $s_{i+1\ldots j}$ 和 $s_{i, j-1}$ 的字典序, 你冲动的写了一发SA, 然后发现因为你只要比较相邻两后缀, 直接预处理 $a_i$ 表示 $s_i, s_{i+1}$ 的大小关系, 就是找到第一个不是等于的.
[SNOI2019] 数论
给出正整数 $P, Q, T$, 大小为 $n$ 的整数集 $A$ 和大小为 $m$ 的整数集 $B$, 请你求出:
$$\sum_{i=0}^{T-1}[(i \in A (mod P) \wedge (i \in B (mod Q)]$$
换言之, 就是问有多少个小于 $T$ 的非负整数 $x$ 满足: $x$ 除以 $P$ 的余数属于 $A$ 且 $x$ 除以 $Q$ 的余数属于 $B$.
对于所有数据, $1 \leq n, m \leq 10^6 , 1 \leq P, Q \leq 10^6 , 1 \leq T \leq 10^{18}$.
考虑直接硬上, 枚举 $A$ 中的元素 $a$, 则表示 $x=kP+a$, 那么要 $kP+a=b \bmod Q$, $kP=(b-a)$ 这个怎么解, 考虑如果有两个解那么 $(k_1-k_2)P=0$ 则两个解的差就是 $d=\dfrac{Q}{\gcd(P, Q)}$, 然后你可以枚举 $k$ 预处理出每个 $v=b-a$ 最小的解 $s_v$, 另外可能的 $k$ 显然最大是 $\dfrac{T-a-1}{P}$, 现在变成要求
$$
\begin{gathered}
\sum_{a\in A} \sum_{b\in B} \dfrac{\dfrac{T-a-1}{P}-v_{b-a}}{d}\
\end{gathered}
$$
然后这个式子你可以对每个 $b-a$ 求出 $\sum \dfrac{T-a-1}{P}$, 啊不会了因为下取整你不能直接把他们加起来. 但是注意 $\dfrac{T-a-1}{P}$ 最多有两种取值($a<P$), 所以就分别对每个 $b-a$ 求两种取值的个数(把 $a$ 分成两类分别贡献), 而统计这个你只需要NTT.
什么? 这其实不是NTT题/kx枚举 $a$ 之后, 你不是每次走 $P$ 吗, 这会形成若干环, 可以直接预处理每个环走 $k$ 步经过的所有 $b$.
[SNOI2019] 积木
有一块 $n$ 行 $m$ 列的网格板, $n, m$ 都是奇数. 网格上平铺着一些 $1\times 2$ 的积木. 积木可以旋转, 不能重叠. 这些积木共有 $\frac{nm-1}{2}$ 块, 也就是说, 网格板上只有一格的空位.
你可以做两种操作:
- 将一块与空白格相邻(指有公共边)的积木旋转 $90^\circ$ 到空白格中;
- 将一块与空白格积木相邻的积木平移至空白格中.
如图所示(被移动的积木颜色较浅):
请你用以上两种操作将给定的网格板变换为指定的状态.
对于所有数据, $1\leq n, m\leq 2000$.
要勇于尝试! 长成这样不一定是不可做题.
你发现你每次可以把格子附近一个长方形放到正确的位置, 不断重复你会走到目标空格, 那么你的空格停下当且仅当旁边的所有格子都是正确的, 所以唯一可能的停止位置是目标位置, 但可能有些位置不在你走到目标的路径上, 你就直接胡乱把它移动过去然后用刚才的办法让它一路调整回来.
[SNOI2019] 通信
$n$ 个排成一列的哨站要进行通信. 第 $i$ 个哨站的频段为 $a_i$.
每个哨站 $i$ 需要选择以下二者之一:
- 直接连接到控制中心, 代价为 $W$;
- 连接到前面的某个哨站 $j$($j<i$), 代价为 $\vert a_i-a_j \vert$.
每个哨站只能被后面的至多一个哨站连接.请你求出最小可能的代价和.
对于所有数据, $1 \leq n \leq 1000$, $0 \leq W, a_i \leq 10^9$.
首先把你的dp放下拿起网络流. . .
然后你会很快建一个模, 大概是 $S \stackrel{1, 0}{\longrightarrow} i, i \stackrel{1, w}{\longrightarrow} t, i’\stackrel{1, 0}{\longrightarrow}t, i \stackrel{1, \vert a_i-a_j\vert }{\longrightarrow}j’$
然后你的边数显然爆炸了, 要优化 $i\to j$ 的连边, 发现这是个二维数点, 在你前面的限制和 $a$ 的限制, 那么只好用二维数据结构, 拿主席树优化建图应该是最好的, 当然还可以分块和KDT.
[SNOI2019] 网络
有 $n$ 个数据中心, 编号为 $1, 2, ……, n$. 它们被 $n-1$ 条光缆连通, 形成一棵树.
每条光缆传输数据时有 $1$ 单位时间的延迟, 两个数据中心之间的延迟为连接它们的光缆的延迟之和.
现在要在这 $n$ 个数据中心中选若干个作为通讯站, 要求任意两个通讯站之间的延迟不超过 $d$. 设选出的通讯站为 ${w_1, w_2, ……, w_k}$, 则通讯总延迟为这 $k$ 个通讯站两两之间的延迟之和.
现在有 $q$ 次询问, 每次选定一个数据中心 $u$, 你需要求出: 如果 $u$ 是一个通讯站, 最大可能的通讯总延迟是多少.
对于所有数据, $1 \leq n \leq 5*10^5 , 0 \leq d<n , 0 \leq q \leq 10$.
你最后的答案一定是一个以包含 $u$ 的直径不超过 $d$ 的极大连通块, 那你可以预处理出每个点/边为直径中心的答案, 那你要合并 $u$ 的子树外和 $u$ 的子树内, 你需要满足条件的点各自到 $u$ 的距离和, 各自内部的距离和, 各自的点数, 因为距离就是深度子树内的你直接长剖, 合并的时候就都有了, 子树外的答案可以换根扫一遍, 你现在在一个节点, 先把所有轻子树的信息合并上去然后递归重链, 然后再对每个轻子树删去它们的信息并递归轻链, 这样你复杂度也是线性的.
Div2是DP和数数专场
CF294C A. Shaass and Lights
考虑没点亮的若干连续段, 段间独立, 段内是每一步从左边点还是右边点.
CF1753C Wish I Knew How to Sort
只考虑 $0$, 你就是要将前若干个变成 $0$, 设 $0$ 的个数为 $c$, $f_i$ 为前 $c$ 位有 $i$ 个 $0$ 的期望时间, 则 $f_c=0$, $f_i=f_{i+1}\dfrac{(c-i)^2}{tot}+f_i\dfrac{1-(c-i)^2}{tot}$ 就行了.
CF660E Different Subsets For All Tuples
对于 $a_n, a_i\in [1, m]$, 求所有的 $a_n$ 的本质不同子序列个数的和.
$n, m\le 10^6$
考虑计数包含某个特定子序列的序列有多少种, 为了让这个不重, 假设这个子序列是原序列的第一个等于该值的子序列, 于是若子序列是 $t_k$, 原序列是 $a_n$, 子序列第 $i$ 个元素的位置是 $p_i$, 则 $1\ldots p_1-1$ 的位置不能有 $p_1, p_1+1\ldots p_2-1$ 的位置不能有 $p_2$, 也就是 $p_k$ 之前的方案数是 $(m-1)^{p_k-k}$, 之后的是 $m^{n-p_k}$, 于是直接枚举 $p_k$, 要求
$$
\begin{gathered}
\sum_k m^k \sum_p m^{n-p}(m-1)^{p-k}\binom {p-1}{k-1}\
=\sum_k \sum_p m^{n+k-p}(m-1)^{p-k}\binom {p-1}{p-k}\
=\sum_{d=p-k} m^{n-d}(m-1)^d\sum_p \binom{p-1}{d}
=\sum_{d} m^{n-d}(m-1)^d \binom{n}{d+1}
\end{gathered}
$$
最后一步是组合数列前缀和.
CF785D Anton and School - 2
给定一个长度为 $n$ 的括号序列, 求该括号序列满足如下条件的子序列个数:
- 长度为正偶数
- 假设该子序列长度为 $2m$, 则该子序列前 $m$ 个均为
(, 后 $m$ 个均为).对 $10^9+7$ 取模.
$n \le 2 \times 10^5$.
考虑枚举这个子序列的中心的那个左括号, 就是 $\sum_m \binom{p_i}{m-1}\binom{s_i}{m}=\sum_m \binom{p_i}{m-1}\binom{s_i}{s_i-m}=\binom{p_i+s_i}{s_i-1}$, 范德蒙德卷积
CF1540B Tree Array
给定一棵 $n$ 个节点的树.
对于这棵树, 我们通过下列方法来生成一个序列:
- 等概率选择这 $n$ 个节点中的一个节点, 并对这个节点打上标记(初始时没有节点被打上标记);
- 在所有没被打上标记且与至少一个打上标记的节点相连的节点中等概率选择一个节点并对这个节点打上标记;
- 重复步骤 2 直到所有节点都被打上标记, 此时生成的序列就是所有节点编号按照节点被打上标记的时间排序后的形成的序列.
求生成序列的期望逆序对数对 $10^9+7$ 取模后的值.
$2\leq n\leq200;$ 给出的是棵树.
用老套路, 逆序对数就是两个数逆序的概率之和, 然后你可以枚举一个根, 然后如果是祖先关系贡献确定了, 否则考虑不是祖先关系, 那么只考虑影不影响选他俩的概率这件事上, 发现只和他俩之间链上的点有关, 设两个点到 $lca$ 的距离分别为 $a, b$, 枚举 $a$ 删除的时间 $i$
$$
\sum_{i=0}^{a+b} \binom{i-1}{a-1}\dfrac{1}{2^i}
$$
就做完了啊
吐槽题解区为啥一页全都是dp求上面按个概率.
CF1716F Bags with Balls
这里有 $n$ 个袋子, 每个袋子里面有 $m$ 个带有从 $1$ - $m$ 标记的球. 对于每一个 $1\le i \le m$ 来说, 每个袋子中都一定存在一个带有 $i$ 标记的球.
你需要在每个袋子中取出一个球 ( 所有的袋子都是不同的, 比如在 $1$ 号袋子取 $2$ 号球 并且从 $2$ 号袋子里取 $1$ 号球 与 从 $1$ 号袋子取 $1$ 号球并且从 $2$ 号袋子取 $2$ 号球是不同的两种方案 ) 然后计算出你取出的标号是奇数的球的数量, 记这个数量为 $F$.
你的任务是计算所有可能的取球方案的 $F^k$ 之和.
$n, m\le 998244352, k\le 2000$
你只关心奇数的数量, 所以一个可以先把 $m$ 扔了取奇数偶数的概率分别是 $a, b$, 那EGF, 式子就是 $x^k^n$ 然后就可以做了啊多项式快速幂划掉.
另外, 斯特林数看起来本质上就是 $e^x$ 和 $x$ 换元的系数, 所以换元 $x$ 展开然后斯特林数可以得到更好的式子.
NOIP2023模拟赛53
A. 谜域的界外
有无穷个点 $(x_i, y_i)$, $x_0, y_0$ 给定, $x_i=a_xx_{i-1}+b_x, y_i=a_yy_{i-1}+b_y$, 你可以每秒走 $1$ 的曼哈顿距离, 问你从 $x, y$ 出发在 $t$ 时间里能经过多少点.
$x, y, x_0, y_0, t\in 10^{16}, a_x, a_y\in [2, 100], b_x, b_y\in [0, 10^{16}]$
你看这个 $a_x, a_y\ge 2$, 就知道只有 $\log t$ 个点有用, 随便做了.
B. 失落的世界
交互题, 你知道 $n$, 不知道 $c\in [1, n]$, 每次你可以询问一个数 $x\in [1, n]$, 设上次询问的是 $x’$, 会告诉你 $c$ 是否 $\ge \vert x-x’\vert$, 求 $c$.
询问次数 $64$, $n\le 10^{18}$
考虑你肯定想二分, 问题就是可能跳出去, 发现答案是 $n$ 的情况是最紧的, 于是你从后模拟看如果每次二分都递归右侧一开始可以在哪即可.
另外, 直接从 $\lceil \dfrac{n}{3}\rceil$ 跳也对, 因为 $\dfrac{1}{3}=\sum_{i=1} \dfrac{1}{4^i}$
C. 最短路
给定 $Graph(n, m)$, 边权序列 $w_m$, 设一条路径经过的边权序列是 $p_1\ldots p_d$, 长度是 $\sum_{i=2}^d cost(p_i, p_{i-1}), cost(x, y)=\sum_{i=0}^k c_ix^{a_i}y^{b_i}$, 问 $1$ 到每个点的最小代价.
$n, m\le 2\times 10^5, k, a, b\le 5$
这种一般图看起来肯定要dij, 另外因为这个路径序列跟边关系很大但跟点关系不大, 应该想到做点边互换成为线图, 于是暴力就 $n^2$ 了.
考虑如何更新出边, 因为dij每次是拿出距离最小的, 则一个点的所有出边中只有 $w$ 最小的那一条可能被用来松弛, 其他边只有在它被用来松弛之后才会可能被用来松弛, 于是考虑每次只更新最小的出边, 每次用一条边 $u\to v$ 松弛后就更新 $u$ 的出边中没被松弛的边中 $w$ 最小的, 这就需要一个数据结构支持添加一个 $5$ 次函数或修改一个 $5$ 次函数的常数项.
然后你掏出了EI科技用二进制分组+分散层叠维护包络线然后你注意到, 首先修改常数项是假的因为你每次都改小, 相当于每次重新插入一个. 又发现五次函数是假的因为若 $w_i>w_j$, 则 $F_i$ 除了常数项的每一项系数都大于 $F_j$, 于是任意两个函数最多有 $1$ 个交点, 李超树维护了.
但这个实际上可以不带 $\log$, 观察性质说我们每次查的位置单调递增, 而更大的 $x$ 一定对应 $w$ 更小的 $F$, 于是开个队列维护即可.
李超树上界开大爆longlong 100 挂到 37.
D. 聚合的塔尖
给定 $DAG(n, m)$, $q$ 次查询除了 $u_i\ldots u_k$ 这些点之外到 $s$ 的最长路是多少.
$n, q\le 10^5, m\le 2\times 10^5$
不能DAG剖, 那个是关于路径数的. 然后你又知道什么DAG上线段树合并是假的, 基本上排除了log结构
考虑根号, 感觉只要想到根号分治立马就能做出来了, 对于 $k$ 大于根号的暴力, 对于 $k$ 小于根号你只要对每个点预处理根号个到它最近的即可.
另外这个暴力不用拓扑排序, 直接扫就行.
NOIP2023模拟赛54
A. 你还没有卸载吗
模板整除分块
B. 仪式感
CF Make It One 模板gcd卷积
C. Warrior
给定 $a_n$, 求一个区间使得把区间的元素拿出来当成可重集, 这个可重集是所有区间中第 $k$ 小, 可重集字典序定义为 $S<T$ 当且仅当最小的两个集合中出现次数不同的元素 $S$ 出现的多.
简单做法是, 考虑可以 $n\log n$ 求一个序列的 $rank$, 因为对于一个区间固定一个端点字典序单调, 所以对于一个给定的序列, 单调增加右端点, 满足恰好小于它的左端点肯定也单调右移, 那就是每次给一个数出现次数改变 $1$ 判断是否小于给定序列, 线段树即可.
于是直接随机二分, 对每个右端点维护可能作为答案的左端点区间, 每次从所有可行区间中等概率随一个然后判 $rank$, 根据 $rank$ 和 $k$ 的大小可以把可行区间缩小, 期望缩一半, 不断重复即可, 因为随机所以期望 $n\log^2 n$
UPD: 评论区有人说实际上随机二分的期望步数是 $\log_{1. 5} n$
D. 摩拉克斯
给一棵树, 有边权, 求两个点 $x, y$ 使得 $\sum_u a_u\min(dis(u, x), dis(u, y))$ 最小.
显然是子树内外的重心, 赛时是无脑2log, 幻想乡战略游戏的树剖做法可以支持改点权求带权重心, 于是直接拍上一份, 然后求子树内的直接做求子树外的把子树里面点维护的子树大小都设成 $0$ 再求全局重心.
然后更厉害的是树的重心一定在根所在的重链上, 那么求子树内的时候在子树内重链上二分, 子树外的话相当于删掉子树, 此时要么在以根为起点的次重儿子的重链上, 要么还是根开始的重链. 直接在这上面二分是单log, 那我离线遍历链是不是线性.
方法3, dfn中位数一定在重心子树内, 因为它子树大小大于一半, 此题换成带权中位数, 然后倍增着跳找重心.
NOIP2023模拟赛55
A.
求能否把 $n$ 划分成 $k$ 个不同的正整数之积, $T=4000$ 次询问, $n\le 10^9$
爆搜题哈哈
直接搜索, 剪枝是把剩下约数都选上到不到 $k$ 和无论怎么选乘积都大于 $n$.
B. 闪烁之光
有无向图 $Graph(n, m)$, 可以 $q$ 次询问点集 $S$ 的导出子图边数, 请确定这张图.
$n\le 2000, m\le 4000, Q\ge 75000$
降智题, 显然这个数给的是 $m$ 单log, 那你对每个点 $u$ 去二分 $v<u$ 的边 $u\to v$, 此时你已经知道除了 $u$ 以外的所有编号小于 $u$ 的点之间的边所以只问一次就能判断 $u$ 到这个集合中的边了.
C. 反射
有以 $n$ 为根的有根树, 保证父亲编号大于儿子, 对一个排列 $p_{n-1}$, 依次在原树上删掉第 $i$ 条边 $u_i\to v_i$, 然后在一个新图上添加 $(a, b)$, 其中 $a, b$ 分别为 $u_i, v_i$ 各自在原树上的连通块中编号最大的点, 这样会得到另一棵树. 问对所有排列新得到的树有多少种.
$n\le 3000$
先尝试对删边过程dp, 发现很难进行, 因为底下一个点可能会接到祖先链上的很多点很难数. 再考虑最终可能的树的形态, 把每个点到新父亲这条边画到原树上一定是一条祖孙链, 发现合法当且仅当没有两条这样的链相交(可以端点处有交, 可以包含, 不能有一个点的一个端点在另一个链非端点上而另一端点不在).
然后就dp, 设 $f_{u, i}$ 表示 $u$ 的祖先中有 $i$ 个点可以选, 转移时枚举 $u$ 的父亲是这 $i$ 个点中从上往下第 $j$ 个, 则 $u$ 子树的点都不能选比 $j$ 深的, 也就是 $f_{u, i}=\sum_{j\in [1, i]} \prod_v f_{v, j}$ 了.
D. 人赢
给定 $a_n$, 寻找排列 $p_n$ 使得 $\min a_i \mathrm{xor} a_{p_i}$ 最大.
$n\le 5\times 10^5$
找排列等价于找若干个环覆盖, 就是把每个点拆两个点, 让他们完美匹配, 这样保证每个点入度出度各 $1$.
于是问题转化为ABC304G, 见dp
然后在那个题基础上:
NOIP2023模拟赛56
A. 平方
给定 $a_n$, 要求构造 $b_n$ 使得 $\forall i\in[1, n-1], b_ib_{i+1}a_ia_{i+1}$ 为完全平方数. $a, b$ 为整数. 最小化 $\prod_i b_i$
$n\le 10^5, a_i\le 10^6$
居然被这个智障题骗了1h. 脑子不清醒了吧.
一开始想先确定 $c_i=b_ib_{i+1}$ 的值, 但这样很难保证 $b$ 是整数. 考虑对于 $a$ 的一个质因数出现次数先都模 $2$, 然后最后要么所有数都有这个质因数要么都没有(模 $2$ 意义下), 所以直接统计次数模 $2$ 为 $1$ 的数的个数即可.
B. 路径覆盖
题目背景: 给 $n$ 个点的无根树, 你想用若干路径覆盖所有边, 且保证任意一条边恰被覆盖一次. “奇数度点数除以2”——小A同学脱口而出. 既然这题已经被秒了, 你只好重新出一道题.
给定 $Tree(n)$, 有操作 $1$ 覆盖与一个点相连的所有边, 操作 $2$ 覆盖一条路径, 边不能重复覆盖, $q$ 询问若先对 $x$ 用一次操作 $1$, 则最少用几次才能把所有边覆盖恰好一次.$n, q\le 10^5$
换根dp简单题.
你可以直接照着题目背景设状态, 设 $f_{u, 0/1/2}$, $0$ 表示 $u$ 使用 $1$ 操作, $1/2$ 表示不使用 $1$ 操作, 是否考虑 $u$ 的父边这条边的情况下, 子树内奇度点的个数. 转移的话 $0$ 是直接累加儿子的 $2$ 再加 $2$ 表示一次操作, $1/2$ 是先把子树儿子们的 $0/1$ 卷起来(选择 $0$ 不增加 $u$ 的度数, 选择 $1$ 增加一个度数, 用背包合并), 然后再根据 $1/2$ 是否增加 $u$ 的度数去合并.
换根同理, 你就设 $g_{u, 0/1/2}$ 表示 $u$ 子树外的即可. 需要预处理前后缀儿子背包合并结果.
C. 条占
左右各 $n$ 点的二分图, 有 $m$ 次加边每次加入 $w_i$ 条 $u_i\to v_i$, $a_n, b_n$, 表示要求左边前 $i$ 个点最多连出 $a_i$ 条边, 右边前 $i$ 个点最多连 $b_i$ 条边, 求最多能加多少边.
$n, m\le 4\times 10^6$
考虑一个网络流, 两边先建两排点 $i, i’$, 认为 $s=n+1, t=(n+1)’$, 则 $i+1\stackrel{a_i, 0}{\longrightarrow} i$, $i’\stackrel{a_i, 0}{\longrightarrow} (i+1)’$, 若有 $(u_i, v_i, w_i)$ 则 $u_i\stackrel{w_i, 1}{\longrightarrow} v_i’$
然后要模拟费用流, 考虑动态加边模拟, 按照 $u$ 从小到大加入一条边, 你发现此时不会形成负环: 成环必定跨过由 $i\to i’$ 和 $i’\to i$ 相同次数, 也就是说环一定权值为 $0$, 并且因为 $u$ 从小到大变化, 去掉这个环之后的增广路一定已经被增广, 于是这是不流反悔边的模拟费用流.
于是只要维护后缀减后缀min, 直接上线段树维护! TLE.
麻了, 另一个做法是最小割加扫描线, 也就是断的边就是
D. 重逢
todo
