2022/04/14 做题记录

Posted on Disqus:

最小树形图

模版。

code: /code/2022.4.14/ac8994.cpp

Kpm的MC密码

一开始写了个 trie 上线段树合并，实际上每个点开个 vector 存所有串就行，反正总长度是 O(n) 的。。。。

code: /code/2022.4.14/bz3439.cpp

A simple rmq problem

可以把每个点转化成 pre(i),nxt(i),i 其中 pre(i),nxt(i) 为 aia_i 的上一次，下一次出现的位置（没有就是 0 , n+1)，之后询问就是矩形查询。

code: /code/2022.4.14/bz3489.cpp

志愿者招募

原点向 1 连流量为 INFINF ，费用为0的边，i 向 i+1 连流量为 INF−aiINF-a_i ，费用为0的边，每类志愿者从 s 向 t+1 连流量为 INF，费用为 c 的边。

因为保证有解，那么我们志愿者边按照最优解流（选几个就流几），用 i 向 i+1 的边流 INF-第i天实际的志愿者人数，可以满足流量平衡且最大流为 INF，而最大流不可能大于 INF。

而对于任何一种满流的方案，我们都可以对应一种选志愿者的方案，第 i 天的实际人数就是 INF- i 向 i+1 的边的流量，这个数不可能小于 aia_i,于是跑最小费用最大流即可。

code: /code/2022.4.14/P3980.cpp

albus就是要第一个出场

设这个序列的线性基大小为 S，那么对于每一个能被现形基表示的数，它异或上剩下的数的 2n−S2^{n-S} 种取法，每一种得到的数都一定能被现性基唯一表示，于是每一个能被线性基表示的数都会出现 2n−S2^{n-S} 次，于是在线性基从高到低考虑即可。

code: /code/2022.4.14/P4869.cpp