P5246 题解
liangbowen
·
·
题解
前言
题目传送门！
更好的阅读体验？
耗时一个晚上，没看题解把消失的源代码切了，很高兴，来写篇题解！
点击 \color{red}\textbf{每个子任务的标题} 可以查看代码。
如果不想看心路历程，请 \color{red}\textbf{划到最底下} 看一行流题解。
Task 1
是一堆小写字母，往 exe 里挨个输入 \texttt{a}\sim\texttt{z} 就能发现这是一个映射。直接做即可。
Task 2
input2.txt 看起来非常简单，但是输进去 \text{exe} 我就破防了：这是啥啊？？？？？
输入 0\sim10，答案 a_i 为 10, 2030, 8082, 18166, 32282, 50430, 72610, 98822, 129066, 163342, 201650。
稍微思考一下就不难了。注意到 8082\approx 2030\times 2^2，18166 \approx2030\times 3^2。尝试变成整除，于是发现 -10 就整除了。
不看前面几项。我草这是等差数列。差是 2016，很吉祥啊！
所以 b_n=2020+2016(n-1)，a_n=n\cdot b_n+10=n(2020+2016(n-1))+10，输出即可。
很快把公式抄进代码里，和 1\sim20 的正确答案比一下。？？？？？？？？为啥这正确答案还带突然变小的？？？？？？？
这并不困难。发现突然变小的那一项和我们的答案正好差 233333，很容易想到是 \bmod 233333 啦。
Task 3
https://oeis.org/A097430。
Task 4
input4.txt 显然是读入一张图。随便输入一点普通图，发现结果总是 n^2，直到你输入了一个不连通的图 (V=\{1, 2, 3, 4, 5\}, E=\{\small(1, 2), (2, 3), (4, 5)\normalsize\})，发现答案是 13=3^2+2^2。这就很显然了，答案即 \sum\textbf{连通块的大小}^2。
Task 5
input5.txt 经过观察，先读入 n-1 条有权边（应该是构成一棵树），再读入 m 组点对，计算答案。
先试试 m=1 的情况。对于 (u,v)，容易发现就是 \operatorname{dist}(u,v)。
再试试 m=2，发现答案非常神秘，为啥那两个点对的距离是 5 和 20，最后的答案还能是 17 啊。于是试了一堆二元运算符后发现答案是所有距离的异或和，就离谱。
Task 6
input6.txt 长得和 input5.txt 一样捏。所以就很轻松了，发现不同点在于 \operatorname{dist}(u,v) 变成了 \min\limits_{t\in(u\to v)} w_t。仍然是异或全部权值。
然后你发现你错了。实际上可以通过输入询问点对 (u,u) 来获取 \text{minn} 的初值应为 1987654321。
Task 7
（表格在洛谷可能会寄，请移步博客园）
输入规模又变小了。设每次读入的两数为 (n,m)，直接打表：
| n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| m=1 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| m=2 |
2 |
5 |
7 |
10 |
12 |
15 |
17 |
20 |
22 |
| m=3 |
3 |
7 |
12 |
16 |
19 |
25 |
28 |
32 |
37 |
| m=4 |
4 |
10 |
16 |
24 |
28 |
36 |
40 |
48 |
54 |
| m=5 |
5 |
12 |
19 |
28 |
37 |
46 |
51 |
60 |
67 |
观察 (m=2)\Rightarrow(m=3)，打表 a_{n,m}-a_{n,m-1}：
| n |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
| m=(1\Rightarrow2) |
1 |
3 |
4 |
6 |
7 |
9 |
10 |
12 |
13 |
| m=(2\Rightarrow3) |
1 |
2 |
5 |
6 |
7 |
10 |
11 |
12 |
15 |
| m=(3\Rightarrow4) |
1 |
3 |
4 |
8 |
9 |
11 |
12 |
16 |
17 |
| m=(4\Rightarrow5) |
1 |
2 |
3 |
4 |
9 |
10 |
11 |
12 |
13 |
再差分，打表 b_{n,m}-b_{n-1,m}：
| n |
1\Rightarrow2 |
2\Rightarrow3 |
3\Rightarrow4 |
4\Rightarrow5 |
5\Rightarrow6 |
6\Rightarrow7 |
7\Rightarrow8 |
8\Rightarrow9 |
| m=(1\Rightarrow2) |
2 |
1 |
2 |
1 |
2 |
1 |
2 |
1 |
| m=(2\Rightarrow3) |
1 |
3 |
1 |
1 |
3 |
1 |
1 |
3 |
| m=(3\Rightarrow4) |
2 |
1 |
4 |
2 |
1 |
4 |
2 |
1 |
| m=(4\Rightarrow5) |
1 |
1 |
1 |
5 |
1 |
1 |
1 |
1 |
整理一下。
| n |
2 |
3 |
4 |
5 |
6 |
6 |
8 |
9 |
| m=2 |
2 |
1 |
2 |
1 |
2 |
1 |
2 |
1 |
| m=3 |
1 |
3 |
1 |
1 |
3 |
1 |
1 |
3 |
| m=4 |
2 |
1 |
4 |
2 |
1 |
4 |
2 |
1 |
| m=5 |
1 |
1 |
1 |
5 |
1 |
1 |
1 |
1 |
显然即 c_{n,m}=\gcd(n,m)。倒推一下就能得到 a_{n,m}=\sum\limits_{i=1}^n\sum\limits_{j=1}^m \gcd(i,j)。
贺一下 P2398 的代码即可。n\ne m 时是一个很小的点，所以直接暴力。
Task 8
很多人说这一问很难，但是我觉得还好捏。
随便输进去一个排列，发现答案是 \dfrac{n(n+1)}2，很容易想到答案是这个数组的 [l,r] 数量。
于是输入 \{1,2,1,2\}，发现答案是 6。枚举一下 [l,r] 就能发现求的是本质不同的子串个数。
去 P2408 贺个题解改一改即可。
Task 9
input9.txt 显然让我们输入一些点对。瞎输了一下，为啥是小数啊。
于是输入 (1,2), (3,4)，发现答案是 2.828\approx2\sqrt2=\sqrt8。很显然是 (x_i,y_i) 在平面上两点的距离。
那么就很简单了，多输入几个数就能发现是平面最近点对。
去 P7883 贺个代码即可。
Task 10
这种题目总是有一些 Task 是不正经的 /hanx。
纯答案题解
- Task1：对于字母 \texttt{a}\sim\texttt{z}，映射 \texttt{yfrbkgimujvphatdsnelozcxwq}。
- Task2：a_n=\Big(\normalsize n(2020+2016(n-1))+10\Big)\normalsize\bmod 233333。
- Task3：a_n=\left\lfloor\sqrt{\dfrac n\pi}\right\rfloor。
- Task4：给定一张图，输出 \sum\textbf{连通块的大小}^2。
- Task5：给定一棵有边权树，输出 \oplus \operatorname{dist}(u,v)。
- Task6：给定一棵有边权树，输出 \oplus \operatorname{minw}(u,v)。
- Task7：\sum\limits_{i=1}^n\sum\limits_{j=1}^m\gcd(i,j)。n\ne m 的情况允许暴力。
- Task8：本质不同的子串个数。
- Task9：平面最近点对。
- Task10：10 个
invalid input!。