(内容主要关于枚举子集和状态压缩，c++中的位运算)

主要的逻辑我认为是：遍历一组很大的范围，这些范围是10进制的数（做到了枚举），通过位运算与函数，把10进制转成2进制，通过2进制的特征（00000-11111），就可以线性枚举n位不同的组合，从原来的(O(n^n))变成线形的，再通过函数和判断，找到符合题意的例子，得到答案。

基础语法
1.

 左移 <<  (a<<b) 相当于ax(2^b)
 右移 >>  (a<<b) 相当于a/(2^b)

2.位运算
int a=5, b=3;
(二进制下：0101 0011） 当然这个时候一定第一次学的时候会有问题，为什么是4位呢，万一是5位呢？
这个就需要用到前面的int n = (1 << m) - 1 表示 m 位全为 1 的数，
一定不能忘了-1 不然就是100...(m个0)....0 一共m+1位，很容易错的边界条件
位与&：两个都是 1 才为 1 (a & b)=0001=int(1)
按位或：有一个是 1 就为 1 (a | b)=0111 =int(7)
按位异或：相同为 0，不同为 1. (a ^ b)=0110 =int(6) *int(num)意思是类型是int，方便理解

这些运算符常用在判断枚举例子是否符合条件，比如需要把n个数分为2堆，

     for (int i = 0; i < n; i++) {
        cin >> num[i];
     }
     for(int s=0;s<(1<<n);s++){
            int temp=0;
            for(int i=0;i<n;i++){
                if((s>>i)&1){                             //意思是0001，0011，0101，1101这样排列，第i位是1的组合
                    temp+=num[I]                       //这样就把排列组合不同位的num累加起来了
                }
            }
      }

呃，还是以一道题来说明吧：(P2392) 你需要把n个数分为2堆，然后尽可能让这2堆的数字和的差值越小越好，然后输出值的和较大的；（具体为什么是这样那就是读题阅读理解的问题了）
逻辑是，列出所有不同的分堆组合，二进制001001，所有有1的为一堆，然后遍历这些第 i 位有1的对应值，累加起来为sum1，再用总和减去sum1，就是剩下的sum2了，
其次记录这一次枚举结果中较大的和，与上一次枚举的计算结果相比较，取值小的，最终的结果就是枚举出来数字和的差值最小；
代码如下：

#include<iostream>
#include<algorithm>
#include<cmath>
#include<vector>
using namespace std;
int main(){
    int id[4];
    int ans=0;
    for(int i=0;i<4;i++){
        cin>>id[i];
    }
    vector<int> arr[4];
    for(int i=0;i<4;i++){
        int sum=0;
        arr[i].resize(id[i]);
        for(int j=0;j<id[i];j++){
            cin>>arr[i][j];
        }
    }
    for(int i=0;i<4;i++){
        int sum=0;
        for(auto it:arr[i]){
            sum+=it;
        }
        int best=sum;
        for(int k=0;k<(1<<id[i]);k++){             //从极端的一堆啥都没有另外一堆是所有开始枚举，如果是需要避开这样就从 1 开始 
            int left=0;
            for(int k2=0;k2<id[i];k2++){          //遍历之前的基础数组，查看是需要第几位的值
                if((k>>k2)&1){
                    left+=arr[i][k2];
                }
            }
            int right=sum-left;                        //计算另外一堆
            best=min(best,max(right,left));        //和上一次枚举结果相比较，取小的
        }
        ans+=best;
    }

    cout<<ans<<endl;
    return 0;
}

注意： 这道题很容易想的很简单就想错了，我最开始想的那不就直接把每一组数先排序，
从大到小，然后奇偶序分成2个数组，其次取奇数或偶数列数组中和较大的，
但是这样会导致情况不符合存在， 通过举例就可以明白这样是不行的。

3.一些常用的技巧和函数

if ((s >> i) & 1)                 判断某一位是否为1；


| 函数                          | 功能                                           |
| ----------------- | --------------------------- | ----------------------- |
| __builtin_popcount(x)   | 返回 x 中 1 的个数                        | __builtin_popcount(5) → 2 (101) |
| __builtin_popcountll(x)  | 返回 long long 中 1 的个数            | 用于 64 位整数                      |
| __builtin_ctz(x)            | 返回末尾 0 的个数                        | __builtin_ctz(8) → 3 (1000)     |
| __builtin_clz(x)            | 返回前导 0 的个数                         | __builtin_clz(1) → 31（32位） |
| __builtin_ffs(x)            | 返回最后一个 1 的位置（从 1 开始） | __builtin_ffs(8) → 4               |

注意函数前面是2个下划线 😦

那么就经常会有一种题：从n个数字里面选择k个数字，这k个数组的一些关系判断有条件，求有多少种选择方式
例子：P1036
已知 n 个整数 x ，以及 1 个整数 k（k<n）。从 n 个整数中任选 k 个整数相加，可分别得到一系列的和。
现在，要求你计算出和为素数共有多少种。

题目意思关键在于选择k个数，则使用 | __builtin_popcount(x) | 返回 x 中 1 的个数 ，只需要判断返回x中1的个数为k就行了，剩下的枚举交给二进制

代码如下：

#include<iostream>
#include<cstdio>
using namespace std;
bool check(int sum){
    for(int i=2;i*i<=sum;i++){
        if(sum%i==0){
            return false;
        }
    }
    return true;
}
int main(){
    int n,k;
    cin>>n>>k;
    int a[n];                                           //  从n个数字里面选择
    int count=0;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    int U=1<<n;                                      //那么意思是有n位，则需要2的n次方大才能枚举从00000-11111的组合喵
    for(int S=0;S<U;S++){
        if(__builtin_popcount(S)==k){          //核心
            int sum=0;
            for(int j=0;j<n;j++){
                if(S&(1<<j)){                          //判断基础数组里面这一位是否是1是需要的另外一种写法
                    sum+=a[j];
                }
            }
            if(check(sum)){                           //判断是否为素数
                count++;
            }
        }
    }
    cout<<count<<endl;
    return 0;
}

注意：这里补充一个“埃氏求素数法”，可以做到优化
核心思想是：从2开始，把每个素数的倍数都标记为合数。（合数的意思就是2，4，6，8，12这样的）
首先假设所有数都是素数，然后从2开始把2的倍数全部重新设定为非素数，下一次从接下来还假定为素数的数开始划去3，5....的的倍数
重复直到 √n，最终没被划掉的数就是素数：2, 3, 5, 7, 11, 13, 17...

代码如下实现：

#include <iostream>
#include <vector>
using namespace std;

vector<bool> sieve(int n) {
    vector<bool> isPrime(n + 1, true);          // 初始化：假设所有数都是素数
    
    isPrime[0] = isPrime[1] = false;              // 0和1不是素数
    
                                                             // 从2开始筛
    for (int i = 2; i * i <= n; i++) {
        if (isPrime[i]) {  
            for (int j = i * i; j <= n; j += i) {       // 把 i 的所有倍数标记为合数，其实这个int j = i * i; j <= n; j += I很不好想，不拿笔从2开始推到是不知道其实是之前从2开始就已经把相关倍数划去了
                isPrime[j] = false;                    //所以就直接从I*I开始 不好想的话可以笨拙一点  for(i*k<n) int j=I;j<=n;j+=i*k
            }
        }
    }
    return isPrime;
}
int main() {
    int n = 100;
    vector<bool> isPrime = sieve(n);
    for (int i = 2; i <= n; i++) {
        if (isPrime[i]) {
            cout << i << " ";
        }
    }
    cout << endl;
    return 0;
}

（好多枚举题 写着写着 发现不会了 去看题解全变成dp dfs的无力感，诶）

4.数组字典序排序函数 next_permutation(str,str+str.size())

这个函数每次会严格生成比他小的的字典序排序，传入的str是数组，经过这个函数后，str会被改变，改变的范围是你括号里面的范围
如果是排列数字的话，一般推荐先sort()成有序的，再使用 next_permutation() k 次后生成第 k 小的字典序排序；

例题：P1088：题意大概：输入n，k；输出1,2,3.....n数组第k小的字典序排序
代码如下：

    for (int i = 1; i <= k; i++){
        next_permutation(a + 1, a + 1 + n);        //这列因为数组是 1 基的 所以a[0]不使用，则函数范围是从a[1]到a[n]
    }

注意：next_permutation(a, b); 左闭右开区间 [a,b)

5.位置枚举(但是这个题用的dfs做的，所以就变成了这样)
P3654:大概题意：m*n的地图上障碍是'#',空地是 '.'，寻找连续的k个空地有多少种选择，
输入如下：

5 5 2
.###.
##.#.
..#..
#..#.
#.###

大概逻辑：先用vector<vector> map;二维char数组存放地图信息，需要额外初始(m+2)(n+2)的范围因为后面边界检查需要，如果没有的话边界检查会访问不存在的空间，会爆错
其次遍历每一个是空格的位置(O(n^2))，检查2个方向：向下和向右，用dfs里面的dis 0，1配上方向数组控制方向，继续检查下一个点，每次+一个长度，当长度大于规定的k，就return

代码如下：

int n, m, r;
int ans = 0;
int dx[2] = {1, 0};
int dy[2] = {0, 1};
vector<vector<char>> map;
void dfs(int x, int y, int dir, int len) {
    if (len == r) {
        ans++;
        return;
    }
    int nx = x + dx[dir];
    int ny = y + dy[dir];
    if (nx >= 1 && nx <= n && ny >= 1 && ny <= m && map[nx][ny] == '.') {
        dfs(nx, ny, dir, len + 1);
    }
}
int main() {
    cin >> n >> m >> r;
    map.resize(n + 2, vector<char>(m + 2, '#'));
    for (int i = 1; i <= n; i++) {
        string temp;
        cin >> temp;
        for (int j = 0; j < m; j++) {
            map[i][j + 1] = temp[j];
        }
    }
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (map[i][j] == '.') {
                for (int k = 0; k < 2; k++) {          // 第二步：遍历所有格子，对每个 '.' 尝试两个方向
                    dfs(i, j, k, 1);
                }
            }
        }
    }

5.一些其他小总结：
在遇到bigint很大的数据时，不妨把这个数字的每一位倒叙存放在一个数组num[]里面，然后模拟对他的运算，遇到进位就把num[i+1]位+1，当前num[i]位-=10，最后结果再倒叙输出

呃，刷题还是太少了，第10章排列组合先这样，接下来第11章递推与递归我来看看怎么个事，20260417，