题意给出一个 $n(\le 10^5)$ ，求集合 $\{1,2,...,n\}$ 的满足：若 $x$ 在集合中，则 $2x$ 和 $3x$ 不能出现在集合中 的子集个数。题解可以构造一个矩形，横向依次 $\times 3$ ，纵向依次 $\times 2$ ，如下图所示：1 3 9 27 81 243
2 6 18 54 162 486
4 12 36 108 324 972在这个矩形中选...
题意有 $n(\le 18)$ 只绿猪，位置在 $(x_i,y_i)$ 。每次可以从 $(0,0)$ 发射一只小鸟，开口向下的抛物线上的猪会被消灭。问至少要发射多少只小鸟。题解容易想到暴力的状压。用 $f(S)$ 表示消灭集合 $S$ 中的绿猪需要多少只小鸟，预处理出经过 $i,j$ 两只猪的抛物线可以消灭的猪 $s[i][j]$，枚举不在 $S$ 中的两只猪 $i,j$ ，方程式为：$$\...
题意给一个数字串 $s(|s|\le 10)$ 和正整数 $d(\le 1000)$ , 统计 $s$ 有多少种不同的排列能被 $d$ 整除（可以有前导 $0$）。题解$|s|$ 较小，考虑状压。用 $f(S,i)$ 表示下标集合 $S$ 内的数都用过了，当前数 $\equiv i\pmod d$ 。每次枚举一个不在 $S$ 的数 $j$ 加入转移，方程式为：$$f(S,i)\rightar...
题意给一个 $n(\le 15)$ 个点 $m$ 条边的无向连通图（不存在自环或重边），每条边有一个边权，要求割掉若干条边，使 $1$ 到 $n$ 只有 $1$ 条路径（不经过重复点），问割掉的边权和最小是多少。题解可以发现最后图的形态一定是一条链，链上可能挂了若干个连通块，要最大化图的边权和。$n$ 比较小，考虑状压。用 $f(S,i)$ 表示目前链上的终点为 $i$ ，加入的点集为 $S...
题意有 $N$ 张卡片，使用过后会往前跳 $S_i$ 格。有 $M$ 个格子是厄运格，如果跳到就输了，求跳到终点的方案数。$N\le 24 \ , \ M\le 2$ 。题解用 $cnt[i]$ 表示当前走到的格子，很容易想出状压方程：$$f[i]=\begin{cases} 0 \ (cnt[i]\in M) \\ f[i]+f[i \ xor \ 2^{j-1}] \ (cnt[i]\n...
题意有 $N$ 个人要排队，要求一队的站在一起，共有 $M$ 队。调整队列的方法为让一部分人出队，再回到不同的空位里。求最少要让多少人出队。$N\le 100000 \ , \ M\le 20$ 。题解对每支队伍是否有序状压，用 $f[i]$ 表示状态为 $i$ 时最少的出队人数。记录第 $j$ 支队伍的人数为 $cnt[j]$ ，设之前排到了第 $l$ 个人，那么现在要排的是 $[l+1,...
题意有 $N$ 个人去执行 $N$ 个任务，每个人执行每个任务有不同的成功率，每个人只能执行一个任务，求所有任务都执行的总的成功率。（直接用题面）$N\le 20$ 。题解用 $f[i]$ 表示任务完成状态为 $i$ 时的最大成功率。预处理出 $1$ 的个数 $cnt[i]$ ，枚举任务 $j$ ，很容易得到方程：$$f[i]=\max f[i \ xor \ 2^{j-1} ]+s[cnt...
题意用 $K$ 个硬币购买 $N$ 个物品。商店不设找零，可以在购买了连续多个物品后用 一个 硬币支付。求最多能剩下多少钱。$N\le 100000 \ , \ K\le 16$ 。题解看到 $K\le 16$ ，状压。用 $f[i]$ 表示硬币使用状况为 $i$ 时能买前几个物品；预处理出 $v[i][j]$ 表示硬币 $i$ ，从 $j$ 物品开始买，能买到哪个物品；枚举当前用的硬币 $...
题意在树上放一些山贼集团的分部，每个分部可以收取根节点到它路径上所有节点的保护费。在节点 $i$ 建立分部 $j$ 花费 $s[i][j]$ 。对于每一个节点，如果它被多个分部收保护费，就可能产生收益或损失。求最优的放置方法，可以得到最大利润。其中点数 $N\le 100$ ，分部个数 $P\le 12$ 。题解看到 $P$ 的范围，显然可以对节点上放置分部的状态进行状压。因为每个分部收取的...
题意一个有点权和边权的无向图，求 所有点权和为 $0$ 的子图 的最小生成树的权值和。其中点数 $N\le 16$ 。题解看了半天题才得到上面的题意，看到 $N\le 16$ ，显然是状压。用 $f[id]$ 表示当前点集状态为 $id$ 时的最优解，当 $i$ 和 $j$ 状态内的点权和为 $0$ 时，转移方程式很显然：$$f[i|j]=f[i]+\text{Kruskal}(j)$$对每...
题意有 $N$ 个长度相同的字符串，问恰好与其中 $K$ 个匹配的字符串有多少个。定义满足如下条件的字符串 $x$ 和 $y$ 为匹配的：$len_x=len_y$$\forall 1\le i\le len_x \ , \ x[i]='?' \ or \ x[i]=y[i]$其中 $N\le 15$ ，字符串长度 $len\le 50$ 。题解看数据范围，可以对 $N$ 进行状压。先预处理...
题意学生排队去食堂吃饭，每个学生都有不同的口味 $\text{T}[]$ 。食堂做第 $1$ 到菜不需要时间，之后在口味为 $x$ 的菜后做口味为 $y$ 的菜花费的时间为 $x\oplus y$ 。为了节省总等待时间，食堂有时会不按排队顺序做，但每个同学最多忍受他后面的 $\text{B}[i]$ 个同学在他之前打饭。求等待总时间的最小值。其中人数 $N\le 1000$ ，$\text{...
题意动物园的笼子环形排列，每个小朋友能看到从站的位置开始往后共 $5$ 个笼子的动物，每个小朋友都有喜欢和害怕的动物。可以移走一部分笼子。定义每个小朋友是开心的，当且仅当下列条件之一满足：在视线范围内至少有一个喜欢的动物没被移走。在视线范围内至少有一个害怕的动物被移走。求最优方案，使得开心的小朋友尽可能多。其中动物数 $N\le 10000$ ，小朋友个数 $C\le 50000$ 。题解动...
题意在 $N\times M$ 的图中部署炮兵，只有平原才能部署。每个炮兵的攻击范围为上下左右各延申两格，求方案数。其中 $N\le 100,M\le 10$ 。题解跟 玉米田 差不多，但是因为前两行都对当前状态有影响，所以需要多一维。如果直接开 $\text{f}[105][1024][1024]$ 的数组空间就爆了，所以需要预处理每一行合法的状态。可以发现合法的状态最多 $60$ 种，所...
题意在一个 $N\times M$ 的田地里种草，有的地方不能种，要求不能有两块相邻的。求方案数。其中 $N,M\le 12$ 。题解状压dp。把图存下来，每次枚举时判断状态合不合法即可。$$\text{f}[i][j]+=\text{f}[i-1][k]$$#include<bits/stdc++.h>
#define ha 100000000
using namespace...