[白俊]18119単語暗記

📌 質問する
俊碩は英語の単語を暗記しなければならない.辞書にはN語ある.すべての単語は小文字です.単語のすべてのアルファベットを知っていると、その単語を完全に知っていると言います.
次のクエリが表示されます.
1 x:アルファベットxを忘れます.
2 x:アルファベットxを覚えます.
最初はすべてのアルファベットを覚えた状態で、母音は完璧に暗記されているので、絶対に忘れません.
各クエリーは、完全に知っている単語の数を出力します.
✔入力
1行目は整数N(1≦N≦10^4)とM(1≦M≦5)である.×10^4).
次のN行に文字列があります.文字列の長さは10^3を超えません.
次のM行の整数oと文字xの各行.oは1,2の1つで、xは小文字です.
oが1であればxを忘れることを意味し、oは2を覚えることを意味する.oが1の場合はxを覚え、oが2の場合はxを忘れることを保証します.
✔方法
問題ばかり見ていると、あまり難しくないような気がします.ただし、MクエリーごとにN個の整数をチェックする場合は、5×10^4*10^4の5億以上の演算が必要です...制限時間は4秒です.一般的な探求は問題を解くことができない.
「ビットマスク」を使えば、問題を解く可能性はずっと高い.
理解すべき演算は以下の通りです.

int alph = (1 << 27) - 1 

1に対して27の左シフト演算を実行すると、27ビット目に1を生成し、残りのビットは0のビットである.
このとき、1を削除すると、いずれも1の26ビット数が生成される.

cur |= 1 << ('c' -'a');

現在の値をcurと呼ぶ場合、現在の値(「c」-「a」)の値は3であり、1<(「c」-「a」)の値は1000である.
この値をcurおよび|(または)演算すると、現在の値のcの位置が1に変更されます.
問題では、入力したアルファベット値が含まれていることを意味します.

alph &= ~(1 << (target-'a')); 

のターゲットアルファベット値を~(not)演算すると、ターゲットアルファベットのビット値は0に変更され、残りは1に変更されます.
この値とalph値を&(and)に演算すると、対応するターゲットアルファベット値の桁数が0に変更されます.
問題では、値を忘れたことを示します.

✔コード

import java.util.Scanner;

//단어 암기
public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);

		//문자열의 수
		int n = sc.nextInt();
		//쿼리 의 수
		int m = sc.nextInt();
		
		//1로 초기화된 26자리 비트
		int alph = (1 << 27) - 1;
		
		//단어를 담는 배열
		int[] words = new int[n];
		
		for(int i = 0; i < n; i++) {
			String word = sc.next();
			// 각단어의 알파벳 위치만 1로 변경
			for(char c : word.toCharArray())
				words[i] |= 1 << (c -'a');
		}
		
		for(int i = 0; i < m; i++) {
			int o = sc.nextInt();
			char target = sc.next().charAt(0);
			
			//잊는다
			if(o == 1) {
				//target위치의 값만 0으로 바꾸고 & 연산자를 통해 그 부분의 alph비트 값을 0으로 변경
				alph &= ~(1 << (target-'a')); 
			}
			//기억한다
			else {
				alph |= (1 << (target-'a')); 
			}
			
			int count = 0;
			for(int j = 0; j < words.length; j++) {
				//alph와 word연산한 값이 word보다 같거나 크면 모든 알바펫을 알고 있는 것으로 단어를 아는 것.
				if((alph & words[j]) >= words[j]) {
					count++;
				}
			}
			System.out.println(count);
			
		}
	}
}

🖋 振り返る
ビット演算をよく知っていれば簡単に解けるが、慣れていないので、時間をかけてビット演算を復習することができる.
ビット演算を実行せずに上記の論理と同じようにコードを記述することもでき、より複雑になるため、ビット演算を用いてコードを記述することができる.
ソース:https://www.acmicpc.net/problem/18119