(`・ω・´)的(假)题解

2018-04-17 09:58:34 By Puredigital

〜( ̄△ ̄〜)巧克力迪斯科

其实我并不会(划掉

考虑dp的时候发现并不好搞,会有重复

那就dp[x]表示循环节是x的倍数的方案数

可以容斥(反演

球这个还要三个互相依赖的dp

是卷积的形式

上FFT即可AC

听yzl说还有单log的做法

我就知道这么多了(逃

THERE IS A REASON

考虑黑白染色

路径一定是黑-白-黑……

所以说

如果最大匹配包含x,泽先手必败,反之先手必胜

用Dinic似乎会T

考虑用与D2T1一样的的优化

用一次残余网络上的dfs代替增广

M♭

考虑最简单的dp

dp[i][j][k]表示串中的第i~j是否可以匹配前k位

发现其实有单调性

那就改dp[i][j]记录最小的k

就可以过了

以上肯定有锅,要是发现了球指正

评论

avatar
fizzydavid
T1 见codeforces 848E T2的图是二分图 结论应该是 若所有的最大匹配包含x,那么先手必败,否则先手必胜 一次dinic不会TLE,但是n^2次dinic会 所以算一个点的答案要优化,用dfs看S和T的到达性就行了

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。