字节笔试 20210321

这场笔试是真的难，而且严格来说，四道题都算动态规划……

第一题

一群贪婪的猴子，每个猴子会尽可能多地拿香蕉，但最多只能拿自己食量的二倍，并且不能拿超过剩余香蕉的一半的数量。

根据题目，有如下条件（tt 为当前猴子拿的数量，mm 为可供后续猴子分配的数量，a[i]a[i] 为当前猴子的食量）

  • 最多拿剩余数量的一半: t≤(t+m)/2⇒t≤mt \le (t+m)/2 \Rightarrow t \le m
  • 最多拿食量的两倍: t≤2×a[i]t \le 2 \times a[i]
  • 最少拿食量数量: t≥a[i]t \ge a[i]
  • 猴子会尽可能多拿

也即 a[i]≤t≤min{2×a[i],m}a[i] \le t \le min\{2 \times a[i], m\}

两种思路

  • O(n)O(n) 的逆序倒推
  • O(nlog2n)O(nlog_2n) 的二分

先说二分，枚举香蕉总数，判断能否满足猴子们的需要。如果可以满足，则答案必然小于等于当前枚举值；否则大于。根据二分搜索的结果，将答案确定到第一个满足的数即可。
该思路较为直观，check() 函数只需要按照猴子习性，在满足条件的情况下尽可能贪婪地拿即可。难点在于能不能正确手撸二分，不过考虑到诸如 Go 之类的语言里，存在可自定义判断函数的 sort.Search()，所以二分不属于难点。

逆序倒退思路为最后一个猴子只给它食量范围的香蕉。而后针对每个猴子，判断当前猴子拿后香蕉总数 mm（后续猴子可分配的香蕉），当前猴子的食量 a[i]a[i]

  • 如果 m>2×a[i]m>2 \times a[i]，可得 a[i]≤t≤2×a[i]<ma[i] \le t \le 2 \times a[i] \lt m，说明猴子已经按照最大值（2×a[i]2 \times a[i]）拿了
  • 如果 m>a[i]m > a[i]，可得 a[i]≤t≤m<2×a[i]a[i] \le t \le m \lt 2 \times a[i]，说明猴子按照 mm 拿
  • 其余情况说明 a[i]>ma[i] > m，不满足上面的情况，说明应该把一部分香蕉补给最后一个猴子，更新 m=2×a[i]m=2 \times a[i]
def s1(n, arr):
    def check(m):
        '''
        判断 m 个香蕉能否满足所有猴子
        '''
        for idx, a in enumerate(arr):
            # 最后一个猴子可以无限拿
            if idx == n - 1:
                continue

            # 当前猴子能拿的最大值
            t = min(a * 2, m / 2)

            if a > t:
                # 香蕉不够猴子吃
                return False
            m -= t

        return m >= arr[n-1]  # 剩下的香蕉足够最后一个猴子吃

    def binarySearch(n):
        l = 0
        r = n
        while r >= l:
            mid = l + (r - l) // 2
            # print(mid, check(mid))
            if check(mid):
                r = mid-1
            else:
                l = mid + 1
        return l

    return binarySearch((sum(arr) + 1) * 2)


def s2(n, arr):

    m = arr[n-1]

    for i in range(n - 2, -1, -1):
        # 当前猴子最多拿剩余总数的一半 (2 * dp[i+1])
        # 最少拿 arr[i]
        # 尽可能拿 2 * arr[i]

        if m > 2 * arr[i]:
            # 拿之后，香蕉总数仍然超过了当前食量的 2 倍
            # 猴子在尽可能多拿的情况下，会拿食量 2 倍
            m += 2 * arr[i]
        elif m > arr[i]:
            # 拿之后，香蕉总数位于猴子 食量 ~ 2倍食量 之间
            # 猴子会拿一半
            m *= 2
        else:
            # 拿之后，香蕉总数少于食量
            m = 2 * arr[i]

    return m


arr = list(map(int, input().split(" ")))
n = len(arr)

print(s1(n, arr), s2(n, arr))

第二题

有 nn 个蛋糕，每个蛋糕的美味度是 a[i]a[i]，最多选 mm 个连续蛋糕，求选择蛋糕的美味度最大值（美味度可能是复数）

洛谷 P1714.切蛋糕

由于需要计算一个连续区间的数值之和，因此需要预计算前缀和，这样就可以在 O(1)O(1) 的时间内求出 [i,j][i,j] 区间的和 sum[j]−sum[i]+a[i]sum[j] - sum[i] + a[i]。其中 sum[i]sum[i] 表示所有小于等于 ii 的和
显然，需要求的结果就是 max{sum[r]−sum[l]+a[l]},0≤l≤r<nmax\{sum[r] - sum[l] + a[l]\},0 \le l \le r \lt n

如果简单的遍历 ll 和 rr 显然会超时，但是注意到在 sum[r]sum[r] 确定时，ll 必然小于等于 rr，要使结果取最大，应该使得 sum[l]−a[l]sum[l]-a[l] 取最小。而这个值可以在遍历时顺手统计，因此实际上时间复杂度为 O(n)O(n)

总体思路为，遍历的同时维护 sum[l]−a[l]sum[l]-a[l] 的最小值（需要记录 ll 的下标，当超过距离 mm 时应该将其移除）。可以使用小顶堆维护这个数据结构。

这道题可以在洛谷补，但是洛谷输入数据问题很大，各种奇怪的空格、空行……建议测试时充分考虑各种奇怪的输入

下面提供一份 Python 和一份 Go 的代码（Python 没有完全通过洛谷的数据……但是我导出了下数据也没明白为啥 MLE）

import heapq

def solve(n, m, a):
    if n == 0 or m == 0:
        return 0
    # 前 i 个蛋糕的最大美味度: sum[i] - min{ sum[j] + a[j] }

    # 预处理前缀和
    sm = [0 for i in range(n)]
    sm[0] = a[0]
    for i in range(1, n):
        sm[i] = sm[i - 1] + a[i]

    q = []

    res = 0
    for i in range(0, n):
        while len(q) != 0 and i - q[0][1] + 1 > m:
            heapq.heappop(q)

        if len(q) == 0:
            res = max(res, sm[i])
        else:
            res = max(res, sm[i] - q[0][0], a[i])
        heapq.heappush(q, (sm[i]-a[i], i))
    return res

def main():
    n, m = list(map(int, input().split()))
    if n != 0:
        a = list(map(int, input().split()))
    else:
        a = []
    if n != len(a):
        print(n,len(a))
    print(solve(n, m, a))

if __name__ == '__main__':
    try:
        while True:
            main()
    except EOFError as e:
        pass
    except Exception as e:
        print(e.with_traceback())

package main

import (
	"bufio"
	"fmt"
	"os"
	"strconv"
	"strings"
)

var in = bufio.NewReader(os.Stdin)

func ReadInts() ([]int, error) {
	line, err := in.ReadString('\n')
	if len(line) == 0 && err != nil {
		return []int{}, err
	}

	ss := strings.Split(
		strings.TrimSpace(line),
		" ",
	)
	res := make([]int, 0, len(ss))
	for _, s := range ss {
		num, _ := strconv.ParseInt(s, 10, 64)
		res = append(res, int(num))
	}
	return res, nil
}

type Obj struct {
	Index int
	Value int
}

// type Heap []Obj

// func (h Heap) Len() int           { return len(h) }
// func (h Heap) Less(i, j int) bool { return h[i].Value < h[j].Value }
// func (h Heap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }
// func (h *Heap) Push(x interface{}) {
// 	*h = append(*h, x.(Obj))
// }

// func (h *Heap) Pop() interface{} {
// 	old := *h
// 	n := len(old)
// 	x := old[n-1]
// 	*h = old[0 : n-1]
// 	return x
// }

// func (h Heap) Top() Obj { return h[0] }

//复杂度  O(logn)
type MinHeap struct {
	Size  int
	Items []Obj
}

func NewHeap(max int) *MinHeap {
	return &MinHeap{Items: make([]Obj, max), Size: 0}
}

func (heap *MinHeap) Push(item Obj) {
	heap.Items[heap.Size] = item
	heap.Size++
	t := heap.Size - 1
	for t > 0 {
		p := (t - 1) / 2
		if heap.Items[p].Value > heap.Items[t].Value {
			heap.Items[p], heap.Items[t] = heap.Items[t], heap.Items[p]
			t = p
		} else {
			break
		}
	}
}

func (heap *MinHeap) Pop() (item Obj) {
	item = heap.Items[0]
	heap.Items[0] = heap.Items[heap.Size-1]
	heap.Size--

	p := 0
	for p < heap.Size {
		l := p*2 + 1
		r := l + 1
		t := p
		if l < heap.Size && heap.Items[l].Value < heap.Items[t].Value {
			t = l
		}
		if r < heap.Size && heap.Items[r].Value < heap.Items[t].Value {
			t = r
		}
		if p != t {
			heap.Items[p], heap.Items[t] = heap.Items[t], heap.Items[p]
			p = t
		} else {
			break
		}
	}
	return
}

func (q *MinHeap) Top() Obj {
	return q.Items[0]
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func solve(n, m int, a []int) int {
	// os.Stderr.WriteString(fmt.Sprintf("%d %d\n", n, m))
	if n == 0 || m == 0 {
		return 0
	}

	// 前 i 个蛋糕的最大美味度: sum[i] - min{ sum[j] + a[j] }
	// 预处理前缀和
	sm := make([]int, n)
	sm[0] = a[0]
	for i := 1; i < n; i++ {
		sm[i] = sm[i-1] + a[i]
	}
	// q := &Heap{}
	// heap.Init(q)
	q := NewHeap(n)

	res := 0
	for i := 0; i < n; i++ {
		for q.Size != 0 && i-q.Top().Index+1 > m {
			q.Pop()
		}

		if q.Size == 0 {
			res = max(res, sm[i])
		} else {
			res = max(res, max(sm[i]-q.Top().Value, a[i]))
		}
		q.Push(
			Obj{
				Value: sm[i] - a[i],
				Index: i,
			},
		)
	}

	return res
}

func main() {
	for {
		arr, err := ReadInts()
		if err != nil {
			break
		}

		n, m := arr[0], arr[1]
		var a []int
		if n != 0 {
			a, err = ReadInts()
			if err != nil {
				break
			}
		} else {
			a = []int{}
		}

		fmt.Println(solve(n, m, a))
	}
}

第三题

将一个数，通过三种不同的操作变成 nn 求最小花费

  • i=i×2i=i \times 2，消耗为 aa
  • i=i+1i=i+1，消耗为 bb
  • i=i−1i=i-1，消耗为 bb

nn 最大为 1e171e17

Codeforces 710.E Generate a String

据说笔试里，最大值范围为 1e171e17，不过如果真是这么大的数，应该没有什么不超时的算法。（笔试的 aa 和 bb 与 Codeforces 的 xx 和 yy 是相反的）

大概思路是，从 00 逼近 nn，第一步必然是从 00 到 11。

而后面考虑如下逼近策略，由于 i>1i \gt 1，因此除去单独的减一操作外，其余的操作均为变大操作

  • 直接加 11: (i+1)−i=1(i+1)-i=1
  • 直接乘 22: (i∗2)−i=i(i*2)-i=i
  • 减 11 乘 22: ((i−1)×2)−i=i−2((i-1) \times 2) - i = i-2
  • 加 11 乘 22: ((i+1)×2)−i=i+2((i+1)\times 2)-i=i+2
  • 乘 22 减 11: (i∗2−1)−i=i−1(i*2-1)-i=i-1
  • 乘 22 加 11: (i∗2+1)−i=i+1(i*2+1)-i=i+1

有如下转移方程
dp[i]={dp[i−1]+x加 1dp[i/2]+y乘 2dp[i/2+1]+x+y=dp[i/2]+y先减 1 再乘 2dp[i/2−1]+x+y=dp[i/2]+y先加 1 再乘 2dp[(i+1)/2]+x+y=dp[i+1]+x先乘 2 再减 1dp[(i−1)/2]+x+y=dp[i−1]+x先乘 2 再加 1={min{dp[i−1]+x,dp[(i−1)/2]+x+y}i是奇数min{dp[i−1]+x,dp[i/2]+y,dp[i/2−1]+x+y}i是偶数 dp[i] = \begin{cases} dp[i-1] + x & & \text{加 1} \\ dp[i/2] + y & & \text{乘 2} \\ dp[i/2+1] + x + y &= dp[i/2] + y & \text{先减 1 再乘 2} \\ dp[i/2-1] + x + y &= dp[i/2] + y & \text{先加 1 再乘 2} \\ dp[(i+1)/2] + x + y &= \bold{dp[i+1] + x} & \text{先乘 2 再减 1} \\ dp[(i-1)/2] + x + y &= dp[i-1] + x & \text{先乘 2 再加 1} \\ \end{cases} = \begin{cases} min\{dp[i-1]+x, dp[(i-1)/2]+x+y\} & i \text{是奇数} \\ min\{dp[i-1]+x, dp[i/2]+y, dp[i/2-1]+x+y\} & i \text{是偶数} \end{cases} 可以看到，除去 dp[i+1]+xdp[i+1]+x 外，其余操作均可以由之前的状态转移来，因此需要将 dp[i+1]+xdp[i+1]+x 从 dp[(i+1)/2]+x+ydp[(i+1)/2] + x + y 转移

Codeforces 上 Go 默认是 int32，需要手动改成 int64 否则会溢出，且 Python 由于本身效率问题会超时

package main

import (
	"fmt"
)

func min(a, b int64) int64 {
	if a < b {
		return a
	}
	return b
}

func main() {
	var n, x, y int64
	fmt.Scanf("%d%d%d", &n, &x, &y)

	dp := make([]int64, (n + 1))
	dp[0] = 0
	dp[1] = x

	for i := int64(2); i < n + 1; i++ {
		if i&1 != 0 {
			// 奇数
			// 从 i-1 更新 或 从 (i + 1) / 2 更新
			dp[i] = min(dp[i - 1] + x, dp[(i + 1) / 2] + x + y) 
        } else {
			// 偶数
			// 从 i-1 更新 或 从 i / 2 更新
			dp[i] = min(dp[i / 2] + y, dp[i - 1] + x)
		}
	}
	fmt.Println(dp[n])
}

第四题

有两个字符串 SS 和 TT，其中 TT 长度固定为 22。拥有 kk 次修改机会，可以修改 TT 字符串的一个字符（修改机会不需要用完）

求 SS 有多少个子序列（不需要连续），刚好为修改后的 TT

Codeforces 1409.F Subsequences of Length Two

首先分两种情况讨论

  • t[0]=t[1]=ct[0]=t[1]=c
    • 若 ss 中有 kk 个字符 cc，那么子序列个数为 Ck2=k×(k−1)2C^2_k=\frac{k \times (k-1)}{2}
  • t[0]≠t[1]t[0] \ne t[1]
    • 当 s[i]=t[1]s[i]=t[1] 时，对应的结果应该为 s[:i]s[:i] 中，t[0]t[0] 出现的次数 加上 i−1i-1 的结果
    • 也即 dp[i]=dp[i−1]+count[i]dp[i] = dp[i-1] + count[i]

由于可以修改，因此需要考虑有哪些状态需要讨论:

  • 当前处理的字符序号 ii
  • 已使用的修改次数 jj
  • 当前位置前 t[0]t[0] 的个数 kk

当位于 dp[i][j][k]dp[i][j][k] 时，可以有如下几种操作:

  • 当前字符与 tt 无关，且不变: dp[i][j][k]→dp[i+1][j][k]dp[i][j][k] \rarr dp[i+1][j][k]
  • 变换为 t[0]t[0]: dp[i][j][k]→dp[i+1][j−1][k+1]dp[i][j][k] \rarr dp[i+1][j-1][k+1]
  • 变换为 t[1]t[1]: dp[i][j][k]+k→dp[i+1][j−1][k]dp[i][j][k] + k \rarr dp[i+1][j-1][k]
  • s[i]=t[0]s[i]=t[0]: dp[i][j][k]→dp[i+1][j][k+1]dp[i][j][k] \rarr dp[i+1][j][k+1]
  • s[i]=t[1]s[i]=t[1]: dp[i][j][k]+k→dp[i+1][j][k]dp[i][j][k] + k \rarr dp[i+1][j][k]
n, m = list(map(int, input().split(" ")))
s = input()
t = input()

if t[0] == t[1]:
    count = 0
    for c in s:
        if t[0] == c:
            count += 1
    count = min(n, count + m)
    print(int(count * (count-1) / 2))
else:
    dp = [[[-1 for k in range(n+5)] for j in range(m+5)] for i in range(n+5)]

    dp[0][0][0] = 0
    for i in range(n):
        for j in range(m+1):
            for k in range(n + 1):
                if dp[i][j][k] == -1:
                    continue
                if s[i] == t[1]:
                    # 与第二个字符相同

                    # 不需要修改，更新结果
                    dp[i + 1][j][k] = max(
                        dp[i + 1][j][k],
                        dp[i][j][k] + k,
                    )

                if s[i] == t[0]:
                    # 与第一个字符相同

                    # 不需要修改，更新 k
                    dp[i + 1][j][k + 1] = max(
                        dp[i + 1][j][k + 1],
                        dp[i][j][k],
                    )

                # 修改为 t[0], 更新 k
                dp[i + 1][j + 1][k + 1] = max(
                    dp[i + 1][j + 1][k + 1],
                    dp[i][j][k],
                )

                # 修改为 t[1]，更新结果
                dp[i + 1][j + 1][k] = max(
                    dp[i + 1][j + 1][k],
                    dp[i][j][k] + k,
                )

                # 不更新，直接赋值
                dp[i + 1][j][k] = max(
                    dp[i + 1][j][k],
                    dp[i][j][k],
                )

    res = 0
    for j in range(m + 1):
        for k in range(n + 1):
            res = max(res, dp[n][j][k])

    print(res)