Grandmaster 计划试题乱做 Part 1
CF1550E Stringforces
瞎扯
看不懂题
考虑二分答案。为啥 $k$ 只有 $17$/jk。二分答案之后就只需要每一种字符的最长段都在 $\text{mid}$ 以上就行了？
如果已经出现长度满足条件的连续段，这个字符就行了。
这东西不会是个什么 $2^k$ 吧/jk。或者是 $nk\log n$ 但是这样为啥不出 k=26。
考虑 $\text{dp}_S$ 是填好 $S$ 所需要的最小长度是不是就行了（。就枚举一下最后一个是谁就行了？
正解
就这么做（
总结
用时 $\text{25min}$。比 zxy 慢了 20 min/ll/ll/ll
大概看到这种东西直接考虑状压就行了？这种东西一开始可能是一个什么 $\text{dp}_{i,S}$ 表示前 $i$ 个字符能不能表示完 $S$，但是这是个 $\text{bool}$ 所以有点浪费，把 $i$ 换进值里就行。
CF1539E Game with Cards
瞎扯
直接暴力枚举，考虑能否在枚举的地方，切换左右手就行了？
然后二分一下找一找是不是就行了（
正解
就这么做（
实际上有一个 $\mathcal{O}(n)$ 的快乐做法：把问题倒过来做，把状态改成从当前点往后，现在换成左手/右手能不能行。因为这个状态是切换的端点，所以左手右手都可以快速得出状态（比如当前切换为左手，则上一次必然是右手），找下一个切换点的话，必定会找距离自己最近的那个，因为越远越劣。
总结
感觉这种题首先肯定是考虑全局的状态长什么样子，比如此题就是左手右手切换。然后据此进行 $\text{dp}$ 或贪心。
还有一个可以考虑的方向是从终止状态开始倒推，如果能推出初始状态就是合法的。有时候会有神奇的效果。
CF1536F Omkar and Akmar
瞎扯
是 $\text{ICG}$，所以只有必胜和必败。终止状态一定不存在两个相邻的空位，对于每一个空位，一定是左右字符不同的。一段连续的放好的位置肯定是 $\tt{ABABA..}$ 状。
现在要考虑什么样的状态不可能出现。是不是只有初始状态和最终状态胜负不同的局面不会出现？
如果存在两个点，夹在中间的点个数是偶数，且两个点同色，则先手能在中间多放一步；同理，中间点数是奇数，两点异色，没有领先优势。
如果后手在中间放了一个奇怪的地方，是不是能证明不改变胜负啊（
好像可以证明，同色的段一定可以使先手多放 $1$，异色不改变状态？归纳一下是不是就行了。很对啊，哦好像直接会被划分为若干子问题（在出现了两个点被染色之后）。
那好像 $n\ge 4$ 的时候，后手必胜啊。$n=3$ 好像后手也必胜。好惨啊先手
先讨论一下 $n=3$，剩下的是不是 $\text{B}$ 第一步显然会放在一个和之前 $\text{A}$ 放的不相邻的位置，并与 $\text{A}$ 同色啊。
擦好像不用，好像直接放在 $\text{A}$ 边上就行了。然后随便 $\text{A}$ 再放在哪里，一定会出现一侧是同色的，然后就赢了。
划分为子问题之后 $\text{B}$ 是不是死不掉啊（，所以好像任意结束状态都行？
正解
差不多，但不完全差不多
考虑最终状态，肯定是一些连续的 $\tt{ABABA..}$，两个连续段之间有恰好一个空格，且空格两边是一个 $\tt{A}$ 一个 $\tt{B}$。所以可以考虑把他们合起来，这样合并之后还是 $\tt{ABABA..}$ 的形式。
考虑如何从这个角度证明后手必胜。当我们把所有的段都合并起来，则会变成一个环。由于是一个环，所以中间的空格个数应该恰好是偶数！偶数说明先手后手下的一样多，这就可以证明后手必胜了。
所以最后，可以枚举终止状态 $f(n)$，游戏过程就有 $n!\times f(n)$。这个方案可以枚举中间的空格个数：
$$ f(n)=2 \times \sum_{2|i} i!\times (\binom{i}{n-i}+\binom{i-1}{n-i-1}) $$
总结
看一看我的瞎扯里有啥是有用的
终止状态一定不存在两个相邻的空位，对于每一个空位，一定是左右字符不同的。一段连续的放好的位置肯定是 $\tt{ABABA..}$ 状。
这个看起来很有用，这也太有用了。这时候如果直接把空位合并，就可以直接导出所有的结论了。不过之后那个归纳证明好像也能导出一样的结论奥，所以四舍五入做出来了（bushi
这种题还是要从终止状态的性质来考虑，观察什么样的状态是可行的，什么样是不可行的，说不定可以找到一些普遍规律。
CF1527E Partition Game
瞎扯
首先盲猜一手复杂度，感觉是 $\mathcal{O}(nk)$ 之类的。
考虑 $\text{dp}$，设 $\text{dp}_{i,j}$ 表示前 $i$ 个划分成 $j$ 段。显然可以分层转移。是不是有决策单调性啊（
考虑一下 $a<b<c<d$，$w(a,c)+w(b,d)$ 和 $w(a,d)+w(b,c)$ 的关系。好像只需要分别考察每一种数就行了。
哈哈好像交叉 $=$ 包含/hanx。那直接决策单调性！然后就是 $\mathcal{O}(nk\log n)$ 了！很对啊（bushi
欸代价咋算。好像不会，这个 $\text{last}(x)-\text{first}(x)$ 一看就能拆成若干 $\text{pos}(x)-\text{pos}(x-1)$。莫队状指针移动！
正解
就这么做。
莫队状指针移动的复杂度证明可以分指针左端点和右端点分开讨论，可以分析出来指针移动次数就是 $\mathcal{O}(n\log n)$ 级别的。
总结
这种区间划分问题，写个式子就很像决策单调性的式子，其贡献也确实很有可能满足决策单调性。
决策单调性由于在考虑某一个 $\text{mid}$ 处的决策点的时候是近乎暴力的，所以实际上贡献的计算形如指针移动。而莫队状计算也恰好是指针移动，所以决策单调性对莫队状移动是很友好的（
CF1527D MEX Tree
瞎扯
考虑计算 $c(i)$ 表示包括 $0$ $\sim$ $i$ 的路径条数。则 $\text{mex}=i$ 的路径条数是 $c(i-1)-c(i)$。
考虑加入一个点。显然首先 $[0,i-1]$ 需要在一条链上。然后考虑加入 $i$，如果仍然在一条链上，就更新链的端点，否则就无解了。
然后每次的答案就是两个端点的子树大小？（去掉中间路径的部分）感觉很对。
正解
就这么做（
总结
$\text{mex}=x$ 的性质中，$x$ 没出现这一点易于处理，但是 $x$ 是最小的没出现的点不太好处理。但是 $x$ 是最小的没出现的，等价于比 $x$ 小的都出现了。
而且对于本题这种，所有 $c(i)$ 都需要求解，且相邻 $c$ 变化不太大的东西，一般都先考虑增量。
CF1523E Crypto Lights
瞎扯
擦 看错题了
一盏灯被点亮之后不会关掉，不知道有啥用。
一个状态没有停止，当且仅当任意亮着的灯之间的距离 $>k$。对于一组方案，点亮了 $x$ 盏灯，对答案的贡献是：
$$ \dfrac{x}{n^{\underline{x}}} $$
这不会还要数据结构维护吧（
一个状态，不存在一个位置使得在这里开灯仍然合法，当且仅当每一个空段的长度都 $\in[k-1,2k-1]$。所以只需要计算这样的所有状态的期望，最后 $+1$ 就行了。
如果不是这个模数，是不是可以直接多项式！
欸但是可以直接把期望换成算概率，就变成：
$$ \sum_{i=1}^n f(i) $$
$f(i)$ 表示开了 $i$ 盏灯还没结束的概率。这能算吗（
欸这就是空段都 $\ge k-1$ 的方案数。那放了 $x$ 个，且空段都 $\ge k-1$ 的方案数是：
$$ \binom{n-(k-1)\times(x-1)}{x} $$
那么概率就是：
$$ \dfrac{\binom{n-(k-1)\times(x-1)}{x}}{\binom{n}{x}} $$
好像就做完了？
正解
就这么做（
总结
先来看看瞎扯里从哪里开始对
好像从把期望换成概率开始就对了。这好像说明对于如下的期望计算方式：
$$ \sum_{i} p_i\times v_i $$
其中 $p_i$ 是概率，$v_i$ 是 $i$ 的贡献，可以考虑变成：
$$ \sum_i p_i\sum_{j=1}^{v_i} 1=\sum_i (v_{i}-v_{i-1})\sum_{j=i} p_j $$
也就是差分一下，然后就可以把“恰好”的概率 $p_i$ 换成“至少”的概率了。这种做法对于一些合法状态好算，终止状态难算，且贡献差好算（比如此题贡献差为 $1$）的东西貌似很友好。
CF1523D Love-Hate
瞎扯
不少于就是 $=\left\lceil\dfrac{n}{2}\right\rceil$。那就是一半的人的按位与的 $\text{popcount}$ 的最大值。
显然这个答案 $\le p$ 而且可以顶到上界，那可能出现在答案里的元素也至多只有 $2p$ 个。
这东西如果有一组解，要怎么 $\text{check}$ 啊。不会了 偷看题解！
正解
好像跟我推的没啥关系的样子（
如果知道一个人喜欢所有的货币，那最后的货币一定是这个人的子集，这可以简单状压 $\text{dp}$。
则现在只需要找到一个在最优答案里的人。因为在最优答案里的人至少有一半，所以可以随机化！
于是就做完了。
总结
感觉这种随机化题有点想不到......
好像自己的瞎扯一直都在朝着 $p$ 很小的方向，希望从这里开始暴力枚举。实际上 $p$ 小的作用是最后在检查的时候做状压......
这题的做法好像是从类似写 $\text{checker}$ 的角度来进行的，大概是利用了按位与优良的性质，从而在暴力枚举了一个人之后，大大减小了枚举量。
CF1510B Button Lock
瞎扯
只有 $2^{10}=1024$ 个点，所以可以乱搞！可以先建一张图，每次从原点走到 $\text{R}$，要求把每个特殊节点都走一遍。
可以把图缩一缩，变得只有原点和特殊节点，特殊节点如果 $T\subset S$，就从 $T$ 到 $S$ 连一条 $\text{popcount}(S-T)$ 的边。
那现在就是要找到一些路径，使得覆盖所有点，且最小化路径长度和。
显然每次要从一个入度为 $0$ 的点开始。
欸，好像网络流就行了？每个数字拆成两个点，中间连流量为 $1$ 就行了。
正解
就这么做（
总结
对这种数据范围看起来有些奇怪的最优化问题，没有很好的 $\text{dp}$ 做法，则可以考虑网络流。
很多奇形怪状的问题，都可以用网络流解决
CF1499F Diameter Cuts
瞎扯
感觉要设 $\text{dp}_{i,k}$ 表示 $i$ 子树内包括根的联通块直径是 $k$ 的方案数。长得有点像个 $\text{dp}$ 套 $\text{dp}$，估计最后是背包状转移。
我好像只会三维状态（，好像要 $\text{dp}_{i,x,y}$ 表示 $i$ 子树内包括 $i$ 的直径是 $x$，连到 $i$ 上的最长链是 $y$ 的方案数。
欸好像不用记直径是 $x$，反正只要 $\le k$ 就行了。然后现在只要求每个子树接在 $i$ 上的最大值次大值加起来 $\le k$ 就行。
哦那好像直接 $\mathcal{O}(nk)$ 力。
正解
哈哈 1A 了
CF1499E Chaotic Merge
瞎扯
擦 看了半天原来范围只有 1000
那就先无脑设 $\text{dp}_{i,j}$ 是 $x$ 最后一个元素到 $i$，$y$ 最后一个元素到 $j$ 的合法方案数。
好像还要一个 $0/1$ 表示现在结尾是 $x$ 还是 $y$。如果当前 $x,y$ 的子串都非空，转移显然。现在只需要考虑有一个从长度为 $0$ 到长度为 $1$ 的情况。
那把 $\text{dp}_{i,0}$ 的位置设成 $y$ 还没填数是不是就行（
正解
1A