04-06 17:10 成都工业学院 C++

关注

浙江理工大学 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]$ 。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAX = 1e3;
const int N = 1e3 + 10;
const int MOD = 1e9 + 7;

int dp[N][N];

void load() {
    for (int i = 1; i <= MAX; i++) {
        for (int j = 1; j < i; j++) {
            dp[i][j] = dp[j][j];
        }
        for (int j = i; j <= MAX; j++) {
            dp[i][j] = 1 + dp[i][j - 1] + dp[i - 1][j - 1];
            dp[i][j] %= MOD;
        }
    }
}

signed main() {
    int n, m;
    cin >> n >> m;
    load();
    cout << dp[n][m] << endl;
}

L. 今天是个上分的好日子

按题意模拟即可

#include <bits/stdc++.h>
#define int long long
using namespace std;

signed main() {
    string s;
    cin >> s;
    int continuous = -1, cur = 0;
    for (char ch : s) {
        if (ch == '1') {
            if (continuous < 5) continuous++;
            cur += 3 + continuous;
        } else {
            continuous = -1;
            cur -= 12;
        }
    }
    cout << cur << "\n";
}

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)$

$\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}$