AGC007
A Shik and Stone
我是沙比这都能蛙一发
https://agc007.contest.atcoder.jp/submissions/7946110
B Construct Sequences
造两个等差数列\(20000,40000,\ldots,20000n\)和反过来作为基础\(A,B\)，然后在上面减一下就好了。
https://agc007.contest.atcoder.jp/submissions/7946428
C Pushing Balls
真tmd神仙题
每次操作后移除对应的石子和洞，并重标号
打表可证（真tmd是打表啊）若干次操作以后，可将一段长度的期望直接作为长度计算，然后这个tmd还是个等差数列= = = = = =
然后打表算算算（甚至tm可以手打
https://agc007.contest.atcoder.jp/submissions/7958580
D Shik and Game
简单打牌，不会可以谢罪= =
可以看出方案一定是每次选择一个前缀\(A[1-i]\)，从\(1\)往返一次\(1,i\)，然后等到\(1\)处金币出来，直接走到\(i+1\)（期间可以拿\(1-i\)所有金币）
设\(f_i\)表示后缀\(i-n\)的答案
dp式：\(f_i=\min\{f_{j+1}+x_{j+1}-x_i+\max\{T,2(x_j-x_i)\}\}\)
\(2(x_j-x_i)\)与\(T\)关系是单调的，\(<T\)单调队列维护，\(>T\)确定了直接记一个min
https://agc007.contest.atcoder.jp/submissions/7959461
E Shik and Travel
神仙题
（这场8个切C，2个切E，无数人切D，5人切F
先二分
设\(f[i][a][b]\)表示点\(i\)，入边是\(a\)出边是\(b\)（\(a,b\)完全可以交换），然后\(a,b\)是没有限制的（因为直接连根的长度任意
然后就神仙优化了
对于相同的\(a\)留最小的\(b\)就行了，所以可以优化掉一维
对于相同的\(b\)留最小的\(a\)也行了，所以\(f[i]\)只用记\(O(siz)\)个二元组\((a_j,b_j)\)，其中\(a\)严格递增\(b\)严格递减，剩下的都可以不要
然后转移的时候点\(i\)会有一条路径从\(ls\)子树到\(rs\)子树，我们要满足这一条\(\leq mid\)
很蠢（用原来dp方法）的办法是那么枚举\(a,b,c,d\)，其中\(b+c\leq mid\)，可以转移给\(a+d\)
优化以后只要枚举一个子树中的\(a\)可以得到最小的\(b\)，然后根据\(b\)得到\(c\)的范围，再选一个最小的\(d\)
这个过程可以双指针优化
因为只需枚举三元组较少的儿子在另一个查询，复杂度同启发式合并
https://agc007.contest.atcoder.jp/submissions/7964497
F Shik and Copying String
题解好神啊
先不考虑最优化步数，\(T\)串显然可以缩连续段，问题转化成：\(S\)串选一个子序列，使得子序列等于缩完后的\(T\)，然后由于只能往右走要满足位置都在\(T\)对应左边
作完dp可以判-1了
然后是最优化步数，这里我sb了
dp完之后过程可以转化成由决策点扩展到整个区间，那么首先扩展到区间左端点，最后花一步全部扩展完毕，新的问题是，有\(m\)只鸡贼位置是\(a_i\)，想到\(b_i\)去，只能向右走，满足\(a_i\leq b_i\)，而且鸡贼相对位置不能改变。这个东西直接模拟是\(n^2\)的，不过可以用单调队列维护做到\(O(n)\)。