A

签到

n = int(input())
print('A' if pow(2,n) < n ** 3 else 'B')

B

滑窗模拟

s = input().strip()
res = 0
n = len(s)
for i in range(n-4):
    t0,t1,t2,t3,t4 = s[i:i+5]
    res += int(t0==t2==t4 and t1 == t3 and t0!=t1)
print(res)

C

分情况讨论，只有三种情况满足：

• 两点位置一样
• / 对角线

0 B
A 0

• \ 对角线

A 0
0 B

这里要注意B不能是终点或者终点的前一列

n = int(input())
x1,y1 = map(int,input().strip().split())
x2,y2 = map(int,input().strip().split())

if (x1,y1) == (x2,y2):
    print('YES')
    exit()

if y1 > y2:
    x1,y1,x2,y2 = x2,y2,x1,y1

if y1 + 1 == y2:
    if x1 == x2 + 1:
        print('YES')
        exit()
    
    if x1 + 1 == x2 and y2 != n and y2 != n - 1:
        print('YES')
        exit()
print('NO')

D

贪心 + 堆 头越大越好，将a[1:]的值入最大堆，即除了开头，然后弹出最大加到头部，当值相等时，优先弹出下标大的值。 即堆中存放(nums[i],i)的最大堆 最后把堆中剩下的值按下标排序输出就好了。

for _ in range(int(input())):
    n,k = map(int,input().strip().split())
    a = list(map(int,input().strip().split()))
    from heapq import *
    heap = []
    for i in range(1,n):
        heappush(heap,(-a[i],-i))
    
    t = a[0]
    while k:
        t -= heappop(heap)[0]
        k -= 1
    
    heap.sort(key = lambda x:-x[1])
    res = [t]
    for num,_ in heap:
        res.append(-num)
    print(*res)

E

计数 + 组合数学

计数

cnt = Counter(a)

组合数学

分情况讨论：

mex = 0

其它值只能选相等值，且不等于0，这样max - min = 0 <= mex，由于选的子序列要非空，所以： C(t,1) + C(t,2) +...+C(t,t) = 2^n - C(t,0)

for v,t in cnt.items():
    if v:
        res += two[t]-1
        res %= mod

mex > 0

子序列的最大值不能超过mex - 1，且子序列中[0,mex-1]都必须存在一个值：

last = 0
t = 1
while cnt[last]:
    t *= two[cnt[last]]-1
    t %= mod
    res += t
    res %= mod
    last += 1

python3

n = int(input())
a = list(map(int,input().strip().split()))

res = 0
mod = int(1e9+7)

two = [1]
p = 1
for _ in range(n):
    p *= 2
    p %= mod
    two.append(p)

from collections import Counter
cnt = Counter(a)
for v,t in cnt.items():
    if v:
        res += two[t]-1
        res %= mod
        
# mex = 0 要特判
last = 0
t = 1
while cnt[last]:
    t *= two[cnt[last]]-1
    t %= mod
    res += t
    res %= mod
    last += 1

print(res)

F

动态规划

dp[i1][j1][i2][j2] 代表：

• 第i1行，第j1列
• 对应的第i2行，第j2列符合题意的回文数

从中间那一行像上递推，由于i1 + i2 == n + 1，因此可以降维： dp[i1][j1][j2]

python3

n = int(input())
a = [[]]

for _ in range(n):
    a.append(list(map(int, input().strip().split())))

mod = int(1e9 + 7)
n_half = (n + 1) // 2

# 初始化DP数组
dp = [[[0 for _ in range(n + 1)] for _ in range(n_half + 1)] for _ in range(n_half + 1)]



if n&1:
    for j in range(n_half):
        dp[n_half][j][j] += 1
else:
    i1 = n_half
    i2 = (n+1) - n_half
    for j1 in range(n_half):
        for j2 in range(j1,j1+2):
            if a[i1][j1] == a[i2][j2]:
                dp[i1][j1][j2] += 1
        
        

# 动态规划填表
for i1 in range(n_half - 1,0,-1):  # 从中间向上填表
    i2 = (n+1)-i1
    # print(i1,i2)
    for j1 in range(i1):  # 第 i 行有 i 个元素
        for j2 in range(i2):  # j2 的范围是 [j1, j1 + 1]
            if a[i1][j1] != a[i2][j2]:
                continue
            dp[i1][j1][j2] += dp[i1+1][j1][j2]
            dp[i1][j1][j2] += dp[i1+1][j1+1][j2]
            if j2 >= 1:
                dp[i1][j1][j2] += dp[i1+1][j1][j2-1]
                dp[i1][j1][j2] += dp[i1+1][j1+1][j2-1]
            
            dp[i1][j1][j2] %= mod



print(sum(dp[1][0])%mod)

吐槽

一开始写的记忆化搜索，过不了，然后改dp，爆内存，最后dp数组要改成： dp = [[[0 for _ in range(n + 1)] for _ in range(n_half + 1)] for _ in range(n_half + 1)] 才没爆内存。

我觉得dp能做的题，记忆化搜索应该也要能过，我也把dfs转化成栈形式了，还是过不了。