Daily Archives

4 Articles

OI

「Codeforces 662A」Gambling Nim – 题解

Posted by kal0rona on

主要思路

考虑设 \(S = \oplus_{i = 1}^n a_i\),然后将 \(c_i = a_i \oplus b_i\) 扔到线性基里面。我们可以发现,线性基最少数来拼出一个和 \(S\) 一样的数使得局面必输。那么,赢得概率就是 \(1 – (\frac12)^{siz}\)。

当然,如果拼不出来,那么就稳赢了。

OI

BZOJ3590:[SNOI2013]Quare – 题解

Posted by kal0rona on

主要思路

我操这个题是真的有意思(做完后索然无味)。

肯定这个题状压 DP 没跑的,所以可以先设 \(f[S]\) 为集合 \(S\) 双连通的最小代价。直接做有点困难,我们需要思考一个归纳的方式来构造一个双连通图。