第十六届蓝桥杯软件赛省赛PythonB组题解-解题陈诉

写在前面

赛题相较于上一年py b组难度明显降低，或许成为本次比赛最简朴的一套题，当然其中出现了原题，H题为Codeforces原题，分数为1700，裸题(是好事，至少说人话了)，题主因时间冲突并未参加正赛，选择了场外vp。个人感觉如果仅有语法底子的话最少可以拿到15分，即通过A题和C题，这样看来最少都得有个省三省二。
本场难度cf预估分数 <=1700。
题解

A 攻击次数 填空题

103 简朴模仿即可，可在草稿纸上手算。
B 最长字符串(填空题)

答案是afplcu,长度为6

1. res = set()
2. path = r"words.txt"
3. with open(path, "r", encoding="utf-8") as f:
4.     for line in f:
5.         cur = line.strip()
6.         res.add((len(cur), cur))
7. res = sorted(res)
8. is_beautiful = set()
9. ans = -1
10. l = 0
11. for length, word in res:
12.     v = [0] * 26
13.     if length == 1:
14.         for i in word:
15.             v[ord(i) - ord('a')] += 1
16.         is_beautiful.add(tuple(v))
17.     else:
18.         for i in range(length):
19.             v[ord(word[i]) - ord('a')] += 1
20.         v1 = [0] * 26
21.         t1 = word[:-1]
22.         for i in range(length - 1):
23.             v1[ord(t1[i]) - ord('a')] += 1
24.         if  tuple(v1) in is_beautiful:
25.             is_beautiful.add(tuple(v))
26.             if length > l:
27.                 l = length
28.                 ans = word
29.             elif length == l and word < ans:
30.                 ans = word
31. print(l)
32. print(ans)

复制代码

C LQ图形

思绪：签到题，按题意模仿即可

1. w, h, v = map(int, input().split())
2. for _ in range(h):
3.     print('Q' * w)
4. for _ in range(w):
5.     print('Q' * (v + w))

复制代码

D 最多次数

思绪：贪婪，注意到先选总是不劣于后选即可

1. s = input()
2. n = len(s)
3. count = 0
4. i = 0
5. while i <= n - 3:
6.     a, b, c = s[i], s[i+1], s[i+2]
7.     if {a, b, c} == {'l', 'q', 'b'}:
8.         count += 1
9.         i += 3
10.     else:
11.         i += 1
12. print(count)

复制代码

E题 A · B Problem

思绪：用调和级数nlogn预处理出1 - L 每个数的因数个数再O(L)处理出小于等于x的数的乘积对数
末了罗列XA · XB的值即可

1. L = int(input())
3. inv = [0] * (L+1)
4. for i in range(1, L+1):
5.     for j in range(i, L+1, i):
6.         inv[j] += 1
7. dp = [0] * (L+1)
8. for i in range(1, L+1):
9.     dp[i] = dp[i-1] + inv[i]
10. res = 0
11. for i in range(1, L):
12.     res += inv[i] * dp[L - i]
13. print(res)

复制代码

F 园艺

思绪：动态规划 n^2的解, dp[j]表示以第i棵树为起点,间隔为j最多可以保留几颗树
不难观察到有dp[j] = dp[i + j][j] + 1 if tree[i+j] > tree else 1

1. n = int(input())
2. line = list(map(int, input().split()))
3. dp = [[0] * n for _ in range(n)]
4. res = 0
5. for i in range(n - 1, -1, -1):
6.     for j in range(1, n):
7.         if i + j < n:
8.             if line[i + j] > line[i]:
9.                 dp[i][j] = dp[i + j][j] + 1
10.             else:
11.                 dp[i][j] = 1
12.         else:
13.             dp[i][j] = 1
14.         res = max(res, dp[i][j])
15. print(res)

复制代码

从数据范围来看，显然不是正解，欢迎在批评区分享你的做法。

G 书架还原

你没看错，这题很裸，就差把“置换环”告诉你了。这里提供两种做法。

1. n = int(input())
2. a = list(map(int, input().split()))
4. def G1(a):
5.     visited = [False] * n
6.     cycles = 0
8.     for i in range(n):
9.         if not visited[i]:
10.             j = i
11.             while not visited[j]:
12.                 visited[j] = True
13.                 j = a[j] - 1  
14.             cycles += 1
15.     return n - cycles
16. def G2(a):
17.     dic = {}
18.     for i,x in enumerate(a):
19.         dic[x] = i
20.     res = 0
21.     for val in range(1, n+1):
22.         val_idx = dic[val]
23.         cur_idx = val - 1
24.         if cur_idx == val_idx: continue
25.         cur = a[cur_idx]
26.         dic[val] = cur_idx
27.         dic[cur] = val_idx
28.         a[val_idx], a[cur_idx] = a[cur_idx], a[val_idx]
29.         res += 1
30.     return res
31. print(G1(a), G2(a))

复制代码

H 异或和

cf原题链接：https://codeforces.com/problemset/problem/1879/D

是不是一模一样呢
思绪：拆位算贡献 + 二阶后缀和

1. n = int(input())
3. l = list(map(int, input().split()))
4. res = 0
5. for i in range(21):
6.     suf1 = [0] * (n + 1)
7.     suf2 = [0] * (n + 1)
8.     for j in range(n-1, -1, -1):
9.         if (l[j] >> i) & 1:
10.             suf1[j] = suf1[j+1] + 1
11.             suf2[j] = suf2[j+1] + suf1[j + 1]
12.         else:
13.             suf1[j] = suf1[j+1]
14.             suf2[j] = suf2[j+1] + suf1[j + 1]
15.         cnt_1 = suf2[j]
16.         cnt_0 = (n - j) * (n - j - 1) // 2 - cnt_1
17.         if (l[j] >> i) & 1:
18.             res += cnt_0 * (1 << i)
19.         else:
20.             res += cnt_1 * (1 << i)
21. print(res)

复制代码

写在末了

感谢white_two同学提供的部分代码~

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。