比赛补题记录

推荐补题顺序：

第 6 题 → 第 4 题 → 第 8 题 → 第 7 题

  • 第 6 题：要求自己能够独立写出并 AC
  • 第 4 题：理解思路后能够独立实现
  • 第 8 题：重点学习核心转化，争取独立实现
  • 第 7 题：作为进阶图论题学习

第 6 题：未竟之志

时间限制：1 秒 | 空间限制：512 MB

题目描述

赛场上有 n 根钢栏杆从左到右排成一排，第 i 根钢栏杆的助推值为 a[i]。

在正式投出椅子之前，小鹿可以至多进行一次调整：选择一根钢栏杆，将它从原来的位置取出，再插入到当前序列的任意位置。调整后钢栏杆的相对顺序按新的排列确定。

随后小鹿会选择连续的 5 根钢栏杆作为助跑轨道，并获得这 5 根钢栏杆助推值之和的分数。

请你帮助小鹿求出，他能获得的最大分数。

输入格式

本题包含多组测试数据。第一行包含一个整数 T，表示测试数据的组数。

对于每组测试数据，第一行包含一个整数 n。第二行包含 n 个整数 a[1], a[2], …, a[n]，表示每根钢栏杆的助推值。

数据范围

  • 1 ≤ T ≤ 2 × 10⁵
  • 5 ≤ n ≤ 2 × 10⁵
  • -10⁹ ≤ a[i] ≤ 10⁹
  • 所有测试数据的 n 之和不超过 2 × 10⁵

输出格式

对于每组测试数据，输出一行一个整数，表示小鹿能获得的最大分数。

样例

输入

1
2
3
4
5
6
7
3
5
3 -4 6 1 2
6
100 100 -100 100 100 100
10
50 -100 -100 4 4 4 4 -100 -100 -100

输出

1
2
3
8
500
66

样例解释

第一组只有 5 根钢栏杆，无论如何调整最终都会选择全部钢栏杆，因此答案为：

1
3 + (-4) + 6 + 1 + 2 = 8

第二组可以将 -100 取出并插入到最右侧，使前 5 根钢栏杆均为 100，因此答案为 500。

第三组可以将最左侧的 50 插入四根连续的 4 旁边，因此答案为：

1
50 + 4 + 4 + 4 + 4 = 66

我的答案

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
package main

import "fmt"

func main() {
	// 首先输入组数
	var n int
	fmt.Scan(&n)
	group := make([][]int, n)

	// 然后输入每个组的长度和元素
	for i := 0; i < n; i++ {
		var m int
		fmt.Scan(&m)
		group[i] = make([]int, m)

		for j := 0; j < m; j++ {
			fmt.Scan(&group[i][j])
		}
	}

	// 开始操作
	for i := 0; i < n; i++ {
		answer := -1 << 60
		length := len(group[i])

		// 当长度刚好是 5 个的时候只能取这 5 个数
		if length == 5 {
			answer = group[i][0] + group[i][1] + group[i][2] + group[i][3] + group[i][4]
			fmt.Println(answer)
			continue
		}

		// 情况一：取连续 5 个元素
		l1, r1 := 0, 4
		sum1 := -1 << 60
		for r1 < length {
			current := group[i][l1] + group[i][l1+1] + group[i][l1+2] + group[i][l1+3] + group[i][l1+4]
			sum1 = max(sum1, current)
			l1++
			r1++
		}
		answer = max(answer, sum1)

		// 情况二：取连续 6 个数，并且去除其中的最小值
		sum2 := -1 << 60
		l2, r2 := 0, 5
		for r2 < length {
			current := group[i][l2] + group[i][l2+1] + group[i][l2+2] + group[i][l2+3] + group[i][l2+4] + group[i][l2+5]
			minnum := Minnum(group[i][l2 : l2+6])
			current -= minnum
			sum2 = max(sum2, current)
			l2++
			r2++
		}
		answer = max(answer, sum2)

		// 情况三：取连续 4 个数，再加上这个区间之外的最大值
		a := group[i]

		// 前缀最大值
		prefixMax := make([]int, length)
		prefixMax[0] = a[0]
		for j := 1; j < length; j++ {
			prefixMax[j] = max(prefixMax[j-1], a[j])
		}

		// 后缀最大值
		suffixMax := make([]int, length)
		suffixMax[length-1] = a[length-1]
		for j := length - 2; j >= 0; j-- {
			suffixMax[j] = max(suffixMax[j+1], a[j])
		}

		sum3 := -1 << 60
		l3, r3 := 0, 3
		for r3 < length {
			current := group[i][l3] + group[i][l3+1] + group[i][l3+2] + group[i][l3+3]
			maxnum := Maxnum(prefixMax, suffixMax, l3, r3)
			current += maxnum
			sum3 = max(sum3, current)
			l3++
			r3++
		}
		answer = max(answer, sum3)

		fmt.Println(answer)
	}
}

func Minnum(group []int) int {
	minnum := 1 << 60
	for _, v := range group {
		minnum = min(minnum, v)
	}
	return minnum
}

func Maxnum(prefixMax, suffixMax []int, l, r int) int {
	maxnum := -1 << 60

	if l > 0 {
		maxnum = max(maxnum, prefixMax[l-1])
	}

	if r+1 < len(suffixMax) {
		maxnum = max(maxnum, suffixMax[r+1])
	}

	return maxnum
}

第 4 题：档案分册

时间限制：1 秒 | 空间限制：512 MB

题目描述

档案馆按时间先后保存了 n 条记录，依次编号为 1, 2, …, n。第 i 条记录属于编号为 c[i] 的案件，材料页数为 w[i]。

你需要将这些记录依次划分为恰好 k 册档案。每册档案必须包含一段非空且连续的记录，所有档案册按照顺序覆盖全部记录。同时，同一案件的所有记录必须在同一册档案中。

一册档案的页数定义为其中所有记录的 w[i] 之和。

请求最小化页数最多的一册的页数。如果无法满足上述要求，输出 -1。

输入格式

第一行包含两个整数 n 和 k，分别表示记录条数和需要划分的档案册数。

接下来 n 行，第 i 行包含两个整数 c[i] 和 w[i]，表示第 i 条记录的案件编号和材料页数。

数据范围

  • 1 ≤ n ≤ 2 × 10⁵
  • 1 ≤ k ≤ n
  • 1 ≤ c[i] ≤ n
  • 1 ≤ w[i] ≤ 10⁹
  • ∑ w[i] ≤ 2 × 10¹⁴

输出格式

如果不存在合法划分，输出：

1
-1

否则输出所有合法划分中，页数最多的一册的最小页数。

样例 1

输入

1
2
3
4
5
6
7
8
9
8 3
1 2
2 1
1 3
3 4
4 2
4 5
5 1
6 6

输出

1
10

样例 2

输入

1
2
3
4
5
6
5 3
1 1
2 1
1 1
2 1
3 1

输出

1
-1

样例 3

输入

1
2
3
4
3 3
1 4
2 1
3 1

输出

1
4

我的答案

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
package main

import "fmt"

func main() {
	var n, k int
	fmt.Scan(&n, &k)

	nums := make([][2]int, n)
	for i := 0; i < n; i++ {
		fmt.Scan(&nums[i][0], &nums[i][1])
	}

	// 记录每个案件出现的最右位置
	hashmap := make(map[int]int)
	for i := 0; i < n; i++ {
		hashmap[nums[i][0]] = i
	}

	// 合并所有不能拆开的记录，得到原子块
	newnums := []int{}
	for i := 0; i < n; i++ {
		sum := 0
		right := hashmap[nums[i][0]]

		for j := i; j <= right; j++ {
			sum += nums[j][1]
			right = max(right, hashmap[nums[j][0]])
		}

		newnums = append(newnums, sum)
		i = right
	}

	if len(newnums) < k {
		fmt.Println(-1)
		return
	}

	maxnum, sum := 0, 0
	for i := 0; i < len(newnums); i++ {
		maxnum = max(maxnum, newnums[i])
		sum += newnums[i]
	}

	// 二分每册允许的最大页数
	left, right := maxnum, sum
	for left < right {
		mid := left + (right-left)/2

		// 贪心计算最大页数为 mid 时最少需要多少册
		currentsum := 0
		count := 1
		for i := 0; i < len(newnums); i++ {
			if currentsum+newnums[i] > mid {
				count++
				currentsum = newnums[i]
			} else {
				currentsum += newnums[i]
			}
		}

		if count > k {
			left = mid + 1
		} else {
			right = mid
		}
	}

	fmt.Println(left)
}

第 8 题：环序成林

时间限制：1 秒 | 空间限制：512 MiB

题目描述

有 n 个编号为 1, 2, …, n 的通信站，站点之间的 n - 1 条双向线路构成一棵树。

你可以选择一个站点 s 作为起点。第 1 天，站点 s 上线；此后每天恰有一个新站点上线，并按照下面的顺序进行：

1
s, s+1, ..., n, 1, 2, ..., s-1

也就是说，第 t 天上线的站点编号为：

1
((s + t - 2) mod n) + 1

在每一天，两端都已经上线的线路会投入使用。已经上线的站点和投入使用的线路组成当天的在线网络。

第 t 天，在线网络的每个连通块都要向当天的每个在线站点各发送一份同步报告。由于当天共有 t 个在线站点，如果在线网络有 C 个连通块，当天就会产生：

1
t × C

份报告。

对于每个可能的起点 s，考虑 n 天内产生的报告总数。

求：

  1. 报告总数的最小值；
  2. 能够取得这个最小值的起点个数。

输入格式

第一行包含一个整数 n，表示通信站的数量。

接下来 n - 1 行，每行包含两个整数 u[i] 和 v[i]，表示站点 u[i] 和站点 v[i] 之间有一条双向线路。

输入保证这 n - 1 条线路构成一棵树。

数据范围

  • 1 ≤ n ≤ 2 × 10⁵
  • 1 ≤ u[i], v[i] ≤ n
  • u[i] ≠ v[i]
  • 输入的 n - 1 条线路构成一棵树
  • 报告总数小于 3 × 10¹⁵

其中：

1
1² + 2² + ... + n² = n(n+1)(2n+1) / 6 < 3 × 10¹⁵

输出格式

输出一行两个整数，依次表示：

1
报告总数的最小值  取得最小值的起点个数

样例 1

输入

1
2
3
4
4
1 3
2 3
3 4

输出

1
10 2

样例解释

起点依次为 1, 2, 3, 4 时，报告总数分别为：

1
12, 10, 10, 18

因此最小值为 10，有 2 个起点可以取得它。

样例 2

输入

1
1

输出

1
1 1

第 7 题：王国驿道

时间限制：2 秒 | 空间限制：512 MB

题目描述

P 国有 n 座城市，编号为 1, 2, …, n。城市之间建有双向驿道，且任意两座城市之间均可以通过若干条驿道互相到达。

每条驿道都有一个非负的维护费用。由于某种神奇的原因，通过一条驿道所需的通行时间与它的维护费用在数值上相等。

国王认为现有驿道过于冗余，想仅保留其中的一部分驿道以削减维护费用。

对于一份保留驿道的方案，国王提出两个要求：

  1. 任意两座城市之间均可以通过保留的驿道互相到达，且在所有满足该条件的方案中，当前方案的维护费用总和必须最小。
  2. 若 P 国首都为城市 u，则从城市 u 出发，仅通过保留的驿道到达任意城市 v 的最短通行时间，必须等于保留全部驿道时从城市 u 到城市 v 的最短通行时间。

需要判断：当首都 u 分别为城市 1, 2, …, n 时，是否存在一种保留驿道的方案满足上述两个要求。

输入格式

本题包含多组测试数据。

第一行包含一个整数 T，表示测试数据的组数。

对于每组测试数据，第一行包含一个正整数 n。

接下来 n 行，第 i 行包含 n 个整数：

1
a[i][1], a[i][2], ..., a[i][n]

若 a[i][j] = -1，表示城市 i 与城市 j 之间不存在驿道；否则 a[i][j] 表示城市 i 与城市 j 之间驿道的维护费用。

数据范围

  • 1 ≤ T ≤ 500
  • 所有测试数据的 n 之和 ≤ 500
  • -1 ≤ a[i][j] ≤ 10⁶
  • a[i][i] = 0
  • a[i][j] = a[j][i]
  • 任意两座城市之间均可以通过若干条驿道互相到达

输出格式

对于每组测试数据，输出一行长度为 n 的 01 串。

若以城市 i 为首都时存在合法方案，则第 i 个字符为 1，否则为 0。

样例

输入

1
2
3
4
5
6
7
8
9
10
11
2
3
0 2 3
2 0 2
3 2 0
5
0 4 6 0 3
4 0 5 -1 1
6 5 0 2 3
0 -1 2 0 -1
3 1 3 -1 0

输出

1
2
010
10110

注意：第 7 题第二组样例输入是根据比赛现场照片整理的，其中部分数字在照片中不够清晰。正式补这道题时，建议与官方原题核对这一组样例。