2021 TPC 腾讯程序设计竞赛 第一季
第一季赛程：4 月 6-11 日赛前体验，4 月 13 日周二晚 19-21 点第一场比赛，4 月 20 日周二晚 19-21 点第二场比赛。
| 名称 | 编号 | 备注 | 题解 |
|---|---|---|---|
| A. Beautiful Sequence（美丽序列） | 题解见下 | ||
| B. Chocolate Bars（巧克力棒） | 题解见下 | ||
| C. Perfect Square（完全平方数） | 题解见下 | ||
| D. Ants（蚂蚁） | |||
| E. Numbers on the Chessboard（棋盘上的数字） | |||
| A. Strange Sorting（奇怪的排序） | |||
| B. Number of Zeros（零的个数） | |||
| C. Minimum Spanning Tree（最小生成树） | 题解见下 | ||
| D. Divisible Continuous Subsequence（可整除连续子序列） | |||
| E. Arrange the Matrices（排列矩阵） |
第 1 题：A. Beautiful Sequence（美丽序列）
题面
1-A Beautiful Sequence（美丽序列）
题目描述
一个序列 $b_1,b_2,\cdots,b_n$ 是美丽序列当对于所有 $1 \le i<n$ 有 $b_i \times b_{i+1} \le 0$。
给定一个整数序列 $a_1,a_2,\cdots,a_n$，问是否可以通过重新排列其中的元素使其变为美丽序列。
输入
有多组测试数据。第一行输入一个整数 $T$ 代表测试数据组数。对于每组测试数据：
第一行输入一个整数 $n$（$2 \le n \le 10^5$）表示序列的长度。
第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$（$−10^9 \le a_i \le 10^9$）表示序列的元素。
保证所有数据 $n$ 之和不超过 $10^6$。
输出
每组数据输出一行。若可以通过重新排列使得序列变为美丽序列输出 "Yes"（不输出引号）；否则输出 "No"（不输出引号）。
做法 1
记录负数的个数 $\mathrm{cnt\_ne}$、零的个数 $\mathrm{cnt\_0}$ 和正数的个数 $\mathrm{cnt\_po}$。显然不能有两个连续的正数或两个连续的负数，则当且仅当 $\mathrm{cnt\_ne}+\mathrm{cnt\_0} \ge \mathrm{cnt\_po}-1$ 且 $\mathrm{cnt\_po}+\mathrm{cnt\_0} \ge \mathrm{cnt\_ne}-1$ 时，可以构造出“美丽数列”。
第 2 题：B. Chocolate Bars（巧克力棒）
题面
1-B Chocolate Bars（巧克力棒）
题目描述
您有 $n$ 根长度为整数的巧克力棒，长度依次为 $a_1,a_2,\cdots,a_n$。您想要选择其中一根巧克力棒，并将它分成两根长度均为整数且更短的巧克力棒，使得最后得到的 $(n+1)$ 根巧克力棒长度互不相同。求有几根巧克力棒可被选择。
更正式地，给定 $n$ 个整数 $a_1,a_2,\cdots,a_n$，您需要选择两个整数 $k$ 和 $x$ 使得
- $1 \le k \le n$ 且 $1 \le x < a_k$；
- $a_1,a_2,\cdots,a_{k-1},x,a_k−x,a_{k+1},\cdots,a_n$ 互不相同。
求有多少个不同的 $k$ 可以选择。
输入
有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 50$）代表测试数据组数。对于每组测试数据：
第一行输入一个整数 $n$（$1 \le n \le 10^5$）表示巧克力棒的数量。
第二行输入 $n$ 个整数 $a_1,a_2,\cdots,a_n$（$1 \le $a_i$ \le 1000$）表示巧克力棒的长度。
保证所有数据 $n$ 之和不超过 $10^6$。
输出
每组数据输出一行一个整数，表示可以被选择的巧克力棒的数量。
做法 1
由于 $1 \le a_i \le 1000$，根据抽屉原理，当 $n>1000$ 时，必然有两个巧克力棒长度相同，答案为 $0$。
这样，$n$ 的范围就限定在 $[1,1000]$ 的范围内，可以使用 $O(n^2)$ 的朴素算法。
需要注意以下几点：
- 多组数据，注意变量初始化；
- 当有多种（$2$ 种及以上）长度的木棒的数量大于 $1$ 或者有一种长度的木棒的长度大于 $2$，无论拆分哪一个巧克力棒，都会有两根巧克力棒长度相同，答案为 $0$。
第 3 题：C. Perfect Square（完全平方数）
题面
1-C Perfect Square（完全平方数）
题目描述
给定两个整数 $n$ 与 $k$，请构造一个长度为 $n$ 的整数序列 $a_1,a_2,\cdots,a_n$（$1 \le a_i \le 10^5$）使得满足以下要求的二元组 $(i,j)$ 的数量恰为 $k$：
- $1 \le i<j \le n$，且
- $(a_i+a_j)$ 是完全平方数
请回忆：完全平方数是一个整数，其平方根也是整数。
输入
有多组测试数据。第一行输入一个整数 $T$（$1 \le T \le 200$）代表测试数据组数。对于每组测试数据：
第一行输入两个整数 $n$ 与 $k$（$1 \le n \le 100$，$0 \le k \le 10^4$）。
输出
对于每组数据，若符合要求的序列存在，首先输出一行 "Yes"（不输出引号），并在接下来的一行中输出 $n$ 个由单个空格分隔的整数 $a_1,a_2,\cdots,a_n$。请注意，您的答案需要满足 $1 \le a_i \le 10^5$；若不存在符合要求的序列，输出一行 "No"（不输出引号）即可。
如果有多种合理答案，您可以输出任意一种。
请勿在行末输出多余空格，否则您的答案可能会被认为是错误的。
做法 1
当任意两个数之和均为完全平方数时，满足要求的二元组的数量 $k$ 为最大值 $\dfrac{n \times (n-1)}{2}$。
于是我们大胆猜测：对于任意一个 $k \le \dfrac{n \times (n-1)}{2}$，都有解。设 $k'$ 表示不满足要求的二元组的数量，则 $k'=\dfrac{n \times (n-1)}{2}-k$。
当 $k'=0$ 时，直接让数列的每一项都是 $2$ 即可。否则，可以使用以下两种方法来增加不满足要求的二元组的数量：
- 将数列的其中一项改为 $114$（$2+114=116$ 不为完全平方数，其他类似的数字也可以），每次减少 $n-1$ 个、$n-2$ 个，以此类推；
- 观察到对于整数 $2$ 和 $98$，$2+2=2^2,2+98=10^2,98+98=14^2$，所以可以将数列的一些项改为 $98$，并将其中一项改为 $46$（$2+46=48$ 不为完全平方数，$46+98=144=12^2$，其他类似的数字也可以），设其中 $2$ 的数量为 $a$，则减少了 $a$ 个。
举一个例子：当 $n=5,k=5$ 时：
- 原序列：$\{2,2,2,2,2\}$；
- 将最后一项改为 $114$，满足要求的数对的数量减少 $4$：$\{2,2,2,2,114\}$；
- 将第 $2$ 项改为 $46$，将第 $3$ 至 $4$ 项改为 $98$，满足要求的数对的数量减少 $1$：$\{2,46,98,98,114\}$；
- 构造完毕。
第 8 题：C. Minimum Spanning Tree（最小生成树）
题面
2-C Minimum Spanning Tree（最小生成树）
题目描述
给定一张连通图，该图有 $n$ 个点以及 $m$ 条带有边权的无向边，且 $n$ 个点中有 $k$ 个点是特殊的。求该图的一棵生成树满足
- 所有特殊点都是该生成树的叶子，并且
- 生成树中边权的总和最小。
请回忆：生成树是原图的连通子图，该连通子图含有 $n$ 个点以及 $n−1$ 条边。另外，叶子指的是树上恰有一条边与其相连的点。
输入
有多组测试数据。第一行输入一个整数 $T$ 代表测试数据组数。对于每组测试数据：
第一行输入两个整数 $n$ 和 $m$（$2 \le n \le 10^5$，$n−1 \le m \le 10^5$）表示图的点数和边数。
对于接下来的 $m$ 行，第 $i$ 行输入三个整数 $u_i$，$v_i$ 和 $w_i$（$1 \le u_i$，$v_i \le n$，$1 \le w_i \le 10^9$）表示有一条边权为 $w_i$ 的边连接点 $u_i$ 和 $v_i$。保证输入的图是连通的，但可能有自环或重边。
下一行输入一个整数 $k$（$1 \le k \le n$）表示特殊点的数量。
再下一行输入 $k$ 个整数 $a_1,a_2,\cdots,a_k$（$1 \le a_i \le n$）表示特殊点。
保证所有数据 $n$ 之和以及 $m$ 之和不超过 $10^6$。
输出
每组数据输出一行，若存在符合要求的生成树则输出生成树的最小边权总和，否则输出 "Impossible"（不输出引号）。
做法 1
与普通的最小生成数相比，本题多了一个条件：一些点只能连一条边。那么，当 $n \ne 2$ 时，若有一条边的两点均为特殊点，则这条边不能选。先求出非特殊点的最小生成树，再加上特殊点即可。