bitsetで殴るとは

bitsetの使い方

  • 今までは2進数表示でprintするときしか使っていなかった
  • 以下のような使い方ができる
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    bitset<10> dp;
    dp[0] = 1;
    dp[3] = 1;
    cout << dp << endl;

    dp |= (dp<<1); // 左に1シフトして自身に足す
    cout << dp << endl;

    return 0;
}

結果は

0000001001
0000011011

これにより、以下の問題が解けます。

  • A = [a0, a1, ..., aN]
  • K
  • Aからいくつか選び（全てでもいいし、0でもいい）、Kが作れるか判定せよ

応用問題

関連

  • 個数制限つきナップサック アリ本p64