สมมติว่าเรามีอาร์เรย์ A ที่มี N องค์ประกอบ และสตริงไบนารี S อีกตัว พิจารณาผู้เล่น 2 คนเล่นเกม พวกเขาได้หมายเลข 0 และ 1 มีตัวแปร x ค่าเริ่มต้น 0 เกมมี N รอบ ในรอบที่ i คน S[i] ทำหนึ่งในสองอย่าง: แทนที่ x ด้วย x XOR A[i] มิฉะนั้นไม่ทำอะไร คน 0 ต้องการ 0 ท้ายเกม คน 1 ต้องการไม่ใช่ 0 เราต้องตรวจสอบว่า x กลายเป็น 0 ท้ายเกมหรือไม่
เช่น ถ้าค่าที่ป้อนเข้าเป็น A = [1, 2]; S = "10" ผลลัพธ์จะได้ 1 เพราะคน 1 เปลี่ยน x ด้วย 0 XOR 1 = 1 ดังนั้นจะเป็น 1 เสมอ ไม่ว่าคน 0 จะเลือกอะไร
ขั้นตอนการแก้ปัญหา
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนดังนี้:
N := ขนาดของ A กำหนดอาร์เรย์ judge ขนาด: 60. z := 0 เติม judge ด้วย 0 สำหรับ n := N - 1 เมื่อ 0 <= n ลด n ทีละ 1 ทำ: x := A[n] วนลูปโดยไม่มีเงื่อนไข ทำ: ถ้า x เท่ากับ 0 แล้ว: ออกจากลูป y := x I := -1 สำหรับ i := 0 เมื่อ i < 60 เพิ่ม i ทีละ 1 ทำ: ถ้า y mod 2 เท่ากับ 1 แล้ว: I := i y := y / 2 ถ้า judge[I] เท่ากับ 0 แล้ว: judge[I] := x ออกจากลูป x := x XOR judge[I] ถ้า S[n] ไม่เท่ากับ '0' แล้ว: ถ้า x ไม่เท่ากับ 0 แล้ว: z := 1 คืนค่า 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
