3
12
2015
1

Codeforces Round #201 (Div. 1)

做了前三题,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

Category: codeforces | Tags: | Read Count: 1055

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

| Theme: Aeros 2.0 by TheBuckmaker.com