Codeforces 练习计划 #1
Codeforces 414E

Codeforces 练习计划 #2

RXDoi posted @ 2015年7月02日 14:36 in Codeforces , 100 阅读

暑假里打算刷一波去年的集训队作业。

多思考少看题解多体会……唉……

Counter: 5 + 0


[311E] 有一些狗,你可以把狗变性,这需要代价,有一些富人希望某些狗的性别都为公/母,如果满足他的要求他会付你钱,如果不满足朋友的要求得补贴他钱。求最大获利。唉最小割都要看题解真是没救了……注意到一个富人的要求是他和某些性别相同的狗都不同割,那么可以把富人也当成点,这样富人就要和某些点同割,某些点不同割,在二分图内这是很简单的。


[235C] 给出字符串S,多次询问多少个S的子串与T循环同构。对S建立SAM,然后把T倍长,就变成求T的所有长为n的子串在S中出现多少次。出现多少次就是|Right|,然后就是要支持在SAM上读入字符串,在后面加,在前面减一个字符。在后面加的是经典东西,用个变量维护长度,退Parent时更新成Parent的Max,在前面减的话,考虑到它的Parent都是它的后缀,实质上也是跳Parent。

[235E] 求\(\sum\sum\sum d(ijk)\)。其中d()表示正约数个数,即0次除数函数。约数和即所有质因子次数+1.然后对于每个质因子,把它次数相同的那些提出来一起算,记忆化搜索下去……理解了一个晚上,不会证复杂度……

[293B] 一个n*m的矩阵,一些点有颜色。要给剩下的点涂色,使得从左上到右下的每条路径都没有相同的颜色。求方案数。颜色≤10。特判掉n+m-1>k,然后暴搜,显然这个东西可以最小表示,也就是新增一个点的时候枚举它和之前的哪种颜色相同,或者新开一种颜色。搜到一种方案乘个组合数就好了。好题。

[317E] 一个人,和他的影子,一些点是障碍,人可以四个方向移动,影子也会相应一起移动。如果影子的目标格是障碍影子就不动。要求构造一个操作序列使人追上影子。搞了一晚上……虽说是个傻题……假如人和影子在不同连通块内就无解,否则人先沿着最短路走,再跟着影子动的方向动。如果有限步之内走到就好,否则人和影子一定走到了无障碍的无限远处。然后根据人与影子的关系用左上、左下、右上、右下的那些障碍可以达到要求。细节要注意:把他们移动过去的途中可能会被障碍挡住,要先往反方向移动一点,再移过来移得多一点,再搞……唉……身心俱疲……


 


登录 *


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