題目描述

Cly很喜歡博弈，這天他和他的分身DD_BOND玩起了一個博弈游戲（本體當然是先手了），游戲規則如下，請你判斷誰能贏得游戲。
最初有一個數字n，每次操作可以選擇一個數字x滿足0<x<n，且n%x==0，接著用n-x替換原本數字，誰不能操作誰就輸了。
對于每次詢問如果先手能贏，你需要告訴cly第一步能選擇的最大x是什么，為了方便起見，你最后只需要告訴他所有詢問x的和就行了。

輸入

第一行查詢數字q (1<=q<=1e5)
接下來q行每行輸入一個數字n (1<=n<=1e5)

輸出

對于每次查詢如果先手勝，輸出clynb，否則輸出DD_BONDNB
最后輸出一個和sum。

樣例輸入

【樣例1輸入】
1
1
【樣例2輸入】
1
2

樣例輸出

【樣例1輸出】
DD_BONDNB
0
【樣例2輸出】
clynb
1

一道博弈題，可以發現如果n為偶數的話，就一定可以出1使其變成奇數，而n為奇數的話，找到的只可能是奇數（奇數不可能整除偶數），相減后就會變成偶數。
總結一下，就是偶數可以變成奇數，奇數只能變成偶數。操作完之后為1的話對方就輸了，所以誰能最后將偶數變為奇數（2變為1），就是贏家。因此可以推算出先手情況下n為偶數必贏，只要找到一個奇數因子即可，題目中要求能選擇的最大值，那就找最大值即可，（這里有個坑點，找最大奇數因子如果從1道n循環會超時，不斷將n除以2到無法整除即可）

代碼：

#include <bits/stdc++.h> using namespace std; const int N = 1e5 + 10; int a[N];int main() {int q;int sum = 0;scanf("%d", &q);for (int i = 1; i <= q; i++) {scanf("%d", &a[i]);}for (int i = 1; i <= q; i++) {if (a[i] % 2 == 0) {printf("clynb\n");int k;while (a[i] % 2 == 0) {k = a[i] / 2;a[i] = a[i] / 2;}sum += k;} else {printf("DD_BONDNB\n");}}printf("%d", sum);return 0; }

總結

以上是生活随笔為你收集整理的问题 B: Cly的博弈的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。