谁能解释一下这个暴力破解使用位掩码

Question

education Codeforces Round 105(评分为div . 2)问题A。Um_nik用这种蛮力方法解决了这个问题，我不完全理解它。我知道什么是位掩码，但我对if ((mask>>)感到困惑。(int)(s[i] - 'A')) &1)和ok &= bal>= 0。问题的链接是:https://codeforces.com/contest/1494/problem/A

cin >> s;
int n = (int)s.length();
//cout << s << endl;
for (int mask = 0; mask < (1 << 3); mask++) {
int bal = 0;
bool ok = true;
for (int i = 0; i < n; i++) {
if ((mask >> (int)(s[i] - 'A')) & 1)
bal++;
else
bal--;
ok &= bal >= 0;
}
ok &= bal == 0;
if (ok) {
printf("YESn");
return;
}
}
printf("NOn");

Answer 1

我知道问题了!

m的取值范围是0b000 ~ 0b111，第i位表示如果'A' + i是符号((如果不是符号))。

例如，m = 0b010表示{'A': ')', 'B': '(', 'C': ')'}。我需要用m[CHAR]来表示(m >> (CHAR - 'A') & 1) ? '(' : ')'，所以m['B'] == '('。

我们知道s[i]是字符串s中的第i个字符，因此m >> (s[i] - 'A') & 1具有m[s[i]]的含义，并且如果第i个字符表示符号(，则会得到。

例如，s = "ABBC",m = 0b010和i = 2，因此s[i] == 'B'，您将知道m >> ('B' - 'A') & 1 == m['B'] == '('

最后，我们需要设置一开始为0的状态，如果满足(，则加1，如果满足)，则减1。如果状态一直是>= 0，最后是== 0，那么它就有了正确的答案，这就是为什么我们需要打印"YES"并返回。

Answer 2

算法背后的思想是尝试字母A, B和c的所有可能性。这意味着A可以是'('或')'，B和c也是如此。

因此我们有8种可能，

A B C   in binary
( ( (   0 0 0
( ( )   0 0 1
( ) (   0 1 0
( ) )   0 1 1
) ( (   1 0 0 
) ( )   1 0 1
) ) (   1 1 0
) ) )   1 1 1

实际上，作者说'('是0，')'是1，或者相反，在二进制中涵盖了8种可能性，即从000到111。为什么是">或相反的"?因为正如你在上面看到的，如果一个蒙版为001提供a:(， B:(和C:)，另一个蒙版110将呈现a:)， B:)和C:(.

因此掩码从0到8-1 ((1 << 3)-1)，或者，以二进制表示，从000到111。

例如，000表示A, B和C都是开始(或结束)括号，而110在这种情况下将是))(，用于ABC(或(())。

对于给定的掩码(外循环)，内循环for (int i = 0; i < n; i++)遍历所有字符，并应用当前掩码。(mask >> (int)(s[i] - 'A')) & 1只是告诉，对于当前掩码，i处的字母是(还是)。

也就是说，(int)(s[i] - 'A')给出A的0, B的1, C的2。因此，A得到掩码第0位(最右边的位)的值，B得到2^和1, C得到3^rd(最左边的位)的值。

C  B  A
mask b2 b1 b0

变量bal可能是balance。每一次都是"开"。(()字母满足，bal递增，)递减。

内循环中的ok &= bal >= 0确保在任何时候闭括号都不会比开括号多。这样可以防止ABBA被限定。

ok &= bal == 0，在内循环之后，确保我们有相同数量的左括号和右括号。

同样，为了避免混淆，掩码尝试了所有的可能性，因此ABAB不符合)()(的条件，例如，掩码001，但是掩码到达010后，()()符合条件。

注意:掩码可以从001(1)开始，以110(6)结束，因为000(0)和111(7)的值永远不会工作(将所有A, B和C赋值给同一个括号不能工作)。