djwj233 的博客

djwj233 的博客

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

posted on 2021-09-04 15:15:29 | under 比赛题解 |

赛时 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}$。