AcWing 1118. 分成互质组
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 15;

int n;
int p[N];
int group[N][N];
bool st[N];
int ans = N;

int gcd(int a, int b)
{
    return b ? gcd(b, a % b) : a;
}

bool check(int group[], int gc, int i)
{
    for (int j = 0; j < gc; j++)
        if (gcd(p[group[j]], p[i]) > 1)
            return false;

    return true;
}

//搜第g组，当前组里有gc个元素，当前一共搜了tc个元素，这组从start号下标开始搜
void dfs(int g, int gc, int tc, int start)
{
    if (g >= ans) return ;
    if (tc == n) ans = g;

    bool flag = true;
    for (int i = start; i < n; i++)
        if (!st[i] && check(group[g], gc, i))
        {
            st[i] = true;
            group[g][gc] = i;
            dfs(g, gc + 1, tc + 1, i + 1);
            st[i] = false;

            flag = false;
        }

    //新开组    
    if (flag) dfs(g + 1, 0, tc, 0);
}

int main()
{
    cin >> n;
    for (int i = 0; i < n; i++) cin >> p[i];

    dfs(1, 0, 0, 0); //搜第1组，当前组里有0个元素，当前一共搜了0个元素，这组从0号下标开始搜

    cout << ans << endl;

    return 0;
}
165. 小猫爬山
#include <iostream>
#include <algorithm>

using namespace std;

const int N = 20;

int n, m;
int w[N];
int sum[N];
int ans = N;

void dfs(int u, int k) //搜索第u个小猫，开了k个车
{
    if (k >= ans) return ;//最优性剪枝
    if (k < ans && u == n)
    {
        ans = k;
        return ;
    }

    //可行性剪枝
    for (int i = 0; i < k; i++)
        if (sum[i] + w[u] <= m)
        {
            sum[i] += w[u];
            dfs(u + 1, k);  //搜索下一个，k个车不变
            sum[i] -= w[u];
        }

    //新开一辆车
    sum[k] = w[u];    //sum[k] 指第k+1个车
    dfs(u + 1, k + 1);
    sum[k] = 0;
}

int main()
{
    cin >> n >> m;
    for (int i= 0; i < n; i++)  cin >> w[i];

    sort(w, w + n);
    reverse(w, w + n);

    dfs(0, 0);  //从第0号开始搜，已经搜了0个

    cout << ans << endl;

    return 0;
}
AcWing 166. 数独
#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

const int N = 9, M = 1 << N;

//打表
//ones[M]快速的求出来状态里有多少个1,map[]log2k
int ones[M], map[M];
int row[N], col[N], cell[3][3];
char str[100];

void init()
{
    //初始化每一位都是1，1代表可以用，1-9都可以用
    for (int i = 0; i < N; i++)
        row[i] = col[i] = (1 << N) - 1;

    for (int i = 0; i < 3; i++)
        for (int j = 0; j < 3; j++)
            cell[i][j] = (1 << N) - 1;
}

//辅助函数
//当前在x,y是把t填上，还是删掉（填就是dfs，删掉就是恢复现场的过程）
//1表示能用，0表示不能用
void draw(int x, int y, int t, bool is_set)
{
    if (is_set) str[x * N + y] = '1' + t; //t是0-8
    else str[x * N + y] = '.';

    int v = 1 << t;
    if (!is_set) v = -v;   //如果是清空操作，取反

    row[x] -= v;
    col[y] -= v;
    cell[x / 3][y / 3] -= v; 
}

int lowbit(int x)
{
    return x & -x;
}

int get(int x, int y)
{
    //哪一个数可以用
    return row[x] & col[y] & cell[x / 3][y / 3]; 
}

bool dfs(int cnt)
{
    if (!cnt) return true;   //当前没有宫格了，就找到合法方案

    int minv = 10;
    int x, y;
    for (int i = 0; i < N; i++)
        for (int j = 0; j < N; j++)
            if (str[i * N + j] == '.')
            {
                int state = get(i, j);
                if (ones[state] < minv)    //每个二进制数里1的个数
                {
                    minv = ones[state];
                    x = i, y = j;
                }
            }

    //循环完，xy存的是分支数量最少的格子
    //先看下这个格子能枚举哪个数
    int state = get(x, y);
    for (int i = state; i; i -= lowbit(i))
    {
        int t = map[lowbit(i)];  //lowbit(i)返回2的k次方，map一下，把2的k次方映射成k(1代表这个数可以填，map映射给t)
        draw(x, y, t, true);
        if (dfs(cnt - 1)) return true; //dfs下一层
        draw(x, y, t, false);
    }

    return false;
}

int main()
{
    for (int i = 0; i < N; i++) map[1 << i] = i;//2的i次幂作为下标，存的值为i
    for (int i = 0; i < 1 << N; i++)
        for (int j = 0; j < N; j++)
            ones[i] += i >> j & 1;   //每个数二进制表示有多少个1

    while (cin >> str, str[0] != 'e')
    {
        init();

        int cnt = 0;
        for (int i = 0, k = 0; i < N; i++)
            for (int j = 0; j < N; j++, k++)
                if (str[k] != '.')
                {
                    int t = str[k] - '1';  //先看下数字是多少
                    draw(i, j, t, true);   //在这个点填上t
                }
                else cnt++;                //否则就是空格

        dfs(cnt);

        puts(str);
    }

    return 0;
}
AcWing 167. 木棒
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 70;

int n;
int w[N], sum, length;
bool st[N];

bool dfs(int u, int s, int start)
{
    if (u * length == sum) return true;
    if (s == length) return dfs(u + 1, 0, 0);

    //i从start开始枚举
    for (int i = start; i < n; i++)
    {
        if (st[i]) continue;
        if (s + w[i] > length) continue;

        st[i] = true;
        if (dfs(u, s + w[i], i + 1)) return true;
        st[i] = false;

        //如果当前大棍的第一个小棍就失败的话，就return
        if (!s) return false;

        //如果当前大棍的最后一个小棍失败的话，就return
        if (s + w[i] == length) return false;

        //当前长度的失败了，等长的都不要试了
        int j = i;
        while (j < n && w[j] == w[i]) j++;
        i = j - 1;
    }

    return false;
}

int main()
{
    while (cin >> n, n)
    {
        memset(st, 0, sizeof st);
        sum = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> w[i];
            sum += w[i];
        }

        //优化搜索顺序
        sort(w, w + n);
        reverse(w, w + n);

        length = 1;
        while (true)
        {
            if (sum % length == 0 && dfs(0, 0, 0)) //枚举每一根大棍，每根长度为0，从0开始枚举
            {
                cout << length << endl;
                break;
            }
            length++;
        }
    }

    return 0;
}#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 70;

int n;
int w[N], sum, length;
bool st[N];

bool dfs(int u, int s, int start)
{
    if (u * length == sum) return true;
    if (s == length) return dfs(u + 1, 0, 0);

    //i从start开始枚举
    for (int i = start; i < n; i++)
    {
        if (st[i]) continue;
        if (s + w[i] > length) continue;

        st[i] = true;
        if (dfs(u, s + w[i], i + 1)) return true;
        st[i] = false;

        //如果当前大棍的第一个小棍就失败的话，就return
        if (!s) return false;

        //如果当前大棍的最后一个小棍失败的话，就return
        if (s + w[i] == length) return false;

        //当前长度的失败了，等长的都不要试了
        int j = i;
        while (j < n && w[j] == w[i]) j++;
        i = j - 1;
    }

    return false;
}

int main()
{
    while (cin >> n, n)
    {
        memset(st, 0, sizeof st);
        sum = 0;
        for (int i = 0; i < n; i++)
        {
            cin >> w[i];
            sum += w[i];
        }

        //优化搜索顺序
        sort(w, w + n);
        reverse(w, w + n);

        length = 1;
        while (true)
        {
            if (sum % length == 0 && dfs(0, 0, 0)) //枚举每一根大棍，每根长度为0，从0开始枚举
            {
                cout << length << endl;
                break;
            }
            length++;
        }
    }

    return 0;
}