今天的内容主要是状压dp，与位运算有很多关联，下面是一些位运算的基本符号、作用、常见用途以、综合操作、今天的测试题以及最后的整体总结

位运算的基本符号、作用、常见用途以、综合操作

1.按位与 (&)

规则：两个对应的位都为 1 时，结果才为 1，否则为 0。

常见用途：

清零特定位：a & mask （mask 中需要清零的位为 0，其余为 1）

判断奇偶：a & 1 （结果为 1 是奇数，为 0 是偶数）

判断是否为 2 的幂：(a & (a - 1)) == 0 （且 a > 0）

获取最低位的1：lowbit = x & (-x)

清理最低位的1：x = x & (x - 1)

2. 按位或 (|)

规则：两个对应的位只要有一个为 1，结果就为 1。

常见用途：

将特定位设为 1：a | mask （mask 中需要置 1 的位为 1，其余为 0）

合并状态标志：flags = flagA | flagB

3. 按位异或 (^)

规则：两个对应的位不同时为 1，相同时为 0。

常见用途：

翻转特定位：a ^ mask （mask 中需要翻转的位为 1）

不使用临时变量交换两个数：a ^= b; b ^= a; a ^= b;

找出数组中唯一出现一次的数字（其他数字都出现两次）：全部异或起来

4. 按位取反 (~)

规则：单目运算符，将 0 变 1，1 变 0。

常见用途

对一个数取反：~mask

5. 左移 (<<)

规则：将所有二进制位向左移动指定的位数，右侧空出的位补 0，左侧溢出的位被丢弃。

常见用途：

快速乘法：a << n 等价于 a * (2^n) （前提是不发生溢出）

构造掩码：1 << n 表示第 n 位为 1，其余为 0

6. 右移 (>>)

规则：将所有二进制位向右移动指定的位数，右侧溢出的位被丢弃。左侧补位规则取决于

数据类型：

无符号数：左侧补 0（逻辑右移）

有符号数：左侧补符号位（算术右移，正数补0，负数补1）

常见用途：

快速除法：a >> n 等价于 a / (2^n) （向下取整）

综合操作：

1.判断第k位是否位1：ok = (x >> k) & 1（从0开始编号）

2.将第k位设为1：x = x | (1 << k)

3.将第k位设为0：x = x & ~(1 << k)

4.翻转第k位：x = x ^ (1 << k)

5.判断任意一个数是否是2的幂：ispow = (x > 0) && (x & (x - 1) == 0)（二进制只有一个1）

考试题目：

T1:Qualification Rounds

链接：****https://qycode64.com/p/CF868C

题意理解：

要求选出若干道题目，满足每一支队伍会的题目数量≤总题目数/2

结论：

如果存在人以合法子集，那么一定存在大小为1或2的合法子集

①若子集大小为1：这道题s=0（没有队伍会这道题）

②若子集大小为2：两题状态a,b满足a&b==0（不存在任何一支队伍同时知道这两道道题）

代码：

#include <bits/stdc++.h>
using namespace std;
int sta[100010];
bool vis[16];
int main () {
	freopen ("rtmrts.in", "r", stdin);
	freopen ("rtmrts.out", "w", stdout);
	int n, k;
	scanf ("%d%d", &n, &k);
	for (int i = 1; i <= n; i++) {
		int s = 0;
		for (int j = 0; j < k; j++) {
			int x;
			scanf ("%d", &x);
			if (x) s |= (1 << j); 
		}
		vis[s] = true;
	}
	if (vis[0]) {
		puts ("YES");
		return 0;
	} 
	for (int i = 0; i < (1 << k); i++) {
		if (!vis[i]) continue;
		for (int j = 0; j < (1 << k); j++) {
			if (!vis[j]) continue; 
			if ((i & j) == 0) {
				puts ("YES");
				return 0;
			}
		}
	} 
	puts ("NO");
	return 0;
}

T2:Dima and a Bad XOR（个人认为这是一道签到题）

链接：****https://qycode64.com/p/CF1151B

题意理解：

在二维数组中的每一行选择一个数字，使得这些数字的xor>0成立，输出这些数

结论：

先全部选择第一列，如果已经严格>0，那么直接输出ans，否则j从2开始遍历，选出一个a[i][j] != a[i][1]，将ans[i]变为j，break，输出答案

代码：

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[510][510]; 
int ans[510];
int main () {
	freopen ("badxor.in", "r", stdin);
	freopen ("badxor.out", "w", stdout);
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) {
		ans[i] = 1;
		for (int j = 1; j <= m; j++) scanf ("%d", &a[i][j]);
	}
	int res = 0;
	for (int i = 1; i <= n; i++) res = res ^ a[i][1];
	if (res > 0) {
		puts ("TAK"); 
		for (int i = 1; i <= n; i++) printf ("%d " , ans[i]);
		return 0;
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 2; j <= m; j++) {
			if (a[i][j] != a[i][1]) {
				ans[i] = j;
				puts ("TAK");
				for (int k = 1; k <= n; k++) printf ("%d ", ans[k]);
				return 0;
			}
		}
	}
	puts ("NIE");
	return 0;
}

T3:Boboniu and Bit Operations

链接：****https://qycode64.com/p/4938

题意理解：

寻找最小的非负整数 x，满足：

对每一个a[i]，至少存在一个b[j]，使得(a[i]&b[j])|x，等价于(a[i]&b[j])&(~x)=0

也就是(a[i]&b[j])的所有置 1 位，都被 x 包含。

目标：求出满足条件最小的 x。

结论：

从小到大枚举答案mask，第一个合法 mask 就是最小值；利用条件(a[i]&b[j])&(~mask)进行可行性的判断

代码：

#include <bits/stdc++.h>
using namespace std;
int n, m;
int a[210], b[210];
int main () {
	freopen ("bit.in", "r", stdin);
	freopen ("bit.out", "w", stdout);
	scanf ("%d%d", &n, &m);
	for (int i = 1; i <= n; i++) scanf ("%d", &a[i]);
	for (int i = 1; i <= m; i++) scanf ("%d", &b[i]);
	for (int mask = 0; mask < (1 << 9); mask++) {
		bool flag = true;
		for (int i = 1; i <= n; i++) {
			bool find = false;
			for (int j = 1; j <= m; j++) {
				int ci = a[i] & b[j];
				if ((ci & (~mask)) == 0) {
					find = true;
					break; 
				}
			}
			if (!find) {
				flag = false;
				break;
			}
		} 
		if (flag) {
			printf ("%d", mask);
			break;
		}
	} 
	return 0;
}

T4:Factorials and Powers of Two

题目链接：****https://qycode64.com/p/4959

题意理解：

规定强大数为：2的幂或者阶乘
求：最少需要几个强大数才能组成给定的数字n

思路：

• 1.预处理1!,2!,3!...14!（14!>10^12)，够用）存入fac数组

• 2.二进制枚举 mask：选取哪些阶乘参与求和

  • sumf：选中阶乘总和，cntf：阶乘个数
  • use 集合：记录选中的阶乘数值，防止和二进制拆分数字冲突

• 3.rem = n-sumf，把剩余数拆成二进制（天然互不相同的 2 的幂）

• 4.检查：二进制分解出来的 2 的幂，不能出现在选中阶乘集合 use 中

  •          合法则更新答案：总数量\=cntf\+cnt2
    

• 5.枚举所有阶乘组合，取最小值输出

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll jc[15]; 
vector <ll> fac; 
void pre () {
	jc[0] = 1;
	for (int i = 1; i <= 14; i++) jc[i] = 1LL * i * jc[i - 1];
	fac.clear ();
	for (int i = 1; i <= 14; i++) {
		if (fac.empty () || jc[i] != fac.back ()) fac.push_back (jc[i]);
	}
}
int main () {
	freopen ("factorials.in", "r", stdin);
	freopen ("factorials.out", "w", stdout);
	int T;
	scanf ("%d", &T);
	pre ();
	int len = fac.size ();
	while (T--) {
		ll n;
		scanf ("%lld", &n);
		int ans = 0x3f3f3f3f;
		for (int mask = 0; mask < (1 << len); mask++) {
			ll sumf = 0;
			unordered_set <ll> use;
			int cntf = 0; 
			for (int i = 0; i < len; i++) {
				if (mask & (1 << i)) {
					sumf += fac[i];
					use.insert (fac[i]);
					cntf ++; 
				} 
			}
			if (sumf > n) continue;
			ll rem = n - sumf;
			bool flag = true;
			int cnt2 = 0;
			for (int b = 0; b <= 40; b++) {
				if (rem & (1LL << b)) {
					ll num = 1LL << b;
					if (use.count (num)) {
						flag = false;
						break;
					}
					cnt2 ++;
				}
			} 
			if (flag) ans = min (ans, cntf + cnt2);
		} 
		printf ("%d\n", ans); 
	} 
	return 0;
}

待改进处：

代码冗余较多，在考试时未考虑到阶乘与2的幂的关系（阶乘中除了2!其它都不会与2的幂冲突），盲目使用哈希集合增加了代码的复杂度

T5:Party Lemonade（这是一道水题）

链接：****https://qycode64.com/p/5029

题意理解：

要买L升水，至少要花多少钱

思路：

1.若v[i]=2*v[i-1]且C[k]>2*C[k-1]，则不会用到C[k]，用2*C[k-1]覆盖C[k]的价格（其中v数组表示溶剂，C数组表示价格）

2.从后向前便利瓶子的价格和容积，计算可买的最大数量take及买的价格take*C[i]

代码：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll c[50];
ll pow2[50]; 
int main () {
	freopen ("party.in", "r", stdin);
	freopen ("party.out", "w", stdout); 
	int n;
	ll L;
	scanf ("%d%lld", &n, &L);
	for (int i = 1; i <= n; i++) scanf ("%lld", &c[i]);
	pow2[1] = 1;
	for (int i = 2; i <= n; i++) {
		pow2[i] = pow2[i - 1] * 2;
		c[i] = min (c[i], 2 * c[i - 1]);
	}
	for (int i = n - 1; i >= 1; i--) c[i] = min (c[i], c[i + 1]);
	ll ans = 1e18;
	ll cost = 0;
	ll need = L;
	for (int i = n; i >= 1; i--) {
		ll tmp = pow2[i];
		if (need <= 0) break;
		ll take = need / tmp;
		cost += take * c[i];
		need -= take * tmp;
		ans = min (ans, cost + c[i]);
	}
	if (need == 0) ans = min (ans, cost);
	printf ("%lld\n", ans);
	return 0;
}

T6:XOR, Expression and Two Binary Numbers

链接：****https://qycode64.com/p/4990

题意理解：

有一个不完整的数组，里面存着k个长度为n的二进制串，二进制串的长度为(1<<k)+1

有数组p表示已经填充好的下标为p[1]<p[2]<...<p[(1<<k)+1]

现在，我们只知道a[1]与a[(1<<k)+1]的值，要求我们填充这个数组

对于每个j∈[1,m-1]，赋值操作为：a[p[j]+p[j+1]]/2=a[p[j]]^a[p[j+1]]

又有数组x,y分别表示a[i] 中二进制位为1的数量与a[i]中二进制位为0的数量

要求我们输出x[1]*y[1]+x[2]*y[2]+..+x[(1<<k)+1]*y[(1<<k)+1]

思路：

考场思路：

因为时间原因，我看完题目后匆匆打了一个暴力，得了16分，暴力过程是这样的：

1.取出填好的，从小到大p[1]<p[2]<p[3]<...<p[(1<<k)+1]

2.相邻一对(p[i],p[i+1])中点mid=p[i]+p[i+1]/2

3.a[mid]=a[p[i]]^a[p[i+1]]

正解思路：

1.按位独立，二进制每一位互不影响，分开算贡献值

2.整条序列长度L=(1<<k)+1，对于单个bit：

①如果首尾该位相等：整条序列全部等于这个值（共 L 个相同数字）

• ②如果首尾该位不等：序列是交替0,1,0,1...，1 的数量固定cntC=(1<<(k-1))
• 3.对于任意位置的一个bit值b:
• ①题目要求求贡献值x*y，x:该数字中1的总数，y:0的总数
• ②若这一位是1，贡献(n-1)。是0贡献0
• 4.预处理两个常数:
• ①cntAB=(1<<(k-1))+1（A、B的出现次数）
• ②cntC=(1<<(k-1))（C的出现次数）
• 5.统计ans:oneA、B、C数组分别表示A、B、C中'1'出现的次数，则0出现的次数就为(n-cntA、B、C)，ans可统计为cntAB*oneA*(n - oneA)+cntAB*oneB*(n-oneB)+cntC*oneC*(n-oneC);

代码：

考场代码（代码写的特别长，实际上是屎山代码）:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char a[2010][110];
bool vis[2010];
int cur[2010];
int op_l[2010], op_mid[2010], op_r[2010];
ll hs (char s[], int n) {
	int cnt1 = 0;
	for (int i = 0; i < n; i++) {
		if (s[i] == '1') cnt1 ++;
	}
	return 1LL * cnt1 * (n - cnt1);
}
int main () {
	freopen ("binary.in", "r", stdin);
	freopen ("binary.out", "w", stdout); 
	int T;
	scanf ("%d", &T);
	while (T--) {
		int n, k;
		scanf ("%d%d", &n, &k);
		memset (vis, 0, sizeof (vis));
		memset (a, 0, sizeof (a));
		int M = (1 << k) + 1;
		char s[110], z[110];
		scanf ("%s%s", s, z);
		strcpy (a[1], s);
		vis[1] = true;
		strcpy (a[M], z);
		vis[M] = true;
		int cur_cnt = 0;
		cur[cur_cnt++] = 1;
		cur[cur_cnt++] = M;
		for (int step = 1; step <= k; step++) {
			int op_cnt = 0;
			for (int i = 0; i + 1 < cur_cnt; i++) {
				int p = cur[i];
				int q = cur[i + 1];
				int mid = (p + q) / 2;
				op_mid[op_cnt] = mid;
				op_l[op_cnt] = p;
				op_r[op_cnt] = q;
				op_cnt ++;
			}
			for (int i = 0; i < op_cnt; i++) {
				int mid = op_mid[i];
				int p = op_l[i];
				int q = op_r[i];
				for (int bit = 0; bit < n; bit++) {
					if (a[p][bit] == a[q][bit]) a[mid][bit] = '0';
					else a[mid][bit] = '1';
				}
				a[mid][n] = '\0';
				vis[mid] = true;
			}
			cur_cnt = 0;
			for (int i = 1; i <= M; i++) {
				if (vis[i]) cur[cur_cnt ++] = i;
			}
		}
		ll ans = 0;
		for (int i = 1; i <= M; i++) ans += hs (a[i], n);
		printf ("%lld\n", ans);
	}
	return 0;
}

正解代码（“整洁”代码）：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main () {
    freopen ("binary.in", "r", stdin);
    freopen ("binary.out", "w", stdout);
	int T;
	scanf ("%d", &T);
	while (T--) {
		int n, k;
		scanf ("%d%d", &n, &k);
		string s, z;
		cin >> s >> z;
		ll oneA = 0, oneB = 0, oneC = 0; 
		for (int i = 0; i < n; i++) {
			oneA += (s[i] == '1');
			oneB += (z[i] == '1');
			oneC += (s[i] != z[i]);
		} 
		ll cntAB = 1, cntC = 0;
		for (int i = 1; i <= k; i++) {
			ll ncAB = cntAB + cntC;
			ll ncC = cntAB * 2 - 1;
			cntAB = ncAB;
			cntC = ncC;
		}
		ll ans = cntAB * oneA * (n - oneA) + cntAB * oneB * (n - oneB) + cntC * oneC * (n - oneC);
		printf ("%lld\n", ans);
	} 
	return 0;
}

整体总结：

1. 常见易错问题

• 1.惯性暴力模拟复杂序列（如T6），未发现位独立规律，导致代码冗余、超时。
• 3.代码冗余，多余使用哈希、遍历等操作，未利用位运算原生特性优化。
• 4.位编号混淆（0/1起始）、移位溢出、掩码构造错误。

2.总结

• 1.做题先找规律、推结论，再写代码，杜绝无脑暴力模拟。
• 2.养成按位拆分习惯，所有二进制序列、异或构造题优先判断位独立性。
• 3.熟记位运算模板与经典结论，减少代码冗余，优化代码简洁度。