事已至此,当然是选择原谅啦。

寻宝游戏

毛:我我我我是不是出得太简单了???
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

分类: 所有

发表评论

电子邮件地址不会被公开。 必填项已用*标注

你是机器人吗? =。= *