两日总结七

杭电杯比赛一场：

 这一场比较简单，有很多题目可以写，但是有些没有写出来。

后面是补题部分：

 对于Link with Bracket Sequence II这个题目:Problem - 7174

是一个区间DP，就是在转移的时候需要用另外一个数组来统计转移的情况。

对于Link is as bear：Problem - 7184

不难猜出题目就是要在给定序列中，选出一些数得到最大异或值即可，证明也非常简单。（111可以转换110, 011, 101, 001, 100, 000,010等状态说明你可以选择将任意一位变成0，也就是选出不要的数变成0，留下的数可以异或得到最大值。这就变成了一个线性基问题。）

 线性基的学习了解：就是维护一个可以通过该集合中的异或得到原序列任何数的最短集合。如此的话对于原序列的数贡献也就会在线性基里面的体现，最后只要贪心优先高位选取就可以得到最大值。

对于Link with Running：Problem - 7175

里面考了图论大半的知识，代码也是非常多。是一个比较好的题目吧！

题意：就是要从起点1走到n，花费体力W最小的情况下得到最多的p值。输出minW和maxP

理解：首先需要体力最少，那我们直接以体力换花费作为边权，然后一遍最短路即可得到答案。

然后就是在最短路的基础之上再去跑一遍以P为权值的最长路就行了 。但是这里有一个问题，就是体力花费为0的时候，P会出现正环情况，此时就会无限增大。因此就需要出去正环，直接使用TarJan算法进行缩点，讲一个环缩成一个点，最后得到一张DAG图，然后跑一遍最长路即可。

三幅图存下每个操作后的用来新建一个图。

1.最短路

 2.创建最短路图

 3.TarJan缩点然后创建第三幅DAG图

 4.在e3DAG最短图里面跑最长路得到答案。 

总之这个题目就是几种算法的套用，就是可能会忽略，W=0是的环，没有缩点。

其他的刷题：