题解 P1657 【选书】

Creeper_LKF

2017-07-03 17:17:23

Solution

###二进制解法 ```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; } ```