状压dp

位运算

有 #define ui unsigned int

1u 是获取一个类型为 ui 的 \(1\)

一般来说 认为 unsigned 比 signed 在为运算上更快

左移/右移

ui left(ui x,int pos){
	return x<<pos;
}
ui right(ui x,int pos){
	return x>>pos;
}

获取某位

bool getBit(ui x,int pos){
	return (x>>pos)&1;
}

设某位

ui setBit(ui x,int pot,bool val){
	if(val) return x|(1u<<pos);
    else return x&~(1u<<pos);
}

取反某位

ui flipBit(ui x,int pos){
	return x^(1u<<pos);
}

下面是一些比较少用的

获取 \(1\) 的个数

int countBit(ui x){
	x-=((x&0xAAAAAAAAu)>>1);
	x=((x&0xCCCCCCCCu)>>2)+(x&0x33333333u);
	x=((x>>4)+x)&0x0F0F0F0Fu;
	x=(x*0x01010101u)>>24;
	return x;
}

对于每一位翻转

比如 \(0\) 位和 \(31\) 位交换

ui bitRev(ui x){
	x=((x&0xAAAAAAAAu)>>1)|((x&0x55555555u)<<1);
	x=((x&0xCCCCCCCCu)>>2)|((x&0x33333333u)<<2);
	x=((x&0xF0F0F0F0u)>>4)|((x&0x0F0F0F0Fu)<<4);
	x=((x&0xFF00FF00u)>>8)|((x&0x00FF00FFu)<<8);
	x=((x&0xFFFF0000u)>>16)|((x&0x0000FFFFu)<<16);
	return x;
}

**求前缀 \(0\) **

int countLeadingZero(ui x){
	int ans=0;
	if(x>>16) x>>=16; else ans|=16;
	if(x>>8) x>>=8; else ans|=8;
	if(x>>4) x>>=4; else ans|=4;
	if(x>>2) x>>=2; else ans|=2;
	if(x>>1) x>>=1; else ans|=1;
	return ans+!x;;
}

**求后缀 \(0\) **

int countTrailingZero(ui x){
	int ans=0;
	if(!(x&65535u)) x>>=16,ans|=16;
	if(!(x&255u)) x>>=8,ans|=8;
	if(!(x&15u)) x>>=4,ans|=4;
	if(!(x&3u)) x>>=2,ans|=2;
	if(!(x&1u)) x>>=1,ans|=1;
	return ans+!x;
}

提取 lowbit

有几种

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

取集合

ui intersection(ui x,ui y){
	return x&y;
}
ui union(ui x,ui y){
	return x|y;
}
ui difference(ui x,ui y){ //属于x但不属于y 是有方向的
	return x^(x&y);
}
ui complement(ui x){
	return ~x;
}

dp

动态规划的一种 通过状态压缩(不一定是二进制 也可以是k进制)来优化转移

特点 某一维比较小 大概有 \(n \le 18\)

luogu#P1896 [SCOI2005]互不侵犯

问题 在 \(N \times N\) 的棋盘中放 \(K\) 和国王(可以攻击上下左右左上左下右上右下8格的),求互不攻击摆放数?

luogu#P1879 [USACO06NOV]Corn Fields G

问题 在 \(M \times N\) 的网格图上种牧草,有些土地不能种草且没有两块土地相邻,求种植方案数?(特别的 空集也是一种)

luogu#P2704 [NOI2001]炮兵阵地

问题 在 \(N \times M\) 的网格上部署炮兵(可以攻击左二右二上二下二),且有山地(不可部署),求最多可摆放炮兵数?

luogu#P2051 [AHOI2009]中国象棋

问题 在一个 \(N \times M\) 的棋盘上,放若干个炮(可以隔着一个攻击)(也可以是 \(0\) 个),求方案数?

luogu#P6192 【模板】最小斯坦纳树

问题 给出一个 \(n\) 个点 \(m\) 条边的带权无向连通图 \(G=(V,E)\) ,再给出一个包含 \(k\) 个点的点集 \(H\) ,选出 \(G\) 的子图 \(G‘=(V‘,E‘)\) 使得: 1. \(H \subseteq V‘\) 2. \(G‘\) 为连通图 3. \(E‘\) 中的所有边权值和最小

luogu#P2831 愤怒的小鸟

问题 在一个平面直角坐标系中有 \(n\) 个特殊坐标,你可以从 \((0,0)\) 画出一个二次函数,求最少需要几条才能覆盖所有的坐标.

luogu#P3959 宝藏

问题 地图上有 \(n\) 个宝藏屋,并用 \(m\) 条道路相连,可以从任意一个点出发.可以开发一条道路,代价为 \(L\times K\) ,最终使图连通,求最小代价?

luogu#P4363 [九省联考2018]一双木棋chess

状压dp

原文：https://www.cnblogs.com/nenT/p/14001813.html