当前位置：首页 > news >正文

做题笔记6

news 2025/9/25 15:32:15

小王精心做题笔记，堂堂连载！

5.21

昨天讲的网络流

连边时都是形如 $u\rightarrow v,(cap,cost)$ 的格式

CF2046D For the Emperor!

首先缩点，一下对缩点后的 DAG 考虑，直接费用流建模

考虑记一个很大的数 $B$，我们每经过一个点，让费用减去 $B$，而再放一个计划的时候，使费用加上一，这样我们肯定是优先遍历所有的点，最后只需要算一个 $n\times B+flow$ 就行了

对于每个点 $u$，拆成三个点 $F_u$、$P_u$、$Q_u$，用 $F_u$ 来限制这个点的初始流量，那么直接 $S\rightarrow F_u,(a_u,0)$。$P_u$、$Q_u$ 为 $u$ 的出点和入点，连 $P_u \rightarrow Q_u$，考虑用这条边来刻画这个点是不是被经过，连出两条边，一条为 $(1,-B)$，另一条为 $(inf,0)$，这样连就是相当于限制第一次经过这个点时才有 $-B$ 的贡献，而以后是费用不变的。另外，连 $F_u \rightarrow P_u,(1,1)$，连 $F_u \rightarrow Q_u,(inf,0)$，若 $u$，$v$ 有边，那么 $Q_u \rightarrow P_u,(inf,0)$

QOJ9224 Express Eviction

首先显然可以把左上到右下的一条路径转化成左下到右上的一组最小割，而且我们肯定只会考虑那些有人的格子，首先拆点，可以考虑把有角相交的格子连边，在边界上的和源汇相连（下边界左边界连源，上边界右边界连汇）

发现这样其实是存在问题的，考虑一个 $3\times 3$ 宫格的对角，如果他们挡在我们的割边路径上，那肯定会造成至少 $1$ 的贡献，而且不在边界上的 $2\times 2$ 的对角肯定也会有 $2$ 的贡献

那如何建图呢？把切比雪夫距离小于 $2$ 的格子相互连边，实际上，这是因为如果我们考虑每一对格子，实际上只有他们所破坏掉的边是连通的才是有贡献的

这样再跑最小割就是对的

[ABC397G] Maximize Distance

当最短距离的最大值为 $1$ 时，实际上就是跑一遍最小割，这启发我们从最小割考虑这个问题

形式化的，我们可以记 $01$ 变量 $x_{i,j}$ 表示从 $1$ 走到 $i$ 这个点的最短路长度是否 $\ge j$，那么我们可以直接连边 $(i,j)\rightarrow (i,j+1),inf$，若 $u,v$ 有边，则 $(u,j)\rightarrow (v,j),1$，$(u,j)\rightarrow (v,j),inf$，我们用这两条边来刻画最短路的转移

这样我们是不好求出答案的，考虑一下二分出答案 $d$，我们钦定 $x_{1,1}=0,x_{n,d}=1$，连一下源汇就行了

[ARC142E] Pairing Wizards

首先发现这个绝对值很搞笑，因为我们可以把 $A_u$ 调整到 $a_i$，使得满足限制的同时使得答案更优，然后对于每一组 $u,v$，我们肯定有 $A_u\ge \min(b_u,b_v),A_v\ge min(b_u,b_v)$，我们把 $a_u$ 对这些值取 $\max$，考虑最终更新后的 $a_i$，对于 $a_u\ge b_u,a_v\ge b_v$，我们根本不需要考虑这一类情况，而 $a_u < b_u,a_v<b_v$ 这种情况肯定是不合法的，于是我们需要考虑的只剩下 $a_u < b_u,a_v\ge b_v $ 了

我们考虑把限制转化成 $a_u\ge \max(b_u,b_v)$ 或 $a_v\ge \max(b_u,b_v)$，那么实际上要刻画的就是一个“若 $a<x$，则 $b\ge y$”的命题，可以考虑切糕模型，只需要把 $a_u \ge b_u$ 的那一组点的边倒过来连，就可以刻画这个限制了

CF1427G One Billion Shades of Grey

首先考虑值域为 $[1,2]$ 的情况，我们直接把权值为 $1$ 的点与源点连边，权值为 $2$ 的与汇点连边，四联通的点之间相互连双向边，直接跑最小割

我们填的数肯定是在边界上出现过的数，从大到小排序之后的数组为 $v_1\sim v_n$

这里我们有一个结论，对于每一个 $i$，把小于等于 $v_i$ 的点看成 $1$，大于 $v_i$ 的点看成 $2$，跑一遍值域是 $[1,2]$ 的情况，再加起来就是答案

暂时不给出证明

这样复杂度太高，考虑退流（若要删掉 $(u,v)$ 这条边，直接跑一边 $(v,u)$ 的最大流，然后把总流量减去这么多，然后再删掉这条边即可，而退流可以把所有要删的边都删掉，在最后求一遍 $(s,t)$ 的最大流正确性也是对的）

最小值之和

对于这种涉及区间最小值的题，我们可以考虑枚举最小值 $k$，可以发现，如果我们把所有的数都减去一个 $k$，那么有 $d_{l,r}\leftarrow d_{l,r}-k$，而所有的 $f'$ 都会有 $f'\leftarrow f'-k\times (n-1)$，如果这个最小值在 $x$ 这个位置，那这时候的 $f'_{1}\sim f'_{x}$ 只和 $f_{1}\sim f_{x}$ 有关了，那我们可以考虑区间 dp

记 $f_{l,r,k}$ 表示令 $\forall i\in [l,r],g'_{i}\leftarrow f'_i-k$，能否构造出 $g$ 使得 $g$ 与 $g;$ 满足 $f$ 与 $f'$ 的限制

转移时考虑枚举最小值在哪个位置即可

这样状态数就是 $\mathcal{O}(n^2V)$ 的，显然不能接受，考虑优化状态，发现如果使得区间中的 $f$ 都加一，那 $f'$ 就会加上 $r-l$，那么有 $f_{l,r,k}\Rightarrow f_{l,r,k-(r-l)}$ 那么可以记 $g_{l,r,k}$ 为最大的 $p\equiv k \pmod {r-l} $ 使得 $f_{l,r,k}=1$，这样使得状态数降为了 $\mathcal{O}(n^3)$

如何转移？枚举 $i,p,q$，将 $g_{l,i,p}$ 和 $g_{i+1,r,q}$ 合并，我们要做的就是找到最小的 $x$ 使得 $x\equiv g_{l,i,p}\pmod{l-i} $ 同时 $x\equiv g_{i+1,r,q}\pmod{r-i+1} $，并且满足 $x\ge \max(g_{l,i,p},g_{i+1,r,q})$，$x$ 可以快速求出

令 $t=\text{lcm}(i-l,r-i+1)$，则会对于所有的 $k\ge 0$，$g_{l,r,(x+k\times t)\mod (r-l)}$ 对 $x+k\times t$ 取 $\max$，可以用同余最短路转移做到 $\mathcal{O}(n^5)$

5.22

模拟赛

困

T1

直接考虑一手 cayley，如果已经有环，那我们的答案就是 $\prod\limits_{i=1}^{k}siz_i\times n^{k-2}$，$k$ 是连通块个数，$siz_i$ 是每个连通块的大小

然后考虑没有环的情况，这时候我们需要造出来一个环，那把这个环连接起来的其他的连通块当成一个大的连通块，接着做没有环的情况的计数就行了

于是可以记 $f_{i,j}$ 表示我当前环上有 $i$ 个点，这个环连成连通块的 $siz$ 之和为 $j$，转移是简单的，这样可以做到 $\mathcal{O}(n^3)$

我们发现只有最后算答案的时候会用到第二维，直接记一维这个显然是有点浪费，于是考虑记 $g_{i}=\sum f_{i,j}\times j$，$h_i=\sum f_{i,j}$，然后转移就变成了 $g_i\leftarrow g_i+g_{i-1}\times siz+h_{i-1}\times siz^2$，$h_i\leftarrow h_i+h_{i-1}\times siz$

那就优化到 $\mathcal{O}(n^2)$ 了，感觉这一步还是挺自然的，为什么没想到呢？

T2

换维，换维，换维，换维，换维，换维

考虑交换时间维和下标维，那我们的操作就变成了在 $l$ 时间对 $i$ 处的位置加上一个 $x$，并在 $r+1$ 处撤销掉，询问时就是问在 $x$ 时刻查询长度为 $i$ 的前缀的答案，用括号序列去刻画两种操作，把第一种操作看成 $($，第二种看成 $)$，并且第一种有权值，那么我们要求的实际上就是最后前缀 $1\sim i$ 组成的括号序列最后无法匹配的括号的权值之和，可以用单侧递归线段树解决

思路可能确实比较自然，怎么被黄翊轩秒了？

T3

~~先不写了，感觉还挺有意思，可能没那么难~~

补了，loj 没过，有一些 YES 1 YES 2 啥的判错了，回来再改吧

(一)

若 $\text{dis}(u,v)=k$，则有 $\text{color}_u=\text{color}_v$

证明显然，若 $u\rightarrow v$ 的路径是形如 $u\rightarrow x\rightarrow y\rightarrow v$，其中 $u$、$x$ 之间有连边，$y$、$v$ 之间有连边，则必须满足 $\text{sum}(u,y)=1,\text{sum}(x,v)=1$，其中 $\text{sum}(a,b)$ 是树上 $a$ 到 $b$ 的 $\text{color}$ 之和，则有 $\text{sum}(x,y)+\text{color}_u=\text{sum}(x,y)+\text{color}_v$，则有 $\text{color}_u=\text{color}_v$

那么考虑拉出来一个直径 $(p,q)$，那么这个直径上 $\text{dis}(p,i)$ 膜 $k$ 相同的点颜色都是相同的，那么可以把这条直径划分成 $k$ 个等价类，我们染色肯定是选择其中一个等价类把这个等价类中的所有点染黑

(二)

对于一个包含 $k$ 个点的限制路径 $(u,v)$，要求 $\text{sum}(u,v)=1$，若 $(u,v)\cap(p,q)\ne \emptyset$ 且 $u\notin (p,q)$ 且 $v\notin (p,q)$，则 $(u,v)$ 的限制是没用的，或者说 $(u,v)$ 的限制可以用其他的限制去表示

可以记 $\text{top}(u)$ 为与 $u$ 距离最近的那个点，如果存在一条路径形如 $u\rightarrow \text{top}(u)\rightarrow \text{top}(v)\rightarrow v$，$u$ 在左侧，$v$ 在右侧，那么肯定在直径上存在一条路径 $u'\rightarrow v'$，$u'$ 在 $\text{top}(u)$ 左侧，$v'$ 在 $\text{top}(v)$ 右侧，记 $\text{sum}(u',\text{top}(u))=a$，$\text{sum}(\text{top}(u),\text{top}(v))-\text{color}_{\text{top}(u)}-\text{color}_{\text{top}(v)}=b,\text{sum}(v',\text{top}(v))=c,\text{sum}(u,\text{top}(u))=d,\text{sum}(v,\text{top}(v'))=e$，则有 $a+b+c=1,d+b+c=1,a+b+e=1$，可以得出 $d+b+e=1$，也就说明了我们只需要考虑一个端点在直径上的或者无交的路径

那么我们可以首先考虑第一类路径，即有且仅有一个端点在直径上的路径

(三)

刚才给直径上的点划分了等价类，现在考虑把其他的点也划分上等价类，先考虑给每个点分类，记 $c_u=[h_u+\text{dis}(u,p)\ge k-1]+[h_u+\text{dis}(u,q)\ge k-1]$，其中 $h_u$ 是 $u$ 子树（越靠近直径深度越浅）中，与 $u$ 的最远距离

若 $c_u=0$，则 $u$ 是无用的，把 $u$ 删掉，把所有答案都 $\times 2$ 即可
若 $c_u=1$，那么称 $u$ 为“一度点”
若 $c_u=2$，那么称 $u$ 为“二度点”

以下其实可以把一度点看成是“计数”，二度点看成是“限制”

然后考虑有用的点划分等价类，注意到若 $\max(\text{dis}(u,q),\text{dis}(u,p))\ge k-1$，那么 $u$ 可以每次向上跳 $k$，一直跳到直径上，这样 $k$ 会有相应的等价类，于是对于点 $u$，记 $\text{class}_p(u)=\text{dis}(u,p) \bmod k$，记 $\text{class}_q(u)=(\text{dis}(p,q)-\text{dis}(u,q) )\bmod k$

发现其实 $\text{class}_p(u)$ 和 $\text{class}_q(u)$ 可能会不同，会导致我们的 $\text{class}$ 并不是一个良定义，这是因为当我们再跳一步跳到直径上的时候，可以往 $p$ 跳也可以往 $q$ 跳，那 $u$ 就有可能同时属于两个类，那这两个类其实也是等价的，也就是说他们最后的颜色肯定得相同，而我们颜色为 $1$ 的等价类最多只有一个，那只要强制这两个类的颜色都为 $0$ 即可

接下来对于一度点和二度点分别考虑就行了

(四)

对于一度点，去掉所有的零度点之后，一度点在树上肯定是一些子树，我们现在去考虑其中一颗子树，为了方便，我们先认为对于这个子树中的每个点 $x$，都有 $\text{dis}(x,p)\ge \text{dis}(x,q)$

考虑一个一度点 $u$，如果 $\text{dis}(u,p) = k-1$，那么 $(u,p)$ 这条路径上有且仅有一个黑点，而且我们可以说明，对于 $\text{dis}>k-1$ 的那些点，这些点的颜色都是可以被 $\text{dis}\le k-1$ 的那些点以及 $p$ 到这个一度点的子树的根的路径唯一确定的，这个比较显然，直接往上跳就行了

那么我们现在只去考虑 $\text{dis}\le k-1$ 的那些点，现在我们要满足，对于所有的叶子，其到 $p$ 的那条链上有且仅有一个黑点，而且对于这个子树中所有的距离为 $k-1$ 的点对，他们的路径上也有且仅有一个黑点

现在我们说，第二种路径根本不存在，证明也是简单的

记这颗子树的根为 $rt$，记 $\text{dis}(rt,p)=x$，考虑子树中的任意一个点 $u$，记 $\text{dis}(rt,u)=y$，则此时有 $x+y\le k-1,x-1\ge y+1$，而如果存在一种这样的路径，那必然存在一个 $y$ 满足 $2y\ge k-1$，由 $2y\ge k-1,x+y\le k-1$ 可以推出 $x\le k-1$，此时则不满足 $x-1\ge y+1$，则不存在第二种路径

这样计算答案也是简单的，若 $(p,fa_{rt})$ 上存在一个黑点，那染色方案是唯一确定的，那现在就是要数一颗树中，对于所有的叶子，其到根链上都有且仅有一个黑点，也就是黑点之间不存在祖孙关系，计数是容易的，记这个方案数为 $F$，那么 $F$ 会造成贡献的等价类不可能在 $(p,fa_{rt})$ 中出现，由于 $\text{dis}(p,rt)\le k-1$，而且这些等价类又是连续的，所以我们的 $F$ 的贡献肯定是一段膜意义下的区间，注意，这里只有一段，我们打区间乘法标记可以轻松解决

这样一度点就讨论完了，接下来讨论二度点的部分

(五)

这里对于一个二度点，我们说他要么属于一个等价类，要么他必须染白，也就是说若要染色的等价类已经确定，那这个点要染的颜色实际上也被唯一确定

如果一个点 $u$ 满足 $u$ 的子树内存在一个点 $v$，其中 $\text{dis}(p,v)\ge k-1$ 且 $\text{dis}(q,v)\ge k-1$，而且 $\text{dis}(\text{top}(v),v)\le \left\lfloor\frac{k-1}{2} \right \rfloor$，则 $u$ 必须染白

考虑 $v$ 向 $p$ 延伸到的点 $p'$，满足 $\text{dis}(v,p')=k-1$，$v$ 向 $q$ 延伸到的点 $q'$，满足 $\text{dis}(v,q')=k-1$，这时若 $u$ 为黑色，则 $(u,p')$，$(u,q')$ 上的其他点肯定都是白色，而因为 $\text{dis}(\text{top}(v),v)\le \left\lfloor\frac{k-1}{2} \right \rfloor$，所以肯定有 $\text{dis}(p',q')\ge k-1$，这时候连续 $k$ 个点都是白色，不合法，所以 $u$ 显然不能染黑色

现在考虑证明最上面的结论，直接进行分讨

若 $\text{dis}(\text{top}(u),u)> \left\lfloor\frac{k-1}{2} \right \rfloor$，那么 $u$ 会属于某一个等价类

$\text{dis}(u,p)\ge 2\times \left\lfloor\frac{k-1}{2} \right \rfloor> k-1$，$u$ 可以向上跳到一个等价类

若 $\text{dis}(\text{top}(u),u)\le \left\lfloor\frac{k-1}{2} \right \rfloor$，那么 $u$ 必须染白

不再赘述，已经提及此方面的证明

这样我们就说明了每个二度点都是可以被唯一确定的

(六)

上面好像只考虑了与直径有交的那些路径，与直径无交的路径怎么办呢

容易说明，与直径无交的路径上的点都是二度点

直接考虑任意一个叶子 $u$，他的 $h$ 值肯定为 $0$，而此时若存在另一个点 $v$ 满足 $\text{dis}(u,v)=k-1$，为了满足 $(p,q)$ 为直径，则肯定有 $\text{dis}(p,u)\ge \text{dis}(u,v)=k-1,\text{dis}(q,u)\ge \text{dis}(u,v)=k-1$，加上 $h_u$ 肯定一样，而其父亲的 $h_u+\text{dis}(u,p/q)$ 肯定更大，得证

这时候对于一个二度点 $u$，记其子树中的非严格最长链为 $f$，次长链为 $s$，若 $f+s>k-1$，他向下可以伸出两条在不同子树中的路径，如果其中一条路径上的等价类组成的集合为 $S$，则此时肯定要对于染色的等价类 $i$（另一条路径上的等价类是对称的），满足 $i\notin S$，考虑最严的限制，如果我们有这两条路径长度不同，肯定不会考虑更长的那个路径上的只存在了一次的等价类，这时我们取次长链肯定限制是最紧的，这样会对 $\mathcal{O}(1)$ 个区间产生限制，也是容易做的

注意上述情况还要分别考虑 $\text{class}_p$ 和 $\text{class}_q$

可能这一部分还有细节问题

(七)

做法，对所有点分类，对于零度点，让答案乘二，对于一度点，计算 $F$ 并进行一个区间乘法，对于二度点，限制一些区间不能选

细节有很多

CF1870G MEXanization

只会根号，先把根号说了吧

首先考虑二分，转成判定性问题，然后我们从后往前扫，如果我们想要构造出一个 $x$，那么必须在最后的时候存在 $0\sim x-1$，首先把与当前值域无关的数都变成 $0$ 肯定是最优的，可以考虑从后往前扫，记 $n_i$ 表示需要多少个 $i$ 才能构造出 $x$，记 $c_i$ 表示我们现在有多少个 $i$

我们扫到一个 $i$ 时，按一下几种情况讨论

若 $c_i<n_i$，则令 $\forall j<i,n_j\leftarrow n_j+n_i-c_i$
若 $c_i\ge n_i$，则令 $c_0\leftarrow c_0+c_i-n_i$

最后判断一下 $c_0$ 与 $n_0$ 的大小关系就行了

那这样可以做到 $\mathcal{O}(n^2\log n)$ ？

二分没必要，因为答案除了第一个以外显然是单调的，然后又发现其实 $c_i<n_i$ 的情况只有 $\mathcal{O}(\sqrt{n})$ 个，这是因为我们每次会给 $\sum\limits_{j<i} n_j$ 至少加上 $i$，但是我们 $\sum\limits_{j<i} n_j>n$ 的话肯定是不合法的，那这样就是自然根号

这样直接用线段树维护，check 的时候，每次找到一个满足 $c_i<n_i$ 的位置，一直做这个过程，复杂度就是 $\mathcal{O}(n\sqrt n\log n)$，过不去

使用一些在线段树上 dfs 剪枝的方法可以做到把 $\log n$ 去掉，若 $n_r\times r>n$，直接停止递归然后终止过程，若 $n_r\le mn_{l,r}$，$mn_{l,r}$ 即当前区间中的最小值，那么这时候我们直接返回就行，先递归右儿子再递归左儿子，这样每层递归的节点不超过 $\mathcal{O}(\sqrt{\frac{n}{2^d}})$，因为如果对于第 $d$ 层的第 $p$ 个节点，如果这个节点中存在关键点，那么至少会给 $\sum n_j$ 加上 $p\times 2^d$，这样一层复杂度就是 $\mathcal{O}(\sqrt{\frac{n}{2^d}})$ 级别，求和就是 $\mathcal{O}(\sqrt n)$

5.23

CF1610G AmShZ Wins a Bet

好题啊

首先我们每次删除的一对相邻的括号肯定更优，因为考虑对于一个右括号，如果存在多个左括号与他匹配，如 ()(() 这时我们考虑最右边那个右括号，有三个左括号可以和他配对并删除，删除越靠前的左括号并不优，因为这时候右边存在一个其他的 )，我们删除之后会使得这个括号左移，造成了字典序变大，肯定是不优的，那我们肯定删除靠后的左括号更优，然后对于 ())) 这种情况，我们让任何一个右括号与左括号匹配都是等价的，那不妨直接让最左边的右括号消除掉，这样每次删除的就是相邻的括号了

那这样我们最后的串肯定是原串删除一些连续的括号匹配串，于是可以考虑 dp，记 $f_i$ 为从后往前考虑到了第 $i$ 个位置，字典序最小的串是什么，接着记 $r_i$ 为 $i$ 到 $r_i$ 为一段合法的括号匹配，那么有转移 $f_i=\max(f_{r_i},s_i+f_{i+1})$，其中 $+$ 表示的是字符串的拼接，$s_i$ 为 $i$ 处的字符，这样我们可以轻松做到 $\mathcal{O}(n^2)$，考虑优化

如果直接做，需要一个可持久化平衡树维护哈希值，复杂度是 $\mathcal{O}(nlog^2n)$ 的，但是我们还可以考虑一个经典的技巧，把可持久化结构建成树，可以发现 $f_i$ 就是这样一个树形结构，而且每次只会添加一个字符

容易考虑到树上倍增维护哈希值，本来要做的平衡树上二分可以直接倍增跳父亲，这样复杂度是 $\mathcal{O}(n\log n)$ 的

[ABC306Ex] Balance Scale

简单题，检验学习成果的时候到了

考虑没有 = 的情况，实际上就是定向数 DAG，加上 = 实际上就是把一些点缩起来了

我们做这类计数的时候都是先枚举出度为 $0$ 的独立集 $T$ 做分层计数，在这里的容斥系数是 $(-1)^{|T|+1}$
但是我们枚举出来的 $T$ 并不一定是独立集，其实这其中是有连边的，那我们实际上是钦定了这些边是 =，也就是说，我们只需要记录下来 $T$ 的导出子图的连通块的数量，记作 $c_{T}$，直接 dp 就行了

显然有转移 $f_{S}=\sum\limits_{T\subseteq S}(-1)^{C_{T}+1}f_{S-T}$，直接做是 $\mathcal{O}(3^n)$，也容易做一个半在线的子集卷积做到 $\mathcal{O}(2^nn^2)$

5.24

模拟赛

T1

幽默了

对于阶乘，有 $i!=i(i-1)!$，即 $i!$ 是 $(i-1)!$ 的倍数，所以可以考虑一个进制状物，每一个数都有唯一的表示方法，那我们发现答案肯定就是形如 $1!+2!+2!+3!+3!+3!+4!+4!+4!+4!...$，可以二分出最大的那个数，这个数是 $\mathcal{O}(n^{\frac{1}{3}})$ 级别的，接着二分这个数出现了多少次，可以预处理出来 $\sum\limits_{i=1}^k i!\times i$，总复杂度容易做到 $\mathcal{O}(T\log n)$，做到线性也很简单，不详说了

T2

。

结论：对于一条路径 $i\rightarrow j$，他最后的高度肯定是形如一些高度相同的连续段拼起来，而这个高度肯定是这个连续段中的某一个

于是可以记 $f_{i,j}$ 表示从 $i$ 开始，高度都为 $h_i$，走到 $j$ 的最短路

怎么把这些 $f$ 拼起来？有一个经典的方法，我们只考虑那些 $h_i$ 不动的点之间的转移，把不动点 $i$ 走到不动点 $j$ 的最小代价记为 $c_{i,j}$，这样我们可以简单地把 $c$ 拼接起来

需要注意的是，我们的起点和终点不一定是不动点

这样可以做到 $\mathcal{O}(n^3)$

T3

不会

P9839 四暗刻单骑

想打雀了，感觉不是难题

首先发现赢牌肯定靠自摸，因为如果是对家打给的，那肯定手中的两张牌是一样的，这时候对家已经能自摸了

只考虑自摸，可以发现我们最后的策略一定是手里握着一张牌一直不动，发现这时候对家如果摸到一张一样的，他一定不会打出去，这样的话两家的策略都是固定的，只需要等到第三张出现，这时候便可以判断是赢/输/平局

这样 $\mathcal{O}(nq)$ 的做法就呼之欲出了，直接从前往后遍历，查询赢牌的最小时刻即可

但是这样会出现问题，如果某人想赢牌而导致输牌，肯定是不优的，那可以考虑另外一个人尽量平局，若前者还能赢，那肯定是必胜的，若两者不存在必胜则是平局

优化到 $\mathcal{O}((n+q)\log n)$ 其实是简单的，直接扫描线扫右端点，考虑每个点 $i$ 不动，能赢牌的最小时刻，然后查询区间最小值就行了，这样我们每张牌其实只有 $\mathcal{O}(1)$ 次变化，每次要做的就是单点修改，查询区间最小值，可以用线段树简单维护

5.26

讲了很多背包

[THUPC 2023 初赛] 背包

令人感慨，当年做这题还是贺的题解

完全背包是否有解，即 $\sum a_ix_i=M$，其中 $a_i,M$ 给定，问是否存在一组 $x$ 满足 $x_i\in [0,\infty]$，有同余最短路做法，找出来最小的 $a_i$，记为 $m$，直接做膜 $m$ 意义下的最短路，复杂度就是 $\mathcal{O}(nm\log )$

这里介绍一种同余最短路上的转圈技巧，如果我们松弛的时候不会连续松弛同一个点，那么就可以用这个转圈技巧，也就是说，图上不存在负环，当我们加入物品 $a_i$ 时，这时候可以拉出来那 $\gcd(m,a_i)$ 个环，直接绕着这个环走两圈，便可以全都转移到了，这样复杂度是 $\mathcal{O}(nm)$ 的

回到这个题，加上权值，也就是求 $\sum x_iv_i$ 最大，我们可以考虑把性价比最高的物当成基准物品，也就是 $\frac{v_i}{a_i}$ 最大的，记基准物品的 $a_i$ 为 $m$，其 $v_i$ 为 $val$，我们便不会重复松弛同一个点，而且这时候对于询问 $q$，若 $q\equiv p\pmod{m}$，其中 $0\le p< m$，那么 $f_q=f_p+\frac{q-p}{m}\times val$，这样只需要找到这个 $p$ 的最长路即可，那么有转移 $f_j+v_i-\left\lfloor \frac{j+a_i}{m}\times val\right\rfloor \rightarrow f_{(j+a_i)\bmod m}$，这样带权的情况我们也可以轻松做到 $\mathcal{O}(nm)$

P4389 付公主的背包

有点无聊

$\forall j\in [1,m]$，求 $[x^j]F=\prod\limits_{i=1}^{n} \frac{1}{1-x^{a_i}}$

取对数，则

\[ \begin{matrix}\ln F= \sum\limits_{i=1}^{n}\ln \frac{1}{1-x^{a_i}} \\= -\sum\limits_{i=1}^{n} \ln (1-x^{a_i})\\ \end{matrix}\]

考虑 $\ln(1+x)$ 的泰勒展开，即 $\ln(1+x)=\sum\limits_{i\ge 1}(-1)^{i+1} \frac{x^i}{i}$，那就有 $\ln(1-x)=-\sum\limits_{i\ge1}\frac{x^i}{i}$

那么则有

\[ \begin{matrix}\ln F= -\sum\limits_{i=1}^{n} \ln (1-x^{a_i})\\=\sum\limits_{i=1}^{n}\sum\limits_{j\ge 1} \frac{x^{a_ij}}{j} \\ \end{matrix}\]

而我们只需要求前 $m+1$ 项的系数值，因此只需要计算 $\ln F$ 在膜 $x^{m+1}$ 意义下的系数，即 $\ln F\equiv \sum\limits_{i=1}^{n}\sum\limits_{j=1}^{\left\lfloor\frac{m}{i}\right\rfloor} x^{ij}\times \frac{cnt_i}{j} \pmod x^{m+1}$，其中 $cnt_i=\sum\limits_{j=1}^n [a_j=i]$，求 $\ln F$ 容易做到 $\mathcal{O}(m\log m)$，只需要计算 $\ln F$ 的 $\exp$ 即可，这样复杂度就是 $\mathcal{O}(m\log m)$ 的

CF1290F Making Shapes

这个数位 dp 还是挺有启发性的

有一个显然的事情，能确定最后凸包形状的，只和每个向量的数量有关，因为对这些向量进行极角排序之后，其在凸包上的顺序是确定的

那么我们只需要统计所有合法的序列 $c$，其中 $c_i$ 是第 $i$ 个向量的出现次数，满足 $\sum c_ix_i=0,\sum c_iy_i=0$，而且还要满足 $x$ 方向和 $y$ 方向上的极差 $\le m$，其实就是 $-\sum\limits_{x_i<0} c_ix_i\le m,-\sum\limits_{y_i<0} c_iy_i\le m$，而 $\sum c_ix_i=0,\sum c_iy_i=0$ 可以进一步表示成 $\sum\limits_{x_i<0} c_ix_i=\sum\limits_{x_i>0} c_ix_i,\sum\limits_{y_i<0} c_iy_i=\sum\limits_{y_i>0} c_iy_i$

由于我们的 $nV$ 只有 $20$，那么可以考虑数位 dp，考虑去对每一个二进制数 $c$ 计数，则我们需要记录的信息有：

当前枚举到的位
$\sum\limits_{x_i>0}c_ix_i$ 的进位
$\sum\limits_{y_i>0}c_iy_i$ 的进位
$\sum\limits_{x_i<0}c_ix_i$ 的进位
$\sum\limits_{y_i<0}c_iy_i$ 的进位
只考虑所有枚举过的位 $\sum\limits_{x_i<0}c_ix_i$ 是否 $\le m$
只考虑所有枚举过的位 $\sum\limits_{y_i<0}c_iy_i$ 是否 $\le m$

转移时，我们只需要枚举每个二进制数 $c$ 当前位的值是多少就行了，这样总复杂度是 $\mathcal{O}(2^n(nV)^4\log m)$

PermuTree (hard version)

好题！

首先每个子树的问题显然是独立的，因为我们只关心子树内的相对顺序，那这时候我们实际上是要解决若干个子问题，每个子问题都形如把所有点元素划分到两个集合中，原来在同一个集合中的元素互相没有贡献，原先不在同一个集合中且划分后不在同一个集合中的元素对有 $1$ 的贡献，要求答案最大

我们可以说明的是，每个原集合中的元素在划分之后肯定还是属于同一个集合，可以通过调整来简单说明

这样就是让我们求 $\max (\sum\limits_{i\in S} a_i)(\sum\limits_{i\in T} a_i)$

考虑直接背包，我们不同的 $a_i$ 是自然根号级别的，直接二进制拆分然后做部分背包看起来是 $\mathcal{O}(\frac{n\sqrt{n}\log n}{w})$ 的，但是我们可以说明这个做法不带 $\log$

记 $S_j$ 为能拆分出来 $2^j$ 的那些物品的下标集合，则有 $\sum\limits_{i\in S_j}2^j\times a_i\le n \Rightarrow \sum\limits_{i\in S_j}a_i\le \frac{n}{2^j}$，又因为 $a_i$ 互不相同，所以 $|S_j|\le \sqrt{\frac{2n}{2^j}}$，那 $\sum\limits_{j}|S_j|\le \sum\limits_{j}\sqrt{\frac{2n}{2^j}}=\sqrt{2n}\times \sum\limits_{j}\frac{1}{\sqrt{2^j}}$，容易说明，后面那个级数是收敛的，那我们就证明了一共只有 $\mathcal{O}(n\sqrt n)$ 个物品

这样我们对于每个子问题可以做到 $\mathcal{O}(\frac{n\sqrt n}{w})$，多个问题该怎么办呢？

容易发现，如果对于一个子树 $u$，存在一个儿子 $v$，满足 $siz_v\times 2\ge siz_u-1$，那么我们最优的方案肯定是把这个儿子划分到一个集合中，其他的所有儿子划分到另一个集合中，这样我们每次的 $siz$ 肯定会减半，那这样我们复杂度最坏的情况下其实就是 $T(n)=2T(\frac{n}{2})+\mathcal{O}(\frac{n\sqrt n}{w})=\mathcal{O}(\frac{n\sqrt n}{w})$ 容易用主定理分析得到

这样就做完了，总复杂度是 $\mathcal{O}(\frac{n\sqrt n}{w})$ 的

gym101064L

经典题了

完全背包，但是 $V$ 比较小，若要求 $f(n)$，我们肯定可以把 $n$ 分成两半，然后再合并，这样两边的容量是在区间 $[\frac{n}{2}-V,\frac{n}{2}+V]$ 之间的，这样我们去递归求解，最后求出来容量小于等于 $3V$ 的完全背包就行了，这样复杂度是 $\mathcal{O}(V^2\log m)$ 的

qoj9870

直接给所有的 $a_i$ 减去 $\left\lfloor\frac{m}{n} \right\rfloor$，然后 $m$ 减去 $n\times\left\lfloor\frac{m}{n} \right\rfloor$，这样之后 $m\in [0,n]$，而 $a_i\in [-n,n]$，大大减小了 $m$ 的范围，显然存在一种排列方案使得所有前缀和在 $[-n,n]$ 中，于是我们在做多项式快速幂的时候只需要保留 $\mathcal{O}(n)$ 个值做卷积就可以了，复杂度 $\mathcal{O}(n\log^2 n)$