B - Sequential Nim (CodeForces - 1382B)
題目鏈接
演算法
博弈
時間復雜度O(N)
1.這道題乍一看以為用Nim博弈直接套用就可以了，結果通過題意發現并不是，題目中要求取石子時只能從下標最小的那一堆開始取，也就是說一堆一堆的取，不能跳著取，
2.分析完題意，我們知道最后取完最后一堆的人必勝，那么怎么分析誰最后會贏呢？
如果只有一堆的話，很容易得出第一個人獲勝，關鍵在于如何分析多堆的情況，
為了方便，我們將每一堆中首先取的人稱為先手，然后取的人是后手，下面我們來進行分類討論：
- 如果某一堆只有1個石子，那么先手只能取這一個石子，如果還有剩余的石堆，那么此先手在下一堆中將成為后手(因為兩個人是輪流取的)；如果沒有剩余的石堆，那么此先手獲勝，
- 如果某一堆中有若干個石子(超過1個)，為了最優，先手有兩種取法，要么全取完，要么取走大部分，只剩余一個，前者會使得先手在下一堆中充當后手，后者會使先手在下一堆中充當先手，當然如果沒有下一堆了，取完即可，這時先手贏，否則還要繼續判斷，
分類討論后發現，一共就上面兩大類情況，那么該怎么做呢？這里是題目的一個難點，
對于先手，當該石堆中石子個數超過1并且還有其他的石堆時，他可以根據實際情況選擇在下一堆中成為先手還是后手，但是當石堆中石子個數為1時他別無選擇，只能是在下一堆中成為后手，所以說石子個數為1的石堆為轉折點，
既然當某石堆石子個數大于1時先手可以任意選擇在下一堆中他的身份，所以如果還有其他石堆，那么該先手必勝，(因為他掌握著主動權，所以他完全可以根據剩余的石堆數來選擇接下來的身份，至于怎么選我們不用考慮)
當石子個數等于1時，先手變成后手，后手變成先手，
3.總結一下，我們只需從頭判斷每一堆的石子的個數，若個數為1，則繼續回圈，直到回圈完，如果回圈完了，說明都為1，這時只需判斷石堆個數即可；若出現個數不為1的，則先手必勝，跳出回圈即可，
C++代碼
#include<iostream>
using namespace std;
const int N = 1e5 + 10;
int t, n;
int a[N];
int main()
{
cin >> t;
while(t--)
{
cin >> n;
for(int i = 0; i < n; i++)
cin >> a[i];
int first = 1, second = 0;
bool flag = false;
for(int i = 0; i < n; i++)
{
if(a[i] == 1)
{
if(first)
{
first = 0;
second = 1;
}
else
{
first = 1;
second = 0;
}
}
else
{
if(first)
puts("First");
else
puts("Second");
flag = true;
break;
}
}
if(!flag)
{
if(n % 2 == 1) puts("First");
else puts("Second");
}
}
}
思路來源（注意這里“先手”的定義與思路來源連接里的“先手"定義不同）
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/140213.html
標籤：其他