牛客小白月赛21解题报告
正式详细题解将在稍后更新！（施工中……）
首先非常抱歉，由于牛客的UI问题导致H题的标点符号显示错误，影响大家体验心情。
题目分类（解题报告按此顺序编写）：
- 签到题：H
- 前期题：A、C、F、G、I
- 中期题：E、J
- 后期题：B、D
H —— "Happy New Year!"
考点：手速和冷静。
输出题目即可。
赛时紧急添加了Special Judge以扭转出锅局面，再次对因该问题影响心情的选手道歉。
PS：使用PHP写据说会有奇效？
A —— Audio
考点：计算几何基础。
由平方反比定律，发现响度相同时只与距离有关，所以我们只需要求一点，使得该点到三角形三个顶点距离相同，即求三角形的外心。
推导过程即联立任意两边的垂直平分线，求垂直平分线的交点即可。
C —— Channels
考点：前缀和思想，容斥的思想。
计算的答案减去
的答案即可，不过需要注意其端点可能在广告的时刻哦！
具体计算方法：即只需要考虑如何计算的答案。
F —— Fool Problem
考点：找规律与公式推导。
不难寻得，可以利用斐波那契的递推公式证明该式，此处留给读者思考。
G —— Game
考点：题意转换。
不难发现某一个数字的质因子个数是一定的，计算其质因子个数来探究可分解的步数进行博弈即可。
其实最后只需要考虑质因子个数的奇偶性。
或者通过sg函数来进行计算：
I —— I love you
考点：动态规划。
请参看小白月赛3的B题，只不过这里的字符串变长了一些QwQ，道理是一样的（记表示匹配到
iloveyou第位的方案数，遇到一个字符从其前序字符转移过来即可），简单DP。
E —— Exams
考点：模拟。
按照题目意思计算学分绩即可。
注意题目中提到“计算且仅计算必修和限选课程”，故任选学分不算在学分绩的总学分里面。
J —— Jelly
考点：Bfs搜索。
三维迷宫？求从(1,1,1)到(n,n,n)的最短路。
搜索的时候一改二维搜索的四连通，改为三维搜索的六连通，上下左右前后6个方向进行Bfs。
B —— Bits
考点：模拟，二进制的神奇应用（计算图形学？？？）
请参看这里，也可以通过Dfs来写，不过注意一下奇偶的位置。
D —— DDoS
考点：题意转化，拓扑图路径计数
不易观察、挺难发现、较难得到攻击者可以通过调整发送数据包的时间来使得所有数据包同时到达服务器，故原题意转化为求1到n的路径条数，拓扑图上DP即可。
注意定向的含义是规定路线及经过的中继节点，所以重边的时候格外小心（需要算两倍）。
边权无用（其实这里给了个奇怪的数据范围是在暗示呢QwQ）。
全部评论
(6) 回帖