2018-6-9 题解

2018-06-09 11:28:35 By diamond_duke

骑士游戏

考虑 $dp$,类似 $SPFA$ 那样做:每次取出队头元素,看看有没有被更新,如果 $dp$ 被更新了就把他的前驱入队,然后重复上述过程。

时间复杂度:$\Theta (SPFA_{n,\sum R})$。

奇怪的计算器

询问离线,用线段树维护每个询问的答案。注意到这些操作过程中,数字的相对顺序不会改变(原来的顺序就是新的顺序)。那么我们把询问排序,用线段树维护。每次溢出的区间一定是一个前缀或者后缀,树上二分求出这个区间即可。

于是这个线段树只要支持:

  • 区间加
  • 区间乘
  • 区间赋值
  • 区间加上一条直线($@$操作)
  • 树上二分出:第一个大于/小于某个数的位置,以及$@$后第一个溢出的位置
  • 单点查询

维护一群懒标记即可,时间复杂度:$\Theta (n\log_2n)$。

小园丁与老司机

先考虑前两问,考虑 $dp$,转移时枚举下一行进入了哪个点以及从哪里进入,然后计算出当前行最多能走多少,转移即可。构造路径的话直接推即可。

在考虑第三问:根据之前的 $dp$ 值进行一遍 $dfs$,即可知道哪些边可能经过。这些边都要被覆盖,所以是一个下界最小流问题。因此跑网络流即可(一定满流,可以省一次)。

时间复杂度:$\Theta (n\times \max_Y\{\sum_{i=1}^n[y_i=Y]\}+最大流_{n,O(n)})$。

评论

回复

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。