json

json 常用函数

函数 输入 输出
json.loads() JSON 字符串 Python 对象
json.dumps() Python 对象 JSON 字符串
json.load() JSON 文件 Python 对象
json.dump() Python 对象 JSON 文件

OPPO

P5226.第2题-最小信号功率

第2题-最小信号功率 - problem_ide - CodeFun2000

核心思路：通过数学公式得到简易表达，注意 $i$ 是变量，所以会有嵌套 max

题意转化

$$ P-|i-c|\ge r_i \rightarrow P\ge r_i+|i-c| $$
因为
$$ |i-c|=\max(i-c,c-i) $$
所以
$$ r_i+|i-c|=\max(r_i+i-c,\;r_i-i+c) $$
要把所有的 $i$ 放到一起考虑
$$ P\ge\max\left(\max_i(r_i+i)-c,\;\max_i(r_i-i)+c\right) $$
再分别取最大，定义
$$ A=\max_i(r_i+i),\qquad B=\max_i(r_i-i) $$
整个问题变成找
$$ \min_c \max(A-c,\ B+c) $$
所以要让两者的最大值尽可能小，最佳位置就是让二者尽量相等
$$ A - c = B+c $$
得到
$$ c=\frac{A-B}{2} $$
由于 $c$ 必须是整数，所以最小发射功率为：
$$ \boxed{P_{\min}=\left\lceil\frac{A+B}{2}\right\rceil} $$ 
1
2
3
4
5
6
7
8
9
10
11
12
def main():
    n = int(input())
    R = list(map(int, input().split()))
    A = float("-inf")
    B = float("-inf")
    for i,r in enumerate(R):
        A = max(A, r+i+1)
        B = max(B, r-i-1)
    P = (A+B+1)//2
    print(P)
if __name__ == "__main__":
    main()

P5221.第2题-监测样本偏离判定

第2题-监测样本偏离判定 - problem_ide - CodeFun2000

核心：了解如何调用 sklearn 实现 PCA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
import numpy as np
import json
import sys
from sklearn.preprocessing import StandardScaler
from sklearn.decomposition import PCA

def main():
    data = json.loads(sys.stdin.read()) # 可以把多行读进来

    train = data["train"]
    test = data["test"]

    X = np.array(train, dtype = float)
    T = np.array(test, dtype= float)

    # 计算训练集每一列的均值
    means = np.nanmean(X, axis = 0)

    # 使用训练均值填充训练集缺失值
    row, col = np.where(np.isnan(X))
    X[row, col] = means[col]

    # 使用相同的训练均值填充测试集缺失值
    row, col = np.where(np.isnan(T))
    T[row, col] = means[col]

    # 标准化，只在训练集上拟合
    scaler = StandardScaler() # 创建标准化器
    X_scaled = scaler.fit_transform(X) # 从 X 中获得 mu 和 sigma
    T_scaled = scaler.transform(T)     # 做标准化，不重新计算均值与标准差

    # PCA 只在训练集上训练
    pca = PCA(n_components=0.95, svd_solver="full") # 创建 PCA 对象
    pca.fit(X_scaled)  # 从标准化后数据中学习 PCA 规则

    # PCA 投影并重建
    # transform 使用 pca 已经学到的规则，把 X_scaled 转换到 PCA 空间
    # inverse_transform 再把PCA空间数据映射回来
    X_rebuild = pca.inverse_transform(pca.transform(X_scaled))
    T_rebuild = pca.inverse_transform(pca.transform(T_scaled))

    # 计算每个样本的重建误差
    train_error = np.sum((X_scaled - X_rebuild)**2, axis= 1)
    test_error = np.sum((T_scaled - T_rebuild)**2, axis=1)

    # 训练误差的 95% 分位数作为阈值
    threshold = np.percentile(train_error, 95)
    ans = (test_error > threshold).astype(int).tolist()
    print(json.dumps(ans))

if __name__ == "__main__":
    main()

sklearn 逻辑：

1
2
3
4
5
model = Something(...)  # 创建工具 / 设置超参数
model.fit(X)            # 从 X 学参数
model.transform(X)      # 用学到的参数转换 X
model.fit_transform(X)  # 先学，再转换 X
model.inverse_transform(Z) # 把转换后的数据尽量映射回原来的空间

科大讯飞

P5227.第1题-巡检通道覆盖补点

第1题-巡检通道覆盖补点 - problem_ide - CodeFun2000

核心思路：维护“从 0 开始已经连续覆盖到哪里”，不要混着节点和区间写

把所有已有节点转换成覆盖区间

1
[xi - ci, xi + ci]

并裁切到[0, L]

如果一个完全需要新节点覆盖的连续区间长度为

$$ \left\lceil\frac{t}{2D}\right\rceil $$
向上取整应该在分子加上分母-1 
1
(t + 2 * D - 1) // (2 * D)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def main():
    L, k, D = map(int, input().split())

    intervals = []

    for _ in range(k):
        x, c = map(int, input().split())

        left = max(0, x - c)
        right = min(L, x + c)

        intervals.append((left, right))

    intervals.sort() # 排序

    cur = 0
    ans = 0
    width = 2 * D

    for left, right in intervals:
        # 这个已有区间已经完全包含在当前覆盖范围内
        if right <= cur:
            continue

        # 当前覆盖还碰不到这个已有区间
        if left > cur:
            gap = left - cur

            cnt = (gap + width - 1) // width

            ans += cnt
            cur += cnt * width

        # 如果现在已经碰到这个已有区间，
        # 就利用已有区间免费向右延伸
        if left <= cur:
            cur = max(cur, right)

        if cur >= L:
            break

    # 最后还有尾部没覆盖
    if cur < L:
        gap = L - cur
        ans += (gap + width - 1) // width

    print(ans)


if __name__ == "__main__":
    main()

拼多多

P5211.第1题-平衡队伍

第1题-平衡队伍 - problem_ide - CodeFun2000

核心思路：转化成“最长和为 0 的连续子数组”，并利用前缀和记录最远idx

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def main():
    n = int(input())
    s = input()

    first = {0:0} # 前缀和为 0 最早出现在0
    prefix = 0
    ans = 0

    for i,c in enumerate(s, 1):
        if c == "A":
            prefix += 1
        else:
            prefix -= 1
        if prefix in first:
            ans = max(ans, i - first[prefix])
        else:
            first[prefix] = i

    print(ans)

if __name__ == "__main__":
    main()

P5212.第2题-评价展示序列

第2题-评价展示序列 - problem_ide - CodeFun2000

核心思路：从左到右构造答案，每一位都尽量放最小的数字，但放之前必须判断“放了它以后，剩下的数还能不能排成合法序列”

需要满足

$$ \max(cnt)\leq \left\lceil\frac n2\right\rceil $$ 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
def main():
    n = int(input())
    star = list(map(int, input().split()))

    cnt = [0] * 6
    for x in star:
        cnt[x] +=1

    if max(cnt) > (n+1)//2:
        print("-1")
        return
    def available(prev, remain):
        """
        已经放置了 prev，
        判断剩余 remain 个元素能否继续排列。
        """
        for x in range(1,6):
            if x == prev:
                # 下一位不能是 prev
                if cnt[x] > remain - cnt[x]:
                    return False
            else: # 普通数字允许比其他数字多一个
                if cnt[x] > remain - cnt[x] + 1: 
                    return False
        return True

    ans = []
    prev = 0

    for pos in range(n):
        for x in range(1,6):
            if cnt[x] == 0:
                continue
            if x == prev:
                continue
            # 尝试放 x
            cnt[x] -= 1
            remain = n - pos - 1

            if available(x, remain):
                ans.append(x)
                prev = x
                break

            # 不可行，恢复
            cnt[x] +=1

    print(*ans)

if __name__ == "__main__":
    main()

P5255.第2题-报文出站判定

第2题-报文出站判定 - problem_ide - CodeFun2000

重点：栈，理解都先往里放

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
def can_queue(u, v):
    return u == v

def can_stack(u, v):
    st = []
    j = 0
    for c in u:
        st.append(c)
        while st and j < len(v) and st[-1] == v[j]:
            st.pop()
            j+=1
    if j == len(v):
        return True
    return False

def main():
    U = input()
    V = input()
    is_queue = can_queue(U, V)
    is_stack = can_stack(U, V)
    if is_queue:
        print("both")
    elif is_stack:
        print("stack")
    else:
        print("neither")

if __name__ == "__main__":
    main()

P5256.第3题-工单最大收益

第3题-工单最大收益 - problem_ide - CodeFun2000

注意以工单作为编号做dp，初做时以时间为窗口做dp，复杂度太大

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
from bisect import bisect_right

def main():
    n = int(input())
    jobs = []
    for _ in range(n):
        start, end, val =map(int, input().split())
        jobs.append((start, end, val))
    # 按结束时间排序
    jobs.sort(key = lambda x:x[1])
    # dp[i] 表示前 i 个工单的最大收益
    dp = [0] * (n+1)
    # 所有结束时间
    ends = [e for _, e, _ in jobs]
    for i in range(1, n+1):
        start, end , val = jobs[i-1]
        # 在当前工单之前，寻找 end <= a 的工单数量
        j = bisect_right(ends, start, 0, i-1)
        # 选当前工单/ 不选当前工单
        dp[i] = max(
            dp[i-1],
            dp[j]+val
        )
    print(dp[n])

if __name__ == "__main__":
    main()

百度

P5216.第2题-最小对冲值

第2题-最小对冲值 - problem_ide - CodeFun2000

二进制整数有一个非常重要的关系

$$ a+b=(a\oplus b)+2(a\&b) $$
已知
$$ a+b = m $$
代入恒等式
$$ (a\oplus b)+2(a\&b) = m $$
得到目标
$$ a\oplus b=m-2(a\&b) $$
因为 m 值固定，所以求 `a&b` 的最大值

两个数越接近，其二进制高位越容易同时出现 1

如果 m 是偶数，那么答案必定是0

如果 m 是奇数，最接近的拆法就是

$$ m = 2k+1\qquad a=k\quad b=k+1 $$
即
$$ \boxed{\left\lfloor\frac m2\right\rfloor\oplus\left\lceil\frac m2\right\rceil} $$

P5217.第3题-报文置换归位

第3题-报文置换归位 - problem_ide - CodeFun2000

思路：置换拆成若干个环 → 每个环上的字符构成一个循环字符串 → 求每个循环字符串的最小周期 → 所有最小周期取 LCM

因为 p 是一个排列，所以它一定可以拆成若干个互不相交的 置换环

一次操作，本质上就是让这个环上的字符串循环移动一位

但重要的是不能直接用环长度，因为环上字符有可能相等，有可能在最小周期前已经复原

求一个字符串的最小周期可以使用 KMP 的 prefix function / 前缀函数

对于长度为 L 的字符串 s，设

$$ x=L-\pi[L-1] $$
$\pi[i]$：对字符串 $s[:i+1]$，从开头取一段、从结尾取一段，最长能有多少个字符完全一样，排除整个字符串本身

如果

$$ L\bmod x=0 $$
那么 $ \text{period}=x$ 否则 $\text{period}=L$

把所有的环找到以后计算每个环的最小周期，然后求最小公倍数 LCM

$$ \boxed{\operatorname{lcm}(a,b)=\frac{a\times b}{\gcd(a,b)}} $$
利用最大公约数函数 `math.gcd` 
1
ans = ans * period // gcd(ans, period) # 得到最小公倍数

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
from math import gcd

MOD = 10**9 + 7

def get_period(s):
    n = len(s)

    # 求pi数组
    pi = [0] * n

    for i in range(1, n):
        j = pi[i-1]

        # 当前字符匹配不上，就往前退
        while j>0 and s[i]!=s[j]:
            j = pi[j-1]
        # 匹配成功
        if s[i] == s[j]:
            j+=1
        pi[i] = j
    # 利用 pi 求最小周期
    period = n - pi[-1]
    if n%period == 0:
        return period
    else:
        return n

def main():
    n = int(input())
    u = input().strip()
    p = list(map(int, input().split()))
    # 改成 0~n-1
    p = [x-1 for x in p]
    visited = [False] * n

    ans =1

    for i in range(n):
        # 已经属于某个环了，就不用再找
        if visited[i]:
            continue
        # 找到一个新的环
        cur = i
        chars = []

        while not visited[cur]:
            visited[cur] = True
            # 记录这个位置的字符
            chars.append(u[cur])
            # 沿着排列走
            cur = p[cur]

        period = get_period(chars)
        ans = ans * period // gcd(ans, period)

    print(ans % MOD)

if __name__ == "__main__":
    main()

字节

P4808.第1题-最小喷灌范围

第1题-最小喷灌范围 - problem_ide - CodeFun2000

核心思路：从暴力做法优化，遍历覆盖，带二分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

def check(area, n, m, x):
    cnt = 0  # 喷的次数
    cover = 0 # 覆盖范围

    for i in range(1,n+1):
        if i<=cover:
            continue
        if area[i-1] == 1:
            cnt +=1
            cover = i+x-1
        if cnt > m:
            return False
    return True


def main():
    T = int(input())
    for _ in range(T):
        n, m = map(int, input().split())
        area = list(map(int, input().split()))
        if 1 not in area:
            print(0)
            continue
        # 已经确定 area 中至少有一个 1，
        # 所以 x 最小至少为 1
        left = 1
        right = n
        while left<right:
            mid = (left+right)//2
            if check(area, n, m, mid):
                right = mid
            else:
                left = mid+1
        # 二分结束时 left == right
        print(left)

if __name__ == "__main__":
    main()

滴滴

P5282.第2题-温感阵列巡检收益

第2题-温感阵列巡检收益 - problem_ide - CodeFun2000

LeetCode这道题的升级：面试题 17.24. 最大子矩阵 - 力扣（LeetCode）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
def solve(nums, min_length):
    """
    求一维数组中：
    连续子数组长度 >= min_length 时的最大子数组和
    """
    n = len(nums)
    # 数组长度不足要求长度，无法形成合法区间
    if n < min_length:
        return None
    # nums 前 i 个元素的和
    prefix_sum = [0] * (n+1)

    for i in range(n):
        prefix_sum[i+1] = prefix_sum[i] + nums[i]

    max_sum = float("-inf")
    # 当前允许作为区间左端点的最小前缀和
    min_prefix_sum = 0
    # 枚举区间右端点
    for right in range(min_length, n+1):
        max_sum = max(
            max_sum,
            prefix_sum[right] - min_prefix_sum
        )
        # 下一轮开始时，新增一个合法左端点
        left = right - min_length + 1
        min_prefix_sum = min(
            min_prefix_sum,
            prefix_sum[left]
        )
    return max_sum

def main():
    P, Q = map(int, input().split())
    matrix = []
    for _ in range(P):
        matrix.append(list(map(int, input().split())))
    ans = float("-inf")
    # 矩形高度是短边
    # 固定上下边界，把二维问题压缩成一维列和问题
    for top in range(P):
        # 表示当前行区间内第 j 列元素和
        col_sum = [0] * Q

        for bottom in range(top, P):
            # 扩展下边界，更新每列累计值
            for c in range(Q):
                col_sum[c] += matrix[bottom][c]

            h = bottom - top + 1
            max_sum = solve(col_sum, h)
            if max_sum is not None:
                ans = max(ans, max_sum * h)
    # 矩形宽度是短边
    # 固定左右边界，把问题转为行方向处理
    for left in range(Q):
        # 表示当前列区间内第 r 行元素和
        row_sum = [0] * P
        for right in range(left, Q):
            # 扩展右边界，更新每行累计值
            for r in range(P):
                row_sum[r] += matrix[r][right]
            w = right - left + 1

            max_sum = solve(row_sum, w)
            if max_sum is not None:
                ans = max(ans, max_sum * w)
    print(ans)

if __name__ == "__main__":
    main()

美团

P5326.第1题-色号喷涂最少次数

第1题-色号喷涂最少次数 - problem_ide - CodeFun2000

单调栈做法，写法不一定最优，但是好理解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def main():
    w = input()
    st = []
    ans = 0
    for c in w:
        while st and st[-1] > c: # 如果无法连续就出栈，加一次次数
            st.pop()
            ans +=1
        if st and st[-1] == c: # 相同的跳过
            continue
        st.append(c)
    if st:
        ans += len(st) # 补一下最后还在栈里的次数
    print(ans)
if __name__ == "__main__":
    main()

联想

联想两道题，一题dp，一道AI coding

合并区间形成单调

第1题-邻项合并归序 - problem_ide - CodeFun2000

第3题-潮位并段 - problem_ide - CodeFun2000

相邻合并 → 最终形成若干连续段 → 要求段与段之间满足单调关系 → 求最少合并次数

那么 最少合并次数 = n - 最大合法分段数

假设要求单调不减(<=)

前缀和

1
2
for x in arr:
    pre.append(pre[-1]+x)

任意区间的和：sum(i+1, j) = pre[j] - pre[i]

最朴素DP：dp[i][j] 前 i 个元素，最后一段从 j+1 开始，最多可以划分多少段

当前段为 

1
cur = pre[i] - pre[j]

需要找一个 k

  • 前面可以合法分段
  • 上一段不能比当前段大
1
last = pre[j] - pre[k]

需要满足 last <= cur 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
def min_merges(arr):
    n = len(arr)
    pre = [0]
    for x in arr:
        pre.append(pre[-1] + x)
    # dp[i][j]: 前i个元素，最后一段j开头，分多少段
	dp = [[0] * (n + 1) for _ in range(n + 1)]
    
    ans = 0

    for i in range(1, n + 1):
        for j in range(i):
            # 最后一段
            cur = pre[i] - pre[j]
            # 整体作为一段
            if j == 0:
                dp[i][j] = 1
                continue
            # 找上一段
            for k in range(j):
                last = pre[j] - pre[k]
                if dp[j][k] and last <= cur:  # 上一段有效划分
                    dp[i][j] = max(dp[i][j], dp[j][k] + 1)

    return n - max(dp[n])  # 得知合并次数
1
2
3
k        j        i
|--------|--------|
上一段      当前段

这种做法时间复杂度为O(n3)，会超时，得分在80左右

优化目标就是：不再枚举所有 k，而是快速找到满足条件的位置

根据上面的条件

$$ pre[j] + (pre[j]- pre[k]) \le pre[i] $$
也就是`pre[j] + last[j] <= pre[i]`，只需要找到最大的 j

定义最大合法位置 valid[i] 表示已经找到的最大合法分割位置 j

需要满足

$$ pre[i] \ge pre[j] + last[j] $$
直接二分 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
from bisect import bisect_left

def min_merges(arr):
    n = len(arr)
    pre = [0]
    for x in arr:
        pre.append(pre[-1] + x)

    # 最多可以划分多少个合法段
    dp = [0] * (n + 1)
    # 最后一段的和
    last = [0] * (n + 1)
    # 当前已知最大的合法分割位置
    valid = [0] * (n + 1)

    for j in range(1, n + 1):
        # 继承之前已经找到的最大合法分割位置
        valid[j] = max(valid[j], valid[j - 1])
        k = valid[j]

        dp[j] = dp[k] + 1 # 最大分段数+1

        last[j] = pre[j] - pre[k]
        target = last[j] + pre[j]

        i = bisect_left(pre, target, j + 1)

        if i <= n:
            valid[i] = max(valid[i], j)

    return n - dp[n]
1
2
3
k        j        i
|--------|--------|
当前段      下一段