删除完这个字符串后面的就接到前面

我们可以想到用栈解决

然后判断剩下的串当前位置是否和目标字符串匹配我们可以用hash来解决

其实下面给出的a数组没什么鸟用

列出方程：

E = \sum_{i=0}^{n-1} \frac 1n \times ( i+ flag \times E)

解方程： E = \sum_{i=0}^{n-1} \frac 1n \times ( i+ flag \times E) \\\\ E = \sum_{i=0}^{n-1} \frac in + (1 - \frac mn)E \\\\ \frac mnE = \frac {\frac 12n(n-1)}n \\\\ E = \frac {n(n-1)}{2m}

LG 3953 逛公园

题意: 求dis(1,n)<=MinDis(1,n)+K的路径数

用拓扑啊什么的一想就很麻烦。

有一种玄学的做法：记忆化搜索

f[x][k]表示dis(x,n)<=MinDis(x,n)+k的路径数。

先跑一般反向的最短路,然后dfs

考虑边(x,y,w),

\because Mindis[x]-Mindis[y]+w<k

\therefore f[x][k]+=f[y][k-(Mindis[x]-Mindis[y]+w)]

\therefore f[x][k] = \sum f[y][k-(Mindis[x]-Mindis[y]+w)]