AtCoder AGC044 总结
A
试一试,发现分别找到 \(\le x\) 的 \(2,3,5\) 的倍数,\(>x\) 的 \(2,3,5\) 的倍数,然后记忆化搜索做即可,证明不会。
B
每个位置维护一个 \(a_{i,j}\) 表示它逃出去的最小路径,每次一个人离开后,这个人对于路径的贡献就从 \(1\) 变成 \(0\),暴力地递归更新它周围点的 \(a\) 即可。每次更新会使 \(a\) 减一,复杂度是初始 \(a\) 的和,是 \(O(n^3)\) 级别。
C
我们只关心位置模 \(3^n\) 的值即可,因此大于 \(3^n\) 也没关系,那么加一就没有限制了。考虑把问题放在在三叉的字典树上,翻转打标记即可,全局加一问题是经典的(考虑从低位到高位建树,那么所有前缀为连续的 \(2\) 的路径都会变成 \(0\),递归前缀为连续的 \(2\) 的路径即可)。
D
首先把所有字符问一次长为 \(L\),那么可以知道所有字符的出现次数,也可以知道 \(S\) 的长度。考虑每种字符依次插入,发现当返回值 \(q=|S|-|T|\) 时当且仅当 \(T\) 是 \(S\) 的子序列。于是二分位置把 \(c\) 插入,询问 \(c\) 开始的后缀是否是子序列,这样可以把第一个 \(c\) 放到最左的位置。若有多个 \(c\),从上一个 \(c\) 开始的位置二分,询问前面个数个 \(c\) 与这个 \(c\) 开始的后缀拼成的字符串是否是子序列。
E
考虑特殊值。考虑 \(a_i\) 最大值,那么如果当前走到了最大值,那么一定不会再走,于是断环成链,首尾各放一个最大值。
记 \(f_i\) 为从 \(i\) 开始走的最大期望,则(对于 \(0<i<n\))
考虑把 \(\max\) 右侧的 \(b_i\) 消去,设 \(g_i=f_i-c_i\),则
只要解出 \(\frac {c_{i-1}+c_{i+1}}2-b_i-c_i=0\) 即可将 \(b_i\) 消去。由于 \(c_0,c_n\) 是无意义的,所以将前式移项得到 \(c_{i+1}=2(b_i+c_i)-c_{i-1}\),并随意指定 \(c_0,c_1\) 即可线性求 \(c\)。于是我们得到了(令 \(d_i=a_i-c_i\))
放在二维平面上,假设若没有 \(d_i\),那么就是 \((0,g_0),(n,g_n)\) 的直线。现在 \(d_i\) 会把直线往上「顶」,我们只需求 \(g_0,\{d_i\},g_n\) 构成的凸包即可。