字节笔试 20210321

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

第一题

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

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

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

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

两种思路

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

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

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

• 如果 $m>2 \times a[i]$，可得 $a[i] \le t \le 2 \times a[i] \lt m$，说明猴子已经按照最大值（$2 \times a[i]$）拿了
• 如果 $m > a[i]$，可得 $a[i] \le t \le m \lt 2 \times a[i]$，说明猴子按照 $m$ 拿
• 其余情况说明 $a[i] > m$，不满足上面的情况，说明应该把一部分香蕉补给最后一个猴子，更新 $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))

第二题

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

洛谷 P1714.切蛋糕

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

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

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

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

下面提供一份 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))
	}
}

第三题

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

• $i=i \times 2$，消耗为 $a$
• $i=i+1$，消耗为 $b$
• $i=i-1$，消耗为 $b$

$n$ 最大为 $1e17$

Codeforces 710.E Generate a String

据说笔试里，最大值范围为 $1e17$，不过如果真是这么大的数，应该没有什么不超时的算法。（笔试的 $a$ 和 $b$ 与 Codeforces 的 $x$ 和 $y$ 是相反的）

大概思路是，从 $0$ 逼近 $n$，第一步必然是从 $0$ 到 $1$。

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

• 直接加 $1$: $(i+1)-i=1$
• 直接乘 $2$: $(i*2)-i=i$
• 减 $1$ 乘 $2$: $((i-1) \times 2) - i = i-2$
• 加 $1$ 乘 $2$: $((i+1)\times 2)-i=i+2$
• 乘 $2$ 减 $1$: $(i*2-1)-i=i-1$
• 乘 $2$ 加 $1$: $(i*2+1)-i=i+1$

有如下转移方程
$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]+x$ 外，其余操作均可以由之前的状态转移来，因此需要将 $dp[i+1]+x$ 从 $dp[(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])
}

第四题

有两个字符串 $S$ 和 $T$，其中 $T$ 长度固定为 $2$。拥有 $k$ 次修改机会，可以修改 $T$ 字符串的一个字符（修改机会不需要用完）

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

Codeforces 1409.F Subsequences of Length Two

首先分两种情况讨论

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

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

• 当前处理的字符序号 $i$
• 已使用的修改次数 $j$
• 当前位置前 $t[0]$ 的个数 $k$

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

• 当前字符与 $t$ 无关，且不变: $dp[i][j][k] \rarr dp[i+1][j][k]$
• 变换为 $t[0]$: $dp[i][j][k] \rarr dp[i+1][j-1][k+1]$
• 变换为 $t[1]$: $dp[i][j][k] + k \rarr dp[i+1][j-1][k]$
• $s[i]=t[0]$: $dp[i][j][k] \rarr dp[i+1][j][k+1]$
• $s[i]=t[1]$: $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)