T1 Marathon

$O(n^2)$做法：

枚举每个要绕过的点，算出最小距离。

$O(n)$做法：

考虑删掉一个点$k$，对总的距离的影响是由原来的$dist(k-1,k)+dist(k,k+1)$ 变为$dist(k-1,k+1)$

因此，只需要算出每个点到它相邻两个点的距离，然后取最小即可。

T2 String

$O(n^2)$做法：

枚举每一个字串的起始位置和终止位置，求和累加即可。

$O(nlogn)$做法：

考虑枚举每一个左端点，然后根据前缀和的单调性，二分满足条件的最小值， 最后累加。

$O(n)$做法：

尺取法

什么是尺取法？

所谓尺取法，也就是取一段连续的区间。。。。好吧 ，这就是定义

尺取法步骤：

1.设s为左端点,t为右端点. 2.不断扩大右端点,直到满足条件. 3.如果2无法满足条件,则break. 4.扩大左端点,重复2.

There is a string $S$.$S$ only contain lower case English character. How many substrings there are that contain at least $ k $ distinct characters?

有一个明显的性质：如果子串$(i,j)$包含了至少$k$个不同的字符， 那么子串$(i,k)$,$(j < k < length)$也包含了至少k个不同字符。 因此对于每一个左边界，只要找到最小的满足条件的右边界， 就能在$O(1)$时间内统计完所有以这个左边界开始的符合条件的子串。

T3 Way

由于本人能力有限，所出数据全都是极限数据...

这道题主要是让大家熟悉最短路的两种常见的打法，纯粹的裸题...

前70%的数据:dijkstra，邻接矩阵存图就可以过......

100%的做法:SPFA，好像没啥好说的。

除此之外，还有一种做法，dijkstra+Heap，这种算法的时间是$O(nlogn)$应该也可以过。