枚举

🔗 引用站外地址，请注意甄别
第一课：枚举
517coding

A：dfs暴力枚举，二进制枚举

🔗 引用站外地址，请注意甄别
按钮变色
517coding

题意：最少操作几次是的所有格子变成同色

以某个格子为中心的翻转最多只会有一次

同样的一个格子不会作为中心被翻转两次

解法

暴力枚举每个格子翻或者不翻，最后检测是否全部同色，如果全部同色，看一下操作几次，更新答案

change 函数改变 $x,y$ 及周边格子的颜色

check 函数判断格子颜色是否全部相同

dfs 函数暴力枚举。dep 参数是搜到了哪个位置（最大16），used 参数记录翻转的次数

不凡当前格子就去 dep + 1 位置，used 不变

翻转当前格子就去 dep + 1 位置，used + 1

注意回溯！因为 used 作为参数，所以不用回溯，只要回溯 mp 数组即可

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
#include <bits/stdc++.h>
using namespace std;

char mp[10][10];

//5个方向
int dx[] = {0, 0, 1, 0, -1};
int dy[] = {0, 1, 0, -1, 0};

int ans = 20;
void change(int x, int y) {
    for (int i = 0; i < 5; i++) {
        int ax = x + dx[i];
        int ay = y + dy[i];
        if (ax < 0 || ax > 4 || ay < 0 || ay > 4)
            continue;
        if (mp[ax][ay] == 'w') mp[ax][ay] = 'b';
        else mp[ax][ay] = 'w';
    }
}
bool check() {
    char x = mp[0][0];
    for (int i = 0; i < 4; i++) {
        for (int j = 0; j < 4; j++) {
            if (mp[i][j] != x) return false;
        }
    }
    return true;
}
void dfs(int dep, int used) {
    if (dep == 16) {
        if (check()) ans = min(ans, used);
        return ;
    }
    dfs(dep + 1, used);
    int x = dep / 4, y = dep % 4;
    change(x, y);
    dfs(dep + 1, used + 1);
    change(x, y);//回溯 
}
int main() {
    for (int i = 0; i < 4; i++) {
        scanf("%s", mp[i]);
    }
    dfs(0, 0);//最开始在第0层 
    if (ans == 20) printf("Impossible\n");//注意判断无解
    else printf("%d\n", ans);
    return 0;
}

状态压缩

用一个整数的二进制来表示某个元素选或不选

B：双指针（尺取法）

🔗 引用站外地址，请注意甄别
最短连续子序列
517coding

题意：给你 $n,S$ 以及 $n$ 个数，求最短的连续子序列的长度似的这个连续子序列的和大于等于 $S$ （$n \le 10^5$）

暴力

暴力枚举所有的区间，求和，判断

如果不用前缀和优化，复杂度为 $O(n^3)$

使用前缀和优化，复杂度为 $O(n^2)$

二分

预处理前缀和 $sum_i$ 表示前 $i$ 个数的和

枚举区间的左端点，此时发现越往右和越大，所以满足单调性，可以二分找到满足条件的最小的右端点，更新答案

复杂度为 $O(nlogn)$ 

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
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int a[N], sum[N];
int main() {
    int n, s;
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
        sum[i] = sum[i - 1] + a[i];
    }
    int ans = n + 1;
    //枚举左端点
    for (int i = 1; i <= n; i++) {
        //在 [i,n] 区间内去找一个满足条件的最小的右端点
        int l = i, r = n, best = -1;
        while(l <= r) {
            int mid = (l + r) / 2;
            if (sum[mid] - sum[i - 1] >= s) {
                best = mid;
                r = mid - 1;
            }
            else l = mid + 1;
        }
        if (best != -1) ans = min(ans, best - i + 1);
    }
    if (ans == n + 1) printf("0\n");//判断无解
    else printf("%d\n", ans);
    return 0;
}

双指针

枚举其中一个端点，另一个端点在滑动

值得的注意的是，右端点 $j$ 在滑动的时候不应当判断 $j$ 是否合法，而应当判断 $j+1$ 位置是否合法，因为只有这样，才能尽可能的找打最靠右的右端点

$j$ 初始值为 $0$ 是因为滑动以下就到了 $1$ ，不然的话会忽略第一个位置

$tmp$ 维护区间和

复杂度为 $O(n)$ 

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
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int a[N];
int main() {
    int n, s;
    scanf("%d%d", &n, &s);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int j = 0;
    int tmp = 0;
    int ans = n + 1;
    //确定左端点
    for (int i = 1; i <= n; i++) {
        //右端点进行滑动
        //尽可能地向右找
        while(j + 1 <= n && tmp < s) tmp += a[j + 1], j++;
        if (tmp >= s) ans = min(ans, j - i + 1);
        tmp -= a[i];//左端向右滑动，因此总和要减掉这个数
    }
    if (ans == n + 1) printf("0\n");
    else printf("%d\n", ans);
    return 0;
}

C：异或

🔗 引用站外地址，请注意甄别
异或和
517coding

异或的性质

两个位不同才为 $1$

$101$ 异或 $010 = 111$

假如 $a$ ^ $b < a + b$ （此处 ^ 为异或符号）

说明什么？说明 $a$ ^ $b$ ^ $c$ 一定也小于 $a + b + c$

那么以后所有的数相异或都不会相等了

解法

利用这个特质，可以得出解法：

枚举一个左端点，然后利用双指针（two-pointers）技巧去滑动右端点，找到最大的满足条件的右端点

右端点滑动：假设我们枚举到一个左端点 $i$ ，接下来我们要用一个 $j$ 代表右端点，不断进行滑动

设 $SA$ 为当前 $[i,j - 1]$ 区间的元素异或和，$x$ 等于 $a_j$ ，$sum$ 为 [$i,j - 1$] 区间和

如果 $SA$ ^ $x$ 等于 $sum + x$，那么 $j$ 就可以一直向右滑动

一直滑倒一个最极限的位置为止

所以 $[i,i],[i,i+1],[i,i+2]…[i,j]$ 都是满足条件的

答案就可以就可以加上 $j-i+1$

左端点移动：当我们扔掉 $i$ 位置的数时，这段区间其实是更加满足条件的，这是因为如果 $a$ ^ $b$ ^ $c=a+b+c$，那么如果把 $c$ 让掉，$a$ ^ $b$ 也一定是等于 $a+b$ 的

所以 $j$ 就没有必要从头开始，可以继续向右滑动，重复上面的操作，计算答案，复杂度就变成了 $O(n)$

和上一题不同的时，这题需要维护两个和，分别是异或和和区间和

不开 long long 见祖宗

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
#include <bits/stdc++.h>
using namespace std;

const int N = 200010;

int a[N];
int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &a[i]);
    }
    int j = 0;
    int suma = 0, sumb = 0;//suma维护异或和，sumb维护区间和
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        //注意异或的优先级比较低，要加括号
        while(j + 1 <= n && (suma ^ a[j + 1]) == (sumb + a[j + 1]))
            suma ^= a[j + 1], sumb += a[j + 1], j++;
        //这里不需要判断j的越界情况，j因为上面的while循环最大会停留在n
        ans += j - i + 1;
        suma ^= a[i];//同一个数异或两次相当于没有异或
        sumb -= a[i];
    }
    printf("%lld\n", ans);
    return 0;
}

D：折半枚举

🔗 引用站外地址，请注意甄别
最大余数
517coding

题意

给你最多 $35$ 个整数，选出一个子集使得这个子集的和区域 $m$ 最大，求最大余数

子集就是某一个组合

暴力枚举所有组合复杂度 $2^{35}$

解法

分成两半之后，暴力枚举前一半数的所有组合，保存到 $b$ 数组并进行排序，复杂度最多为 $2^{18}$

暴力枚举另一半的所有组合，去 $b$ 数组里面寻找一个数，使得这个数跟 $x$ 加起来模 $m$ 最大

去 $b$ 数组里面查找小于等于 $m - 1 - x$ 的最大的一个数，如果不存在就直接取 $b$ 数组里面最大的数

所以问题就变成了在一个有序数组中查找某一个数，用二分解决

可以利用二进制枚举，注意：二进制枚举时下标一般从 $0$ 开始

注意：$b$ 数组要开的很大，否则会 RE 或 WA

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
#include <bits/stdc++.h>
using namespace std;

const int N = 300010;//数组至少要这么大
int a[N], b[N];

int n, mod, tot;
//在b数组里二分，找到小于等于x的最大的数，找不到则返回b数组中最大的数
int find(int x) {
    if (b[0] > x) return b[tot - 1];
    int l = 0, r = tot - 1, best = -1;
    while(l <= r) {
        int mid = (l + r) / 2;
        if (b[mid] <= x) {
            best = mid;
            l = mid + 1;
        }
        else r = mid - 1;
    }
    return b[best];
}
int main() {
    scanf("%d%d", &n, &mod);
    for (int i = 0; i < n; i++) {
        scanf("%d", &a[i]);
        a[i] %= mod;
    }
    int m = n / 2;
    int ans = 0;
    //第一半的组合，保存在b数组
    for (int i = 0; i < (1 << m); i++) {
        int tmp = 0;
        for (int j = 0; j < m; j++) {
            if (i & (1 << j)) tmp = (1LL * tmp + a[j]) % mod;//注意1LL，小心溢出
        }
        b[tot++] = tmp;
        ans = max(ans, tmp);//特殊处理再某一半的最大组合
    }
    sort(b, b + tot);
    m = n - (n / 2);
    for (int i = 0; i < (1 << m); i++) {
        int tmp = 0;
        for (int j = 0; j < m; j++) {
            //因为开始点是从n/2开始的，所以要加上这些偏移量
            int jj = j + n / 2;
            //cout << i << " " << jj << " " << (1 << jj) << endl;
            if (i & (1 << j)) tmp = (1LL * tmp + a[jj]) % mod;
        }
        //特殊处理再某一半的最大组合
        ans = max(ans, tmp);
        int x = find(mod - tmp - 1);//尽量找最接近mod - 1的数
        ans = max(ans, (x + tmp) % mod);//这里注意取模
    }
    printf("%d\n", ans);
    return 0;
}