主要思路
这些 3000+ 题目里做过最小清新的。
首先肯定可以想到，分解质因子之后，对于一个 \(p^c\)，把每个元素该质因子的指数拿出来做中位数即为此质因子的贡献。我大概想到这里就断片了。
Continue reading →「Codeforces 662A」Gambling Nim – 题解
主要思路
考虑设 \(S = \oplus_{i = 1}^n a_i\)，然后将 \(c_i = a_i \oplus b_i\) 扔到线性基里面。我们可以发现，线性基最少数来拼出一个和 \(S\) 一样的数使得局面必输。那么，赢得概率就是 \(1 – (\frac12)^{siz}\)。
当然，如果拼不出来，那么就稳赢了。
Continue reading →BZOJ3590:「SNOI2013」Quare – 题解
主要思路
我操这个题是真的有意思（做完后索然无味）。
肯定这个题状压 DP 没跑的，所以可以先设 \(f[S]\) 为集合 \(S\) 双连通的最小代价。直接做有点困难，我们需要思考一个归纳的方式来构造一个双连通图。
Continue reading →AtCoder Grand Contest 038 – 解题报告
A – 01 Matrix
这个题还是很思博的，直接挂题解的图：
// A.cpp
#include <bits/stdc++.h>
using namespace std;
int main()
{
int n, m, A, B;
scanf("%d%d%d%d", &n, &m, &B, &A);
for (int i = 1; i <= n; i++, puts(""))
for (int j = 1; j <= m; j++)
if ((i <= A) ^ (j <= B))
printf("1");
else
printf("0");
return 0;
}
Continue reading →