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序中,一个点的子树是一段连续的区间,那么,可以使用数据结构来维护修改,如树状数组,线段树。