Grandmaster 计划试题乱做 Part 2
CF1498F Christmas Game
瞎扯
对于一个固定的根，显然深度 $\bmod k$ 不同的点是独立的子问题。
对于 $\bmod k$ 的一个同余系，好像是一个阶梯 $\text{nim}$。那现在可以抽象成一个序列，每次选择一堆中一些元素，移到左边一格，移到 $1$ 就不能移了。奇数位置的元素，对答案没有影响，因为后手可以模仿先手移动。
当一个偶数位置挪到奇数位置了，他就对答案也没有影响了。所以只需要把偶数位置拿出来，每次相当于把某一堆中一些元素扔掉。所以是偶数位置的异或和。
哦那是不是可以直接设 $\text{sg}_{i,j,0/1}$ 表示 $i$ 子树内，$\bmod k=j$ 的位置中，在奇数位置/偶数位置的异或和。然后换根就随便推推就行。$\mathcal{O}(nk)$。
正解
好像是对的，代码鸽了
CF1497E Square-free division
瞎扯
先套路地把所有平方因子除掉，然后变成子段中没有数字相同。如果 $k=0$，贪心是对的。
考虑 $\text{dp}$！设 $\text{dp}_{i,k}$ 为前 $i$ 个元素，用了 $k$ 次修改的最小子段个数。然后就不会了
好像可以 $\mathcal{O}(nk^2)$。可以暴力枚举最后一段花费了多少个修改，设 $l_{i,k}$ 为以 $i$ 为右端点，修改了 $k$ 个位置，最左的左端点是谁，然后就行了。$l$ 可以直接双指针。
总结
此问题有一个很简单的 $\mathcal{O}(n^2k)$ 做法，而此处又用到了那个类似于修改枚举项的 $\text{trick}$，改为枚举修改了多少个位置，再根据贪心，得到更为优秀的解法。
以后对于这种枚举维度不太平衡的问题，一般可能枚举量较大的维度更容易想到，但也可以尝试着切换一下枚举的内容。
CF1497D Genius
瞎扯
卡空间，估计要 $\mathcal{O}(n)$ 空间，但是时间可以 $\mathcal{O}(n^2)$。
感觉解决问题的顺序限制有点紧，每次相当于在数轴上跳来跳去，但是每次要比上次跳得远。
如果上次从 $i\rightarrow j$（$i < j$），下一次要么去 $j+1$ ~ $n$，要么去 $1$ ~ $i-1$。如果 $i>j$，那就不能往左跳了，只能接着往右边跳，而且要跳到 $i$ 右边。而且贡献恒 $\ge 0$，在两次移动之间，如果能插入一次，答案不会变小。
那一次移动的路径一定是不断右移，在右移的过程中考虑往左边跳一下再回来。
如果往左跳的 $s$ 在前后两个 $s$ 之间，等于没跳。
md 咋每个问题可以解决多遍啊
那显然就是每次往右边跳，然后找左边 $\Delta$ 的 $\max$。
正解
md 好像跟我推的区别挺大的
考虑 $\text{dp}_i$ 表示仅考虑前 $i$ 个元素的答案。当只考虑前 $i$ 个时，他们都可以跳到 $i+1$。$i+1$ 也可以直接跳到他们中的任意一个。
所以直接拿他们相互转移就行了，注意转移顺序的细节。
总结
有时候一些题看起来很贪心，但如果贪心没有很好的做法，也可以考虑 $\text{dp}$。一般来说，贪心题大多数都能用 $\text{dp}$ 求解，但是可能复杂度偏高，需要通过贪心证明的一些细节来优化状态。
CF1495D BFS Trees
瞎扯
考虑 $\mathcal{O}(n^2)$ 枚举一下顶点对，然后数。
首先可以 $\text{Floyd}$ 一下，那一个点 $x$ 的父亲要满足他和 $x$ 之间的边，是两张最短路图上的边。
然后 $\mathcal{O}(n^2m)$ 算算是不是就行了？
正解
差不多了。一个细节是 $x,y$ 之间一定只能恰好有一条最短路，否则这些在最短路上的点、边都要在最后的树上，这样就会成环。这个 $\text{BFS}$ 判一下就行。
CF1572B Xor of 3
瞎扯
显然对三个 $0$ 或 $1$ 操作是没有意义的。异或和不变，可以用来判无解，如果序列里没有 $0$ 也无解。
擦这和 CF1438D Powerful Ksenia 咋这么像，那就也先变得两两一样！
奇数的情况下，如果最后剩的是 $1$ 说明无解，否则每次只要找到 $11$ 状的边界，拿一个 $0$ 把 $11$ 吃掉就行了。
偶数不会了！
正解
奇数好像是对的。
对于偶数的情况，如果能找到一个长度为奇数，且异或和为 $0$ 的前缀，那对这个前缀与相应的后缀分别做一遍奇数的部分就行了。
可以证明，如果不存在这样一个前缀，则无解。如果不存在这样一个前缀，则说明 $a_1=a_n=1$，且每一个偶数 $i$ 满足 $a_i=a_{i+1}$。
每次操作，由于必然会覆盖一个偶数 $i$ 与 $i+1$，所以剩下的一个元素一定是不会改变的。因此，$a_1$ 不可能从 $1$ 变成 $0$，因此无解。想到一模一样的卡人方法 但是还是没想到
CF1494E A-Z Graph
瞎扯
好难啊这为啥只有 2400
如果存在长度为 $2$ 的同色环，则所有询问全部解决了。哦如果存在长度为 $2$ 的环，则点数为奇数的询问都解决了。
哦如果没有环就直接 $\text{GG}$ 了 我是 sb 吧。
如果没有长度为 $2$ 的环，奇数怎么搞呢？草如果有 $x\rightarrow y$ 的边，但是没有 $y\rightarrow x$ 的边，直接就挂了，所以 $k$ 是奇数就做完了。
哦对于 $k$ 是偶数，经过的边，所以一定会有一条边恰好正着反着颜色相同，所以就行了。哈哈做完了
正解
过了。
CF1594F Ideal Farm
瞎扯
考虑每一个前缀和，首先 $0$ 和 $s$ 都必须要选，然后每选择一个 $x$，就会 $\text{ban}$ 掉 $x-k$ 和 $x+k$。那如果能选择 $\ge n$ 个前缀和的点，使得他们互相没有 $\text{ban}$ 掉，是不是就是 $\text{NO}$。
哦，那显然贪心从大往小能选就选，那每 $2k$ 个能选 $k$ 个。剩下的 $m=s\bmod {2k}$ 可以讨论出能选择几个，如果 $m\ge k$ 那至多选 $k-1$，否则可以选 $m$ 个。
正解
差不多就这样。
需要特判一个情况：$s=k$，这样实际上 $0$ 和 $s$ 已经被互相 $\text{ban}$ 掉了，所以一定是 $\text{YES}$。