首先设 $f_i$ 为从 $1$ 跳到 $i$ 的最小花费，$O(n^2)$ DP 是简单的。

观察性质。首先，如果 $a_k\le a_j,a_k\le a_i$，那么 $i\to j$ 的转移一定是不优于 $i\to k\to j$ 的。

其次，考察 $j\to i$ 的转移，若 $i-j\ge\frac n{a_i}$，那么有 $a_i(i-j)^2\ge(i-j)n$，也即该转移不优于 $j\to j+1\to\cdots\to i-1\to i$。

所以只需从前往后遍历每个位置 $i$，向前枚举 $j$，直到 $a_j\le a_i$ 或 $i-j\le\dfrac n{a_i}$，进行 $j\to i$ 的转移；再向后枚举 $j$，直到 $a_j\le a_i$ 或 $j-i\le\frac n{a_i}$，进行 $i\to j$ 的转移即可。

上述两个性质分别保证了两种优化的正确性，现在来证明其复杂度。

对于不超过 $\sqrt n$ 的数，最多有 $O(\sqrt n)$ 种，每个数向前向后枚举遇到相同数就会停止，所以每一种数带来的的总复杂度为 $O(n)$。

对于超过 $\sqrt n$ 的数 $a_i$，向前/向后枚举的次数为 $\frac n{a_i}\le\sqrt n$。

综上，总复杂度为 $O(n\sqrt n)$。

将该组合游戏进行拆解，某个 DAG 上该游戏先手必胜等价于 $1,2$ 节点的 SG 值不相等。

某个节点的 SG 值为其所有后继节点的 $\mathrm{mex}$，也即某个节点的 SG 值为 $x$ 当且仅当其向 SG 值分别为 $[0,x)$ 的节点各连了至少一条边，并且没有连向 $x$ 的边。

这提示我们从小到大，每次考察 SG 值为 $x$ 的点的集合。SG 值大于 $x$ 的所有节点必须向这个集合中至少连一条边；这个集合中的节点不能向集合中其它节点连边；SG 值小于 $x$ 的所有节点连边无限制。

状压 DP 即可。

设初始局面只有点 $x$ 被染色，最后被染色的点集为 $f(x)$，那么显然起初有多个点 $x_1,x_2,\cdots,x_m$ 染色，最终被染色的点集为 $f(x_1)\cup f(x_2)\cup\cdots\cup f(x_m)$。

于是我们探寻 $f(x)$ 会包含哪些节点。

对于点 $i<x$，它被染色当且仅当存在点 $j$ 不在 $x$ 左侧，并且满足 $V_j<V_i$。这样 $i$ 要么先与 $x$ 相遇，被染色；要么先与 $j$ 相遇，此时 $j$ 一定在 $x$ 左侧，即 $j$ 一定被染色，于是 $i$ 被染色。显然不存在其它染色情况。

同理，对于点 $i>x$ 它被染色当且仅当存在点 $j$ 不在 $x$ 右侧，并且满足 $V_j>V_i$。

我们把所有点按照 $X$ 排序后重新编号。设 $\mathrm{pmx}_i=\max_{i\in[1,i]}V_i$ 和 $\mathrm{smn}=\min_{i\in[i,n]}V_i$。于是 $f(x)=\{i\mid i<x\land V_i<\mathrm{smn_i}\}\cup\{i\mid i>x\land V_i>\mathrm{pmx_i}\}\cup\{x\}$。

于是考虑对初始局面进行 DP。设 $g_i$ 为最靠右的初始被染色的点，且能够最终将 $[1,i]$ 中所有点都染上色的初始局面数。

那么由 $g_j$ 到 $g_i$ 的转移只需要保证 $(i,j)$ 中所有节点都染上色即可，即 $(i,j)$ 中不存在点 $t$ 使得 $V_t\in[\mathrm{pmx}_j,\mathrm{smn}_i]$。考虑到 $\mathrm{pmx},\mathrm{smn}$ 均单调，可以使用双指针维护。

考虑到序列的后缀颜色数随着后缀长度增加单调不减，而非空区间内的颜色数只可能有 $1,2,3$ 种，所以尝试维护后缀颜色数出现差异的左端点位置，即从右向左第一次出现新颜色的位置、第二次出现新颜色的位置。

对前缀 $[1,i]$ 进行 DP，校验所有右端点为 $i$ 的限制，对符合限制的状态向后贡献即可。

所有人按照 $l$ 从小到大排序，依次尝试匹配从左到右每一个凳子。如果当前考虑到第 $i$ 个人，在尝试匹配从左到右第 $j$ 个凳子，且不满足 $j\le l_i$，此时 $[1,i]$ 中至少有一个人需要选择满足 $j\ge r_i$ 的凳子 $j$，显然在这些人中选择 $r_i$ 最小者一定不劣。

左侧匹配完，再把所有第一步未匹配的点按照 $r_i$ 从大到小排序，然后类似地贪心匹配。

正确性大概来源于，匈牙利算法可以以任意顺序遍历每个尚未被匹配的点，以任意顺序遍历一个点的所有出边。

---

第二种做法，先用运用霍尔定理的推论，将题意转化为，选择多条线段，求线段条数加线段交的长度最大值。

枚举线段交的左端点 $l$，此时能够选取的线段的左端点一定 $\le l$。此时对于该点右侧的每个点 $r$，它作为线段交的右端点的答案是 $r-l+k$，其中 $k$ 为完全包含 $[l,r]$ 区间的线段数量。

于是给线段树上每个点 $i$ 赋初始权值 $i$，把线段按照左端点从小到大排序，依次枚举线段 $[l,r]$，在线段树上给 $[l,r]$ 区间加一，求 $[l,+\infty)$ 区间最大值即可。

将答案序列看作一条平面上由 $(n,m)$ 到 $(0,0)$ 的路径，某次答案为 Yes 则往左走，否则往下走。于是每道题都与某条边一一对应；而每次答题人所面对的状态，即目前两种答案分别剩 $x,y$ 个，则与平面上某个点 $(x,y)$ 一一对应。

那么答题人的最优策略是显然的，当目前在直线 $y=x$ 以下时，猜答案为 Yes；当目前在直线 $y=x$ 以上时，猜答案为 No；当恰好落在直线上时，随便怎么猜，猜对的概率均为 $\frac12$。

我们来考察某种答案序列所对应的路径，假设 $n\ge m$，将整条路径在所有 $x=y$ 点处断开，形成多个段。

$n>m$ 时第一个段一定在 $y=x$ 下，这个段中每次询问都会得到回答 Yes，其中所有向左走的路径对应的问题是正确的，于是这段中答对问题的数量等于这部分路径的 $x$ 坐标跨度。

其余段中，除了段首第一个询问恒定有 $\frac12$ 的概率是正确的，其余所有边朝向直线 $y=x$ 的问题都是回答正确的。而这些段中起点终点均在 $y=x$ 上，所以 $x$ 坐标跨度等于 $y$ 坐标跨度，所以这些段中回答正确的问题数量期望都等于 $x$ 坐标跨度加 $\frac12$。

于是总答案等于 $n+\frac k2$，其中 $k$ 为回答的第二类段的期望数量，等于该路径与直线 $y=x$ 的交点个数减一。

那么对于每个点 $(x,x)$ 计算路径经过它的概率，计算相应贡献即可。

Floyd 全源最短路

设 $f_{t,u,v}$ 为只经过图中 $[1,t]\cup\{u,v\}$ 中的点，$u\to v$ 的最短路。$f_{0,u,v}$ 即 $u$ 到 $v$ 的所有边中的边权最小值，$u$ 到 $v$ 间无边即为 $+\infty$。

那么转移为 $f_{t,u,v}\xleftarrow[k]{\min}f_{t-1,u,k}+f_{t-1,k,v}$。复杂度 $O(n^3)$

Bellman-Ford 单源最短路

维护 $d_u$，第 $t$ 轮更新时表示从起点到点 $u$ 经过不超过 $t$ 条路径的最短路。

每轮更新时遍历每条边 $(u,v,w)$，令 $d_v\xleftarrow[]{\min}d_u+w$。

这样做的正确性是显然的，考虑到若原图存在最短路，那么起点到每个点一定存在一条长度不超过 $n-1$ 的最短路。所以在经历 $n-1$ 轮更新后 $d_i$ 即为起点到 $i$ 的最短路；也即如果第 $n$ 轮更新仍然有 $d$ 变小，说明原图不存在最短路，即存在负环。

时间复杂度 $O(nm)$。

SPFA 单源最短路

Bellman-Ford 中每轮更新会遍历一遍所有点。实际上只有上一轮中 $d$ 减小的那些点有更新其它点的能力。所以我们维护一个队列，每次取队头出来更新其它点。

显然一个点 $u$ 第 $t$ 次入队时，$d_u$ 一定小于等于 Bellman-Ford 中第 $t$ 轮更新后 $d_u$ 的值。那么一个点入队 $n$ 次说明原图存在负环。

时间复杂度 $O(nm)$。

Dijkstra 单源最短路

对于一个无负权边的图，维护一个集合 $S$ 包含所有已经求得最短路的点。初始为空集。

再维护 $d_i$ 表示用 $S$ 中的点能够更新得的每个点最短路，特殊地，起点的 $d$ 值为 $0$。

每轮更新时，考察不在 $S$ 中的所有点中 $d$ 最小者 $i$，由于在 $S$ 中的点已经更新过了，不在 $S$ 中的点已经无法再更新它，所以此时 $d_i$ 即为 $i$ 的最短路。将其加入 $S$ 并更新其它所有点。

找出不在 $S$ 中的所有点中 $d$ 最小值这一步，暴力求得时间复杂度为 $O(n^2)$，使用不支持删除的堆（priority_queue）为 $O(m\log m)$，使用支持删除的堆为 $O(m\log n)$，使用支持 $O(1)$ 插入的堆（斐波那契堆、配对堆等）为 $O(n\log n+m)$。

Johnson 全源最短路

对于无负权边的图，全源最短路可以对每个点都做一遍 Dijkstra，时间复杂度为 $O(nF(n,m))$，其中 $F(n,m)$ 为一轮 Dijkstra 的时间复杂度，若使用堆实现，其时间复杂度低于 Floyd 的 $O(n^3)$。

对于一般图没办法直接应用 Dijkstra。我们尝试给每个点 $t$ 都规定一个权值 $h_t$，并将每条边 $(u,v,w)$ 边权改为 $w+h_u-h_v$。不难发现，无论 $h$ 取什么值，新图最短路即原图最短路，且新图上 $s\to t$ 的最短路长度为原图上 $s\to t$ 的最短路长度加上 $h_s-h_t$。

为了使新图能够应用 Dijkstra，我们需要求出一组合适的 $h$ 使新图上没有负权边。即对于每条边 $(u,v,w)$ 有 $w+h_u-h_v\ge0$。于是变成了一个差分约束问题。先做一遍 SPFA 得到 $h$，修改边权，然后以每个点为起点分别做一遍 Dijkstra，最后求得原图上最短路即可。

首先，可以自由排序等价于可以任意交换满足 $a_i>a_{i+1}$ 的 $i,i+1$，于是等价于任意重排后保持原有顺序对不交换。

那么从前往后枚举 $t$ 中的每个字符，在保证不与已匹配的字符中小于它的冲突的基础上，贪心地匹配 $s$ 尽量靠前者即可。

赛前状态其实不错，不是很紧张。甚至可以说有点过度放松了。

全程用 NOI Linux 虚拟机读题做题，没有出现硬件上的问题。vim+gdb 用着很舒服。

前两道题读完感觉有点麻，感觉是来凑数的，NOIP 出这么简单确实有点出乎意料。

不过还是发现自己在一些逻辑上缺乏敏感，比如 T2 一开始以为是个 2-SAT，后来发现是双向边，然后才突然意识到同一个连通块里的变量，确定其中一个可以确定所有，并非 DAG 上确定一个点后可以确定后继。

第三道题，考察了问题的几个等价形式，转化的时候漏掉了一个限制，导致胡了一个假做法，写完调完一共浪费了几乎一个小时。后来发现错了的那一瞬间很炸心态，赶紧喝水、吃巧克力、上厕所。

整场比赛犯下的另外一个严重错误是先读完前三道题，第四道题放着没读。心态崩掉以后才开 T4，导致大脑宕机，一个弱智 DP 写+调用了几乎 30min。并且只写了较低档暴力，离散化的部分分、特殊性质的部分分一个也没拿到。

失败？失败！水平不行，谈何成绩。

首先，将一个斐波那契数写成两个斐波那契数之和的方案是唯一的。

并且不难发现将一棵大小为斐波那契数的数划分为两个大小为斐波那契数的子树，最多只有两种方案。

我们来证明，如果 Fib-tree 有两种划分方案，那么这两种划分方案都可以划出两个 Fib-tree 来，也即我们可以任意决策。

考察其中一种能够划出两个 Fib-tree 的划分方案，称两个子树中较大者为 $A$，较小者为 $B$，显然另一种方案中，断开的边落在 $A$ 中，并且 $A$ 照这条边断开后仍然能形成两个 Fib-tree，所以原树按照这条边断开后亦能形成两个 Fib-tree。得证。

所以暴力寻找要割开的边即可。