P7859 [COCI2015-2016#2] GEPPETTO
tuxuanming2024
·
·
题解
前置知识：位运算
用法： 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 ，再用位运算依次判断是否冲突即可。
```cpp
#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;
}
```