YGP题解
NOIP 2019 模拟赛day2 题解 浮尘ii* 1 排兵布阵 显然最优的策略一定是每个城堡要么不派遣士兵，要么恰好派遣某名玩家在这座 城堡士兵数的2 倍+1。直接背包就好了。
具体地，设ai;j 表示其他玩家在第i 个城堡派遣士兵数升序排序后的第j 个，
dp(i; j) 表示前i 个城堡，派遣j 名士兵所能获得的最大收益，则有
dp(i; j) = maxfdp(i ???? 1; j); dp(i ???? 1; j ???? 2ai;k ???? 1) + ikg
时间复杂度O(nms)，由于常数小，可以通过。
2 小X 的二叉树
2.1 算法一
搜索。期望得分：10 分。
2.2 算法二
注意到题目中每个点对它祖先的限制，可以等价为一个点对它子树的限制，而中序 遍历中每个子树是一个区间，所以可以区间DP。
设f(l; r) 表示区间[l; r] 是否可行，转移时枚举当前区间表示子树的根i，需要满足pi ???? k 不超过区间最小值，pi + k 不小于区间最大值。
时间复杂度O(n3)，期望得分：30 分。
2.3 算法三
注意到如下结论：题目中给定的序列合法的充要条件是对于任意一个区间，都存在 一个数使得这个数与区间其他数的差的绝对值不超过k。 • 充分性：若任意一个区间都满足此性质，那么我们一定可以构造出一棵满足题意 的二叉树。我们从区间[1; n] 开始构造，选择一个满足条件的i，将i 作为当前子 树的根，接着递归构造[l; i ???? 1] 和[i + 1; r]。由于每个区间都存在一个数满足条 件，所以一定有合法的i，也就能构造出满足题意的树。
• 必要性：如果这是由一棵合法的树中序遍历得到的点权序列，那么每个区间中深 度最浅的点一定是其他点的祖先，而这个点必须要满足条件，所以每个区间一定 存在一个数，满足与区间内其他数的差的绝对值不超过k。 于是我们就要判断原序列是否每个区间都存在一个数满足与其他数的差的绝对值 不超过k。我们考虑分治，对于当前区间[l; r]，找到一个i(l i r) 使得pi ???? k 不 超过区间最小值，pi + k 不小于区间最大值，这时跨过i 的区间一定都合法，分治到 [l; i ???? 1] 和[i + 1; r] 判断即可。
时间复杂度T(n) = T(k) + T(n ???? k ???? 1) + O(k) = O(n2)，期望得分：60 分。
2.4 算法四
我们发现算法三分治的时间复杂度瓶颈在于寻找一个合法的i。我们如果从l; r 同 时向中间找，也就是第t 步判断l + t 和r ???? t 是否是合法的i，那么时间复杂度变成了
T(n) = T(k) + T(n ???? k ???? 1) + minfO(k);O(n ???? k)g = O(n log n)，期望得分：100 分。
2.5 算法五 考虑换一个思路判断是否每个区间都存在一个数满足与其他数的差的绝对值不超 过k。 对于i，求出最小的li 和最大的ri 满足8j 2 [li; ri]; jpi ???? pj j k。 这时左端点在[li; i] 右端点在[i; ri] 的区间就都合法了。 设二维平面上的点(x; y)(x y) 表示区间[x; y]，这就相当于对左下角为(li; i) 右 上角为(i; ri) 的矩形覆盖，最后求是否覆盖完全。 扫描线维护矩形并即可，时间复杂度O(n log n)。
2.6 算法六 我们可以求出最小的k0 判断题目给定的k 是否满足k k0。
可以直接贪心构造，对于每个区间取最接近min+max 的数分治下去，可以证明这 样是不劣的。 直接写复杂度是O(n2)，可以使用数据结构优化到O(n log2 n) 或O(n log n)。
3 特技飞行
以下为表述方便用m 表示总的交点数。 注意到a; b 和c 两种情况的贡献是独立的，而c 对答案的贡献是固定的，为ct，t 为能被观测到的交点个数。 而a; b 的贡献只需要在每个交点处决定使用哪种特技，并且保证最后的相对顺序 和原来是相等的即可。 设使用“对向交换”次数为x，则这部分对答案的贡献为y = ax + b(m ???? x) = (a????b)x+bm，由一次函数的知识可知，当x 取最值时，目标函数y 一定也取最值，最 大值最小值的对应关系根据a; b 的大小关系来确定。 于是问题变成了我们要求出x 的最小值和最大值。
x 的最大值是显然的，为m，考虑如果在每个交点处都进行“对向交换”的话，任 意两个飞机间的相对位置不变，所以最后仍然是合法的。
考虑求x 的最小值，发现问题相当于是要对yi;1 进行排序，假设yi;1 要交换到pi 的位置。
我们把i 向pi 连边，则每个点出度为1，入度为1，构成了若干个简单环。而对于 一个长度为l 的环，需要进行l ???? 1 次交换相邻两个数才能整体循环移位1，也就是要进行l ???? 1 次“对向交换”。 所以
Σ(l ???? 1) 即为x 的最小值，这一部分的时间复杂度为O(n + m)。 接着考虑如何求出t。
把坐标系旋转45◦，则斜着的菱形变成了正着的正方形，扫描线维护矩形并，判断 每个交点是否在矩形内部即可。 时间复杂度O((m + k) logm)。 3