题解 | python3 code only

写在前面

讲题录播：bilibili传送门

题都讲解完了，这里仅贴一套可以AC的完整的 python3 代码供学习参考，欢迎交流讨论🌹

注：C题【主席树，大常数$\mathcal{O}(n\log n)\backslash mathcal\{O\}(n\backslash log\; n)$】、D题【背包，$\mathcal{O}(nWk)\backslash mathcal\{O\}(nWk)$】复杂度比较极限，需要注意各种细节，且须使用 pypy3 提交。

一些实用TIP：

• 使用 int/float 代替 eval 会跑得更快！

• 使用 sys.stdin.readline() 代替 input() 会跑得更快！（但不完全一致）

A题

if input()[4:8] == "3022":
    print("HNNU")
else:
    print("CSUST")

B题

n, q = map(int, input().split())
presum = [[0] * 26 for _ in range(n + 1)]
k = 1
for c in input():
    for i in range(26):
        presum[k][i] = presum[k - 1][i]
    presum[k][ord(c) - ord('a')] += 1
    k += 1
for _ in range(q):
    L, R = map(int, input().split())
    res = 0
    t = 0
    for k in range(26):
        tmp = presum[R][k] - presum[L - 1][k]
        if tmp > res:
            res = tmp
            t = k
    print(chr(ord('a') + t))

C题

import sys


NN = int(5e5) * 20
lc = [0] * NN
rc = [0] * NN
h = [0] * NN
cnt = [0] * NN
tot = 0
NIL = 0

n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
mem = list(set(a))
mem.sort()
dc = {}
sav = [1] * (len(mem) + 1)
m = 0
for x in mem:
    m += 1
    dc[x] = m
    sav[m] = sav[m - 1] * 131 % (1 << 24)
for k in range(n):
    a[k] = dc[a[k]]


def newLeaf(hval, count):
    global tot
    tot += 1
    h[tot] = hval
    cnt[tot] = count
    return tot


def newNode(l, r):
    global tot
    tot += 1
    lc[tot] = l
    rc[tot] = r
    h[tot] = (h[l] + h[r]) % (1 << 24)
    cnt[tot] = cnt[l] + cnt[r]
    return tot


def modify(val, root, l, r):
    if l == r:
        return newLeaf((h[root] + sav[val]) % (1 << 24), cnt[root] + 1)
    mid = (l + r) // 2
    if val <= mid:
        return newNode(modify(val, lc[root], l, mid), rc[root])
    else:
        return newNode(lc[root], modify(val, rc[root], mid + 1, r))


root = [NIL] * (n + 1)
for k in range(n):
    root[k + 1] = modify(a[k], root[k], 1, m)

q = int(sys.stdin.readline())
for l1, r1, l2, r2 in map(lambda line: map(int, line.split()), sys.stdin.readlines()):
    l1 -= 1
    l2 -= 1
    len1, len2 = r1 - l1, r2 - l2
    L1 = root[l1]; R1 = root[r1]; L2 = root[l2]; R2 = root[r2]
    l, r = 1, m
    while l < r:
        mid = (l + r) // 2
        if ((h[lc[R1]] - h[lc[L1]]) - (h[lc[R2]] - h[lc[L2]])) % (1 << 24) != 0:
            L1 = lc[L1]; R1 = lc[R1]; L2 = lc[L2]; R2 = lc[R2]
            r = mid
        else:
            len1 -= cnt[lc[R1]] - cnt[lc[L1]]
            len2 -= cnt[lc[R2]] - cnt[lc[L2]]
            L1 = rc[L1]; R1 = rc[R1]; L2 = rc[L2]; R2 = rc[R2]
            l = mid + 1
    dif = (cnt[R1] - cnt[L1]) - (cnt[R2] - cnt[L2])
    if dif == 0:
        print('=')
    elif dif < 0:
        if cnt[R1] - cnt[L1] == len1:
            print('<')
        else:
            print('>')
    else:
        if cnt[R2] - cnt[L2] == len2:
            print('>')
        else:
            print('<')

D题

import sys


dp = [[0] * (1001) for _ in range(501)]
n, W, k = map(int, sys.stdin.readline().split())
k0 = 0
for w, p in map(lambda line: map(int, line.split()), sys.stdin.readlines()):
    k0 += 1
    for j in range(min(k, k0), 0, -1):
        for t in range(W, w - 1, -1):
            dp[j][t] = max(dp[j][t], dp[j][t - w] + p)
        for t in range(W, p - 1, -1):
            dp[j][t] = max(dp[j][t], dp[j - 1][t - p] + w)
    for t in range(W, w - 1, -1):
        dp[0][t] = max(dp[0][t], dp[0][t - w] + p)

ans = 0
for y in dp:
    for x in y:
        ans = max(ans, x)
print(ans)

E题

n, x = map(int, input().split())
vec = [(0, 0)] * n
for k in range(n):
    p, v = map(int, input().split())
    vec[k] = (p, v)
vec.sort()
for p, v in vec:
    if p > x: break
    if p >= v: continue
    x += v - p
print(x)    

F题

T = int(input())
for _ in range(T):
    n, m = map(int, input().split())
    mp = [list(input()) for _ in range(n)]
    for bgm in range(n):
        for row in range(n - 1, 0, -1):
            for col in range(m):
                if mp[row][col] == '.' and mp[row - 1][col] == '*':
                    mp[row][col] = '*'
                    mp[row - 1][col] = '.'
    for row in range(n):
        print(''.join(mp[row]))
    print()

G题

这份是大模数NTT的代码，其中 $\mathtt{\text{2748779069441}}=5\cdot 2^{39}+1\backslash texttt\{2748779069441\}\; =\; 5\; \backslash cdot\; 2^\{39\}\; +\; 1$ ，原根为 $33$ 。

不能使用 $\mathtt{\text{998244353}}\backslash texttt\{998244353\}$ 的原因是：考虑数组全为 $11$ 的情形，此时该模数小于 $22$ 的指数部分（接近 ${10}^{10}\{10\}^\{10\}$），根据欧拉降幂定理，指数部分理应对 $\phi (p)=p-1\backslash varphi(p)\; =\; p\; -\; 1$ 取模而非对 $pp$ 取模，从而导致答案错误。

mod, g = 2748779069441, 3
N = int(2e5) + 1
mx = 1
while mx <= N: mx *= 2
rev = [0] * mx
for k in range(mx):
    rev[k] = rev[k >> 1] >> 1
    if k % 2 == 1:
        rev[k] |= (mx >> 1)


def ntt(a, f):
    global mx, rev, mod, g
    for k in range(mx):
        if k < rev[k]:
            a[k], a[rev[k]] = a[rev[k]], a[k]
    h = 1
    while h < mx:
        wn = pow(g, (mod - 1) // (2 * h), mod)
        if f == -1:
            wn = pow(wn, mod - 2, mod)
        for L in range(0, mx, 2 * h):
            t = 1
            for k in range(L, L + h):
                x, y = a[k], t * a[k + h] % mod
                a[k] = (x + y) % mod
                a[k + h] = (x - y + mod) % mod
                t = t * wn % mod
        h *= 2
    if f == -1:
        invmx = pow(mx, mod - 2, mod)
        for k in range(mx):
            a[k] = a[k] * invmx % mod


n = int(input())
a = list(map(int, input().split()))
ac = [0] * mx
for x in a:
    ac[x] += 1
ntt(ac, +1)
for k in range(mx):
    ac[k] = pow(ac[k], 2, mod)
ntt(ac, -1)
for x in a:
    ac[x + x] -= 1
ans = 1
P = 998244353
for k in range(mx):
    if ac[k] > 0:
        ans = (ans * pow(k, ac[k], P)) % P
print(ans)

H题

from heapq import *


n = int(input())
a = list(map(int, input().split()))
a.sort()
a.append(int(1e9) + 1)
b = map(int, input().split())

pque = []
for x in b:
    heappush(pque, (x + a[0], x, 0))
ans = [0] * n
for k in range(n):
    ans[k], x, idx = heappop(pque)
    heappush(pque, (x + a[idx + 1], x, idx + 1))

print(*ans)

I题

n = int(input())
s = input()
t = 'HNNU'
k = 0
for c in s:
    if c == t[k]:
        k += 1
        if k == 4:
            n -= 4
            k = 0
print(n)

另外，本题有一份使用正则表达式的“一行流”代码（偷偷看到的）：传送门

J题

from math import cos, sqrt

f = lambda x : cos(x) + sqrt(2 * x ** 2 + 1)
T = int(input())
for _ in range(T):
    print("%.10f" % f(int(input())))

K题

注：math.gcd() 对多参数的支持是从 python3.9 开始的（参考资料），赛时牛客提供的解释器中 python3（3.9）是支持的但 pypy3（3.6）不支持，因此下面的代码须使用 python3 提交（如果以后更新了应该就都支持了）。

from math import gcd


for _ in range(int(input())):
    n = int(input())
    a = map(int, input().split())
    b = map(int, input().split())
    ga, gb = gcd(*a), gcd(*b)
    if ga == gb:
        print('YES')
    else:
        print('NO')

L题

T = int(input())
for _ in range(T):
    a, b, n, m = map(int, input().split())
    a %= n
    b %= n
    cur = 0
    if m <= 3 * n:
        for k in range(m):
            cur = (cur + a * cur + b) % n
    else:
        idx = [-1] * n
        k = 0
        while idx[cur] == -1:
            idx[cur] = k
            k += 1
            cur = (cur + a * cur + b) % n
        loop = k - idx[cur]
        start = idx[cur]
        end = start + (m - start) // loop * loop
        remain = m - end
        for k in range(remain):
            cur = (cur + a * cur + b) % n
    print(cur)

M题

n = int(input())
a = list(map(int, input().split()))
idx = [0] * (n + 1)
mx = 0
for k in range(n - 1, -1, -1):
    if a[k] > mx:
        for x in range(a[k], mx, -1):
            idx[x] = k
        mx = a[k]
for k in range(n):
    a[k] = a[idx[a[k]]]
print(*a)