事已至此，当然是选择原谅啦。
寻宝游戏
毛：我我我我是不是出得太简单了？？？
HNOI 有没有比这更简单的题啊？？
单独考虑一个询问，如果这一位是 $1$，那么最后一个 $|1$必须在 $\&0$后面，反之在前面。
把 $\&$看成 $1$，$|$看成 $0$，第 $i$位的数字表示第 $i$个串前的运算符号。
将第 $i$位的数字提取出来，则使这一位为 $1$的所有运算符的 $01$串的字典序小于这一位的数字构成的字典序。
于是我们处理一下每一位 $01$串的字典序判断一下有没有解计算一下有多少解就好了
(表面笑嘻嘻内心 mmp.jpg)
转盘
有一个显然也不显然的的结论：答案一定是在某一点时待到它出现然后一路走到底。因为每个点总不会遛两遍，否则可以从它开始；那么走到一个点总是要等它出现，这跟等其中最晚的那个点出现是等价的。
所以我们是在求 $Min_{i=1}^N \{Max_{j=i}^{i+N-1}(T_j – j + i + N – 1)\}$
等价于 $Min_{i=1}^N \{Max_{j=i}^{2*N}(T_j – j + i + N – 1)\}$（少遛几个点是不会对 $Max$有贡献的）
令 $a_i = T_j – j$，那么我们就是在求：$Min_{i=1}^N (\{Max_{j=i}^{2*N}a_j\} + i)+ N – 1$
考虑怎么用线段树维护。
每个节点维护 $val=ans$，$maxv=a_i(L\leq i \leq R)$。考虑 $o$的 $rs$对 $ls$的贡献。
考虑 $ls$的左儿子和右二子，即左孙子一号和左孙子二号，如果 $maxv($左孙子二号 $)\geq maxv(rs)$，那么左孙子一号的 $val$就是它的贡献。左孙子二号就得递归处理。
如果 $maxv($左孙子二号 $)\leq maxv(ls)$，则左孙子二号的贡献就是 $mid + 1 + maxv$，左孙子一号就得递归处理了。
总复杂度 $\Theta(nlog_2^2n)$。
毒瘤
考虑一棵树的情况，显然有：
\begin{eqnarray}
f[u][1] &= &f[u][1] \times f[v][1];\
f[u][0] &= &f[u][0] \times (f[v][1] * f[v][0]);
\end{eqnarray}
考虑非树边 $(u\rightarrow v)$，只有三种情况：$(1, 0), (0, 0), (0, 1)$。也就是说就算枚举也不要紧。（这正是一档暴力的打法）
可以发现，每条非树边的 $f$对它的上方的祖先的贡献都可以写成 $k_{0/1,0}*f[v][0], k_{0/1, 1}*f[v][1]$。而且只会影响某一些点，十分符合某个数据结构的尿性。
于是我们可以建出虚树然后 $dp$出系数计算贡献。
还有注意第一遍 $dfs$的时候是遍历完所有边 QAQ
游戏
不难想到每个点能到达的地方必然为一段区间。
缩点之后考虑 $i$和 $i+1$之间的门，如果锁在的位置 $\leq i$，则 $i+1$无法到达 $i$，加一条边 $i+1 \rightarrow i$，反之亦然。
拓扑排序然后暴力往左右扫。
排列
连边 $(a[i], i)$，然后这就成为了 $HDU1055$。
很难忘记这道题了吧。
道路
出题人：我以为我出了一道网络流神题……
一不小心出了道普及组 $DP$。
表面笑嘻嘻内心 MMP.jpg
0 条评论