牛客小白月賽94 解題報告 | 珂學家

前言

很久沒寫題解了，有幸參加了94小白月賽內測，反饋是很nice，AK場。

爭議的焦點在于哪題最難

D題
E題(沒有F題)
F題(沒有E題)

你選哪題呢？

alt

題解

歡迎關注

珂朵莉牛客周賽專欄

珂朵莉牛客小白月賽專欄

A. 小苯的九宮格

思路: 映射 + 模擬

grid = []
for _ in range(3):arr = input().split()grid.append(arr)s = input()
r = []
for c in s:p = ord(c) - ord('0')h = (p - 1) // 3w = (p - 1) % 3r.append(grid[h][w])
print (''.join(r))

B. 小苯的好數組

切入點: 尋找相鄰元素的逆序對

n = int(input())
arr = list(map(int, input().split()))flag = False
for i in range(n - 1):if arr[i] > arr[i + 1]:flag = Truebreakprint (n if flag else 0)

C. 小苯的數字合并

思路: 貪心+枚舉

從貪心的角度，因為數組的數都是非負數，所以最小數一定是數組中的某個元素，最大數則是左右兩側和的最大值

如果這題數組中存在負數，那該如何解？

n = int(input())arr = list(map(int, input().split()))res = 0
s = arr[0]
for i in range(1, n - 1):s += arr[i]res = max(res, abs(s - arr[i + 1]))s = arr[n - 1]
for i in range(n - 2, 0, -1):s += arr[i]res = max(res, abs(s - arr[i - 1]))print (res)

D. 小苯的排列構造

1~N的排列，其GCD一定收斂很快

$A數列的不同元素個數不會超過 log_2(10^5) = 16 個$

這就是貪心的核心點:

$所以大部分 A 數列，尾巴一定都是 1 ，所以后續 P 序列的數其順序就不重要的$

那如何構造呢？

可以從分組的角度，然后按倍數遞增

所以這樣的時間復雜度 $c\le18$

也可以引入驗證函數，來快速過濾無解的情況

def check():prev = arr[0]for i in range(1, n):if prev < arr[i] or prev % arr[i] != 0:return Falseprev = arr[i]return Truedef solve():vis = [False] * (n + 1)res = []# 分組循環i = 0while i < n:j = i + 1while j < n and arr[i] == arr[j]:j += 1k = 1tmp = []while len(tmp) < j - i and k * arr[i] <= n:if not vis[k * arr[i]]:vis[k * arr[i]] = Truetmp.append(k *arr[i])k += 1if len(tmp) != j - i:return [-1]res.extend(tmp)    i = jreturn resn = int(input())
arr = list(map(int, input().split()))if check():res = solve()print (*res)
else:print (-1)

E. 小苯的01背包（easy）

方法一: 期望法貪心

從價值的角度出發

枚舉期望的價值（從大到小），然后嘗試去構造

由于與操作的特點，越與越小，所以全部都要（小孩子才做選擇題）。

純思維題，也是最簡單的解法

n, k = list(map(int, input().split()))pack = []
for _ in range(n):v, w = list(map(int, input().split()))pack.append((v, w))def solve():for s in range(2000, 0, -1):tmp = 0xfffffffor (v, w) in pack:if (s & w) == s:tmp &= vif tmp <= k:return sreturn 0print (solve())

方法二：BFS + 最優性剪枝

也是欺負數據小

看著像 $O(n^3)$ , 但是hack不掉。

n, k = list(map(int, input().split()))res = 0
pack = []
for _ in range(n):v, w = list(map(int, input().split()))pack.append((v, w))if v <= k:res = max(res, w)pack.sort(key=lambda x: -x[0])
st = set()
st.add((0x0ffffffff, 0x0ffffffff))for (v, w) in pack:if v <= k:continueif w <= res:continuest2 = set()st2.add((v, w))for (k1, v1) in st:if (v & k1) <= k:res = max(res, w & v1)elif (w & v1) > res:st2.add((k1&v, w&v1))if v1 > res:st2.add((k1, v1))st = st2
print (res)

這個解法，輕松過easy范圍

alt

甚至在hard的值域范圍下，也是很無敵的存在

alt

方法三: 試填法

位運算相關的題，很經典的解法和思路

n, k = list(map(int, input().split()))res = 0
pack = []
for _ in range(n):v, w = list(map(int, input().split()))pack.append((v, w))if v <= k:res = max(res, w)# 試填法
mask = 0
for i in range(29, -1, -1):mask += 1 << ifv = (1 << 30) - 1for (v, w) in pack:if (mask & w) == mask:fv &= vif fv <= k:passelse:mask -= 1 << iprint (mask)