BZOJ3943: [Usaco2015 Feb]SuperBull
我们在$i-j$之间连边权值为$a[i]\otimes a[j]$。然后做这张图的最大生成树即可。
因为我们只要让一个点的父亲淘汰掉这个点即可。
BZOJ3890: [Usaco2015 Jan]Meeting Time
$bitset$大法吼！
BZOJ3886: [Usaco2015 Jan]Moovie Mooving
没想出来
首先注意到这个更新是有先后关系的，就是我们不能简单的先用哪个来更新答案，因为我们并不知道先用哪个。
所以比较麻烦。
然而$n<=20$给了我们状压$DP$的思路。
而n这么大只允许我们设一维状态$f[i]$表示选用的集合为$i$然后什么呢？
只能是从$0$开始最远呆到什么时候把。
然后枚举最后一个看的电影，贪心选取最后面的即可。
BZOJ3942: [Usaco2015 Feb]Censoring
我们考虑用$hash$来判断是否存在$t$子串。令$n$为$s$串的长度，$m$为$t$串的长度，$k$为$t$串的$hash$值。
首先我们将所有起始位置长度为$m$的子串的$hash$值求出来，然后如果$hash[i]==k$，那么将$i$放入$set$。（一开始全部放入$set$T出翔）
然后每次删掉一个$t$串后，最多会有$m$个$hash[i]$要发生变化，但是带胶布，我们可以暴力维护这$m$个$hash[i]$。
因为$O（\frac{n}{m}*m）=O（n）$
最坏复杂度是$O（\frac{n}{m}*m*logn)=O（nlogn）$
UPD:看了网上的题解，如果可以把题意转化成把一个一个字符加到$s$后面，某一时刻后缀为$t$就删掉这个后缀。这就是$KMP$傻逼题了。
评论 (0)
