Powered by:NEFU AB-IN

Link

update 2022/5/1
已经省一了

文章目录

Python大学A组 个人题解

  • 试题 A: 裁纸刀

    • 思路

      x ∗ y − 1 + 4 x*y-1+4 x∗y−1+4

    • 代码

      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 ( s q r t ( n ) ) O(sqrt(n)) 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) O(n)
      再依据贪心的思想，数目大的 对上 标记多的，差分数组前缀和求和即可
      总体复杂度 O ( n l o g n ) O(nlogn) O(nlogn)

    • 代码

      '''
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 60+40+30+24 60+40+30+24个，也就是 5 ! / 2 , 5 ! / 3 , 5 ! / 4 , 5 ! / 5 5!/2, 5!/3, 5!/4, 5!/5 5!/2,5!/3,5!/4,5!/5
      2的有 40 + 30 + 24 40+30+24 40+30+24个
      3的有 30 + 24 30+24 30+24个
      4的有 24 24 24个

      可以看出规律

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

      复杂度 O ( n ) O(n) 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没做，但听说不难
# 蓝桥杯
Logo
2048 AI社区

有“AI”的1024 = 2048，欢迎大家加入2048 AI社区

更多推荐

cover

90天速成！零基础入门AI大模型开发，保姆级路线图助你弯道超车！

avatar 2048 AI社区
cover

减少 HR80% 重复沟通：聘小助自动打招呼在猎头 / 企业招聘中的应用

avatar 2048 AI社区

大模型加载太慢怎么办，三行代码搞定 Qwen3-VL 国内加速

很多小伙伴想要一窥网络安全整个体系，这里我分享一份打磨了4年，已经成功修改到4.0版本的《平均薪资40w的网络安全工程师学习路线图》对于从来没有接触过网络安全的同学，我们帮你准备了详细的学习成长路线图。压箱底的好资料，全面地介绍网络安全的基础理论，包括逆向、八层网络防御、汇编语言、白帽子web安全、密码学、网络安全协议等，将基础理论和主流工具的应用实践紧密结合，有利于读者理解各种主流工具背后的实现

avatar 2048 AI社区