<h2>赛时</h2>

T1 是个带环的博弈,我比较菜不会做 写了无环和有自环的点就跑了。
T2 这种题一看就很 $O(n^2)$ 可是我只会暴力 就跑了 $n$ 遍最短路,拿到了一点点暴力分
T3 一开始不会,发现 Sub1 可做 Sub2 可做 Sub5 可做。。。写了一场然后发现 Sub5 套个cdq 就过了,可惜这是在比赛结束前一分钟发现的 [流泪]

最后 T1 不知道为什么爆零了 0+25+50=75,光荣省三。

<h2>题解</h2>

<h3>A. Idioms</h3>

T1 无环的话建反边 dp 是很显然的。设 $f_{i,0/1}$ 是到了第 $i$ 个点,是谁在操作的最优答案。
考虑使用类似于 bfs 最短路的东西来完成这个操作,对于一个状态 $f_{ * ,0}$,我们需要最小值,那么第一个能更新它的肯定是最短的;对于一个状态 $f_{ * ,1}$,我们需要最大值,那么最后一个能更新它的肯定是最大的。我们只需要处理好未更新的状态 就可以去环了。
注意到 $f_{ * ,1}$ 如果没有状态能到(并且不是起点),那么就说明存在一个点未被确定。考虑这些未被确定的状态会构成一个类似于环的东西,说明这些状态形成了稳定态不会受外界干扰。其余同理。
代码

<h3>B. Traffic</h3>

这种题一看就是 $n^2$ 题。。。拆位显然不现实
但是注意到普通的最短路是 $O(n^3)$ 的,无法接受。我们注意到边权都一样(为 $1$),我们自然联想到了 bfs。可是如果不对边进行优化,我们还是要每次遍历 $O(n^2)$ 条边,还是会 T。
我们首先考虑最短路可以长成什么样:一定是从一个点先向右跳非负整数步,再向左跳非负整数步(更加复杂的跳法都可以找到一种简单的不劣的做法)。于是我们考虑先预处理出 $f_{i,j}$ 表示点 $i$ 到点 $j$ 向右走的最短路,然后就只需要考虑向左的边了(便于一个点对其他点的集体更新)。
考虑我们枚举 $j$,那么讨论:

  1. $i \geq B_j$,$f_{i,j} = 1$
  2. $i &lt; B_j$

这个时候我们需要考虑我们一定是跳到区间 $[B_j,j-1]$ 的某个点上,然后跳回去的。我们可以贪心的去跳到 $B$ 更小的点上(意味着可以用更小的代价跳过去),也就是求 $B_{B_j \cdots j-1}$ 的最小值,从这里转移即可。

然后我们可以考虑最短路:首先我们将有值的点都扔到堆里,然后每次取出最小的点,每次去更新区间。发现一个点只会被更新一次,所以我们用并查集维护哪些点还未被更新,就能保证遍历时间是 $O(n)$ 的了。可是在 $n=6000$ 下 $O(n^2logn)$ 这样要跑 10s...
考虑每次边权递增,并且最短路不超过 $n$,我们将堆换成一个桶,完美的解决了该问题(qwq)
代码

<h2>C. Generator</h2>

可以看成每次插入一个操作,询问这个操作对答案的影响,最后做个前缀和。
考虑 Sub5 的做法:操作在询问之前,维护一个修改操作和询问操作的线段树,插入一个修改操作就在询问线段树上查一下,插入询问类似。
现在考虑顺序不保证了,可以考虑 cdq。
这里的两组限制是 $(插入时间,序列位置)$。
我们可以两边 cdq ,分别考虑插入询问和修改的贡献。我们先考虑第一种:
求询问的贡献,也就是要统计修改的该次询问结果的贡献,满足条件的修改应该

  1. 插入时间在它前面
  2. 序列位置在它前面

然后直接分治下去就好了,反之亦然。
代码

<h2>总结</h2>

T1 其实没做过怎么消环。。。以后可以考虑一下当 dp 状态建出的转移图边权简单时与 bfs 的关系,并且暴力还打挂了
T2 没有去思考(如果能意识到暴力最短路是错的或许就能去想想 $n^2$ 了),还是自己菜
T3 写的太慢,导致知道正解后没时间写出来
NOIPDay2 如果这么差,再这样下去怕不是省三文化课预定(

Last modification:April 7th, 2020 at 10:14 pm
如果觉得我的文章对你有用,请随意赞赏