洛谷 2021 SCP初赛模拟 简要解析

赛时 88pts。 只记了一些难一点的题。 正确答案： ``` ACBCBDADCBCAABD TFFFBD TFTFDC TTTFBC BDBAD DCCBA ``` ### 一、单项选择 挺白给的，就全 A 了。 **4.** 我也不知道这个堆是什么辣鸡玩意，不过可以看作写假了的斐波那契堆优化 Dijkstra。 **8.** 错排裸题，答案是 $\dfrac{D(5)}{A_5^5}$。 **10.** 直接套主定理。 **11.** 答案为下式： $$ \int_{0}^1 \frac{1}{x}\int_{0}^x (x-y) \operatorname{d}y\operatorname{d}x $$ 随便算算就知道答案是 $\frac{1}{4}$。 **13.** 注意到总共可能有 $C_4^2=6$ 条边，要在里边选 $4$ 条，答案即为 $C_6^4=15$。 ### 二、阅读程序 为什么我每次都是在读程里挂分（ **16.** 通过类似队列的一个过程不断往字符串里塞字母。具体地，对于每个出现的字母，程序都要在后面塞 $51$ 个。 - **3）**反例：$\texttt{a...(50 times) b...(50 times) ... z...(50 times)}$。 - **4）**输入 $\texttt{a}$，输出 $\texttt{a...(52 times)}$。 ​ 实际上应改为「长度**不大于** $50\times 26+500$」。 - **6）**挂分了，说明我是 sb。 ​ 我们注意到 $2+51=53$，因此选 D，而不是像某 sb djwj233 一样去选 C。 **17.** 我们发现那个 $\textrm{update}$ 操作本质就是在维护一个映射堆。因此显然这是一个堆优化 Dijkstra 的过程。 - **4）**代码里面用 $0$ 表示堆中不存在这个数，观察 $\textrm{update}$ 过程可知如果 $f(0)=0$ 则堆顶恒为 $0$。 - **5）**又挂分了！！1 ​ 这个 sb 看完选项不假思索地选了 A，没看到 D 选项。 ​ 边权相同说明最短路过程等价于一个 BFS。实际上如果图不连通，每次最多只会有 $\Theta(m)$ 个点被访问到。 - **6）**同上如果图不连通，每次最多只会有 $\Theta(m)$ 个点被访问到，因此单次 Dijkstra 复杂度是 $\mathcal O(m\log n)$。 ​ 总复杂度$\mathcal O(nm\log n)$。 **18.** 最短路考麻了 大致是用写假的 Dijkstra 和写假的 Floyd 跑全源最短路，求结果中有多少组不同。 ~~像极了场上拿两个错误程序对拍的你~~ 估计是人类智慧题，做法就是乱搞。 - **1）**这个人做题时脑子不好使！！1 ~~发现第 22 行是`if (!vis[j] && (!now || dis[i][now] > dis[i][j]))`，说明这是个假的暴力 Dijkstra。~~（这是之前的错解） **Update：这里考虑到的是一个自环的问题。** 我们注意到程序在输入一张图的时候并没有判断自环，而且题面中也没说没有自环，就可能出现下面的情况： ``` 3 1 1 1 1 ``` 这样跑完后 $\texttt{dis1[1][1]=1}$，显然有误。 解决这个问题可以通过在第 60 行中加入特判解决。 另外，这个 bug 只会对 $\texttt{dis1[i][i]}$ 的值产生影响，因为松弛时一定会有 $\texttt{dis1[x][x]}+\texttt{dis1[x][y]}>\texttt{dis1[x][y]}$，因此不可能更新别的答案。 - **2）**考虑下图： ``` 4 4 1 2 10 3 2 1 4 3 1 1 4 1 ``` 输出 $1$，故选 T。 - **3）**因为 Dijkstra 跑 $n-1$ 轮就能出答案，因此选 T。 - **4）**这是个 $\mathcal O(n^2)$ 的暴力，选 F。 - **5）**人脑模拟发现答案是 $3$。 ​ 由于这图看着一点性质都没有，赛时就懒得模拟了，蒙了个 C，然后就错了。 - **6）**不知道正解是啥，大概是暴力枚举所有的图然后做？？看着十分不可行。 ​ 据说随机数据能跑出答案 $6$。 ​ 赛时模拟了几组小数据，然后猜了 $\sum\limits_{x=1}^{\left\lceil \frac{n}{2}\right\rceil} x$ 的憨批结论。 ​ 由于 $1+2+3=6$，于是蒙的 C，然后莫名奇妙对了。 ### 三、完善程序 完善程序一直是拿手好戏，谁知竟然错了一个 **19.** 思博题。 **20.** 一看就很 Arcaea，然后题目十分毒瘤。 由于一直在玩读程 T3，最后没时间检查了，凭意念填的。于是就错了第三小题 题目中的 $0,\dfrac{x}{2},x,x+1$ 分别对应游戏中打击效果的 Lost, Far, Pure 和 Max Pure。 由于 $2\times \dfrac{x}{2}=x$，因此我们发现打两个 Far 出来相当于打一个 Pure。 而由于 Pure 还能晋升为 Max Pure，有更多的可能性。因此从方案数的角度，打两个 Far 出来不优于打一个 Pure。 所以我们钦定**小 A 至多打一个 Far 出来**。 至于变量的含义，观察 $i,j$ 的循环范围可知，代码中的 $i$ 表示最终分数中有几个 Notes 不是 Lost，$j$ 表示小 A 是否打出了 Far。 这里面的 $\textrm{lower}$ 和 $\textrm{upper}$ 分别在算小 A 在 $i$ 个 Notes 中最多、最少能打出几个 Max Pure。 比较四个选项可知，这个 $\textrm{base}$ 则是在算把 Max Pure 看作 Pure 后的分数的 $2$ 倍。 - **1）**$n=m$，有 $\forall i\in [0,n], \text{Score } i(x+1)\text{ is available}$。 - **2）**$i=j=0$，即全 Lost 的一种情况。 - **3）**这里挂了！！1 我们发现由于最多有 $n-m$ 个 Pure/Far（这里把 Far 算进去了！），因此最少的 Max Pure 数是 $i-(n-m)$。 - **4）**答案应是 $\dfrac{iM}{n}-\dfrac{jM}{2n}$（先全看作 Pure，然后减掉 Far）。 但是由于下取整后相减会带来一些问题，因此采用 A 选项的形式。 - **5）**20~21 两行是要减去重复计算的部分。 如果前一次统计到的最大分数不小于现在的最小分数，那么就要减去这个重复的部分。 因此这里应该是 $\textrm{lst}\gets \textrm{base} + \textrm{upper}$。