A. Eating Game
考点：思维
思路：
在a中，元素相同的个数最多的那个就是答案。
复杂度：O(n)
import sys
from collections import Counter
input=sys.stdin.readline
t=int(input())
for _ in range(t):
n=int(input())
a=list(map(int,input().split()))
m=max(a)
if m==0:
print(0)
else:
c=Counter(a)
print(c[m])
B. Deletion Sort
考点：贪心，思维
思路：
只要在a中里面有
的部分，就直接输出1，因为你始终有一对是降序的，可以先把其余升序全都删完，最后再删这一对的其中一个即可得到最小长度。
复杂度：O(n)
import sys
from collections import Counter
input=sys.stdin.readline
t=int(input())
for _ in range(t):
n=int(input())
a=list(map(int,input().split()))
ok=False
for i in range(n-1):
if a[i]>a[i+1]:
ok=True
if ok:
print(1)
else:
print(n)
C. Specialty String
考点：栈，贪心
思路：
用栈模拟，如果栈首等于当前字母就直接出栈。否则将当前字母入栈。最后如果栈的长度等于0的话就是YES，否则输出NO。
复杂度：O(n)
import sys
from collections import Counter
input=sys.stdin.readline
t=int(input())
for _ in range(t):
n=int(input())
a=input().strip()
st=[]
for v in a:
if st and st[-1]==v:
st.pop()
else:
st.append(v)
print("YES" if len(st)==0 else "NO")
D. Portal
考点：贪心，排序
思路：
题目意思就是有两个传送门l,r：
- 把l左边的元素搬到r的右边元素
- 把r右边的元素搬到l的左边位置
要求字典序最小排列。
与s的第一个较大元素的位置，因此用while找到第一个s[k]>即可。复杂度：O(n)
import sys
from collections import Counter
input=sys.stdin.readline
t=int(input())
for _ in range(t):
n,x,y=map(int,input().split())
p=list(map(int,input().split()))
m=p[x:y]
s=p[:x]+p[y:]
b=min(m)
wz=m.index(b)
b=m[wz:]+m[:wz]
b0=b[0]
k=0
while k<len(s) and s[k]<b0:
k+=1
ans=s[:k]+b+s[k:]
print(*ans)
E. Divisive Battle
考点：博弈，质数筛
思路：
由题目可知能够操作的只有合数，1和质数不能动。
（1）如果a本来就是非递减的，Bob赢
（2）如果存在b[i]==-1，Alice赢。理由：她第一步就能把这个数拆成一个更小的质数放在后面。
（3）否则（所有数都是质数/质数幂/1），此时拆分永远不会改变每个块的质因子类型，只会把同一个pd复制成更多个。
- 若b非递减，最终一定会走到非递减状态，Bob赢。
- 若b不是非递减，永远不可能变成非递减，最后卡死时仍下降，Alice赢。
所以最终结论就是：
- a已排序，就是Bob赢。
- 否则，有-1就是Alice赢。
- 否则，看b是否排序：是Bob，否则Alice
复杂度：O(
)
import sys
from collections import Counter
input=sys.stdin.readline
#质数筛模板
maxa=10**6
spf=list(range(maxa+1))
def build(limit):
spf=list(range(limit+1))
for i in range(2,int(limit**0.5)+1):
if spf[i]==i:
for j in range(i*i,limit+1,i):
if spf[j]==j:
spf[j]=i
return spf
spf=build(maxa)
#判断质数幂
def pd(x):
if x==1:
return 1
p=spf[x]
while x%p==0:
x//=p
return p if x==1 else -1
#排序
def sortd(a):
return all(a[i]<=a[i+1] for i in range(len(a)-1))
t=int(input())
for _ in range(t):
n=int(input())
a=list(map(int,input().split()))
#如果他是升序的，直接是Bob胜
if sortd(a):
print("Bob")
continue
b=[pd(x) for x in a]
if -1 in b:
print("Alice")
else:
print("Bob" if sortd(b) else "Alice")
