本文主要是介绍牛客小白月赛94 解题报告 | 珂学家 | 茴字有36种写法,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
前言
很久没写题解了,有幸参加了94小白月赛内测,反馈是很nice,AK场。
争议的焦点在于哪题最难
- D题
- E题(没有F题)
- F题(没有E题)
你选哪题呢?
题解
欢迎关注
珂朵莉 牛客周赛专栏
珂朵莉 牛客小白月赛专栏
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 数列的不同元素个数不会超过 l o g 2 ( 1 0 5 ) = 16 个 A数列的不同元素个数不会超过 log_2(10^5) = 16 个 A数列的不同元素个数不会超过log2(105)=16个
这就是贪心的核心点:
所以大部分 A 数列,尾巴一定都是 1 ,所以后续 P 序列的数其顺序就不重要的 所以大部分A数列,尾巴一定都是1,所以后续P序列的数其顺序就不重要的 所以大部分A数列,尾巴一定都是1,所以后续P序列的数其顺序就不重要的
那如何构造呢?
可以从分组的角度,然后按倍数递增
所以这样的时间复杂度 O ( c n ) , c ≤ 18 O(cn), c\le18 O(cn),c≤18
也可以引入验证函数,来快速过滤无解的情况
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 ) O(n^3) O(n3), 但是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范围
甚至在hard的值域范围下,也是很无敌的存在
方法三: 试填法
位运算相关的题,很经典的解法和思路
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)
F. 小苯的01背包(hard)
详见 E 中的方法三: 试填法
剩下的33种方法,只有聪明的人才能看到…
写在最后
这篇关于牛客小白月赛94 解题报告 | 珂学家 | 茴字有36种写法的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!