题目描述
http://codeforces.com/gym/103202/problem/D
Solution
我们令 $s0$ 表示前缀异或和中 $0$ 的个数，$s1$ 表示前缀异或和中 $1$ 的个数
那么容易得到答案就是 $s0\times s1$，并且 $s0+s1=n+1$
那么显然要将 $s0$ 和 $s1$ 对半分
所以我们我们考虑直接 $dfs$ 所有答案，当 $s0$ 或 $s1$ 超过 $n+1$ 的一半的时候直接退出
注意到我们相当于对于每个点判断子树内是否可能存在答案点，不存在直接退出
所以最终的时间复杂度就是 $O(100n)$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| #include <iostream>
#define maxn 100010
#define ll long long
using namespace std;
int n;
char s[maxn];
ll sum;
int ans[maxn], num; char ch[2];
void dfs(int d, int s0, int s1, int p, ll cnt) {
if (num == 100) return ;
if (max(s0, s1) > (n + 2) / 2) return;
if (d == n + 1) {
for (int i = 1; i <= n; ++i) putchar(ch[ans[i]]);
putchar('\n'); ++num; return ;
}
ans[d] = 0;
dfs(d + 1, s0 + (p == 0), s1 + (p == 1), p, cnt + (p == 0 ? s1 : s0));
ans[d] = 1;
dfs(d + 1, s0 + (p == 1), s1 + (p == 0), p ^ 1, cnt + (p == 0 ? s0 : s1));
}
int main() {
cin >> n; ch[0] = 'b'; ch[1] = 'r';
sum = 1ll * (n + 1) / 2 * ((n + 2) / 2);
cout << sum << endl;
dfs(1, 1, 0, 0, 0);
return 0;
}
|