[伯俊]1723番集合/Java,Python

17964 ワード
python Java 白駿 11723号 テキストリンク

Baekjoon Online Judge


algorithm practice


-問題を逐次解く


33.動的計画法3


ビットマスクを学習し、ダイナミックプランニング法に適用します.次に,線形ではなく円形からなる問題について議論する.
Java/Python

1.集合


11723号
ビットマスクDPについて議論する前に、ビットマスクから開始する.

この問題は、空の共通セットSが与えられた場合に、以下の演算が実行されるという問題である.

intデータ型が宣言された場合、4バイト(4*8ビット)をメモリに割り当て、合計32種類の場合、真偽を判断できます.この問題に対しては,20個の数字の有無,intデータ型変数,32個を格納すれば十分である.
bit set=0,000,000,000,000,000,000,000(2)メモリに割り当てます.
下図のように0から31個の数の集合を表すことができます.
2^0ビット>0のtrue、false
2^1ビット▶1のtrue,false
2^2ビット▶2のtrue,false
...
2^30ビット▶30のtrue,false
2^31ビット▶31のtrue,false
ビット演算の利用
  • Java 
    • import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();

		int N = Integer.parseInt(br.readLine());
		int bit_set = 0;
		while (N-- > 0) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			String op = st.nextToken();
			int num;

			// 연산
			switch (op) {
				case "add":
					num = Integer.parseInt(st.nextToken());
					bit_set |= (1 << (num - 1));
					break;
				case "remove":
					num = Integer.parseInt(st.nextToken());
					bit_set = bit_set & ~(1 << (num - 1));
					break;
				case "check":
					num = Integer.parseInt(st.nextToken());
					sb.append((bit_set & (1 << (num - 1))) != 0 ? "1\n" : "0\n");
					break;
				case "toggle":
					num = Integer.parseInt(st.nextToken());
					bit_set ^= (1 << (num - 1));
					break;
				case "all":
					bit_set |= (~0);
					break;
				case "empty":
					bit_set &= 0;
					break;
			}
		}
		bw.write(sb.toString());

		bw.flush();
		bw.close();
		br.close();
	}
}
  • Python 
    • import sys
input=sys.stdin.readline
bit_set = 0
for _ in range(int(input())):
    op = input().split()
    if op[0]=='add' : bit_set |= 1 << int(op[1])
    if op[0]=='remove' : bit_set &= ~(1 << int(op[1]))
    if op[0]=='check' : print(1 if bit_set & (1 << int(op[1])) else 0)
    if op[0]=='toggle' : bit_set ^= (1 << int(op[1]))
    if op[0]=='all' : bit_set = (1<<21)-1
    if op[0]=='empty' : bit_set = 0
    Git KernelBuild
    7.01 AI SCHOOL CSS(2)