早上起来晚了。早饭很悲戚一点都不好而且连早饭里都是辣椒。这里的人真重口味。然后中饭晚饭因为师大附中的人来上课所以所有菜都有海量辣椒，连汤都没了。这么辣真捉急。

-----------------------------------------------------------------------------------------------

今天考的不错rank2了。哈哈终于我能发cena包了。到这里几天，感觉自己写朴素写搜索写随机的能力强了不少- -

----------------------------------------------------------------------------------------------

第一题：

从前有一位旅者，他想要游遍天下所有的景点。这一天他来到了一个神奇的王国：在这片土地上，
有n个城市，从1到n进行编号。王国中有m条道路，第i 条道路连接着两个城市ai,bi，由于年
代久远，所有的道路都已经不能使用。如果要修复第i条道路，需要wi的时间。为了更好的旅
行，旅者想要将某些道路修复，使得1号城市能够到达n号城市，2号城市能够到达n-1号城市..k
号城市能够到达n-k+1号城市。为了满足他的要求，请问最少需要多少时间去修复道路。无解请输
出-1。 (n,m<=10000,k<=4)

【k小得很蹊跷。标程的解法是把这2*k个点的连通性情况用状态压缩记录，然后转化成最短路（或者说dp？差不多一个意思）。考试的时候我没想到是状态压缩。第一眼看过去就敲了个最小生成树然后在最小生成树上贪心。但是在2个小时后被自己造了一组数据卡掉了。最后一个小时写了个费用流的变种。这题给我这么一种感觉：如果不考虑1一定要到n，2一定要到n-1，…，而是只要求从1,2,…,k，走到n,n-1,…,n-k+1，那么直接计算这么一个网络上的最小费用最大流即可：一个超级源与1,2,…,k分别连边容量1费用0，其他所有边的容量无限大费用为其长度，然后一个超级汇与n,n-1,…,n-k+1分别连边容量1费用0.并且这个网络里的边只有在流量由0变为1或1变为0时才产生相应费用，其他情况不产生费用。因为这个网络很特殊每次增广流量最大+1，所以改写spfa即可。不过不知道为什么wa60分。 [updata@13.3.22：这个算法完全是错的。因为不能保证如果一开始不存在负圈那么不管怎么增广永远不会出现负圈。所以连费用流的基本要求都无法满足。当时居然给我拿了60分。。。数据太弱- -]】

第二题：

山的模型如下：山由一个顶点集：A1,A2…An给定，保证Ai的x单调递增。我们将Ai 和Ai+1 之间连上线段，表示山的某一段。Pty想要爬到这座山的最高的顶点，当两个顶点的高度相同时，我们认为x比较大的顶点要高一些。Pty不是盲人，所以他将会在爬山时采取一些策略，使得他能够尽量快的到达最高的顶点。Pty从初始的顶点出发，往左右看去，他将朝他能够看到的最高的顶点方向走去。当走到每一个顶点时，他都会重新观察，如果这时看到的顶点比之前看到的顶点还要高，那么他将选择此时看到的顶点走去，直到他到达最高点为止。如果顶点A能够看到顶点B，则不存在某条线段和线段AB严格相交。Pty想知道从每一个顶点出发，分别需要经过几个顶点才能到达最高点。(n<=300000，输入保证xi递增，hi<=10^6)

【这题给我的第一感觉跟noip2012Day1T3很像。嗯…都是有高度的一些点…都是有人在走来走去…数据还都这么大一看就不能暴力。根据那一题的经验，应该先预处理出每一个点向左或者向右会到哪个点，然后再倍增就可以知道每个点的答案。根据数据大小分析…效率应该是O(nlogn)的。首先要解决预处理。获取一个点左边的最高的能看到的点，还有一个隐藏条件，即那个能看到的最高点还要满足比当前站的位置要高。这个原因很简单就不说了。那么就可以从左到右扫描用斜率单调的栈维护一个上凸包来预处理一个点向左会看向哪里。右边同理。效率O(n)的。

嗯到此为止效率很让人满意。但是这里讨厌的是这个走路的人很容易走到一半看到更高的就马上改变主意了，所以这个人第一次停下来并不一定是走到了他看到的那个位置，也有可能是在第一个使他改变主意的位置。所以根据每个点向左看到哪里要计算出他最终会向左走到哪里第一次停下来。这个地方可以用rmq+二分位置O(nlog^2n)来做，也可以在对所有点按照能看到的高度从低到高排序后双向链表来做O(nlogn+n)。{双向链表在那一题里也可以用。}那么就获得了每一个点第一次会停在哪个点，并且这中间经过了几个点也能知道。那么接下来{I、可以照着那一题的做法，倍增来做。O(nlogn)}{II、可以发现每个点只能走向一个点，并且每个点最终都会走向山顶。所以这些连线构成了一棵树，并且边权都已知，那么直接bfsdfs都可以做了。O(n)}。所有有两种方法地方我都写的是蠢一点的那个- -。但是不知道怎么搞的写挫了WA70分。】

第三题：

在神秘的东方有一棵奇葩的树，它有一个固定的根节点（编号为1）。树的每条边上都是一个字符，字符为a,b,c中的一个，你可以从树上的任意一个点出发，然后沿着远离根的边往下行走，在任意一个节点停止，将你经过的边的字符依次写下来，就能得到一个字符串，例如： 在这棵树中我们能够得到的字符串是： c, cb, ca, a, b, a
现在pty得到了一棵树和一个字符串S。如果S的一个子串[l,r]和树上某条路径所得到的字符串完全相同，则我们称这个子串和该路径匹配。现在pty想知道，S的所有子串和树上的所有路径的匹配总数是多少？ (n<=800000,S<=800000)

【这题是后缀自动机。下午讲的后缀自动机至今不懂。悲惨下场。】

-------------------------------------------------------------------------------------------------

之前两天发cena包的人第二天都遭到了悲惨下场。希望明天不要挂。