AtCoder Beginner Contest 196 题解

· · 个人记录

A 没啥好说的

B 没啥好说的

C 没啥好说的

D 直接 O(3^n) 不到的暴力，没啥好说的

F 参考《残缺的字符串》，

\begin{aligned} ans&=\min_{0\le i\le n-m}^{} \sum_{j=0}^{m-1} (s_{i+j}-t_{j})^2\\ f_i&=\sum_{j=i}^{m+i-1} s_{j}^2+\sum_{j=0}^{m-1} t_j^2-2\sum_{j=0}^{m-1}s_{i+j}t_{j}\\ \end{aligned}

其中前两项可以前缀和，最后一项可以卷积。O(n\log n) 解决。

（第二次离AK差一道题 /dk）

E 听说是吉司机线段树的板子，但是我不会

发现每个操作都可以表示成 f_i(x)=\min(c_i,\max(b_i,x+a_i)) 的形式。我们考虑两个操作的复合，f_2(f_1(x))=\min(\min(c_2,c_1+a_2),\max(\max(b_2,b_1+a_2),x+(a_1+a_2)))。于是根据这个法则我们可以得到最后的复合函数是 \min(c,\max(b,x+a)) 的形式。算一下即可。