摘要
Title: A, B, C, D, F, G

Python大学A组个人题解

试题 A: 裁纸刀
- 思路
  
  $x*y-1+4$
- 代码
  1
  443

试题 B: 寻找整数

思路

中国剩余定理拓展版的板子题，由于模数两两不互质，所以不能用通式
设计到不定方程的最小整数解之类的，不了解的可以看我之前博客 Link

(前几天刚练了)

代码

'''
Author: NEFU AB-IN
Date: 2022-04-10 13:01:10
FilePath: \Contest\b.1.py
LastEditTime: 2022-04-10 13:01:10
'''


def exgcd(a, b):
    global k1, k2
    if b == 0:
        k1, k2 = 1, 0
        return a
    d = exgcd(b, a % b)
    k1, k2 = k2, k1
    k2 -= (a // b) * k1
    return d


n = int(input())

m1, a1 = map(int, input().split())
flag = 0
for i in range(n - 1):
    m2, a2 = map(int, input().split())
    k1, k2 = 0, 0
    d = exgcd(m1, m2)
    if (a2 - a1) % d:
        flag = 1
        break
    k1 *= (a2 - a1) // d
    # k1' = k1 + k * (m2 // d) , k取任意整数
    t = m2 // d
    k1 = k1 % t  # 取最小的k1
    # x = a + km
    a1 = k1 * m1 + a1
    m1 = m1 // d * m2

if flag:
    print(-1)
else:
    print(a1 % m1)  #x的最小正整数解

'''
48
2 1
3 2
4 1
5 4
6 5
7 4
8 1
9 2
10 9
11 0
12 5
13 10
14 11
15 14
16 9
17 0
18 11
19 18
20 9
21 11
22 11
23 15
24 17
25 9
26 23
27 20
28 25
29 16
30 29
31 27
32 25
33 11
34 17
35 4
36 29
37 22
38 37
39 23
40 9
41 1
42 11
43 11
44 33
45 29
46 15
47 5
48 41
49 46
2022040920220409
'''

试题 C: 质因数个数

思路

板子题 $O(sqrt(n))$

代码

'''
Author: NEFU AB-IN
Date: 2022-04-09 09:14:21
FilePath: \Contest\c.py
LastEditTime: 2022-04-09 09:17:15
'''
n = int(input())

cnt = 0
i = 2
while i <= n // i:
    if n % i == 0:
        cnt += 1
        while n % i == 0:
            n //= i
    i += 1
if n > 1:
    cnt += 1

print(cnt)

试题 D: 矩形拼接

思路

结论不一定对，一共4，6，8三种情况
假设三个矩形a,b,c，如果任意两个矩形的其中各一条边，等于另一个矩形的一条边，说明最多6条边
如果能重合，就是4条边
其次就是
- 如果三个矩形都有一条边相同，那么就是4条边
- 如果两个矩形都有一条边相同，那么就是6条边
  其余情况8条边 (代码不准确)

代码

'''
Author: NEFU AB-IN
Date: 2022-04-09 09:23:50
FilePath: \Contest\d.py
LastEditTime: 2022-04-09 11:29:16
'''


def judge(i, j, k):
    ans = 8
    # 0 0
    if a[i][0] + a[j][0] == a[k][0]:
        if a[i][1] == a[j][1]:
            ans = min(ans, 4)
        else:
            ans = min(ans, 6)
    if a[i][0] + a[j][0] == a[k][1]:
        if a[i][1] == a[j][1]:
            ans = min(ans, 4)
        else:
            ans = min(ans, 6)
    # 1 0
    if a[i][1] + a[j][0] == a[k][0]:
        if a[i][0] == a[j][1]:
            ans = min(ans, 4)
        else:
            ans = min(ans, 6)
    if a[i][1] + a[j][0] == a[k][1]:
        if a[i][0] == a[j][1]:
            ans = min(ans, 4)
        else:
            ans = min(ans, 6)
    # 0 1
    if a[i][0] + a[j][1] == a[k][0]:
        if a[i][1] == a[j][0]:
            ans = min(ans, 4)
        else:
            ans = min(ans, 6)
    if a[i][1] + a[j][0] == a[k][1]:
        if a[i][0] == a[j][1]:
            ans = min(ans, 4)
        else:
            ans = min(ans, 6)
    # 1 1
    if a[i][1] + a[j][1] == a[k][0]:
        if a[i][0] == a[j][0]:
            ans = min(ans, 4)
        else:
            ans = min(ans, 6)
    if a[i][1] + a[j][1] == a[k][1]:
        if a[i][0] == a[j][0]:
            ans = min(ans, 4)
        else:
            ans = min(ans, 6)
    return ans


for _ in range(int(input())):
    a1, b1, a2, b2, a3, b3 = map(int, input().split())
    a = [0, [a1, b1], [a2, b2], [a3, b3]]
    if (a1 in a[2] and a1 in a[3]) or (b1 in a[2] and b1 in a[3]):
        print(4)
        continue
    print(min([judge(1, 2, 3), judge(1, 3, 2), judge(2, 3, 1)]))

试题 F: 重新排序

思路

就是先处理查询的总和为多少，并对每个点统计的数目打上标记，可以用前缀和和差分来解决， $O(n)$
再依据贪心的思想，数目大的 对上 标记多的，差分数组前缀和求和即可
总体复杂度 $O(n)$

代码

'''
Author: NEFU AB-IN
Date: 2022-04-09 09:28:11
FilePath: \Contest\f.py
LastEditTime: 2022-04-09 09:38:42
'''
n = int(input())
a = list(map(int, input().split()))

# 求原先的ans
s = [0] * (n + 2)
a = [0, *a]
for i in range(1, n + 1):
    s[i] = s[i - 1] + a[i]

a = sorted(a[1:], reverse=True)
a = [0, *a]

b = [0] * (n + 2)

m = int(input())
ans1 = 0
for i in range(m):
    l, r = map(int, input().split())
    b[l] += 1
    b[r + 1] -= 1
    ans1 += (s[r] - s[l - 1])

stk = []
for i in range(1, n + 1):
    b[i] += b[i - 1]
    stk.append(b[i])

stk.sort(reverse=True)
stk = [0, *stk]

ans = 0
for i in range(1, n + 1):
    ans += (a[i] * stk[i])
print(ans - ans1)

试题 G: 全排列的价值

思路

其实打出全排列的板子，再打几个数就可以发现规律

'''
Author: NEFU AB-IN
Date: 2022-04-09 09:43:50
FilePath: \Contest\g.py
LastEditTime: 2022-04-10 13:12:43
'''
from collections import Counter

N = 20
st, path = [0] * N, [0] * N
d = [Counter() for _ in range(N)]


def judge():
    for i in range(1, n + 1):
        cnt = 0
        for j in range(1, i):
            if path[j] < path[i]:
                cnt += 1
        d[i][cnt] += 1


def dfs(x):
    if x == n + 1:
        judge()
        for i in range(1, n + 1):
            print(path[i], end=" ")
        print()
        return
    for i in range(1, n + 1):
        if st[i] == 0:
            path[x] = i
            st[i] = 1
            dfs(x + 1)
            st[i] = 0


n = int(input())
a = [i for i in range(n + 1)]

dfs(1)
for i in range(1, n + 1):
    print(i, d[i])
'''
5
1 2 3 4 5 
1 2 3 5 4
1 2 4 3 5
1 2 4 5 3
1 2 5 3 4
1 2 5 4 3
1 3 2 4 5
1 3 2 5 4
1 3 4 2 5
1 3 4 5 2
1 3 5 2 4
1 3 5 4 2
1 4 2 3 5
1 4 2 5 3
1 4 3 2 5
1 4 3 5 2
1 4 5 2 3
1 4 5 3 2
1 5 2 3 4
1 5 2 4 3
1 5 3 2 4
1 5 3 4 2
1 5 4 2 3
1 5 4 3 2
2 1 3 4 5
2 1 3 5 4
2 1 4 3 5
2 1 4 5 3
2 1 5 3 4 
2 1 5 4 3
2 3 1 4 5
2 3 1 5 4
2 3 4 1 5
2 3 4 5 1
2 3 5 1 4
2 3 5 4 1
2 4 1 3 5
2 4 1 5 3
2 4 3 1 5
2 4 3 5 1
2 4 5 1 3
2 4 5 3 1
2 5 1 3 4
2 5 1 4 3
2 5 3 1 4
2 5 3 4 1
2 5 4 1 3
2 5 4 3 1
3 1 2 4 5
3 1 2 5 4
3 1 4 2 5
3 1 4 5 2
3 1 5 2 4
3 1 5 4 2
3 2 1 4 5
3 2 1 5 4
3 2 4 1 5
3 2 4 5 1
3 2 5 1 4
3 2 5 4 1
3 4 1 2 5
3 4 1 5 2
3 4 2 1 5
3 4 2 5 1 
3 4 5 1 2
3 4 5 2 1
3 5 1 2 4
3 5 1 4 2
3 5 2 1 4
3 5 2 4 1
3 5 4 1 2
3 5 4 2 1
4 1 2 3 5
4 1 2 5 3
4 1 3 2 5
4 1 3 5 2
4 1 5 2 3
4 1 5 3 2
4 2 1 3 5
4 2 1 5 3
4 2 3 1 5
4 2 3 5 1
4 2 5 1 3
4 2 5 3 1
4 3 1 2 5
4 3 1 5 2
4 3 2 1 5
4 3 2 5 1
4 3 5 1 2
4 3 5 2 1
4 5 1 2 3
4 5 1 3 2
4 5 2 1 3
4 5 2 3 1
4 5 3 1 2
4 5 3 2 1
5 1 2 3 4 
5 1 2 4 3
5 1 3 2 4
5 1 3 4 2
5 1 4 2 3
5 1 4 3 2
5 2 1 3 4
5 2 1 4 3
5 2 3 1 4
5 2 3 4 1
5 2 4 1 3
5 2 4 3 1
5 3 1 2 4
5 3 1 4 2
5 3 2 1 4
5 3 2 4 1
5 3 4 1 2
5 3 4 2 1
5 4 1 2 3
5 4 1 3 2
5 4 2 1 3
5 4 2 3 1
5 4 3 1 2
5 4 3 2 1
1 Counter({0: 120})
2 Counter({1: 60, 0: 60})
3 Counter({2: 40, 1: 40, 0: 40})
4 Counter({3: 30, 2: 30, 1: 30, 0: 30})
5 Counter({4: 24, 3: 24, 2: 24, 1: 24, 0: 24})
'''

1的有 $60+40+30+24$ 个，也就是 $5!/2, 5!/3, 5!/4, 5!/5$
2的有 $40+30+24$ 个
3的有 $30+24$ 个
4的有 $24$ 个

可以看出规律

先求出n的阶乘，再求 $\frac{n!}{i}$ ，其中 $i$ 可以线性求逆元优化一个 $log$ ，
最后求个前缀和，每个前缀和乘上对应的 $i$ 即可

复杂度 $O(n)$ ，不过常数比较大，不是最优做法

代码

'''
Author: NEFU AB-IN
Date: 2022-04-09 09:58:36
FilePath: \Contest\g.1.py
LastEditTime: 2022-04-10 12:33:52
'''
MOD = 998244353

n = int(input())

fa = 1
for i in range(2, n + 1):
    fa = fa * i % MOD
fac = []
inv = [0] * (n + 1)
inv[1] = 1

for i in range(2, n + 1):
    inv[i] = (MOD - MOD // i) * inv[MOD % i] % MOD

for i in range(2, n + 1):
    fac.append(fa * inv[i] % MOD)

fac = fac[::-1]
fac = [0, *fac]

for i in range(1, n):
    fac[i] = (fac[i] + fac[i - 1]) % MOD

ans = 0
for i in range(1, n):
    ans = (ans + (i * fac[n - i] % MOD)) % MOD

print(ans)

# 200
# 495662656

其余的题不太确定

E是骗分
H打的贪心，我的思路是二分求出最优上升子序列，根据子序列的下标距离，判断距离之间能不能放k，如果不够放k，那么就需要考虑平推的问题
I是打的线段树维护的最大值，思路比较糊
J没做，但听说不难