6
3
2015
0

BZOJ刷水记录

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$傻逼题了。

Category: 杂题 | Tags: | Read Count: 701

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com