昨天晚上肝了几道斜率优化的题,这里一起把题解写了吧。
传送门
这真的是个黑科技了。以后忘了怎么写KMP就写FFT了。
给出两个长度不超过$10^5$的由小写英文字符构成的字符串$S,T$,询问$T$在$S$中出现了多少次及每次出现的位置(下标从$0$开始)。
$T$中可能存在?
通配符,可以匹配任何英文字符。
传送门
简直就是万有引力吧。
给出$n$个数$q_i$,定义:
$F_i={j<i}\frac{q_iq_j}{(i-j)^2}-{j>i}\frac{q_iq_j}{(i-j)^2}$
$$E_i=\frac{F_i}{q_i}$$
求$E_i$
传送门
我一定是脑子烧坏了,FFT都写不对。
给你两个长度为$n$的序列$a,b$,满足$a_i,b_i\in [1,m]$,$a,b$中的数组可以循环(即可以把开头放到结尾,结尾放到开头)。
定义$a,b$之间的差异值为$$\sum_{i\in[1,n]} (a_i-b_i)^2$$。你可以选择一个常数$c$,使得$a$或$b$中的每个数加上$c$。
求最小差异值。$n\le 50000,m\le 100$
Update your browser to view this website correctly. Update my browser now