【火题合集】4.6考试

好像这次考试是停课以来最简单的一场吧。。总算还是有能做的题

1.ss (Codeforces 526 D. Om Nom and Necklace)

喜闻乐见的送分题

思路还是很巧妙的。。

A+B+A+B+…+A可以等价为PPPPP…Q,其中Q是P的前缀

那么就可以玩KMP了

到第i位,P的最小长度S为i-next[i](即一个BA的长度)

那么A一定是Q前面加上若干个P构成的串,Q的长度为i%S

并且P的个数T为i/S,因为P的个数要能被k整除,所以剩下分给Q的P有T%k个。

那么A的总长度为T%k*S+i%S,即P部分和Q部分的总和。

此时能够保证A有k+1个,B有k个了,并且A的长度不为负,那么只要保证B的长度不为负,即A的总长度小于等于i即可。

(听说标程用了字符串hash然而根本不需要嘛233)

4.walk (Codeforces 113 D. Museum)

都只是D题但我却没做出来。。

(你问我2、3题哪去了?2题因为考过这次没做,3题太神了不会做233

考试的时候还把XOR路径和的代码翻出来看了。。但还是没做出来= =

其实我已经接近正解了。。每个状态(x,y)视为一个点然后连边解方程。。

但是我一直想着一个方程直接解完。。然而这是不可行的。

为什么呢?

因为在每一次游戏中(暂且称它游戏吧),只会有一个终态。。所以要对于每一种可能的终态分别解方程。。

对于每一种终态(x,x):

$$f(x,x)=1,f(i,i)=0 (i\ne x)$$
$$f(x,y)=\sum_{i\ne j}f(i,j)\times(f(x,y)转移到f(i,j)的概率)$$

高斯消元即可

然后就是鬼畜的复杂度。。是n7的,不过将所有(x,y)(x>y)的状态合并到(y,x)就可以除掉一个8的常数。。就可以过了

5.print (Codeforces 132 E. Bits of merry old England)

这么久了终于见到网络流的题了!

然而根本没看出来。。费用流还不会。。

待完成。。

6.tree (Codeforces 379 F. New Year Tree)

这题居然是F题?

这题真不是送分题?

考试凭借这道水题虐场

每一次添加两个点,这两个点本质相同,距这两个点最远的点一定是添加之前直径的某个端点。会求两遍DFS/BFS求树的直径的肯定知道。那么用倍增LCA判断一下新添加的点和两个端点是否能更新直径,如果能的话ans++。

2
说点什么

1 Comment threads
1 Thread replies
0 Followers
 
Most reacted comment
Hottest comment thread
2 Comment authors
Recent comment authors
  Subscribe  
最新 最旧 得票最多
提醒
游客

千古神犇xyk,扑通扑通跪下来。
选手,没有您我们会死!
向总:你不错
cyb:这道题xyk都会做
cyb:这道题xyk都会做
cyb:这道题xyk都会做
cyb:这道题xyk都会做
cyb:这道题xyk都会做
cyb:这道题xyk都会做
cyb:这道题xyk都会做
cyb:这道题xyk都会做
cyb:这道题xyk都会做
cyb:这道题xyk都会做