一行超人

做了前三题，rank大概前100？A和C都是猜结论蒙过去的。。。

A.一个n个元素的set，轮流操作，每次选两个数x，y，使得abs（x-y）不中set并且把abs（x-y）加入set，无法操作的人输。问谁会赢？n<=100

题解：最后set里的数是所有数的gcd的倍数，且<=max{a[i]}，然后根据奇偶性判断即可。

B.给出串a，b，c。然后问a和b的LCS，且必须满足这个LCS不能有c作为连续子串。len<=100

题解： f[i][j][k]表示a串到i，b串到j，c串匹配到k的LCS，然后用kmp转移即可，也可以直接建成AC自动机。

C.给了n个数x[i]，现在要把b变成a，每次可以让b--，或者选择一个x[i]，让b-=b%x[i]，问最小步数。b-a<=100W,n<=10W.

题解：无奈用了和bzoj3136差不多的方法，就是处理最大因数+单调队列。尽管A了，但感觉总是不对劲，好像不对的样子。。。

    看了题解发现f[i]表示a+i到i的次数，这是个单调不减函数！因为j用某个x[i]变成了k，那么j-1一定也能用x[i]变成k。

    然后我们每次只需要让b减少max{b%x[i]}还有一个问题就是可能会T，所以每次要把队尾a-b之间已经不存在x[i]的倍数的x[i]删掉。

   至于为什么我也布吉岛QAQ

D.一张有向图，一个robot要从s走向t，可以消耗1让robot朝指定方向走，否则robot会随机走，求最坏情况下从s到t最少需要消耗多少。n<=100W,m<=100W

题解：感觉因为有环的问题，所以问题很不好处理。。。

      我个nc dp方程都想错了，dp方程是：dp[u] = min(min(dp[v]) + 1 , max(dp[v])) | u->v

            问题就在于dp的顺序，然后答案用了一种奇怪的方法，神奇的得到了答案：

        while (!Q.empty()) {

    u = Q.front(), Q.pop_front()
    for each edge from v to u
        --out_degree[v]
	if (out_degree[v] == 0) {
           relax dp[v] by dp[u]
           if success, add v to the front of Q
	}
	else{
	   relax dp[v] by dp[u] + 1
	   if success, add v to the back of Q
        }	
  }

     然后发现这其实是按dp[i]的值从小到大更新的！！！所以当一个点出度被减为0的时候，u一定是dp值最大的！！！这样就ok了！！！

     OrzOrzOrzOrz   还有代码为什么随便刷一发就rank1了。。。

官方题解：http://codeforces.com/blog/entry/8903