Codeforces1082(div2)

A. Parkour Design

考点：数学

思路：

设三种动作分别用了：

• a次：(+2,+1)
• b次：(+3,0)
• c次：(+4,-1)

那么从(0,0)到(x,y)就满足：x=2a+3b+4c，y=a-c。(并且a,b,c都必须是非负整数)

推条件

当y=a-c的时候

条件1：x-2y

x-2y=(2a+3b+4c)-2(a-c)=3b+6c=3(b+2c)

所以必须满足：

条件2：x+4y

x+4y=(2a+3b+4c)+4(a-c)=6a+3b=3(2a+b)

所以必须满足：

最终结论

到达(x,y)时当且仅当：时为YES，否则为NO。

注：x-2y和x+4y的由来都是为了凑3的倍数，因为b次操作是(+3,0)。

import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
x,y=map(int,input().split())
b=x+4*y
if b>=0 and b%3==0 and x>=2*y:
print("YES")
else:
print("NO")

B. ABAB Construction

考点：贪心，模拟

思路：

如果n是偶数：

• a必须满足：(s1,s2),(s3,s4)…每一对都为一奇一偶字母
• 也就是说每对只能是"ab"或"ba"

如果n是奇数：

• 第一个字符一定是'a'。(因为原串两端都是'a')
• 然后(s2,s3),(s4,s5),…每一对都必须不同。（只能"ab"或"ba"）

对于?，只要能填成满足条件即可，所以只有在一对里两个都确定且相同（如aa或bb）时才不行。

import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
n=int(input())
a=input().strip()
ok=True
if n%2==1:
if a[0] not in('a','?'):
ok=False
kt=1
else:
kt=0

for i in range(kt,n-1,2):
if a[i]!='?' and a[i+1]!='?' and a[i]==a[i+1]:
ok=False
break
if ok:
print("YES")
else:
print("NO")

C1. Lost Civilization (Easy Version)

考点：贪心，栈

思路：

维护一个栈，对于遇到的每个较早元素，我们将消除栈顶所有值为的元素，随后将压入栈顶。

复杂度：O(n)

import sys
input=sys.stdin.readline
t=int(input())
for _ in range(t):
n=int(input())
a=list(map(int,input().split()))
ans=0
s=[]
for v in a:
while s and s[-1]>=v:
s.pop()
if s and s[-1]==v-1:
s.append(v)
else:
ans+=1
s=[v]
print(ans)