七段第一课：枚举

A - 第一课：按钮变色

主要知识点：二进制枚举

No.1 - 题面

有一个4x4的网格上面有16个按钮。按钮只有黑(b)白(w)两种颜色。按动任意一个按钮，那么该按钮本身以及其上下左右的按钮（如果有的话）都会改变颜色(由白变黑，由黑变白)。给出初始按钮的状态，输出最少要按多少次按钮才可以让所有按钮变为同一种颜色。

img

输入

输入有4行，每行包括4个字符（‘w’或’b’, ‘w’表示该位置目前为白色按钮，’b’表示该位置为黑色按钮）。

输出

输出最少要按多少次才能将所有的按钮变成同一颜色，如果没有办法变成相同颜色，输出 Impossible 。

No.2 - 解题思路

一般来讲这一道题第一眼都是广搜，广搜的注意点在于，**某些人把数组改了发现不对劲直接 continue 然后忘记改回来了。 **

但是，这一节课名字叫做枚举，自然是有枚举做法的。
我们观察数据范围，发现数据是 $4 \times 4 = 16$ 的矩阵，所以可以直接暴力枚举所有要按的按钮，看看哪个是有解的就可以。

No.3 - 关键代码

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
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
// BFS 解法
void Work(){
	queue<pair<int , int > >q;
	q.push(make_pair(Turn(ch), 0)); // 数组转二进制（有点状压的意思）
	vis[Turn(ch)]=1;
	while(!q.empty()){
		pair<int , int >f=q.front(); q.pop();

		if(f.first==0||f.first==65535){ // 全 0 或者 全 1 
			printf("%d", f.second);
			return ;
		}

		Change(f.first); // 二进制转数组

		for(int i=1; i<=4; i++){
			for(int j=1; j<=4; j++){
				ch[i][j]=(ch[i][j]=='b'?'w':'b'); // 转换颜色
				for(int k=0; k<4; k++){
					int x=i+dx[k];
					int y=j+dy[k];
					if(x<1||x>4||y<1||y>4) continue;
					ch[x][y]=(ch[x][y]=='b'?'w':'b');
				}

				if(!vis[Turn(ch)]){ 
                    vis[Turn(ch)]=1;
				    q.push(make_pair(Turn(ch), f.second+1));
                    // continue; 某人就因为这个continue导致调了半小时
                }


				ch[i][j]=(ch[i][j]=='b'?'w':'b'); // 改回来，继续更状态
				for(int k=0; k<4; k++){
					int x=i+dx[k];
					int y=j+dy[k];
					if(x<1||x>4||y<1||y>4) continue;
					ch[x][y]=(ch[x][y]=='b'?'w':'b');
				}
			}
		}
	}
	printf("Impossible");
}

// 二进制枚举
void Work() {
	int ans=1e9; // 答案
	for(int i=0; i<(1<<16); i++){ // 二进制枚举按下哪个按钮，1表示按，0表示不按
		int tot=0;
		for(int j=0; j<16; j++){
			if(i&(1<<j)){ // 按了哪一个按钮
				tot++; // 统计按了几下
				Change(j); // 改变颜色
			}
		}
		if(Check()){ // 是否成功
			ans=min(ans, tot);
		}
		for(int j=0; j<16; j++){ // 改回来，继续枚举
			if(i&(1<<j)){
				Change(j);
			}
		}
	}
	if(ans==1e9) printf("Impossible");
	else printf("%d", ans);
}

B - 【提高组】第一课：最短连续子序列

主要知识点：尺取法

No.1 - 题面

给定一个长度为N的整数序列以及整数S。求最短的连续子序列的长度使得这个连续子序列的和大于等于S。

如果找不着，输出0。

输入

第一行输入两个整数 $N(1≤N≤10^5)$ 和 $S(1≤S≤10^9)$。

第二行输入N个整数表示序列，序列中的元素属于区间 $[0,104]$。

输出

输出一个整数作为答案。

No.2 - 解题思路

这一题的话，首先想到的应该是 $O(n^2)$ 的解法，那就是枚举长度和左端点。但是显而易见，这是会超时的。我们可以先看看这样一个模拟的过程：

我们发现每一次移动都是一个固定长度从第一个到最后一个，但是显而易见，这样枚举枚举出了很多不是满足题目要求的答案，肯定不行。而我们发现，如果固定端点变长度就会发现：由于每一个节点非负，每增加一个节点，总量一定增加，每减少一个节点，总量一定减少。很眼熟吧，是不是满足单调性！那么这道题就有一个很好玩的解法：
每次向右拓展一个单元格，直到满足题意，那么从这个满足题意的点以后，每一个都是满足条件的右端点，答案增加 $n - r + 1$ 。
然后向左移动一个单元格，如果不满足题意，继续右移，如果满足题意直接统计。

这就是所谓的尺取法（有人也说叫做“双指针”）

No.3 - 关键代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void Work(){ // 只有满足单调性才可以尺取
	int ans=1e9;
	int l=0, r=1, tot=0;
	while(1){
		tot-=a[l++];
		while(r<=n&&tot<s){
			tot+=a[r++];
		}
		if(tot<s) break; // 如果移动到底都无法满足题意，直接跳过
		ans=min(ans, min(r, n+1)-l);
	}
	if(ans==1e9) printf("0");
	else printf("%d", ans);
}

C - 【提高组】第一课：异或和

主要知识点：尺取法，异或的性质

No.1 - 题面

给定长度为 $N$ 整数序列 $A_1,A_2,A_3,…,A_N$ ，要求计算有多少区间，它里面数字的异或之和 $=$ 相加之和。

输入

第一行一个整数 $(1≤N≤2\times10^5)$ 。

第二行输入 $n$ 个整数 $A_1,A_2,A_3,…,A_N,0≤A_i<2^{20}$ 。

输出

输出一个整数作为答案。

No.2 - 解题思路

这道题先从异或和加法的关系开始思考。

异或，又被称为不进位加法，这个性质也使得异或和最多和加法和相等。
这时候单调性就来了，只要一些数字的加法和大于其异或和，以后不论怎么加，都无法挽回加法和大于异或和的命运。

那代码就出来了。

No.3 - 关键代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Work(){
	long long ans=0;
	long long totx=0, tots=0;
	int r=0;
	for(int l=1; l<=n; l++){
		while(r<=n&&(totx^a[r])==tots+a[r]){
			totx^=a[r], tots+=a[r];
			r++;
		}
		ans+=r-l; // 由于r是第一个不符合的，所以可以直接减，不用减一
		totx^=a[l];
		tots-=a[l];
	}
	printf("%lld", ans);
}

D - 【提高组】第一课：最大余数

主要知识点：$\tt meeting - in - the - middle$

No.1 - 题面

给定 $n$ 个整数, 从中选出若干个数字（每个数字最多选一次），使得它们的和取余 $m$ 最大，求最大的余数。

输入

第一行输入两个整数 $n(1≤n≤35)$ 和 $m(1≤m≤10^9)$ 。

第二行输入 $n$ 个整数，这些整数属于区间 $[1,109]$ 。

输出

输出一个整数作为答案。

No.2 - 解题思路

选择若干个数字使得他们的和取余 $m$ 的值最大。

这一个题，第一眼就是枚举选择什么数字，组合的复杂度，但是显而易见是会超时的。
而我们发现 $n$ 是 $35$ ，就是因为这个数字，我们连二进制枚举都存不下。

但是，为什么他会莫名奇妙出一个这样的数据，肯定是有原因的。$35$ 除以二就是 $17$ 左右，而这样一个数字，不论是枚举组合还是二进制枚举（其实这两个没有太大的区别，复杂度一样，只不过是递归形式和非递归形式而已），都是可以达到效果的。

但是，只有一半枚举到了啊，另外一半呢？也可以枚举出所有结果。现在每一半都枚举出了所有结果，只剩下匹配了。而匹配，是不是可以用二分解决？显然可以。把它以对 $m$ 取模的结果排序，然后枚举左边的所有状态，设左边对 $m$ 取模是 $tot$ ，那么右边是不是 $(m - 1)-tot$ ？因为余数最多是除数减一，而你又用掉 $tot $ 的一部分，所以就剩下这个了。二分找小于等于他的值就可以。

这个分别二进制枚举所有两半的所有解法，二分匹配得出结果的算法，就叫做 meeting in the middle。

No.3 - 关键代码

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
void BinEnum(int l, int r, vector<long long > &v) {
    int len = r - l + 1;
    for(int mask = 0; mask < (1 << len); mask++) {
        long long tot = 0;
        for(int i = 0; i < len; i++) {
            if(mask & (1 << i)) {
                tot += a[l + i];
            }
        }
        v.push_back(tot % m);
    }
}

void Work() {
    BinEnum(1, n / 2, x);
    sort(x.begin(), x.end());
    BinEnum(n / 2 + 1, n, y);
    long long ans = 0;
    for(auto &p : y) {
        auto it = upper_bound(x.begin(), x.end(), m - 1 - p);
        if(it == x.begin()) {
            it = x.end();
        }
        it--;
        ans = max(ans, (p + (*it)) % m);
    }
    printf("%lld", ans);
}