NFLS省选模拟赛 (`・ω・´) 简要题解

2018-12-08 17:47:52 By fizzydavid

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

原题:CF 848E

可以参考原题题解,评论中有$O(n \log n)$做法。

There is a reason

将棋盘黑白染色后变成二分图。如果以$x$为先手,那么后手必胜的充要条件是所有的最大匹配都包含$x$。可以用增广路径来证明这个结论。

下面考虑如何判断是否所有的最大匹配都包含$x$。首先求出任意最大匹配,那么我们只要考虑在这个匹配上的$x$。对于每个点,如果我们能找到一个包含这个点的匹配树上的交错路径,那么可以在不改变最大匹配数的前提下得出一个不包含$x$的最大匹配。而这就等同于在网络流的残余网路上判断S(或T,取决于$x$在左边还是右边)是否能到达$x$。两遍dfs后即可求出所有点的答案。

M♭

$dp[k][i][j]$表示S中$[i...j]$的子串是否能匹配$T[1..k]$,其中匹配方法是题面中描述的那样。注意到一个子串如果能匹配,那么所有包含它的子串都可以匹配。我们可以优化状态$dp[k][i]$表示最小的$j$满足$S[i...j]$匹配$T[1...k]$。每次转移的时候枚举向前加还是向后加,使用前缀和技巧优化后可以做到$O(nm)$。

评论

回复

发表评论

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