Cari pemain dengan bilangan sifar paling sedikit selepas mengosongkan rentetan binari (dengan mengalih keluar subrentetan bukan kosong)

Dalam artikel ini, kita akan membincangkan masalah menarik yang berkaitan dengan bidang manipulasi rentetan dan teori permainan: "Kosongkan rentetan binari dengan mengeluarkan subrentetan bukan kosong" , cari pemain dengan baki 0 ​​yang paling sedikit." Soalan ini meneroka konsep menggunakan rentetan binari untuk permainan kompetitif. Matlamat kami adalah untuk mencari pemain dengan baki 0 ​​paling sedikit pada penghujung permainan. Kami akan membincangkan isu ini, menyediakan pelaksanaan kod C++, dan menerangkan konsep melalui contoh.

Memahami penyataan masalah

Dua pemain diberikan rentetan binari dan mereka bermain secara bergilir-gilir. Pada setiap giliran, pemain mengalih keluar subrentetan bukan kosong yang mengandungi sekurang-kurangnya satu "1". Permainan berakhir apabila rentetan menjadi kosong atau tiada "1" dalam rentetan. Pemain yang tidak dapat mengambil tindakan akan kehilangan permainan. Tugasnya adalah untuk mencari pemain dengan bilangan 0 akhir terkecil.

kaedah

Untuk menyelesaikan masalah ini, kita perlu mengira bilangan segmen yang dipisahkan dengan '0' yang mempunyai sekurang-kurangnya satu '1'. Pemain yang memulakan permainan sentiasa memilih serpihan dengan '1' terbanyak. Oleh itu, melainkan bilangan serpihan ialah nombor genap, pemain pertama sentiasa boleh memastikan bahawa mereka mengeluarkan lebih banyak '1' daripada pemain kedua. Dalam kes ini, kedua-dua pemain boleh mengeluarkan bilangan '1' yang sama.

Pelaksanaan C++

Contoh

Contoh

Berikut ialah kod C++ untuk melaksanakan strategi di atas:

#include<bits/stdc++.h>
using namespace std;

int findWinner(string s) {
   int segments = 0;
   for (int i = 0; i < s.size();) {
      if (s[i] == '1') {
         segments++;
         while (i < s.size() && s[i] == '1') {
               i++;
         }
      }
      i++;
   }
   return segments % 2 == 0 ? 2 : 1;
}

int main() {
   string s = "100101";
   int winner = findWinner(s);
   cout << "Player " << winner << " wins";
   return 0;
}

Output

Player 1 wins

Kod ini berulang pada rentetan, mengira bilangan segmen, dan kemudian menyemak sama ada bilangan segmen adalah genap atau ganjil untuk menentukan pemenang.

Kes Ujian

Mari kita pertimbangkan rentetan binari "100101". Serpihan dalam rentetan ini ialah "1", "1" dan "1". Oleh kerana bilangan keping adalah nombor ganjil, pemain pertama akan memenangi permainan kerana mereka dapat mengeluarkan lebih banyak '1' daripada pemain kedua.

KESIMPULAN

Dalam artikel ini, kami mengkaji masalah mencari pemain dengan sekurang-kurangnya 0s selepas mengosongkan rentetan binari dengan mengalih keluar subrentetan bukan kosong. Masalah ini membentangkan persimpangan yang menarik antara manipulasi rentetan dan teori permainan. Kami meneroka masalah, menggariskan pendekatan untuk menyelesaikannya, menyediakan pelaksanaan kod C++ dan menghuraikan konsep menggunakan contoh.

Atas ialah kandungan terperinci Cari pemain dengan bilangan sifar paling sedikit selepas mengosongkan rentetan binari (dengan mengalih keluar subrentetan bukan kosong). Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!