浙江理工大学 2024 年程序设计竞赛
DE 出题人失联，暂时没有题解。
各出题人觉得讲题太麻烦了，不想讲题了，直接给了文字题解。
可能后面我会在 b 站上传个人讲题视频。
出题人：
fresh_boy：FGHJ
超级gjl：AI
Greatliangpi：BC
smallC233：KL
DS_Tape：DE
interesting things：
- 题目顺序是加入 problem pool 的顺序。
- 正赛有一题因为没人验，所以没放到牛客上。
难度预估：
easy：GLI
easy-mid：AFC
mid：HJK
hard：DEB
interesting things：
- 出题人以为 G 会是最签的，因为只要一直交保证每次答案不一样应该总能过啊，真“枚举答案”，结果 L 更签。
- DE 的出题人出题时就认为是板子题，在我的强烈“建议”不适合放校赛的情况下，他仍认为不难，属于可做题。从结果上来看，懂都懂。
- B 原本定位是 easy-mid？但是验题后 B 出题人改变了主意。
出题人题解：
F：leetcode
子序列自动机即可，或者 DP 的思路也可以。
子序列自动机在这题其实就是一个后继数组 $suf[i][c]$ 表示 $c$ 这个字符在 $i$ 后第一次出现的位置（对于包不包括 $i$ 自己，自行讨论）。
那么从每一个 $i$ 开始，遍历 leetcode，迭代 $suf[i][c]$ 即可。
G：好想会数学啊
根据质数距离很小的原则，直接从 $10^{30}+50$ 逐步加即可。
优化：$+2,+3,+4,+5,+6$ 均可手动判断不是质数。所以只要尝试输出 $+1,+7$ 即可。
$10^{30}+57$ 采用 Miller-Rabin 判断质数。
所以最坏 $7$ 次提交一定能通过。
聪明一点 $2$ 发，和出题人博弈（观察榜单） $1$ 发。
H：OS
模拟题。
原本是打算出成 $O(n\log n)$ 的，但是发现是李超树，放校赛过难了，就变成了 $O(n^2)$ 的模拟题。
每次一个循环按规则找要进行的作业即可。
可能有两个小坑点是：
- 作业时间可能不连续，即：完成一个作业后到下一个任务，时间有空档。
- 对于分数比大小，如果聪明的选手，把分数比较变成整数乘法。但是，就要注意乘了之后会爆 long long，需要 int128。然而事实上使用 long double 甚至 double 就能通过此题。因为不涉及等于，所以几乎没有什么问题（也不排除是出题人水平问题，造不出卡 double 精度的数据）
interesting things：
- 有多名前排选手此题 WA 了好多发，虽然我还不知道为什么。
- 有选手在 debug 注释里写暴戾语言（引恐禁三），出题人被骂了，呜呜呜。
J：triangle
计算几何。
原本出题人打算的是 $O(n^2\log n)$ 的极角序做法，但是验题的时候发现由于是整点，且保证点不重复。所以就有一个性质：长度相同的边不会很多。
所以直接枚举边，对同一种长度的边，双指针去判断是否构成钝角三角形即可。
判断是否构成钝角三角形的条件是：
- 两短边的平方和大于第三边（余弦定理可证，或者直接直观地从直角三角推导过来）。
- 两短边之和不等于第三边（去掉平角）或者就是判断三点共线，用叉积和点积即可做到无精度误差。
时间复杂度证起来感觉会比较麻烦，出题人感性估计是 $O(n^2)$ 的。
因为一个点到另外两点的距离相同，则这个点就在另外两点的中垂线上。如果还要加入第四个点，然后四点之间任意距离都相同。那么应该只有一种情况。所以总的边相等就会很少。
总之，在 $n\leq 1000$ 的范围下，这个“剪枝”肯定是能通过的。
原做法：
因为钝角三角形钝角顶点唯一，所以枚举这个顶点作为极点，后对所有点进行极角排序，然后做极角序扫描线，相当于一个双指针维护一个 $180°$ 的半平面内的极边。因为边长的平方在 $10^6$ 级别，所以用一个桶统计一下个数即可。
时间复杂度：$O(n^2\log n)$。无精度误差的稳定做法。
K. 痴呆邦·大盗呆德
方便起见，下文以**”最高高度”指代“在保证一定能找到让金蛋落下不碎的最高楼层的基础上，大楼的最高高度”**。
设 $dp[i][j]$ 表示有 $i$ 颗金蛋和 $j$ 次丢蛋次数时，大楼的最高高度。
假设我们从第 $x$ 层丢下金蛋，如果金蛋碎了，我们就需要用 $i - 1$ 颗金蛋和 $j - 1$ 次丢蛋次数从 $x+1$ 层往上寻找，由定义得 $x$ 层上方的最高高度为 $dp[i - 1][j - 1]$；如果金蛋没碎，我们就需要用 $i$ 颗金蛋和 $j - 1$ 次丢蛋次数从 $x - 1$ 层往下寻找，由定义得 $x$ 层下方的最高高度即为 $dp[i][j - 1]$。因此，有 $i$ 颗金蛋和 $j$ 次丢蛋次数时，大楼的最高高度为：$x$ 层上方最高高度 + $x$ 层下方最高高度 + 1，即 $dp[i][j] = dp[i - 1][j - 1] + dp[i][j - 1] + 1$。此外，当 $i > j$ 时，显然 $dp[i][j] == dp[i][i]$。
1 |
|
L. 今天是个上分的好日子
按题意模拟即可
1 |
|
A：春天到了，该练习 dp 了
这题不怎么考察 dp 的状态转移怎么推。
但是会 dp 的同学一下就能看出来这dp在干嘛。
我们可以直接从这个 dp 转移式入手。
$b[i]$ 为简单的累加的，所以 $\sum_{i=l}^rb[i]$ 对 $dp[m][1\cdots m]$的贡献是一样的都是 $\sum_{i=l}^rb[i]$的值。
对于 $i^2$ 的部分，可以直接理解为为取前 $k$ 大的 $i^2(l\leq i \leq r)$,这部分对答案的贡献即为 $\sum_{i=r-k+1}^ri^2$。
$O(n)$ 预处理前缀和，每次询问 $O(1)$ 查询即可。
I：神说要有光
按题意 $O(n)$ 模拟即可。
B：痴呆邦·第 $k$ 等式
分类讨论，由于边界情况很多，需要讨论很多类。
对于每种情况，如果第一个数确定，第二个数的数量是确定的，二分第一个数即可。
C：痴呆邦·附庸
附庸关系组成了二叉树形结构，即将树的剩余节点分为两个部分考虑即可。又由于树是不区分左右的，得到递推式：
$$
dp[x]=\sum_{i=0}^{\lfloor\frac{x}{2}\rfloor-1}{dp[i] \times dp[x-1-i]}+M(x)
$$
特别地，需要考虑左右子树节点数相同的情况（即 $M(x)$），直接加上将出现重复计数。
$$
\begin{array}{rl}
M(x) & =\left{\begin{array}{lll}
\sum_{i=0}^{dp[\frac{x-1}{2}]}{i} & ,x=2k+1 & ,k \in \mathbb{Z} \
0 & ,x=2k & ,k \in \mathbb{Z}
\end{array}\right. \
& =\left{\begin{array}{lll}
\frac{dp[\frac{x-1}{2}] \times (dp[\frac{x-1}{2}]+1)}{2} & ,x=2k+1 & ,k \in \mathbb{Z} \
0 & ,x=2k & ,k \in \mathbb{Z}
\end{array}\right.
\end{array}
$$
M：荒野乱斗锦标赛
设编号较大的人一定赢过编号较小的人，这与题目条件是相反且对称的。
我们发现恶魔之子的条件是以递归形式定义的，这启发我们使用动态规划解决该问题。
先确定树的形态：顶部为根，底部为叶子，1∼n+1 共 n*+1 层，第 i* 层每个点的子树大小为 $2^{n−i+1}$。
自顶向下或自底向上考虑。
- 自底向上考虑时，我们需同时记录当前赢家的编号，和当前子树内获得特别奖的编号，无法接受；
- 自顶向下考虑时，每次转移都需要枚举输掉的玩家编号（在本小局中，获胜的玩家编号就是当前赢家编号），最后一步输掉的玩家刚好符合特别奖的要求，可以接受。
通过上述分析，设$f_{i,j}$ 表示自上而下第 i 层（倒数第 i 轮）的赢家为 j 且它输掉了之后的所有比赛的方案数。根据实际意义，$f_{1,j}$=$[j=2^n]$。
考虑 $f_{i,j}$ →$f_{i+1,j}$ （j>k）的贡献系数。我们不关心第 i+1 层 j子树形态，其方案数为从 j-1-$2^{n-i}$-1 个数（1∼j，除了 j 和第 i+1 层 k 子树内 $2^{n−i }$个数）中选出$2^{n−i}$−1 个数（最后有解释），和 j 一起作为第 i+1 层 j 的子树内所有点，乘以 $2^{n-i}!$ 表示任意排列。还需要乘以 2 表示第 i+1 层 j,k 的位置可交换。
注意到贡献系数和 k 无关，因此前缀和优化即可做到 $O(2^{n}n)$。
关于贡献系数中组合数的解释：在 $1~p_1$ 中选 $q_1$ 个数，然后在 1∼$p_2$ 中选 $q_2$ 个数（不能和之前选择的数重复），以此类推，选择之间无序。从限制最严格的 $p_1$ 开始依次考虑，有 $({q_1}^{p_1})({q_2}^{p_2-q_1})(_{q_3}^{p_3-q_1-q_2})⋯$。而整个 DP 过程相当于倒过来考虑这个问题，故有该看似不符合组合意义的转移系数。