数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化学
生物
数学
英语
经济学
心理学
社会学
时尚研究
法律研究C++ 程序，用于检查异或游戏结果为 0 或不为 0
假设我们有一个包含 N 个元素的数组 A 和另一个二进制字符串 S。考虑两个玩家正在玩游戏。他们被编号为 0 和 1。有一个变量 x，其初始值为 0。游戏有 N 轮。在第 i 轮，S[i] 执行以下其中一项操作：将 x 替换为 x XOR A[i]，否则什么都不做。第 0 号玩家希望在游戏结束时得到 0，而第 1 号玩家希望得到非零值。我们必须检查 x 在最后是否变为 0。
因此，如果输入像 A = [1, 2]; S = "10"，那么输出将为 1，因为第 1 号玩家将 x 更改为 0 XOR 1 = 1，因此无论第 0 号玩家如何选择，它都将始终为 1。
步骤
为了解决这个问题，我们将按照以下步骤操作 -
N := size of A Define an array judge of size: 60. z := 0 fill judge with 0 for initialize n := N - 1, when 0 <= n, update (decrease n by 1), do: x := A[n] loop through the following unconditionally, do: if x is same as 0, then: Come out from the loop y := x I := -1 for initialize i := 0, when i < 60, update (increase i by 1), do: if y mod 2 is same as 1, then: I := i y := y / 2 if judge[I] is same as 0, then: judge[I] := x Come out from the loop x := x XOR judge[I] if S[n] is not equal to '0', then: if x is not equal to 0, then: z := 1 return z
示例
让我们看看以下实现，以获得更好的理解 -
#include <bits/stdc++.h>
using namespace std;
int solve(vector<int> A, string S){
int N = A.size();
int judge[60];
int z = 0;
fill(judge, judge + 60, 0);
for (int n = N - 1; 0 <= n; n--){
int x = A[n];
while (1){
if (x == 0)
break;
int y = x;
int I = -1;
for (int i = 0; i < 60; i++){
if (y % 2 == 1)
I = i;
y /= 2;
}
if (judge[I] == 0){
judge[I] = x;
break;
}
x ^= judge[I];
}
if (S[n] != '0'){
if (x != 0)
z = 1;
}
}
return z;
}
int main(){
vector<int> A = { 1, 2 };
string S = "10";
cout << solve(A, S) << endl;
}输入
{ 1, 2 }, "10"输出
1
更新时间：03-03-2022
126 次浏览
广告