G题是否可以离线Tarjan做LCA，然后通过树上差分+DFS求和得到每条边被覆盖的次数。
接下来考虑从根做一次DFS，在这过程中dp每个点向上最多连续走几条被覆盖了至少k次的边。
这样的复杂度是纯线性的？
2018.9 月赛题解
oxx1108 edited 6 年，3 月前
oxx1108：为了当选拔赛，题目出的非常简单 + “友好”（F 之前都是签到题，除了最后一题别的题都比较套路，所以比较无聊），留了两个还有点意思（难度）的题到下个月月赛（可能摸了）。
Xiejiadong：明明我出的 G 就是签到题，被 ultmaster 的假算法忽悠到改大了数据范围，不背锅。
ultmaster：赛前 oxx 和 xjd 都觉得要被几十个人 AK 了。
zerol: 赛前预测会变成自闭场。
A 圆
by Xiejiadong.
异常温暖的签到题。
圆的计算大概是谁都会吧。
哈密顿距离下的圆的图形，就是一个呈 $45^{\circ}$ 放置的正方形，给出的 $r$ 就是对角线长度的一半，然后就很好算了吧。
这道题目其实要卡的话，很容易，比如 $\pi $ 的精度问题，比如后面正方形面积需要高精度……
B 解密信件
by Xiejiadong.
加密的过程是一个递归的过程，每次倒置整个区间内的字符串，然后从中间切开，继续递归。
暴力模拟加密的过程时间复杂度是 $\mathcal{O}(n \log_2 n)$，这样显然是接受不了的。
但是我们很容易发现，我们每一次询问只包含一个位置，并没有要求你把整个字符串都还原，而要求一个位置的话，每一次递归的时候，我们只需要判断被一个位置是被分在了左区间还是右区间就行了，另一个区间显然是不需要处理的，因为处理了也没什么用。
这样一来，我们每次处理询问的复杂度就降到了 $\mathcal{O}(\log_2 n)$，所以总的复杂度是 $\mathcal{O}(T \cdot \log_2 n)$。
Xiejiadong：本来出的题目是求出原来的位置，加密后在哪里。ultmaster 觉得可以改成还原的题，然后似乎计算都变简单了？真·签到。
ultmaster：其实可以二分答案的区间范围，然后模拟验证，逐步缩小，复杂度是 $\mathcal{O}(T \log_2^2 n)$。但是感觉这个跟正解差距并不大，而且写起来也麻烦。应该没有人会想要这样做吧？
C 整数划分
by oxx1108.
简单而又套路的构造题，2，3 和模 3 余 1 的（和不是 3 的倍数）显然不行，别的都可以。
首先构造出 5，6，8，9，然后在对应的构造上六个六个加，$(0,5),(1,4),(2,3)$ 这样分组即可。
小的构造保险点可以暴力或者背包（套路），当然最简单的人脑构造一下就行。
D 素数子序列
by ultmaster.
分类讨论题又开始了。这个题本身难度不大，但是可能相对其他题更容易自闭一点吧。
- $n=1$: 给一个质数可以。如果要填的话，就填一个质数。
- $n=2$: 如果 $p_1>2$ 且 $p_2>2$，显然不行。所以肯定有一个等于 $2$，不妨令 $p_1=2$（等会别忘了讨论 $p_2=2$ 的，或者 reverse 一下），只要检查 $p_2$ 和 $p_2+2$ 是不是都是素数即可（孪生素数）。建议的写法是把所有可能的填法都填一遍然后再检查。如果两个数都可以乱填，那就……乱填。
- $n=3$：只有
2 3 2这一种情况（给在样例里了）。证明援引三胞胎素数：当素数 $p$ 大于 $3$ 时，可以证明形同 $(p,p+2,p+4)$ 的数组不可能是三胞胎素数。事实上，这三个数对 $3$ 的模两两不同，所以必然有一个能被 $3$ 整除。然而这三个数都比 $3$ 要大，因此一定有一个是 $3$ 的倍数，从而这个数不是素数。 - $n \ge 4$: 无解。首先两个奇数不能相邻，所以肯定是类似
2 p 2 p ...这样的形式（其中 $p$ 是大于等于 $3$ 的质数），而一旦出现p 2 p，$2+2p$ 一定是偶数。
主要是 $n=2$ 的时候要搞搞清楚吧。别的好像也没什么……
E 双人旋转赛车
by oxx1108.
简单而又套路的贪心题，如果在某一瞬间赢了，肯定是因为前面的得分不落后于对面得分加上对面初始得分。所以肯定选得越大越好。为了防止造成困惑，这里先说明：下面所说的 $k$ 跟题目中的 $k$ 无关。
解法一：二分答案然后优先队列维护一下最大 $k$ 个数即可。优先队列队列维护前 $k$ 大值的方法：创建一个小根堆，每次 push 之后如果发现堆的大小大于 $k$ 就弹掉最小值。复杂度 $\mathcal{O} (n \log^2 n)$。由于本解法不是标答，常数需要比较优秀，用 multiset 维护前 $k$ 大的做法，反复测试都是 TLE。
解法二：二分答案，维护最大 $k$ 个数：可以将值全部离散化后，开一个 $n$ 的数组，然后就能够非常智能地找到每个数加进来之后应该放在什么地方，才能保证既不碰撞又有序。还需要一个一开始指向第 0 个位置的指针表示目前前 $k$ 大的数都在这个后面。如果里面出现了超过 $k$ 个数，就将头指针一直后移，直到找到一个牺牲品删除。由于头指针至多移动 $n$ 次，复杂度就变成 $\mathcal{O} (n \log n)$。
解法三：考虑解法一的优化，发现可以丢掉二分，不是严格维护最大 $k$ 个数，而是维护能够满足题意的最大的一些数即可。如果这些数的总和还满足要求，就可以弹掉最小的数，答案就是最小的满足要求的优先队列大小。复杂度是 $\mathcal{O} (n \log n)$。
解法四：枚举最后赢了的位置，可以知道现在需要赢至少需要得多少分。就是求已经出现的数中最少需要多少个和才能大于等于某个特定的值。可以离散化后将数值插入树状数组，然后在树状数组上二分求前缀和大于等于某个特定值的最小下标。复杂度是 $\mathcal{O} (n \log n)$。甚至直接在外面二分也能过：树状数组常数到底小，而且 EOJ 超快哒，复杂度 $\mathcal{O} (n \log^2 n)$。
解法五：与解法四类似，求区间前 $k$ 大应该是主席树经典操作，给值求 lower_bound 下标也是主席树经典操作，给前缀和求 lower_bound 应该魔改一下也行。不过还是需要离散化，复杂度 $\mathcal{O} (n \log n)$。但是由于增加了内存限制给了 1GB，所以不离散化也是可以的，复杂度 $\mathcal{O} (n \log A)$。
P.S. 有兴趣的同学可以思考一下相反的问题，就是一直保持领先至少要赢多少场，当然这是 EOJ 上的一个原题。
F 画点小游戏
by oxx1108.
简单而又套路的 SG 函数，由于分割后的三角形都是独立的，所以就可以看作不同的堆，然后就是裸的 SG 函数 + 记忆化搜索了。复杂度是 $\mathcal{O} (n^8)$，常数非常小。
当然，记忆化还是需要优雅地记忆化，不然会 TLE。
可优化的有几个地方：
- 三角形平移都相同。（只需要存四维，必要。会改善复杂度，变成 $\mathcal{O} (n^6)$，但是常数变大了）
- 三角形三点可以有序存。
- 三角形旋转 90 度相同。
- 三角形对称相同。
- 用 short 甚至 char 来存数据。（影响不是特别大）
2~4 的优化用到一个就能过这题了，不然可能会 TLE，常数足够优秀的四方状态不用优化都能过。
注意，有一种错误的优化方法是根据边长哈希，因为会有旋转非 90 度的情况。
P.S. 出题人原来想把没优化 3、4 的都卡掉，std 不到 0.3s。
ultmaster’s comment: 野鸡验题人存了六维状态稍微优化了一下就过了。可见还是比较宽松的。
G 染色游戏
by Xiejiadong.
某些人看到这张图片可能会异常的亲切吧……（憋住，别骂人……没错就是 CCPC 的某一题签到。
这道题目的想法可能不是那么直接，我们可以暴力地枚举每一个点，假设我们是从这个点开始向根的方向前进的。
如何计算，从这个点开始向上走到某一个位置已经被多少链覆盖了？
解法一（std）
算法：启发式合并
by Xiejiadong.
我们可以通过 $m$ 条链的两个端点和当前枚举的这个点 $x$ ($1\le x\le n$) 的 LCA 上打标记来处理。
假设这条链为 $(p,q)$，如果 $LCA(p,x)=x$，那么我们在 $y$ ($y=LCA(x,q)$) 上打标记，则链 $(x,y)$ 一定被 $(p,q)$ 这条链完全覆盖了。
很显然的发现，我们如果要计算从当前点 $x$ 出发向上到某一个结点 $y$ 的路径被多少染色路径覆盖，我们只需要知道从 $y$ 到根节点有多少标记。标记的数量就是我们被染色路径覆盖的数量。
具体维护标记的数量的方法，我们可以对每一个结点建一棵权值线段树，线段树的结点表示深度为这个权值的标记数量，然后对于每一个结点，将它所有儿子结点的线段树进行启发式合并就可以得到他的权值线段树，然后直接在线段树上处理就行了。
解法二
算法：主席树
by zerol.
读进来的时候直接将所有路径拆成 LCA 到两端点的两条路径。然后不妨考虑二分答案，然后枚举路径的下端点，由于 $ans$ 知道了，所以上端点也知道了，等于 $(p,q)$ 固定了。要检查的就是 $(p,q)$ 是否被至少 $k$ 条路径覆盖了。也就是说，是否有至少 $k$ 条路径，下端点在 $q$ 的子树内，上端点深度小于等于 $p$ 的深度。可以按照路径的下端点的 DFS 序存储路径，每条路径存路径的上端点的深度，那么所求就转化成某一区间内是否有至少 $k$ 个数小于等于 $p$ 的深度。区间第 $k$ 小是主席树经典问题。当然这样的复杂度是 $\mathcal{O} ((n+m) \log n \log m)$，时限有点紧。可以进一步考虑把这个二分优化掉，其实只需要查区间内第 $k$ 小的深度，然后用 $q$ 的深度减这个深度得到的值更新答案即可。复杂度是 $\mathcal{O} ((n+m) \log m)$。
解法三
算法：树链剖分
by dreamcloud.
把染色的路径，拆成 LCA 到两端点的两条路径，并且在 LCA 上存下路径。
然后做一遍 DFS，访问一个节点的时候，就把该节点所存的所有路径经过的点计数都加 $1$，链上的部分，通过树链剖分实现。
那么对于查询，就去看它的子树中满足计数 $\ge k$ （表示这个结点已经被覆盖了超过 $k$ 次了）最深的点。子树上的查询，同样可以剖分后来做，用线段树来维护。
ultmaster & zerol: 研究了半天还是觉得该做法复杂度有点玄学。（真厉害！）
Xiejiadong: 这个线段树的维护不玄学啊（突然立直），所有的修改都是区间修改，大部分都是直接在区间结点上打 tag 就行了，那么大部分修改的复杂度是$\mathcal{O} (\log n)$，不过为了得到满足计数 $\ge k$的最深的点，会在当前结点变成的 tag 变成 $k$ 的时候，将标记下传。而所有的标记一旦 $=k$ 就不会再出现下传标记的情况。所以暴力下传最多一次，这个程序的总复杂度是$\mathcal{O} ((m+n)\log n+5\cdot n)$。
题外话
Xiejiadong：这题的定位明明就是签到啊。
ultmaster：你这个签到题。。反正我是签不出来。。不过 zerol 做了没多久，果然还是得靠队友。
dreamcloud：那可不。。我都花了三小时 debug 了。
oxx1108：楼上大佬们太强了，我连 $\mathcal{O} (n\cdot m)$ 都想了好久，果然只能靠抱队友大腿为生了……
Xiejiadong：和 ultmaster 在讨论 idea 的时候，ultmaster 提出了一个树上差分的做法，觉得 $\mathcal{O} (n\cdot m)$ 的题目有一些过于简单了。结果我把数据范围改大以后，第二天 ultmaster 发现算法假了，甚至假到过不了样例（捂脸）。这锅我不背。
你过样例三了吗？