---

更好的閱讀體驗

• 高速訪問：https://wiki.dwj601.cn/ds-and-algo/lan-qiao-cup/16th-python-a/
• 永久鏈接：https://explorer-dong.github.io/ds-and-algo/lan-qiao-cup/16th-python-a/

---

官方還沒有開放評測，洛谷 開放了全部評測，但是時間限制與比賽不太一樣，往往更加嚴格，所以可能會出現洛谷過不了，但其實賽時能過的情況。

T1 偏藍 (5’/5’)

題意：定義三元組中每一位的取值范圍為 $[0,255]$ 的整數，問有多少個三元組滿足：三元組中的第三個位置的數嚴格大于前兩個位置的數。

思路：直接三重循環遍歷一遍即可。

最終答案為：$5559680$

ans = 0
for i in range(256):for j in range(256):for k in range(256):ans += (k > i) and (k > j)
print(ans)

T2 IPv6 (0’/5’)

題意：問所有的最簡 IPv6 的表示形式有多少種。

思路：不會，TODO。

T3 2025 圖形 (10’/10’)

題意：給定 $h,w(1\le h,w\le 100)$，按照 $2,0,2,5$ 的順序循環打印一個 $h$ 行 $w$ 列的字符串矩陣，同行中沒有空格。

思路：純模擬。

時間復雜度：$O(hw)$

h, w = tuple(map(int, input().strip().split()))a = ['2', '0', '2', '5']for i in range(h):ans = ''idx = i % 4j = 0for j in range(w):ans += a[idx]idx = (idx + 1) % 4print(ans)

T4 最大數字 (10’/10’)

題意：給定一個含有 $n(1\le n\le 10^4)$ 個數的排列，現在需要重排使得重排后的序列中所有元素「二進制拼接」后的二進制數值最大，輸出這個最大二進制數對應的十進制數。

思路：

• 貪心題，就是自定義一個排序規則。對于 $x$ 和 $y$ 兩個二進制表示，如果 $x+y>y+x$，則 $x$ 要排在 $y$ 的前面（加號表示字符串拼接）；
• Python 對字符串與十進制數的轉換有限制，需要手動調大。每個數的二進制最多 $14$ 位，$n$ 個數開到 $150000$ 肯定可以，但這是 Python 3.11 引入的，不知道藍橋杯的評測機能不能過；
• 力扣原題，證明。

時間復雜度：$O(n\log n)$

from functools import cmp_to_key
import sys
sys.set_int_max_str_digits(150000)def cmp(x: str, y: str) -> int:if x + y > y + x:return -1  # 小于號elif x + y == y + x:return 0return 1n = int(input().strip())a = [bin(x)[2:] for x in range(1, n + 1)]
a.sort(key=cmp_to_key(cmp))print(int(''.join(a), 2))

T5 倒水 (15’/15’)

題意：給定一個含有 $n(1\le n\le 10^5)$ 個數的序列 $a(1\le a_i\le 10^5)$ 和一個整數 $k(1\le k\le n)$。現在定義一種數值轉移規則：對于第 $i$ 個元素 $a_i$，其可以從任意一個 $j<i$ 且 $i\equiv j(\mathrm{mod}k)$ 的元素中轉移一部分數值到自己身上。問經過任意次這種轉移操作后，序列最小的元素最大可以是多少。

思路：看到最大化最小元素立刻想到了二分，但是看到只能從前綴部分轉移，掃描一遍就可以了。我們分 $k$ 組，每組從左往右遍歷并記錄前綴元素數量、前綴和、前綴最小值：

• 如果當前元素比不小于前綴最小值，那么就不會影響全局最小值，不用操作；
• 如果當前元素嚴格小于前綴最小值，那么就肯定要拿前綴的數值轉移一部分到自己身上，至于轉移多少不重要，重要的是要更新轉移后的前綴最小值。

時間復雜度：$O(n)$

n, k = tuple(map(int, input().strip().split()))
a = list(map(int, input().strip().split()))ans = max(a)
for i in range(k):cnt = 1pre = a[i]pre_min = a[i]for j in range(i + k, n, k):if a[j] >= pre_min:cnt += 1pre += a[j]continuecnt += 1pre += a[j]if pre // cnt >= pre_min:continuepre_min = pre // cntans = min(ans, pre_min)print(ans)

T6 拼好數 (0’/15’)

題意：給定一個含有 $n(1\le n\le 10^3)$ 個數的序列 $a(0\le a_i\le 10^9)$。為了最大化「數字中 $6$ 的個數超過 $6$ 個」的數字個數，現在可以給這些數分組（每組不超過 3 個元素）并將同一個組的數直接拼起來。問「數字中 $6$ 的個數超過 $6$ 個」的數字個數最大是多少。

思路：不會，TODO。

T7 登山 (20’/20’)

題意：給定一個 $n$ 行 $m$ 列的矩陣 $a(1\le a_{ij}\le 10^9)$，滿足 $1\le n,m\le 10^4,1\le n\times m\le 10^6$。給定在矩陣中的行走規則：可以走到同行同列中任意一個滿足「向左或向上比當前元素大的位置上」、「向右或向下比當前元素小的位置上」。計算每個格子可以到達的最大高度，輸出其均值并保留 $6$ 位小數。

思路：直接遍歷每一個連通分量即可，可以用 DSU，也可以二次遍歷來給連通分量中每個位置標上可到達的最大值。其余實現可以參考 01 迷宮 這道題。

時間復雜度：$O(nm(n+m))$

=== “Python BFS”

from collections import dequen, m = tuple(map(int, input().strip().split()))
g = [list(map(int, input().strip().split())) for _ in range(n)]
ans = [[0] * m for _ in range(n)]vis = [[False] * m for _ in range(n)]def bfs(u: int, v: int):q = deque()path = []ma = -1vis[u][v] = Truepath.append((u, v))q.append((u, v))ma = max(ma, g[u][v])while q:x, y = q.popleft()for j in range(m):if j < y and g[x][j] > g[x][y] and not vis[x][j]:vis[x][j] = Truepath.append((x, j))q.append((x, j))ma = max(ma, g[x][j])if j > y and g[x][j] < g[x][y] and not vis[x][j]:vis[x][j] = Truepath.append((x, j))q.append((x, j))ma = max(ma, g[x][j])for i in range(n):if i < x and g[i][y] > g[x][y] and not vis[i][y]:vis[i][y] = Truepath.append((i, y))q.append((i, y))ma = max(ma, g[i][y])if i > x and g[i][y] < g[x][y] and not vis[i][y]:vis[i][y] = Truepath.append((i, y))q.append((i, y))ma = max(ma, g[i][y])for x, y in path:ans[x][y] = mafor i in range(n):for j in range(m):if vis[i][j]:continuebfs(i, j)s = 0
for i in range(n):for j in range(m):s += ans[i][j]print(f"{s/(n * m):.6f}")

T8 原料采購 (20’/20’)

題意：在一維坐標軸正方向上，給定一輛位于原點處的貨車，其容量為 $m(1\le m\le 10^9)$。正方向上有從近到遠的 $n(1\le n\le 10^5)$ 個進貨源，每個進貨源都有一個進貨單價、存貨量和到原點的距離，分別記作 $a,b,c(1\le a_i,b_i,c_i\le 10^9)$。貨車每行駛 $1$ 個單位花費 $o$ 且無需返程。輸出進滿貨的最低成本，若沒有方案可以裝滿輸出 $?1$。

思路：一道比較經典的反悔貪心題，模擬的過程略復雜，但整體難度不大。初始貪心時直接選擇即可；后續反悔時，每次和之前單價更高的貨物進行置換。可以使用大根堆來維護選擇過的「貨物單價與貨物數量」。至于路費，無需在貨物置換的過程中考慮，只需在全部置換結束后再算上即可。

時間復雜度：$O(n\log n)$

=== “Python”

from heapq import *MII = lambda: map(int, input().strip().split())class Site:def __init__(self, price, num, dist):self.price = priceself.num = numself.dist = distn, m, o = MII()
sites = [Site(*MII()) for _ in range(n)]def solve() -> None:# 特判if sum([site.num for site in sites]) < m:print(-1)return# 貪心val = 0  # 車上貨物價值num = 0  # 車上貨物數量i = 0    # 枚舉到的進貨點下標h = []   # [[貨物單價的負數，選擇的數量], [], ...]while i < n:choose = min(sites[i].num, m - num)if choose == 0:i -= 1breaksites[i].num -= choosenum += chooseval += choose * sites[i].priceheappush(h, [-sites[i].price, choose])i += 1# 反悔heapify(h)ans = val + sites[i].dist * owhile i < n:if sites[i].price >= -h[0][0]:i += 1continuealter_num = 0  # 第 i 個進貨源替換貨物的數量while len(h):if -h[0][0] <= sites[i].price:breakalter = min(h[0][1], sites[i].num)  # 替換量h[0][1] -= altersites[i].num -= alteralter_num += alterval -= alter * (-h[0][0] - sites[i].price)if h[0][1] == 0:heappop(h)if sites[i].num == 0:breakif alter_num:heappush(h, [-sites[i].price, alter_num])ans = min(ans, val + sites[i].dist * o)i += 1print(ans)if __name__ == "__main__":solve()

=== “C++”

#include <iostream>
#include <queue>
using namespace std;
using ll = long long;const int N = 100010;ll n, m, o;
struct Site {ll price, num, dist;
} sites[N];int main() {ios::sync_with_stdio(false);cin.tie(nullptr);ll all_num = 0;cin >> n >> m >> o;for (int i = 0; i < n; i++) {cin >> sites[i].price >> sites[i].num >> sites[i].dist;all_num += sites[i].num;}// 特判if (all_num < m) {cout << -1 << "\n";return 0;}// 貪心ll val = 0, num = 0, i = 0;priority_queue<pair<ll, ll>> h;while (i < n) {ll choose = min(sites[i].num, m - num);if (!choose) {i--;break;}num += choose;sites[i].num -= choose;val += choose * sites[i].price;h.push({sites[i].price, choose});i++;}// 反悔ll ans = val + sites[i].dist * o;while (i < n) {if (h.top().first <= sites[i].price) {i++;continue;}ll alter_num = 0;while (h.size()) {if (h.top().first <= sites[i].price) {break;}auto [price, num] = h.top();h.pop();ll alter = min(num, sites[i].num);num -= alter;sites[i].num -= alter;alter_num += alter;val -= alter * (price - sites[i].price);if (num) {h.push({price, num});}if (!sites[i].num) {break;}}if (alter_num) {h.push({sites[i].price, alter_num});ans = min(ans, val + sites[i].dist * o);}i++;}cout << ans << "\n";return 0;
}