题解 P1657 【选书】
Creeper_LKF
2017-07-03 17:17:23
###二进制解法
```cpp
#include<bits/stdc++.h>
using namespace std;
int x,love[2][21],ans;
bool used[21];//位运算版
inline int read(){//读入优化超空间压行版
int num=0;
char c;
while(isspace(c=getchar()));
while((num=num*10+c-48)&&isdigit(c=getchar()));
return num;
}
inline bool query(int tar){
memset(used,false,sizeof(used));//初始化没选书
for(int i=1;i<=x;i++,tar>>=1)//枚举每一个人选的每一本书,tar&1==0代表选第一本,tar&1==1代表选第二本
if(used[love[tar&1][i]]) return false;//如果该书被选过则方案错误
else used[love[tar&1][i]]=true;//如果该书没被选过则标记该书
return true;//所有人选的书都没有重合
}
int main(){
if(!(x=read())){//特判+压行
printf("0");
return 0;
}
for(int i=1;i<=x;i++) love[0][i]=read(),love[1][i]=read();
int max_x=(1<<x);//在不开O2的情况下节约时间,下一行当i++时便可枚举下一种情况
for(int i=0;i<max_x;i++) if(query(i)) ans++;//如果要按字典序输出的话,可枚举格雷码,如果方案正确则计数器++
printf("%d",ans);
return 0;
}
```