台灣運動娛樂論壇

標題: 博弈思维训练 Div1 B GameGame 异或博弈 [打印本頁]

作者: admin 時間: 2023-11-28 18:21
標題: 博弈思维训练 Div1 B GameGame 异或博弈
给定长度為n的数组，每次Alice和Bob轮番從数组當選擇一個数，终极選擇的数的异或和大的人获胜，请問在最优的前提下流戏的成果若何。

阐發：

异或的思惟在博弈中是比力難的，刚看到這题的時辰感受很難，無法思虑，但他的本色實際上是贪婪。

两人在都但愿本身的成果尽量的大，换句话说，但愿本身二進制上的每位都是1，再换句话说，但愿本身每位拿到的次数尽可能是奇数。咱們發明，存在最高位的時辰，在某種環境下必定可以經由過程抢最高位来分出输赢。

環境1 最高位呈現的次数x是偶数

此時两人都不必要斟酌這一名，由於無论最後怎样分派，要末二者分派都是奇数数目，要末二者都是偶数数目，分数差不會變革，是以两人不會去纠结這類環境，可以直接疏忽，继续斟酌下一個次高位。

環境2 最高位呈現的次数x是奇数

這是决议输赢手的關頭，此時奇数的分派方法是只有两種：

1 x % 4 == 1，此時先手先拿一個，剩下的由於是4的倍数，雙方城市拿到偶数個数的最高位，也就是至關於没拿，先手便可以比背工多拿這個位，以後的位無论怎样拿都是先手成功。

2 x % 4 == 3，此時先手若是先拿的话，最後先手就會拿治療高血壓中藥,到偶数個，地板污漬清潔，至關於没拿，也就是说，谁先拿某一個数包括该最高位的人就會输。先手必定不會碰，是以他必要從剩下不包括该最高位的数中拿，其数目為(n - x)，明显若是n - x是奇数，先手就获胜了，不然背工获胜。

比力妙的博弈思惟～

代码：

v台灣運動彩券首頁，oid solve()
{
cin >> n;
int sum = 0, h = 0;
for(int i = 1; i <= n ; i ++ ) cin >> a[i], sum ^= a[i];
if(sum == 0) {
puts("DRAW");
return ;
}
for(int i = 31; ~i ; i -- ) {
if(sum >> i & 1) { // 计较最高自嗨鍋，位
h = i;
break;
}
}
int res = 0; // 统计最高位数目
for(int i = 1; i <= n ; i ++ )
if(a[i] >> h & 1) res ++ ;
if(res % 4 == 1) puts("WIN");
else {
if((n - res) 關節止痛膏，& 1) puts("WIN");
else puts("LOSE");
}
}

複製代碼

歡迎光臨台灣運動娛樂論壇 (http://bbs.ss6499.com.tw/)