Овоонуудын XOR ашиглан Nim тоглоомын ялагчийг тодорхойлж, ялах нүүдлийг олдог арга.

IntermediateХугацаа: O(n)Санах ой: O(1)

Эхлээд жижиг бодлого

Хоёр овоо: 5 ба 3 чулуу. x = 5 ^ 3 = 6 тэг биш тул эхэлж нүүсэн нь ялна.

Ялах нүүдэл: 5 ^ 6 = 3 < 5 тул эхний овоог 3 болгоно, өөрөөр хэлбэл 2 чулуу авна. Одоо 3 ^ 3 = 0. Код First 1 2 хэвлэнэ.

Энгийн аргаас санаа руу

Энгийн арга: бүх байрлалыг ялах, ялагдах гэж тэмдэглэнэ (DP). Овооны тоо олон, чулуу ихтэй бол байрлалын тоо асар их.

Гол санаа: бүх овооны XOR. x = 0 бол ялагдах байрлал, x ≠ 0 бол ялах байрлал. Учир нь x = 0 байрлалаас ямар ч нүүдэл x-ийг тэг биш болгоно. x ≠ 0 байрлалаас үргэлж x-ийг тэг болгох нүүдэл олдоно. Тиймээс ялагч нь өрсөлдөгчөө үргэлж x = 0 байрлалд үлдээж чадна.

Нэр томьёо ба тэмдэглэгээ

XOR (^)
Хоёртын системд бичсэн тоонуудын багана бүрт 1-ийн тоо сондгой бол 1, тэгш бол 0. 3 ^ 5 = 6.
x
Бүх овооны XOR: a[0] ^ a[1] ^ … ^ a[n - 1].
ялагдах байрлал
Нүүх ээлжтэй тоглогч хэрхэн ч тоглосон ялагдах байрлал. Nim-д яг x = 0 үед.
a[i] ^ x
i-р овоог хэдэн чулуутай болговол x тэг болох вэ. Энэ нь a[i]-гаас бага байх ёстой.
овоо8421a[0] = 3
0
0
1
1
a[1] = 4
0
1
0
0
a[2] = 5
0
1
0
1
x = 0
0
0
0
0
x = 0

3 овоо чулуу: 3, 4, 5. Хоёр хүн ээлжлэн нэг овооноос дурын тооны чулуу авна. Сүүлийн чулууг авсан нь ялна. Эхэлж нүүсэн нь ялах уу? Бүх овоог XOR хийгээд мэднэ.

Алхам 1 / 6
Хурд
  • Одоогийн овоо
  • Шинэ утга
  • x-ийн хамгийн ахлах 1 бит
  • Хариу
  • 0 бит, эсвэл тохирохгүй овоо
Слайд 1 / 6

Чулууны тоглоом

Хэд хэдэн овоо чулуу байна. Хоёр тоглогч ээлжээрээ нэг овооноос дурын тооны чулуу авна. Сүүлийн чулууг авсан нь ялна. Хоёулаа зөв тоглоход хэн ялахыг ганц тоо хэлж өгнө.

nim-game.cpp
#include <bits/stdc++.h>
using namespace std;
int n, a[20], x;
int main() {
cin >> n;
for (int i = 0; i < n; i++) cin >> a[i];
for (int i = 0; i < n; i++) {
x ^= a[i];
}
if (x == 0) {
cout << "Second\n";
return 0;
}
for (int i = 0; i < n; i++) {
if ((a[i] ^ x) < a[i]) {
cout << "First " << i + 1 << ' ' << a[i] - (a[i] ^ x) << '\n';
return 0;
}
}
return 0;
}

Юунд хэрэгтэй вэ?

Хоёр тоглогч ээлжилж нүүдэг тоглоомын бодлогод хэн ялахыг тодорхойлох. Олимпиадын тоглоомын онолын хамгийн гол суурь.

Яаж ажилладаг вэ?

1. Бүх овооны чулууны тоог XOR хийнэ: x = a[0] ^ a[1] ^ … ^ a[n − 1]. 2. x = 0 бол эхэлж нүүсэн нь ялагдана (Second). Ямар ч нүүдэл x-ийг тэг биш болгох бөгөөд өрсөлдөгч нь буцааж тэг болгоно. 3. x ≠ 0 бол a[i] ^ x < a[i] болох овоо бий. Түүнийг a[i] ^ x болгож, a[i] − (a[i] ^ x) чулуу авна. Оролт: эхний мөрөнд n, дараагийн мөрөнд n тоо. Гаралт: "Second" эсвэл "First i k" (i-р овооноос k чулуу ав).

Яагаад зөв, хэр хурдан бэ?

x = 0 үед нэг овоог өөрчлөхөд түүний ядаж нэг бит солигдоно. Тэр баганын 1-ийн тоо сондгой болж, x тэг биш болно.

x ≠ 0 үед x-ийн хамгийн ахлах 1 битийг ав. Тэр баганад 1-тэй овоо заавал бий. Түүнийг a[i] ^ x болговол тэр бит 1-ээс 0 болох тул тоо багасна. Өөрөөр хэлбэл чулуу авах зөв нүүдэл. Хугацаа O(n): n = 100 000 овоо байсан ч нэг loop.

Түгээмэл алдаа

  • XOR-ын оронд нийлбэр ашиглах. 1, 2, 3 овооны нийлбэр 6 боловч XOR нь 0 тул эхэлсэн тоглогч ялагдана.
  • a[i] ^ x < a[i] нөхцөлд хаалт мартах. C++-д < нь ^-ээс түрүүлж бодогддог тул (a[i] ^ x) < a[i] гэж бич.
  • Дүрэм өөр тоглоомд Nim-ийн хариуг шууд хэрэглэх. Жишээ нь "сүүлийн чулууг авсан нь ялагдана" бол хариу өөр.
  • Авах чулууны тоог a[i] ^ x гэж хэвлэх. Авах тоо нь a[i] - (a[i] ^ x).

Хязгаарын тохиолдол

  • Ганц овоо: x нь тэр овоо өөрөө. Бүгдийг нь аваад ялна. 7 бол First 1 7.
  • Хоёр ижил овоо, 2 2: x = 0 тул Second. Хоёр дахь тоглогч эхнийхийн нүүдлийг нөгөө овоон дээр давтана.
  • Хэд хэдэн ялах нүүдэл байж болно. Код эхний тохирох овоог л хэвлэнэ.

Өөрийгөө шалга

  1. 1, 2, 3 овооноос эхэлсэн тоглогч ялах уу?

    Хариу харах

    Үгүй. 1 ^ 2 ^ 3 = 0 тул Second.

  2. 3 ^ 4 ^ 5 хэд вэ?

    Хариу харах

    2.

  3. 2, 5, 6 овоонд ялах нүүдэл юу вэ?

    Хариу харах

    x = 1. 5 ^ 1 = 4 < 5 тул 2-р овооноос 1 чулуу авна: First 2 1.

Гурван дадлага

Hint-ээ нээхээс өмнө өөрөө оролдоорой.

  1. 1.1, 4, 6 овооны x-ийг ол, код ямар нүүдэл хэвлэхийг тодорхойл.

    Hint харах

    1-ийг хоёртоор 001, 4-ийг 100, 6-г 110 гэж бич.

    Хариу ба тайлбар

    x = 1 ^ 4 ^ 6 = 3. 1 ^ 3 = 2, 4 ^ 3 = 7 тул эхний хоёр овоо тохирохгүй. 6 ^ 3 = 5 < 6. First 3 1.

  2. 2.Ялах нүүдлийн нийт тоог тоолдог болго.

    Hint харах

    Зөв нүүдэл олдоход шууд гарахын оронд тоолуурыг нэмэгдүүл.

    Хариу ба тайлбар

    return хийхийн оронд cnt++. Овоо бүрт хамгийн ихдээ нэг ялах нүүдэл бий тул хариу нь x-ийн ахлах битэд 1-тэй овооны тоо.

  3. 3.Нэг нүүдэлд хамгийн ихдээ 3 чулуу авч болдог бол хэн ялах вэ?

    Hint харах

    Ганц овоонд: 4-т хуваагддаг чулуутай бол нүүх ээлжтэй нь ялагдана. Олон овоонд овоо бүрийг a[i] % 4 болгож үз.

    Хариу ба тайлбар

    Овоо бүрийн Grundy утга a[i] % 4. Эдгээрийн XOR тэг бол Second, үгүй бол First. Энэ бол Sprague–Grundy онолын хамгийн энгийн жишээ.

Жишээ

Оролт

3
3 4 5

Гаралт

First 1 2