ICPC 2020沈阳站 - D. Journey to Un‘Goro（暴搜+剪枝）

https://codeforces.com/gym/103202/problem/D

题意
一共有 n 个位置，每个位置能够染成红色或者蓝色。
如果选择一段区间 $[i,j](1\le i\le j\le n)$ 满足其中红色的个数为奇数，那么这段区间就是完美的。

问如何构造能使得完美区间的个数最多？
输出最多的完美区间数，按字典序输出所有构造方案（如果超过100种方案，只输出前100种）

$1\le n\le 10^5$

思路
因为只需要输出前 100 种方案，可以暴力判断每个位置染成了红色还是蓝色。
然后考虑如何剪枝？

考虑前缀红色位置的个数：定义前 i 个位置中，红色位置的个数 s[i]。
如果对于一段区间 [l, r] 来说，s[r] - s[l-1] 为奇数，那么区间中红色位置个数就为奇数，这段区间就是完美区间。
s[r] - s[l-1] 为奇数，说明 s[r] 和 s[l-1] 的奇偶性不同。
所以对于 0 到 n 这 n+1 个位置中，s[i] 为奇数的个数和 s[i] 为偶数的个数决定了一共有多少个完美区间：如果有 x 个 s[i] 为奇数，y 个 s[i] 为偶数，那么就会构成 x*y 个完美区间。
为了使得完美区间尽量多，也就是使得 x*y 尽量大，由 x+y=n+1，所以当 x 和 y 对半分的时候，乘积最大。

剪枝：搜索的过程中，如果发现 s[i] 的奇数个数或者偶数个数大于 $\lceil \frac{n}{2}\rceil$ 了，那么这个方案一定不是得到完美区间数最多的方案，剪掉。

Code

#include
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long

const int N = 500010, mod = 1e9+7;
int T, n, m;
char a[N];
int sum, cnt;

void dfs(int u, int cnteven, int cntodd)
{
	if(cnteven > (n+2)/2 || cntodd > (n+2)/2) return;
	
	if(u == n + 1)
	{
		cnt ++;
		for(int i=1;i<=n;i++) cout << a[i];
		cout << endl;
		if(cnt >= 100) exit(0);
		return;
	}
	
	a[u] = 'b';
	if(sum % 2) dfs(u+1, cnteven, cntodd + 1);
	else dfs(u+1, cnteven + 1, cntodd);
	
	a[u] = 'r';
	sum ++;
	if(sum % 2) dfs(u+1, cnteven, cntodd + 1);
	else dfs(u+1, cnteven + 1, cntodd);
	sum --;
}

signed main(){
	Ios;
	cin >> n;
	
	cout << (n + 1)/2 * ((n + 2)/2) << endl;
	
	dfs(1, 1, 0);
	
	return 0;
}
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
37
38
39
40
41
42
43
44
45

经验
完全没有想到暴搜，看到输出100种觉得只是出题人怕输出太多太耗时搞的。。
以后看到数据稍微小点的话需要能想到暴搜，然后想办法剪枝。