Day3

【作文】
题意:求一个字符串的子串,使其在字符串中至少出现三次,分别是前缀、后缀、以及非前、后缀。
字符串匹配,考虑KMP,分别将字符串删去前一个字符和后一个字符,将这两个串进行匹配,求出前缀、后缀的可行长度。对原串求next数组,在可行前后缀的位置求答案。
正解是二分,哈希暴力求出前后缀的可行长度,二分这些长度暴力判断。
【智能机器人】
题意:用多个机器人遍历一棵树,使消耗的代接最小。
首先,一个明显的结论,如果从某个节点往下走去了多于1个机器人,那么它们绝对不会再回头.如果它们有一个回头,则令这个机器人处于该节点的父节点不动,令另外一个机器人先走这个机器人走的路线然后在走自己的路线,就会更优!
令f[x][i]表示i个机器人走完x子树的最优值。g[x]表示只用一个机器人走x子树(即机器人要回到x点)。可得:
f[x][i] = min(f[x][i - j] + f[y][j] + w * j)。
f[x][i] = min(g[x] + f[y][i] + w * i)。
f[x][i] = min(f[x][i] + g[y] + w * 2)。
g[x] = g[x] + g[y] + w * 2。
【大都市】
题意:给定一棵树,从1结点出发,每次修改一条边,求到某个点的路径上经过的未修改路径树。
可以发现,如果修改一条边,则这条边所连接的子树答案都会改变(-1)。联想到DFS序,在DFS序中,一个点的子树是一段连续的区间,那么,可以使用数据结构来维护修改,如树状数组,线段树。

[BZOJ 1901] Dynamic Rankings

树状数组套主席树。

考虑无修改求区间第 K 大的情况:因为主席树之间支持相加减,故可以维护一些包含 1~i 的线段树,计算它们的树前缀和,从而快速得到区间 [l, r] 中的第 K 大数。

考虑对于数的静态区间和与动态区间和的关系——前缀和与树状数组。

类似地,我们可以维护一个树状数组,但线段树记录的不再是前缀和,而是树状数组的辅助数组的值。

这样就能做到带修改的区间第 K 大值查询了。

Reference:

http://blog.csdn.net/u014664226/article/details/47839973

代码如下:

继续阅读[BZOJ 1901] Dynamic Rankings

[BZOJ 2743] [HEOI 2012] 采花

树状数组 + 差分

看上去就像莫队算法。

然后发现数据有点大......算了。

可以发现每种花只有当前区间中的第二枝对后面有贡献。则计算答案可以利用差分方法:若在 pos 位置的一束花能对后方产生贡献,则在树状数组中将 [pos, n] 区间 +1。最终此时某个区间答案即为区间和。

记录下位置 i 后第一次出现该位置颜色花的位置 nxt[i]。考虑从一个区间 [L, R] 到另一个区间 [L+1, R] 答案的变化:既然位置 L 处的花退出了区间,那么花 i 对答案的影响也要被去除,即在树状数组中把 [L, n] 答案 -1。原本 nxt[i] 位置的花是区间内第二朵花,现在也变成了第一朵,因此更新答案,[nxt[i], n] 区间 +1。

既然知道了相邻区间的转移,那么整体的做法也可以明确了:先将读入的所有区间按左端点排序,然后按刚才的方法在左端点间一位一位转移,答案就是区间和了。

代码如下:

继续阅读[BZOJ 2743] [HEOI 2012] 采花