有些是抄的 chenzhe 发的 pdf.
前言 · 出题方向
讲评 pdf：12测试与评估.pdf
本次考试，考察的是本学期所学的知识，也多了一种在线上比赛中常见的知识——构造题。
第 1 题，素数：难度：简单，J 组第一题，算法：模拟
第 2 题，和树：难度：简单，J 组第二题，算法：图论（最近就在讲这系列知识点）
第 3 题，迷宫：难度：中等，J 组第三题，算法：搜索
第 4 题，数列：难度：中等，J 组第三题，算法：构造（正式赛一般不考）
第 5 题，优秀：难度：较难，J 组第三-第四题，算法：贪心+01 背包
T1
模拟题意即可。
复杂度即为 埃氏筛 的复杂度，O(n\log{\log{n}})，近似于线性。
参考代码（本人写的）：
#include <bits/stdc++.h>
using namespace std;
bool T[5000010];
int n;
void input()
{
cin >> n;
T[0] = T[1] = 1;
}
bool isRemoved(int x)
{
return T[x];
}
void remove(int x)
{
T[x] = 1;
}
void work()
{
for (int i = 2; i <= n; i++)
{
if (!isRemoved(i))
{
for (int j = i; j <= n; j += i)
{
if (!isRemoved(j))
{
T[j] = 1;
printf("%d ", j);
}
}
}
}
}
int main()
{
input();
work();
return 0;
}T2
Description
给定一棵树，树有点权，问从根节点1出发有多少条简单路径使得路径上所有节点的权值之和不少于 val.
Solution #1
树是无向的，要建反向边。
模拟深度遍历一棵树的过程，每次遍历时记录走到当前结点的点权和，与val进行比较，统计结果，注意要开long long.
Solution #2
预处理每个点的子树大小，到一个结点发现已经不少于val时，直接加上这个结点的子树大小即可。还可以避免开long long，只不过缺点是码量较大。
T3
难度相当于 CSP-J T3.
Solution 30%
只有一行。此时可以找出第k个墙壁的位置，再找到其右边延伸出去的道路的最右边的位置即可。
Solution 40%
没有道具。直接写普通 dfs 或 bfs.
Solution 70%
以上 30% 与 40% 加起来就可骗到70分。
Solution 100%
看到走迷宫首先想搜索，然后考虑如何处理k个道具。
不妨设 f[x][y] 表示到达了点 (x,y) 之后，能够剩下的最多的道具个数，初始值除了左上角的格点是 k 之外，其余的格点都是 -1。则能够到达的格点数量就是 f[x][y] \ge 0 的数量。
对此进行搜索，搜索时需要剪枝，若到达这个格点的时候道具少于 f[x][y]，就没有必要进行后续搜索了。
时间复杂度为\mathcal{O(nmk)}.
注意要剪枝，否则会超时。
T4
什么都不说了 上图。
构造题中比较入门的内容。
出处：上海某中学高三模拟卷压轴题最后一问。
Description
定义一次操作为：将数列中所有的数值减去任意指定的常数c后取绝对值。
2个问题：
- 对于任意长度为n的数列，用不超过n次操作将其全部清零；
- 对于长度为n的排列，用\min(n-1,3022)次操作将其全部清零。
4 \le n \le 6,000.
Subtask 1: Solution
首先我们发现，如果一个数列在第m次操作被清零，则第m-1次操作时数列的数值必然全部相等。
则对于问题一，我们可以将问题转化为，用不超过n-1次操作，将所有数字化为相同的数字。更进一步来说，如果每次操作需要让数列中的不同数字的个数下降1，那么在n-1次操作后数列便可以全部相等。
那么如何处理？我们不妨解方程：\lvert a-c \rvert = \lvert b-c \rvert，可得c=\dfrac{a+b}{2}.
这给了我们一个启示，只要每次让c指定为两个元素的平均值即可。
这样，我们在第i次操作，令c[i]=\dfrac{a[i]+a[i+1]}{2}即可，稍加验证可得这样最后得到的数列的值是相等的。
这样，最后一次我们减去数列中的任意元素，即可将数列全部清零。时间复杂度 \mathcal{O(n^2)}.
Subtask 1 解决，获得 30 pts.
Subtask 2: Solution
问题二难度较高。长度为n的数列，且数列中1-n都出现了恰好一遍，其实说明了数列从小到大排序就是长成1, 2, 3, ..., n的样子。由于每次操作是对整个数列进行运算，因而不管数列长得怎么样其实对操作方式
是没有影响的。我们就不妨假设它就是1, 2, 3, ..., n.
n最大是 6000，但是只给了 3022 次操作机会，本质上要求的是每一次让两个原本不相同的数字变得相同，才可以在规定次数内完成。观察样例。
样例中对于数列 1,2,3,4，先用 c[1]=2.5 操作，这样一来就让数列变成了 1.5,0.5,0.5,1.5 的样子，相当于直接让数列中，不同的数字的种类直接少掉一半。此外，我们还能发现，0.5 进行一次c=1的操作之后还是 0.5，但是其他的数字会下降1。
暗示了什么？如果我们能一次性直接把数列值域降低一半，那么剩下的操作都交给c=1去解决即可。
这里的做法将n进行了奇偶性的讨论。
当n为偶数的时候，不妨令c[1]=\dfrac{n+1}{2}，即原来数列的中位数。这样可以把原来1, 2, 3, ..., n的数列变成
\dfrac{n-1}{2},\dfrac{n-3}{2},\dfrac{n-5}{2},\cdots ,\dfrac{3}{2},\dfrac{1}{2},\dfrac{1}{2},\dfrac{3}{2}, \cdots, \dfrac{n-5}{2},\dfrac{n-3}{2},\dfrac{n-1}{2}
这样之后我们对数列进行若干次 c=1 的操作。由于最后所有的数字都会被下降到 \dfrac{1}{2}，而且 \dfrac{1}{2} 再怎么操作 c=1 还是 \dfrac{1}{2}，在最后一次令 c=\dfrac{1}{2} 即可。
这样操作要多少次呢？\dfrac{n-1}{2}要用\dfrac{n}{2}-1次c=1的操作才能下降到1. 也就是说，总共需要操作\dfrac{n}{2}+1次，符合要求。
n为奇数时同理，总操作次数为\dfrac{n+1}{2}+1次，时间复杂度均为\mathcal{O(n)}.
T5
Description
给定一个长度为n的序列，从中选出不超过k个数，要求乘积的末尾0最多。
1\le k \le n \le 300,1\le a_i\le 10^{18}.
Solution
因为在原来没有0的情况下，只有2\times 5才能产生0；所以，一个数字末尾0的个数，取决于将其质因数分解后2与5的个数中较小的一个。
由于乘一个正整数，其质因子2和5的个数是不会下降的，所以说最佳策略就是选k个数。
基本上就是个 0-1背包 板子题。
最后的乘积（product）为p=2^x\times 5^y \times z.
赛后总结
上号一看T1简单，然后发现T2巨坑；
T3T4一看巨难，T5骗分0分完蛋。
寄。
注：本人观点，没有任何现实意义。