Automatic Control Machine(bitset+二进制枚举)

Automatic Control Machine

题解:\(bitset\)应用二进制枚举

AC_Code:

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <cmath>
 4 #include <bitset>
 5 #include <string>
 6 #include <algorithm>
 7 #include <cstring>
 8 using namespace std;
 9 typedef long long ll;
10 const int maxn = 505;
11 const double eps = 1e-8;
12 
13 char s[maxn];
14 bitset<maxn>p[20];
15 
16 int main()
17 {
18     int t; scanf("%d",&t);
19     while( t-- ){
20         int n,m; scanf("%d%d",&n,&m);
21         for(int i=1;i<=m;i++){
22             scanf("%s",s+1);
23             p[i].reset();   //reset:把p[i]中所有二进制位都置为"0"
24             for(int j=1;j<=n;j++){
25                 if( s[j]==1 ) p[i].set(j);    //set(j):把p[i]的j位置设成"1"
26             }
27         }
28 
29         int base = (1<<m)-1, ans=20;
30         for(int i=0;i<=base;i++){   //暴力枚举每一种组合,i的二进制:第x位"0"代表不选x,第x位为"1"代表选x
31             bitset<maxn>cnt;
32             int k=0;
33             for(int j=0;j<m;j++){
34                 if( i&(1<<j) ){
35                     cnt |= p[j+1];
36                     k++;
37                 }
38             }
39             if((int)cnt.count()==n ) ans=min(ans,k);
40         }
41         if( ans==20 ) printf("-1\n");
42         else printf("%d\n",ans);
43     }
44     return 0;
45 }

顺便总结一点\(bitset\)的用法:

bitset的定义和初始化

bitset<n> b; 
b有n位,每位都为0

 

bitset<n> b(u); 
b是unsigned long型u的一个副本


bitset<n> b(s); 
b是string对象s中含有的位串的副本


bitset<n> b(s, pos, n); 
b是s中从位置pos开始的n个位的副本



bitset的操作

b.any() 
b中是否存在置为1的二进制位?


b.none() 
b中不存在置为1的二进制位吗?


b.count() 
b中置为1的二进制位的个数


b.size() 
b中二进制位的个数


b[pos] 
访问b中在pos处的二进制位


b.test(pos) 
b中在pos处的二进制位是否为1?


b.set() 
把b中所有二进制位都置为1


b.set(pos) 
把b中在pos处的二进制位置为1


b.reset() 
把b中所有二进制位都置为0


b.reset(pos) 
把b中在pos处的二进制位置为0


b.flip() 
把b中所有二进制位逐位取反


b.flip(pos) 
把b中在pos处的二进制位取反

Automatic Control Machine(bitset+二进制枚举)

上一篇:75道Java常考面试题+18篇面试疑难点解析|面试必看


下一篇:Eclipse中仅enter键确认补全代码