AOJ プログラミング応用 トピック#10, トピック#11

#トピック#10
##[ITP2_10_A](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_10_A)
###Bit Operation I

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    ll x;
    cin >> x;
    bitset<32> b(x);
    
    cout << b << endl;
    cout << b.flip() << endl;
    cout << (b.flip()<<1) << endl;
    cout << (b>>1) << endl;

    return 0;
}
```

##[ITP2_10_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_10_B)
###Bit Operation II

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    ll x, y;
    cin >> x >> y;
    bitset<32> X(x);
    bitset<32> Y(y);
    
    cout << (X&Y) << endl;
    cout << (X|Y) << endl;
    cout << (X^Y) << endl;

    return 0;
}
```

##[ITP2_10_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_10_C)
###Bit Flag

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    ll q;
    cin >> q;
    bitset<64> bit;
    rep(qq, q){
        int query, i;
        cin >> query;
        
        switch (query) {
            case 0:
                cin >> i;
                cout << bit.test(i) << endl;
                break;
            case 1:
                cin >> i;
                bit.set(i);
                break;
            case 2:
                cin >> i;
                bit.reset(i);
                break;
            case 3:
                cin >> i;
                bit.flip(i);
                break;
            case 4:
                if(bit.all()) cout << 1 << endl;
                else cout << 0 << endl;
                break;
            case 5:
                if(bit.any()) cout << 1 << endl;
                else cout << 0 << endl;
                break;
            case 6:
                if(bit.none()) cout << 1 << endl;
                else cout << 0 << endl;
                break;
            case 7:
                cout << bit.count() << endl;
                break;
            case 8:
                cout << bit.to_ulong() << endl;
                break;
            default:
                break;
        }
    }
    
    return 0;
}
```

##[ITP2_10_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_10_D)
###Bit Mask

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    ll n, q;
    cin >> n;
    vector<bitset<64>> masks(n);
    rep(i, n){
        int k;
        cin >> k;
        rep(j, k){
            int x;
            cin >> x;
            masks[i].set(x);
        }
    }
    
    cin >> q;
    bitset<64> bit;
    rep(i, q){
        int query, m;
        cin >> query >> m;
        
        switch (query) {
            case 0:
                cout << bit.test(m) << endl;
                break;
            case 1:
                bit = bit | masks[m];
                break;
            case 2:
                bit = bit & (~masks[m]);
                break;
            case 3:
                bit = bit ^ masks[m];
                break;
            case 4:
                cout << ((bit & masks[m])==masks[m]) << endl;
                break;
            case 5:
                cout << (bit & masks[m]).any() << endl;
                break;
            case 6:
                cout << (bit & masks[m]).none() << endl;
                break;
            case 7:
                cout << (bit & masks[m]).count() << endl;
                break;
            case 8:
                cout << (bit & masks[m]).to_ulong() << endl;
                break;
            default:
                break;
        }
    }
    
    return 0;
}
```

#トピック#11
##[ITP2_11_A](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_11_A)
###Enumeration of Subsets I

0からn−1までのn個の整数を要素とする集合Uの全ての部分集合を列挙してください。
n=4として、0, 1, 2, 3の要素の部分集合は、

0からn−1をそれぞれ2進数の00...0001、00...0010、00...0100、...、10...0000とし、存在する要素のビットごとの論理和を取ったもの

4bit, 2進数で0~15までのloopし、各bitが1の時、0, 1, 2, 3を表示する。
部分集合とはbitフラグが１となっている要素のindex。


```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {

    int n;
    cin >> n;
    
    for(int bit=0; bit<(1<<n); bit++){
        cout << bit << ":";
        for(int i=0; i<n; i++){
             if(bit>>i&1) cout << ' ' << i;
        }
        cout << endl;
    }
    
    return 0;
}
```

##[ITP2_11_B](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_11_B)
###Enumeration of Subsets II

Tの要素の部分集合は、各bitが1になる数字が入力で与えられます。
n=4の時、２行目Tは2, 0, 2とすると、
0, 2bitが1である整数5, 7, 13, 15が出力になります。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    int k;
    cin >> k;
    bitset<18> T;
    rep(i, k){
        int t;
        cin >> t;
        T.set(t);
    }
    
    for(ll bit=0; bit<(1<<n); bit++){
        if((bit&T.to_ulong())!=T.to_ulong()) continue;
        cout << bit << ":";
        for(ll i=0; i<n; i++){
             if(bit>>i&1) cout << ' ' << i;
        }
        cout << endl;
    }
    
    return 0;
}
```

##[ITP2_11_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_11_C)
###Enumeration of Subsets III

ITP2_11_CがUの部分集合でありTの部分集合。
今回は、Tの全ての部分集合。
Tを反転し、Uとの論理和がTRUEなら判定しない。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    int k;
    cin >> k;
    bitset<28> T;
    rep(i, k){
        int t;
        cin >> t;
        T.set(t);
    }
    
    for(ll bit=0; bit<(1<<n); bit++){
        if((bit&~T.to_ulong())) continue;
        cout << bit << ":";
        for(ll i=0; i<n; i++){
             if(bit>>i&1) cout << ' ' << i;
        }
        cout << endl;
    }
    
    return 0;
}
```

##[ITP2_11_D](https://onlinejudge.u-aizu.ac.jp/courses/lesson/8/ITP2/all/ITP2_11_D)
###Enumeration of Combinations

0からn−1までのn個の整数の中から異なるk個の整数を選ぶ組み合わせ、
bitが1の数をカウントし、kと等しい数字とその数字で1になっているbitを表示する。

```C++:C++
#include<iostream>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<utility>
#include<iomanip>
#include<map>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<list>
#include<set>
#include<bitset>

#define rep(i,n) for(int i=0; i<(n); i++)
#define pai 3.1415926535897932384
#define NUM_MAX 2e18
#define NUM_MIN -1e9

using namespace std;
using ll =long long;
using P = pair<int,int>;

int main(int argc, const char * argv[]) {
    int n;
    cin >> n;
    int k;
    cin >> k;
    
    for(ll bit=0; bit<(1<<n); bit++){
        bitset<18> T(bit);
        if(T.count()!=k) continue;
        cout << bit << ":";
        for(ll i=0; i<n; i++){
             if(bit>>i&1) cout << ' ' << i;
        }
        cout << endl;
    }
    
    return 0;
}
```

集合を少し理解した！