本文章所讲述的是在2022.10.22日举行的ICPC程序设计竞赛 陕西省省赛
之中的题目思路讲解
出题团队在得到出题任务的时候得知区域赛金牌选手是不能参赛的，所以题目整体偏简单，希望给参赛
选手更好的参赛体验，但是赛前一周多又看到所有选手都允许报名了，所以加强了部分题目，且把看起
来简单实际很难的Tree放到了Problem A。
实际的结果是造成了好几道题目变成了防AK题，在此表示歉意。
A.Tree
定位：防AK题
实际：有很多队伍尝试进行构造，赛后也尝试交了很多次，某几次提交大数据都通过了，被 的几 个手造小数据卡掉了（Yes的情况，输出了No），赛时如果能 暴力则能通过。
考虑根据 k 进行讨论。
k=1
当 k=1 时，显然，每次只能移动到一个相邻的节点。
所以此时当且仅当整个树形成一条链（并且 是其中的一端）时有解。
解的构造就是从1往下输出。
k>=3
可以证明，对于所有 k>=3 的情况，都存在一组解。
根据贪心的角度考虑，如果从一个子树出去，然后回到这个子树，这样的构造肯定不是最优的。 所以我们每一次进入某一个子树后，一定是遍历完整个子树才会向外走。
我们称某棵子树中，第一个被遍历的节点为“开始节点”，最后一个被便利的节点为“结束节点”。
首先dfs这棵树，求出每个节点的深度（假设 号节点深度为 ）。
然后将所有的节点按照深度进行分类。
对于所有深度为奇数的节点，我们令这个子树的开始节点为根节点，然后依次遍历每个子树。
对于所有深度为偶数的节点，我们先依次遍历他的每个子树，最后遍历根节点（即根节点为结束节 点）。
所有的叶子节点比较特殊，因为它们对应子树的开始节点和结束节点都是它们本身。
不难发现，所有深度为奇数的节点，它们的儿子都是深度为偶数的节点，即这种子树的结束节点一定是 它们的任意一个儿子。
所有深度为偶数的节点，它们的儿子都是深度为奇数的节点，这种子树的开始节点一定是它们的任意一 个儿子。
所以在不同子树之间“跳跃”时，所有移动的距离一定是 <=3 的。
k=2
这个部分就比较麻烦了。
与 k>=3 一样，一定不会从一棵子树出去，然后回到这个子树。
考虑使用dp进行求解。 我们设 dp(i,0) 为：以 i 为根的子树，能否以 i 本身为开始节点，以 i 的任何一个儿子为结束节点，构造一个合法的方案。
注意， dp(i,0) 同时代表着，能否以 i 的任何一个儿子为开始节点, i 本身为结束节点，构造一个合法的方案。
设 dp(i,1) 为：以 i 为根的子树，能否以 i 本身为开始节点，任何一个节点为结束节点，构造一个合法的方案（即从 i 开始，以子树内的节点为整棵树的结束节点）。
设 dp(i,2) 为：以 i 为根的子树，能否以 i 的任何一个儿子为开始节点，任何一个节点为结束节点，构造 一个合法的方案。
在计算 dpi 时，枚举 i 有多少个非叶子儿子，然后再根据儿子的 dp 值进行转移。
看起来比较简单，实际上非常难写。
B.Type the String
定位：简单题
实际：银牌区
题目 能加能删的情况下，两个串互相构造的代码其实都是LCS(si,sj)。
我们建立一个虚点，虚点向每一个串连边，代价是 li ，然后两两连边，代价是LCS（si,sj) ，显然对这 幅图跑最小生成树就是最终的答案。
时间复杂度 O(n^4) 。
C.Card
定位：签到题
实际：铜牌门槛题
容易发现，对于初始的模型，我们直接按 bi-ai 从大到小 sort 一下取前 k 个就是答案了。
现在多了若干个位置不让选，我们可以在读入的时候顺便把他们标记出来，如果在前 k 个位置，则记录 一下我们需要往后多选一个。然后直接从 k+1 开始暴力向后枚举，把那些没有被标记的点选进来即可。
用堆，线段树之类的数据结构来维护，都能通过此题。
D.Hash
定位：中档题
实际：银牌区题目
做法1：
暴力枚举所有长度 <=6 的串以后会发现可以构造出所有不同的 hash 值，于是直接把原串向左移动 6 位， 给前面拼 个字母使得 hash 值不变即可。
直接暴力的话复杂度是不对的（主要是这个模数速度挺慢的），可以考虑考虑这样一个事实：既然这 6 位 的哈希值 X 是多少已知，我们直接枚举它是几倍的 mod+X，然后把他还原回原串，如果每一位都在 区间 [1-26]之间，就是一组合法解。这样的解非常密集，枚举一次的成功率大约是 (26/29)^6 = 51%， 所以只需要枚举几个数就能得到解。
时间复杂度 O(k*6)， k是 SPFA 的那个 k。
做法2：
我们从一个空串开始，不断的往后加字符，通过 BFS 来构造出所有的 hash 值，这样我们得到了从 0 到 每一个 hash 值的路径。
然后再反着来一遍：假设当前 hash 值是 X，我们在末尾添加一个字符，变成新的 hash 值，这又是一副 有向图，我们把边反向，再去 BFS 一遍，就能得到从每一个 hash 值到 0 的路径。
对于读入的每一个字符串，我们先把它不断添字符，把 hash 值变成 0，再不断添字符变回去就可以了。
最多需要用到 12 位。
牛客的机器速度超出预期，应该不会被卡常。
E.Guess The Number
定位：中档偏难
实际：多人尝试，无人AC
F.Cross Fire
定位：中档题
实际：银牌区题目
G.2d-lake
定位：签到题
实际：铜牌门槛题
容易看出来，如果 是奇数，最优搭建策略是一个三角形，如果n是偶数，最优搭建策略是一个底部为2的三角形。
所以直接对于给定的 n，计算最多能容纳多少水，如果够用则直接输出答案，如果不够用需要二分一 下，或者直接 O(1)计算答案。
加强后：卡了 longlong。
一个hack点是 n=8*10^9，用longlong会爆掉，需要用ull以及合适的写法（先除后乘）来避免爆 掉，或者直接用int128 ，换编程语言等办法。
H.Cute Rabbit
定位：简单题
实际：铜牌区题目
解法1： 一个重要结论是：要么把除了最小值以外的兔子都涂成绿色，要么把所有兔子按从小到大排序，把一段 前缀涂成绿色。不想看证明的同学请跳过下面的片段：
现在我们考虑枚举分割线x ，然后判断所有比 x大的数字对所有比 x小的数字求余得到的结果是否全部 相同。我们将所有比 x 小的数字的最小公倍数求出来（记为 Q），如果所有比 x 大的数字求余 Q 相等，就说明这种涂色方案可行。判断多个数字同余 Q 的方式是看这些数字的差值的 gcd 是否是 Q 的整数倍。
I.Date
定位：中档偏难
实际：有两支队伍尝试，其中一只队伍在赛后3秒时提交通过。
这道题的题意验题人视角也觉得比较难以理解，理解题意需要比较久的时间。
理解题意之后，判断完无解之后，发现这其实是一个有向图，每条边的转移是有概率的，问期望从起点 多少步到达终止节点（终止节点可以有多个）。
J.Make it Equal
定位：真正的签到题
实际：有 8 支队伍没签了。 考虑到把 n-1 个元素 -1，就相当于把某一个数字 +1，所以答案要么是n-1 ，要么是 n。只需要 check一下所有的元素是否相等即可。
K.Path maker
定位：中档题
实际：无人尝试 非常可惜的点是，此题可能因为题面过长， 无人尝试去做，实际是一道水题。
这个题思路比较显然，第一步肯定是预处理出 表示如果在第 i 回合放了一次防御技能，在第 Ri 回合结束后，护盾会爆掉。
预处理 数组有两种思路，
我们可以直接用经典的并查集维护区间染色的方法来解决该问题，从而避免使用线段树。
PS：加强前此题是不能在护盾断掉之前再次使用护盾技能的，就不需要用到log级别的数据结构了。
L.Mr.Bridge and Tree Planting
定位：难题
实际：无人AC
我们先来看这样一个题目： 给定一棵树，点带颜色，多次询问某一个点子树内有多少个颜色为 x 的点。
做法很多，这里给出一个具有启发性的：
对于每一个颜色维护一个桶，我们离线下来把询问挂在点上，dfs整棵树，进入某一个点的时候先把所有 的询问减去对应颜色桶里的值，然后把当前点颜色的桶++，dfs结束的时候直接把询问加上对应颜色的桶 即可。
为什么正确呢，因为两次做差之间加入的点刚好是整个子树。
我们考虑把上面的做法套过来：
对于每一棵树维护一个栈，栈里面记录的是当前子树的大小，下移上移生长节点的过程其实就是dfs，每 一次下移往栈顶丢一个 ，回退的时候把栈顶的值加到新栈顶即可，询问答案就是栈顶的值。
这个做法维护的栈需要把栈顶的值加到新栈顶上，这个操作不是正常栈的东西，不好处理，我们考虑换 一种维护方式：
回顾一下上面的做法：我们其实只用知道当前生长节点的时间戳即可，时间戳到询问时间之间这个树被 操作过多少次就是答案。
所以我们只用往栈里面压时间戳，最后离线下来扫一遍所有生长指令即可。
现在的问题转化成了维护栈：要求支持区间压栈区间弹栈单点查询栈顶。
考虑一个询问的答案可能在什么地方被压进来，我们对于一个单独的栈把所有的操作单独拎出来，压栈 我们叫做+1 ，弹栈就是-1 。
那么一次压栈可以成为一次查询的必要条件就是这次操作之后到查询操作之前所有操作的价值和是0 。
正确性很显然，因为一个压栈操作是栈顶当且仅当他上面的元素恰好被pop完。
但是有一个问题就是我们没法保证他自己不被pop。
所以我们要找最靠后的一个符合条件的位置。考虑从后往前扫操作序列，遇到询问就挂在对应点上，把 这个询问标记权值为 0，遇到弹栈就区间内询问权值 -1，遇到压栈先把所有权值是0的询问的答案置为 这一次压栈，然后删掉他们，正确性显然。
考虑这么维护：
使用一棵叶子节点是set的线段树，支持区间加减，维护区间最小值，插入直接差，加减打tag，找点按 照最小值暴力dfs，复杂度均摊下来显然正确，这样子我们就可以找到每一个询问的时间戳了，再按照上 面的做法扫一遍操作序列就可以得到答案了。
M.Mountain
定位：中档偏难
实际：无人AC
我们把山峰当1 ，山谷当0 ，其实题目就是让你选一个 10 交替的子序列，以 1 开头，以 1 结尾，要求代价之和最大。在这个基础上，有若干段不相交的区间，如果区间内选了大于等于2个0，就额外获得一个收益。
有若干次修改操作，每次修改后询问答案。
