1094号:棒

質問する

1094号:棒

に近づく

は簡単な公式問題で、棒はいつも半分に切るので、ビットマスクで解くこともできます.

64 cmをバイナリで表す棒が1000000で、Xcmを作ります.

の集合として、要素が含まれているかどうかを計算します.△簡単に言えば、Xがバイナリの場合、1の個数を計算すればよい.

マイコード

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int x = Integer.parseInt(br.readLine());
        int count = 0;
        for (int i = 0; i <= 6; i++) {
            if ((x & (1<<i)) != 0) count++;
        }
        System.out.println(count);
    }
}

forループのビット数は64であり、ループ内で(x & (1<<i))と判断すればよい.

📌 ビットマスク？

整数のバイナリ表示を資料構造にする手法です.

長所

O(1)より迅速に問題を解決できる

より簡潔なコード

:繰り返しを必要とせずに、様々なコレクション演算を1行に書き込むことができます.

より小さいメモリ使用量

関連配列の代わりに配列を使用する:C++の場合、ビットマスクを使用してmap<vector<bool>, int>をint[]に変更できます.

えんざん

演算コード2つの整数a、bビットAND演算a&b 2つの整数a、bビットOR演算a|b 2つの整数a、bビットXOR演算a^b整数aのビットNOT演算結果

ビットマスクセットの使用例

あるピザ屋には0から19の番号の20種類の具があり、注文時に具を入れるか入れないかを選択することができます.これにより,1つのピザの情報は20種類の要素のみの集合となり,ビットマスクで表現できる.

完全な集合を求める

int fullPizza = (1 << 20) - 1;

要素

を追加

toppings |= (1 << p);

要素

が含まれているかどうかを確認します.

if (toppings & (1 << p)) System.out.println("peperoni is in");

要素

を削除

toppings &= ~(1 << p);

要素の

に切り替えます.

toppings ^= (1 << p);

2つのセット

を演算する

int added = (a | b); // a와 b의 합집합
int intersection = (a & b); // a와 b의 교집합
int removed = (a & ~b); // a에서 b를 뺀 차집합
int toggled = (a ^ b); // a와 b중 하나에만 포함된 원소들의 집합

セットの大きさの

を求めます

public int bitCount(int x) {
    if (x == 0) return 0;
    return x % 2 + bitCount(x/2);
}

またはInteger.bitCount(toppings)検索

最小要素
2の修理演算を用いて、以下のように編成する.

int firstTopping = (toppings & -toppings);

またはInteger.numberOfTrailingZeros(toppings)

最小要素

をクリア

toppings &= (toppings - 1);

すべての部分集合

を巡回する.

for (int subset = pizza; subset; subset = ((subset-1) & pizza)) {
    // subset은 pizza의 부분집합
}

Reference

プログラミングコンテストで学習したアルゴリズム問題解決戦略(a.k.a.種のみ)