牛客的编辑器真是佛了。

1. 数组中两个元素和小于等于M的组合数

题目描述

对于一个整型数组，里面任何2个元素相加，小于等于M的组合有多少种；
如果有符合的，输出组合对数；
没有，输出0；

参考代码

import sys
from bisect import bisect_right

readline = sys.stdin.readline

nums = list(map(int, readline().strip().split()))
M = int(readline().strip())

nums.sort()
ans = 0

for i, x in enumerate(nums):
    # ans += bisect_right(nums[:i], M - x) # 实际上 nums[:i] 的复杂度为 O(i)，所以会导致整体的复杂度为 O(n^2)，但是笔试时也过了，或者双指针可以达到 O(n)
    ans += bisect_right(nums, M - x, 0, i) # O(nlog(n))  

print(ans)

2. 计算K位

题目描述

给你两个正整数 n 和 k，其中 1 =< n <= 26，字符串 Sn 的形成规则如下：

Li表示26个字母a-z，依次是：
L1 = "a"
L2 = "b"
L3 = "c"
...
L26="z"

S1 = "a"
当 i > 1 时，Si = Si-1 +Li + reverse(invert(Si-1))
其中 + 表示字符串的连接操作，reverse(x) 返回反转 x 后得到的字符串，而 invert(x) 则会翻转 x 中的每一位（例如：'a' 翻转为'z'，'b' 翻转为'y', ... 而 'z' 翻转为 'a'）。

例如，符合上述描述的序列的前 4 个字符串依次是：

S1="a"
S2="abz"
S3="abzcayz"
S4="abzcayzdabzxayz"

请你返回 Sn 的 第 k 位字符 ，题目数据保证 k 一定在 Sn 长度范围以内。
示例1输入输出示例仅供调试，后台判题数据一般不包含示例

参考代码

B = [0]
for i in range(1, 27):
    B.append(B[-1] * 2 + 1)


class Solution:
    def findKthBit(self, n: int, k: int) -> str:
        mid = (B[n] + 1) // 2
        if k == mid:
            return chr(n + ord("a") - 1)
        elif k < mid:
            return self.findKthBit(n - 1, k)
        return chr(
            ord("z")
            - ord(self.findKthBit(n - 1, B[n - 1] + 1 - (k - mid)))
            + ord("a")
        )

3. 纸张分配问题

题目描述

一群小朋友围成一圈准备开始画画，现在老师需要给这些孩子发纸张；
规则是如果一个小朋友的年龄比自己旁边的人大，那么这个小朋友就必须分到比身旁孩子更多的纸张；
所有孩子至少要有一个纸张，请帮助老师设计一个算法，算出最少需要多少张纸。
备注：
假设小朋友的总数量不会超过100个；
每个小朋友至少要求至少有一张纸；
当且仅当年龄大于相邻小朋友时，才会要求纸张数量更多（年龄相等的情况下，允许小于或者等于）。

参考代码

import sys
from collections import deque

readline = sys.stdin.readline

a = list(map(int, readline().strip().split()))
n = len(a)
adj = [[] for _ in range(n)]
indeg = [0] * n
for i in range(n):
    l = (i - 1 + n) % n
    r = (i + 1) % n
    if a[i] > a[l]:
        adj[l].append(i)
        indeg[i] += 1
    if a[i] > a[r]:
        adj[r].append(i)
        indeg[i] += 1
q = deque()
for i in range(n):
    if indeg[i] == 0:
        q.append(i)
b = [1] * n
while q:
    u = q.popleft()
    for v in adj[u]:
        b[v] = max(b[v], b[u] + 1)
        indeg[v] -= 1
        if indeg[v] == 0:
            q.append(v)
print(sum(b))

4. 航海探险

题目描述

给你一个由 '0'（水）、'1'（陆地）和'2'（障碍物）组成的的二维网格，再给你一个两栖交通工具，走陆地费用为1，走水路费用为2，障碍物无法通行，请你计算从网格的起始位置行驶到最终位置的最小费用。
注意：仅可以水平方向 和 竖直方向行驶。如果无法到达目的地，则返回-1
另外，起始第1个位置不算，根据到达位置的属性来决定费用。
示例1输入输出示例仅供调试，后台判题数据一般不包含示例

参考代码

import heapq
from typing import List


class Solution:
    def minSailCost(self, g: List[List[int]]) -> int:
        n = len(g)
        m = len(g[0])
        dist = [[float("inf") for _ in range(m)] for _ in range(n)]
        dist[0][0] = 0
        q = []
        heapq.heappush(q, (0, 0))
        dx = [0, -1, 0, 1]
        dy = [-1, 0, 1, 0]
        while q:
            d, u = heapq.heappop(q)
            i, j = divmod(u, m)
            for k in range(4):
                r, c = i + dx[k], j + dy[k]
                if 0 <= r < n and 0 <= c < m and g[r][c] != 2:
                    if d + 2 - g[r][c] < dist[r][c]:
                        dist[r][c] = d + 2 - g[r][c]
                        heapq.heappush(q, (dist[r][c], r * m + c))
        if dist[-1][-1] == float("inf"):
            return -1
        return dist[-1][-1]