Problem A
First Solved：DeaphetS
构造题。解法非常多。

首先无解是唬你的，不存在无解的情况，可以很容易的证明，这里省去。

解法1
随机。

我们首先按照顺序三个三个分组，发现其中有一些是不满足要求的，于是考虑随机交换。

每次随机选择一组的第二个和另一组的第三个进行交换。

但是我把我自己卡掉了。

大家有更好的随机策略可以在评论区交流。

解法2
by oxx1108

从钝角出发，很直接的就想到构造两条短边和一条长边，只要使得短边的和与长边的差值很小就行。

又是 3n 个，又是三角形，最直接想法就是分成三堆（最小的 n 个一堆，中间的 n 个一堆，最大的 n 个一堆），从最小堆里取一个，中间堆里取一个，最大堆里取一个，但是既要是钝角又要是三角形行不通，那么就改变一下想法。从最小堆里取一个偶数，中间堆里取两个；最小堆里取一个奇数，最大堆里取两个。比如 n=4 的时候分组就为 {2,3,4,5},{6,7,8,9},{10,11,12,13} 那么结果就是 {2,7,8},{4,6,9},{3,11,12},{5,10,13}。奇数的时候要注意多加一组 {n+1,2n+1,3n+1} 即可。证明显然。

解法3
通过解法1，我们发现对于每一组的第一个默认为 2 、 3 、⋯ 、n 、n+1 ，是一定存在这样的解的。

于是我们默认每一组的第一个数，来构造后面两个数。

首先，如果长度为 a 、 b 、 c ( a<b<c )的能够构成钝角三角形，显然 a 、 b+x 、 c+x ( x≥0 ) 也能构成钝角三角形。

我们考虑从 n 的解，通过变换得到 2n+1 的解：我们对 n 的解，每一组的第二条和第三条边分别进行 +n 操作，由上得，显然满足钝角三角形。

这样一来，空出了 (n+2)⋯(2n+1) 和 (4n+2)⋯(6n+1) ，前面一部分有 n 个数，后面一部分有 2n 个数，而且正好 x+2 、 4x+2 、 5x+2 ( x≥1 ) 能构成钝角三角形，于是，我们可以从 n 推到 2n 。

而对于 n 推到 2n+1 的情况，无非是多出了三个数，组成一组即可，其他情况和推到 2n 的情况类似。

解法4
同样我们默认每组的第一个是 2 、 3 、⋯ 、n 、n+1 ，考虑从最后一组开始。

第二数选择当前没有被选择的数中最小的一个数，然后在剩下的数中二分寻找一个满足要求的数。

可以证明，这样的构造方法是满足要求的。

Comments
oxx1108 ：套路的构造题，但是好像大家都觉得有点难？可能更适合放数学竞赛里吧……

Problem B
First Solved：dreamoon
签到题。

考虑最旁边的两个数，如果相等，直接略过他们，因为他们本身已经是回文了；

如果不相等，那么一定是较小的一个要向内合并，合并完以后继续比较当前最旁边的两个数。

显然这样的策略是最优的，最坏的情况就是，所有的数合并成一个数，一个数显然满足回文。

Problem C
First Solved：applese
一种解法是显然的，我们的线段树建法，决定了线段树要么左右孩子等大，要么左孩子比右孩子大 1 。

对于一个线段树上的结点 l,r ，他的父亲只有四种情况：

当前结点为左孩子，左右孩子等大，父亲为 [l,r+len] ；
当前结点为左孩子，左孩子更大，父亲为 [l,r+len−1] ；
当前结点为右孩子，左右孩子等大，父亲为 [l−len,r] ；
当前结点为右孩子，左孩子更大，父亲为 [l−len−1,r] 。
这样一来，我们就可以直接暴力了。这样的暴力还不足以通过这道题目。

一些剪枝是必要的。

比如可行性剪枝 r≥ans （ r 是当前的做区间， ans 是当前已经得到的可能最小答案 ）时，直接 return ；

比如 r≥lim,lim=2⋅109 时，直接 return ；

比如特判 l=r 的情况。

当然验题人 oxx1108 提出了一种更加精妙（手动划去）愚蠢的解法：

本质就是枚举所有可行的 n ，一个个 check 。

首先，可以明确的是如果 l≠1 的时候，该段一定在线段树的右半棵子树上，即 l>n2，因为如果在左半棵子树上的话，那么直接可以把右边丢了，那么将会是一个更小的解。这也意味着要是直接枚举 n 的话，也至多枚举 l 次。但是显然这样是行不通的，那我们来研究下线段树的性质来进行剪枝，以下两种枚举均可，方法一效果更优，方法二在个别 len 小的时候会效果比方法一更好。

方法一： 显然在该层线段个数一定为二的次幂，而每个线段长度一定为 len−1,len,len+1 之一，因此暴力枚举 2k(len−1)∼2k(len+1) 即可，实验证明无论如何取值（即去掉限制条件），枚举次数上限约为 5×104。在有限制条件的情况下，可以严格计算出不会超过 5×104 次。实际结果跑得飞快，最终大约20 ms。

方法二： 由于在该层，每个线段长度必为 len−1,len,len+1 之一， 因此我们只需枚举 l+i(len−1)∼l+i(len+1) 即可，由于题目的限制条件，因此可以保证枚举次数不会很多。最终大约120 ms。

利用类似性质应该有很多方法能过此题。

花絮
由于出题人本身技艺不佳，原本的题目是限制了 lr−l+1 的大小的，这样的话，直接暴力就能过了。

牛逼网友 oxx1108 在验题中的代码速度经过优化，甚至跑得比 std 快近 1000 倍，经过斟酌，我们取消了限制条件。

验题人一致认为本场月赛难度太高，又无法严格证明，于是，限制条件又加上了。

Comments
oxx1108 ：递归暴力过不去，只能想野鸡做法了，结果野鸡做法比std跑得还快。如果有会证明野鸡做法正确性的可以交流一下，想了好久不知道为什么可以跑那么快。

Problem D
First Solved：BanFcc
签到题。

要想清楚还是比较麻烦的，大力猜测结论与奇偶性相关，就稳了。

结论是：如果 |x1−x2|+|y1−y2| 是奇数，先手必胜，否则，后手必胜。

下面我们定义距离为两个玩家棋子间的曼哈顿距离，我们发现，每个玩家每个回合开始时距离的奇偶性是保持不变的，因为每个玩家移动时，距离的奇偶性都会发生改变，而到下个玩家移动时，奇偶性就会变回来。由于只有回合开始时距离为 1 时才是必胜态，所以回合开始时距离为偶数的玩家是一定赢不了的。

接着，证明不存在平局情况：

因为一方不可能输，所以想要赢，只要不断拉近距离即可。先来简单证明双方距离不会变大：

无论守方如何移动，双方的距离都最多增加 1，而攻方总能找到一个移动方向，使双方距离 −1。

因此，想要平局，守方只能保证距离不变。为了不拉近距离，守方肯定会选择远离一方的方向移动。双方之间的位置关系有两种可能：第一种，不在同一行也不在同一列；第二种，在同一行或同一列。

先来讨论第一种情况，我们假设守方在攻方的左上方，那守方只能向左或向上走，否则就会主动拉近距离。此时，攻方只要重复守方的移动即可。因为守方在攻方的左上方，因此如果守方一直向左或向上，肯定比攻方先碰到边界，最终被逼到边角，不得不向右或下方移动，不可能保证距离一直不变。

接着讨论第二种情况，我们假设守方在攻方的正上方，如果守方向左或向右，那攻方只要向上走，就会在不增加距离的情况下变成第一种情况，因此守方只能向上走，但这么走也早晚会碰到边界，最后不得不将情况变成第一种情况。

于是，我们知道两个棋子之间的距离只可能减小。因此，不存在平局情况，回合开始时距离为奇数的一方必胜。

Comments
ultmaster ：牛逼啊？

Xiejiadong ：由于楼上不信，现学了博弈搜索，莽了一发。

Problem E
First Solved：applese
给出 dp 实现的伪代码：

其中第五第六行为背包过程，由于只需要输出答案，因此保留 max 值即可。

F 的含义是不包含子树根结点，其祖先已取的集合为 A 时最大取值，G 的含义是包含子树根结点。

由于一定是祖先中最近的结点最优，因此可以用最近的祖先/距离来代替集合 A，注意空集时候的问题，最终复杂度 O(n2k2)。

Comments
Xiejiadong ：这个树形 dp 也太难了。想出来了也写不出来。何况我也想不出来。

oxx1108 ：这是从某篇正在研究的paper里提取出来的问题，原本还需要套一个虚树，但是太胖了虚树部分就扔掉了（原来计划放校赛里卡 Xiejiadong ，现在校赛里应该是一堆“友好”的题了）。如果有更好的解法或者推广（到 DAG ，改成无根树等）欢迎交流。

Kilo_5723 ：这题两个星期前就给我了，终于在比赛当天中午验出来了。