发表于 | 分类于 | | + s

BZOJ 1596
本题可以贪心做，如果一个节点他的孩子没被覆盖，并且这个点和他的父亲没覆盖，就覆盖这个点的父亲，这里主要用树形DP来做。
设
$f(u, 0)$为不在$u$建基站，$u$与$u$的子树都有信号
$f(u, 1)$为在$u$建基站，$u$与$u$的子树都有信号
$f(u, 2)$为不在$u$建基站，$u$没有信号，$u$的子树都有信号

以上这种状态是非常常用的

我们看转移(很容易推出来):
$f(u,0)=min(f(j,1)+\sum min(f(son, 0/1)))$
$f(u,1)=\sum min(f(son, 0/1/2))$
$f(u,2)=\sum f(son, 0)$

阅读全文 »

发表于 | 分类于 | | + s

BZOJ 1559
题意：见上。

很容易想到这是一个AC自动机(经典题，多模式串)上的状压DP(数据范围)，那么列出方程即为$dp(i,st,u)$为密码前$i$位包含模式串状态$st$，在AC自动机上$u$点的方案。

那么转移很显然，即刷表
$$
dp(i+1,st|zt[v], v)= \sum dp(i,st,u)
$$

然后考虑如何输出方案。
因为这个数字小于等于$42$才输出方案，可以考虑爆搜(方案DP不好记录前驱)

重要结论

字符串都是紧密结合的，不存在自由的可以填$26$种字母的位置

证明很显然，因为如果存在这个，那么会对答案产生$26$的贡献，而字符串可以交换位置，那么一定方案数大于$42$，那么我们只需要预处理两个模式串组合最少的字符长度，$O(n!)$枚举模式串排列即可，注意要舍掉不合法的，即长度大于$L$的。

知识点：
1、发现有阻碍的地方，要从这里下手，在纸上应该多写写

阅读全文 »

发表于 | 分类于 | | + s

BZOJ 2442
设$dp(i)$为$i$不选，之前的选择合法时损失的最小效率
则$dp(i)=min(dp(j))+e_i$
而这是$O(n^2)$的，我们发现$min(dp(j))$满足单调性，且是一段区间的最小值，所以可以用单调队列来优化

阅读全文 »

发表于 | 分类于 | | + s

BZOJ 3378
$O(n^2)$算法肯定不行，我们尝试拆公式
对于$max(V_i, V_j)$，我们把牛按$V$排序，然后就可以消除$V$的影响，不再考虑这部分
对于$|X_i-X_j|$,我们不妨把他分成两部分，$(X_i-X_j) +(X_j-X_i)$
然后$\sum((X_i-X_j) +(X_j-X_i))=NUM_l \times X_i - SUM_l +SUM_r - NUM_r \times X_i$
其中$SUM_l$是在$X_i$左边的牛到起点的距离和，$SUM_r$同理
$NUM_l$是在$X_i$左边的牛的头数，$NUM_r$同理

阅读全文 »

发表于 | 分类于 | | + s

模板及讲解

字符串Hash的核心就是把原本$O(n)$比较两个字符串变成$O(1)$比较两个Hash值(整数)。

Hash的方法取决于是否会冲突，这里运用不同模数巧妙解决冲突
因为字符串相等、字符串ASCII码前缀和具有单调性，所以经常用固定左端点二分右端点来解决问题(有时用二分查找、map、桶、排序等解决问题)

BASE 选取：
1、不要将任何数对应到 0 ，例如将 A对应到0 则无法区分AB、B
2、大于$max($对应数$)$

双Hash

两个模数$MO1,MO2$(最好为质数，$19260817, 19660813$)，只有两个模数的值都相同才判定Hash值相同
BASE：大于所有字符串取值的一个数，不能包含模数的质因子
求Hash值：
$$Hash=(s_1 \times BASE^{n-1}+ s_2 \times BASE^{n-2} + … + s_n) \mod MO$$

快速hash一个字符串的所有子串：先对串的所有前缀Hash，记为$Hash_i$，设$p_i=BASE^i$，则
$$Hash_i=(Hash_{i-1} \times s_i) \mod MO$$
$$Hash_{i, j}=(Hash_{r} - Hash_{l-1} \times p_{r-l+1}) \mod MO$$
$Hash_{i, j}$即为答案。

const ULL BS = 300;
ULL hsh[MAXN], p[MAXN];

p[0] = 1;
for (int i = 1; i <= n; i++) p[i] = p[i - 1] * BS, hsh[i] = hsh[i - 1] * BS + (s[i] - 'a');

inline ULL getH(int x, int y) {return hsh[y] - hsh[x - 1] * p[y - x + 1];}

运用 unsigned long long 的自然溢出完成取模(能双Hash就双Hash，自然溢出很容易被卡)。

二维 Hash

例题：Bzoj 2351

给行列分别hash一次，行先hash，然后将hash值再hash一次，即hash列

然后查询子矩阵Hash值直接像二维前缀和一样做即可，类比于一维的 Hash 方法

树 Hash

对于有根树的 Hash。无根树找重心当根。

$h[x]$表示$x$为根的子树的hash​，$g[x]$表示$x$为根时全树的​hash​。
$$
h[x] = 1 + \sum_{y \in \text{son}(x)} h[y] \times p[\text{siz}[y]] \\
g[x] = (g[fa] - h[x] \times p[\text{siz}[x]]) \times p[n-\text{siz}[x]] + h[x]
$$

例题1: BJOI2015 树的同构
例题2: JSOI2016 独特的树叶

阅读全文 »

发表于 | 分类于 | | + s

BZOJ 3223
平衡树模板题，处理区间问题，本题用下标来做$key$，区间翻转直接交换两棵子树，因为$key$按中序遍历有序。而交换两棵子树虽然破坏了排序二叉树的性质，但是并不影响解题，只需要知道当前节点在区间的某个位置就行了

阅读全文 »

发表于 | 分类于 | | + s

模板及讲解
非旋转Treap：
Treap=Tree+heap，即键值$key$(满足排序二叉树性质(左小右大)，并且按照中序遍历有序)，附加值$val$(满足堆性质(孩子都比父节点小))
核心操作$O(nlogn)$：

  • $newNode(x)$ 新建一个以$x$为权值的点
  • $merge(a, b)$ 把$a$树和$b$树合并，必须满足$\forall key_a < \forall key_b$
  • $split_v(a,v,x,y)$把$a$树按权值$v$分成$x,y$两棵树，一棵树小于等于$v$，一棵树大于$v$
  • $split_k(a,v,x,y)$把$a$树按前$k$个分配成$x,y$两棵树

能够实现的操作$O(nlogn)$：

  • $rank(x)$ 查询$x$的排名
  • $kth(x)$ 查询第$x$大的数
  • $pre(x)$ 查询$x$的前驱
  • $succ(x)$ 查询$x$的后继
  • $insert(x)$ 插入一个数权值为$x$
  • $del(x)$ 删除一个权值为$x$的数

具体可以看相关代码
写时注意：
1 不要忘了srand(19260817)
2 $split$里$x, y$用*&
3 主程序记得加$initTreap()$
4 $merge$前面记得加赋值

可持久化Treap：
暂略

常见题型
1、直接使用操作完成
Q: 求第$k$大\求$x$的排名……
解: 直接套模板。
例题: bzoj3224
2、操作区间
Q: 翻转某个区间
解: 非旋Treap处理区间。
例题: bzoj3223

阅读全文 »