[Gym101653Q]Number Game

題目大意：

\(T\) 組數據。給定一個 \(1\sim n\) 的全排列，Alice 和 Bob 輪流取數。一個數能被取走，當且僅當這個數緊鄰兩側沒有比它大的數。取走 \(1\) 的人獲勝。兩人都按最優策略進行游戲。

\(T\le 100; n\le 100\)

思路：

當 \(1\) 緊鄰兩側僅剩一個數時，Alice 和 Bob 肯定都不愿主動取走這個數（“山峰”），因為這樣一來，就能讓對方把 \(1\) 取走，然后自己就輸了。

有題意得 Alice 和 Bob 都聰明絕頂，為了避免陷入這樣的絕境，他們肯定會想方設法先取走別的數。直到不得不面對這一絕境時，輸家取走“山峰”，而贏家則將 \(1\) 取走。

此時，剩下的數只有受“山峰”支配的數，在原數列中具體體現為從山峰出發，往 \(1\) 反方向延伸的一段“下坡”。設“坡長”為游戲結束后剩余數的個數，亦即排除山峰以后“下坡”的長度，設其為 \(\ell\)，那么游戲進行的總步數為 \(n - \ell\)。顯然，若 \((n - \ell) \mod 2 = 1\) 則 Alice 勝，否則 Bob 勝。

當 \(1\) 在兩端時，“下坡”是唯一的（“坡長”可以為 \(0\)）；但是當它在中間時，則會在兩側各形成一段“下坡”。不妨設 \(1\) 的位置為 \(p\)，左邊的“坡長”為 \(\ell_l\)，右邊的為 \(\ell_r\)，我們可進行如下分類討論（為使表達簡練，此處匹配到第一個條件則停止匹配后續條件）：

1. \(p = 1\)：最后留下“右坡”共 \(\ell_r\) 個數，游戲總步數為 \(n - \ell_r\)；
2. \(p = n\)：最后留下“左坡”共 \(\ell_l\) 個數，游戲總步數為 \(n - \ell_l\)；
3. \(\ell_l = 0 \vee \ell_r = 0\)：由于 \(1\) 受至少一側的“上坡”所支配，若兩人都按最優策略進行游戲，\(1\) 一定會在“上坡”取完后，成為整個游戲最后被取走的數，故總步數為 \(n\)；
4. \(\ell_l\mod 2\ne\ell_r\mod 2\)：作為先手，Alice 可以任選一邊開始游戲，使另一邊剩下，總會有一種辦法使得總步數為奇數，故贏家一定是 Alice；
5. \(\ell_l\mod 2 = \ell_r\mod 2\)：無論 Alice 從哪邊開始游戲，總步數的奇偶性都相同，結局都是一樣的，此時只能隨便選一邊，然后聽天由命。

最后根據游戲總步數的奇偶性判斷勝負即可。

時間復雜度 \(\mathcal O(n)\)。

源代碼：

#include<cstdio>
#include<cctype>
#include<algorithm>
inline int getint() {
	char ch;
	while(!isdigit(ch=getchar()));
	int x=ch^'0';
	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');
	return x;
}
constexpr int N=101;
int a[N];
int main() {
	for(int T=getint();T;T--) {
		const int n=getint();
		for(int i=1;i<=n;i++) a[i]=getint();
		const int p=std::find(&a[1],&a[n]+1,1)-a;
		int len1=0,len2=0;
		for(int i=p-2;i>=1&&a[i]<a[i+1];i--) len1++;
		for(int i=p+2;i<=n&&a[i-1]>a[i];i++) len2++;
		int take=0;
		if(p==1) {
			take=n-len2;
		} else if(p==n) {
			take=n-len1;
		} else if(len1==0||len2==0) {
			take=n;
		} else if(len1%2!=len2%2) {
			take=n-((n-len1)%2?len1:len2);
		} else {
			take=n-len1;
		}
		puts(take%2?"Alice":"Bob");
	}
}