显然是 vp 。
传送门 – Educational Codeforces Round 85 (Rated for Div. 2)
题目难度尚可，手速快点大概可以阿克？（虽然不会做 G
总结：做简单题的时候心态要平稳，手速要快，不要犹豫。（做后面几题的时候才提起兴趣是不好的
A
模拟，吃了三发罚时，吐力。
B
注意到可选的是一个集合而不是一个区间。如果要凑出 $i$ 个合法的数，最好的方法就是用前 $i$ 大的数凑。因此排序后扫一遍即可。时间复杂度 $O(n\log n)$ 。
C
显然是选定一个怪，将这个怪打死，然后引发爆炸，收割残血。
枚举第一个被打死的怪是哪个即可，时间复习度 $O(n)$ 。
D
手玩一发：
- 从 $1$ 出发，走完 $2$ 至 $n-1$ 后走向 $n$，这里的序列是
121314...1n。这个时候与 $1$ 相关的边基本走完了，最后剩下一条 $n\rightarrow 1$ 的边显然是最后走的。 - 接着 $n\rightarrow 2$ ，然后现在有 $n-1$ 个点，仍然在最小点上开始走，这是原问题的一个子问题。按从小到大的顺序走完 $2$ 相关的边后，走向 $n$ ，然后 $n\rightarrow 3$ ，变成了更小的原问题的子问题。
最优的策略就浮出水面了，最终的答案一定是 1213..1n 2324..2n 3435..3n ..n1 这样的。
然后就枚举每一段直接算即可。
E
对于 $v|u$ 的情况，最优解一定是从 $u$ 一直向下走到 $v$ 。对于 $v\not| u$ 的情况，最优解一定是先到 $\gcd(u,v)$ 再到 $v$ ，其实和第一种是等价的。
那么最短路是怎么形成的呢？
考虑用 $(a_1,a_2,\cdots,a_n)$ 表示 $p_1,p_2,\cdots,p_n$ 的次数，走一步的意义就是将 $a_i$ 减去一。假设当前一步改变了 $a_i$ ，下一步改变了 $a_j$ ，考虑这两步的贡献以及交换后的贡献：
$$
\left(\prod_{k\not=i}a_k+(a_i-1)\prod_{k\not=i,k\not=j}a_k\right)=\left(\prod_{k\not=i}a_k+\prod_{k\not=j}a_k-\prod_{k\not=i,k\not=j}a_k\right)=\left(\prod_{k\not=j}a_k+(a_j-1)\prod_{k\not=i,k\not=j}a_k\right)
$$
发现交换两步，距离仍然是不变的。因此 $(a_1,a_2,\cdots,a_n)$ 走向 $(0,0,\cdots,0)$ 的最短路径数其实就是：
$$
\frac{(\sum a_i)!}{\prod a_i!}
$$
然后就做完了。时间复杂度 $O(\sqrt{D}+d(D)q)$ ？
F
容易想到用 $dp_i$ 表示以 $i$ 这个位置结尾的最小答案，如果 $a_i\notin {b_1,b_2,\cdots,b_m}$ 的话不做定义。
发现 $dp_i$ 的转移其实就是找 $b$ 序列中 $a_i$ 的上一个数出现的位置。不妨以 $a_i$ 为下标开桶维护贡献。定义 $sum_j$ 表示 $\min\limits_{k\leq i,a_k=j}dp_k+calc(k+1,i)$ ，然后转移显然就有：$dp_i=sum_{las(a_i)}$ ，其中 $las(i)$ 表示数字 $i$ 在 $b$ 序列中的上一个数的值。
现在更新了位置 $i$，考虑如何维护 $sum$ ：
- 对于 $b_k<a_i$ ：那么必须选，$sum_k=sum_k+p_i$ 。
- 对于 $b_k\geq a_i$ ：可选可不选，$sum_k=\max(sum_k,sum_k+p_i)$ 。
- 对于 $b_k=a_i$ ：考虑上述情况后，还需要对 $dp_i$ 取 $\min$ 。
用线段树简单维护就好。时间复杂度 $O(n\log n)$ 。
G
卷积匹配，学到了。
考虑 $s_i$ 和 $t_j$ 匹配的条件是 $(s_i-t_j)(p_{s_i}-t_j)=0$ ，如果要整个串都匹配的话注意要平方一下再加起来，不然容易出问题，即 $\sum(s_i-t_j)^2(p_{s_i}-t_j)^2=0$ 意味着匹配成功。
将 $s$ 翻转后可以发现这是个卷积，然后卷一下就没了。
不过有许多细节。
首先，$\sum (s_i-t_j)^2(p_{s_i}-t_j)^2$ 可能大于模数，然后这样就变成了一个相当危险的单模哈希。处理方法有二：
- 拿两个模数各跑一遍，相当于双模哈希。
- 给每个字符赋上一个随机值。
第二种显然好写一些，然后就写了第二种（
然后，如果是用 $(s_i-t_j)^2(p_{s_i}-t_j)^2$ 来卷的话，拆开是九个式子，两个可以前缀和处理，剩下的只能 $\rm{NTT}$ ，这样就要做 $7$ 次 $\rm{NTT}$ ，本地极限数据要跑 $1.4s$ 。
不知道怎么搞，然后就学 EA 的做法信仰一波卷 $(s_i-t_j)(p_{s_i}-t_j)$，随机种子瞎打了一个交上去过了（/qiang（不过后面连着调了好几个种子都过不去 /dk
0 条评论