真容易颓。
E 构造一个序列\(a_1\)已经确定 使得\((a_i,a_{i-1})=1,a_i>1\) 求整个序列最大值。
容易知道\(a_2\)是与\(a_1\)互质的最小质数 若是2接下填3,2,3,2,3即可.若不是2填 2,3,2,3即可。
J 先后手每次从当前序列两端取走一个数字使得取出的数字严格递增取不出的人输 求谁赢。
明显取数为两端一个递增序列 先比较一下a1,an 若相等则答案固定。
若a1>an 则考虑取a1能否必胜不能则必须取an，这样递归到下一个子问题。总层数O(n).
注意两个最大值在同一端点的情况。
code
#include<cstdio>
#include<iostream>
#include<vector>
#include<cmath>
#include<algorithm>
#include<cstring>
#define rep(a,b,w) for(int w=a;w<=b;++w)
#define add(x,y) (x=(x+(y))>=jt?x+(y)-jt:x+(y));
#define mul(x,y) (x=(x-(y))<0?x-(y)+jt:x-(y));
using namespace std;
#define zz (now << 1)
#define yy (now << 1 | 1)
#define SZ(x) ((int)(x).size())
typedef long long ll;
const int maxn=100010;
int n,L,R;
int a[maxn],op=0;
inline void put()
{
if(op)puts("Alice");
else puts("Bob");
}
inline void solve(int l,int r)
{
op^=1;
if(l>L)
{
if(L==R)put();
else op^=1;put();
exit(0);
}
if(r<R)
{
if(L==R)put();
else op^=1;put();
exit(0);
}
if(a[l]==a[r])
{
if((L-l+1)&1)
{
put();
exit(0);
}
if((r-R+1)&1)
{
put();
exit(0);
}
op^=1;
put();
exit(0);
}
if(a[l]>a[r])
{
if((L-l+1)&1)
{
put();
exit(0);
}
else solve(l,r-1);
}
else
{
if((r-R+1)&1)
{
put();
exit(0);
}
else solve(l+1,r);
}
}
int main()
{
//freopen("1.in","r",stdin);
scanf("%d",&n);
rep(1,n,i)scanf("%d",&a[i]);
L=1;
rep(1,n,i)if(a[i+1]>a[i])L=i+1;
else break;
R=n;
while(a[R-1]>a[R])--R;
solve(1,n);
return 0;
}