本场所有题目均可以使用python3通过（

A.小红的数组重排

显然输出 即可。

时间复杂度 。

a, b, c = map(int, input().split())
print(c, a, b)

B.小红的回文串构造

如果回文串长度至少为 ，则一定有重复的字符。

因此 输出任意字符， 输出 即可。

时间复杂度 。

for _ in range(int(input())):
    n = int(input())
    if n == 1:
        print('a')
    else:
        print("No")

C.小红的排列

如果 出现次数大于 （ 个数字奇数的个数）或 出现次数大于 （ 个数字偶数的个数），则一定不可能。

否则设有 个 ， 个 ，对于 个 ，将其中 个分配为 有 中方案。

剩下所有奇数在 的位置任意排， 在偶数位置任意排，有 种方案。

因此答案即为 。

时间复杂度 。

n = int(input())
s = input()
cnt0 = s.count('j')
cnt1 = s.count('o')
MOD = 998244353
cnt2 = n - cnt0 - cnt1
def C(n, m):
    if n == 0 or m == 0:
        return 1
    res = 1
    for i in range(1, n+1):
        res = res * i %MOD;
    for i in range(1, m+1):
        res = res * pow(i, MOD-2, MOD)%MOD
    for i in range(1, n-m+1):
        res = res * pow(i, MOD-2, MOD)%MOD
    return res
if(cnt0 > (n+1)//2 or cnt1 > n//2):
    print(0)
else:
    ans = 1
    ans = ans * C(cnt2, (n+1)//2  - cnt0)%MOD;
    for i in range(1, (n+1)//2+1):
        ans = ans * i %MOD
    for i in range(1, n//2+1):
        ans = ans * i %MOD
    print(ans)

D.小红的中位数

如果所有数字均相同，答案为 。

要变化中位数，可以分为变成比原来 小 和比原来 大。

设有 个数字比 小， 个数字比 大。

若比 小，如果 则不可能，否则则至少需要删除 个数字。

若比 大，如果 则不可能，否则则至少需要删除 个数字。

注意中位值奇偶的区别。

时间复杂度 。

n = int(input())
a = list(map(int, input().split()))
a.sort()
f = 1
for i in range(1, n):
    f &= a[i] == a[0]
if f:
    print(-1)
else:
    mid = (n+1)//2 - 1
    cntl = 0
    cntr = 0
    for i in range(n):
        cntl += a[i] < a[mid]
        cntr += a[i] > a[mid]
    ans = 10**18
    if cntl > 0:
        ans = min(ans, n-2*cntl)
    if cntr > 0:
        ans = min(ans, n-2*cntr+1)
    print(ans)

E.小红的树上博弈

考虑 ，设 为从 开始是否有一条路径小红能获胜 。

显然对于所有叶子节点，。

对于节点 ，如果其子节点中至少有两个 ，则无论小紫赌堵哪一个节点，都可以走其他节点获胜，则 。否则会被小紫堵掉，。

则 小红赢，否则小紫赢。

时间复杂度 。

import sys
sys.setrecursionlimit(600000)
for _ in range(int(input())):
    n = int(input())
    g = [[] for i in range(n+1)]
    for i in range(n-1):
        u, v = map(int, input().split())
        g[u].append(v)
        g[v].append(u)
        
    fa = [0] * (n + 1)
    order = []
    stack = [1]

    while stack:
        u = stack.pop()
        order.append(u)
        for v in g[u]:
            if v != fa[u]:
                fa[v] = u
                stack.append(v)
        
    dp  = [0 for i in range(n+1)]
    for u in order[::-1]:
        if len(g[u]) == 1 and u != 1:
            dp[u] = 1
            continue
        cnt = 0
        for v in g[u]:
            if v == fa[u]:
                continue
            cnt += dp[v]
            
        if cnt >= 2 or cnt >= 1 and u == 1:
            dp[u] = 1
    print("red" if dp[1] else "purple")

F.小红的点构造

手玩一下可以发现，正方形的对数的最多的，上限为 。

否则，可以螺旋放置，从小正方形扩展到达的，直到新增后超过 ，此时最多剩余 。

显然此时可以暴力遍历放在每一个点周围是否可行，最多遍历 次一定能找完。

如果还有剩余的点，放在极远处间隔放置即可。

时间复杂度 。

from collections import defaultdict
from math import ceil, sqrt

n, k = map(int, input().split())

if k > 2 * n - ceil(2*sqrt(n)):
    print("No")
    exit(0)
    
memo = defaultdict(int)

d = 0
dx = [1, 0, -1, 0]
dy = [0, 1, 0, -1]
le = 1
cnt = 0
x = 0
y = 0
now = 0
for i in range(n):
    if cnt == k:
        memo[(-10**9+i*2, -10**9)] = 1
        continue
    res = memo[(x-1, y)] + memo[(x, y-1)] + memo[(x+1, y)] + memo[(x, y+1)]
    if res + cnt <= k:
        cnt += res
        memo[(x, y)] = 1
        x += dx[d]
        y += dy[d]
        now += 1
        if now == le:
            d = (d + 1)%4
            if d == 2 or d == 0:
                le += 1
            now = 0
    else:
        okx, oky = -10**9, -10**9
        mx = -1
        t = dict(memo)
        for xx, yy in t.keys():
            if memo[(xx, yy)] == 0:
                continue
            for dd in range(4):
                xxx = xx + dx[dd]
                yyy = yy + dy[dd]
                if memo[(xxx, yyy)]:
                    continue
                res = memo[(xxx-1, yyy)] + memo[(xxx, yyy-1)] + \
                memo[(xxx+1, yyy)] + memo[(xxx, yyy+1)]
                if res + cnt <= k:
                    if res > mx:
                        okx = xxx
                        oky = yyy
                        mx = res
        cnt += mx
        memo[(okx, oky)] = 1
print("Yes")
for xx, yy in memo.keys():
    if memo[(xx, yy)] == 0:
        continue
    print(xx, yy)