自动搬运

查看原文

来自洛谷，原作者为

	tuxuanming2024 NOIP 三等奖

搬运于2025-08-24 22:33:43，当前版本为作者最后更新于2021-09-17 14:07:16，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前置知识：位运算

• 左移运算：<<

用法： x<<y

作用：将表示 $x$ 的二进制数的每一位左移 $y$ 位，移出去的数就丢掉，空余地方用 $0$ 补位。

例如：一个二进制数 $10101011$ 将其左移 $3$ 位，得到 $01011000$。

• 按位与运算： &

用法：x&y

作用：按位进行与运算。

例如：$1101$ 和 $0011$ 进行与运算就为：$0001$。

利用上面的两种运算，我们就可以来判断一个二进制数的某位是 $0$ 或 $1$ ，假设我们要判断 $x$ 的从右到左第 $n$ 的数字，只需判断 x&(1<<(n-1)) 是真还是假即可。因为对于 1<<(n-1) 所算出来的数，除了从右到左第 $n$ 位，其他的都是 $0$，再与 $x$ 进行与运算，如果 $x$ 的第 $n$ 位是 $1$，那么 1&1 的结果为 $1$ ，反之则为 $0$。

题解

令一个二进制数的第 $i$ 位表示：

$$\begin{cases}0 \ \ \text{不放第 i 种材料}\\1 \ \ \text{放第 i 种材料}\end{cases} $$

所以，我们只需要枚举这样的二进制数，从 $0$ 枚举到 (1<<n)-1 ，再用位运算依次判断是否冲突即可。

$\color{white}\colorbox{green}{AC}$ Code：

#include <iostream>
using namespace std;
struct node {int x,y;}b[405];
int n,m,a[405],ans;
bool c[25][25];
int main()
{
	cin>>n>>m;
	int x,y;
	for(int i=1;i<=m;i++) cin>>b[i].x>>b[i].y;
	for(int i=0;i<(1<<n);i++)
	{
		bool bj=0;
		for(int j=1;j<=m;j++)
			if(i&(1<<(b[j].x-1))&&i&(1<<(b[j].y-1)))
				{bj=1; break;}
		if(!bj) ans++;
	}
	cout<<ans;
	return 0;
}