BY 苏弘烨
写blog前必吐槽
今天第2题莫名其妙的挂了一个点,经本机测试,发现无误。由cys大佬处得知,OJ的变量都要初始化才能用,不然会莫名其妙的挂。真TM个破OJ!

1. 小红的电话簿


题目描述
临场思路
首先,题目有个不得不说的槽点:
现在,小红学姐嘿嘿一笑,问你:他的电话簿有多少页?

好的,继续。
这题就是纯模拟。
因为每页最多可以记录k个号码并且一定要是同一个数字开头的。所以我们可以用book数组标记每个读入的号码的开头。然后遍历book数组,对于每个数字开头出现的次数都令sum加上出现次数除以k,有余数的情况加1。
什么垃圾题目,一个不男不女的,还嘿嘿一笑,看着老有毒的。
1372. 神奇数


1372. 神奇数
临场思路
根据乘法分配律,可得:
n=a*10^0+a*10^1+a*10^2+...+a*10^k
=a*(10^0+10^1+10^2+...+10^k)
=a*(111...111)
那我们就可以枚举111...111,通过判断n能不能整除111...111得出a。
垃圾OJ,变量居然还要初始化才不会挂,毁我青春
3. 聚会

临场思路
每一个员工顶多只有一个直接上司,这是一个树的结构。
考虑并查集,代码实现不好,只拿了10分。
原先考虑将所有人的上司关系组成树,再两两枚举。但是时间复杂度太高,实现又很乱。所以没有完成。
正解
这题其实就是个没有路径压缩的并查集。
遍历一遍到每个人的最高上司,求出所在的树的深度。分组数即是每棵树的最大深度。
如图所示:

在不同的树中,同深度的所有节点都可以为一组,所以总组数就为所有树的最大深度。
1374. 森林探险

临场思路
很明显,zjc 走出森林的最少时间即从 s 到 k 再到 t 的最短路。
这猴子真TM无聊。
因为n≤1000,m≤200000。
所以Floyd可能超时,可以考虑Dijkstra或SPFA。
当然SPFA是O(NM),Dijkstra是O(N^2)。相比之下SPFA时间复杂度比较高,还是有点悬(容易卡常),还是用Dijkstra好点。
PS:临场无聊把两种都打了一遍。
注意:这题可能有重边,所以读入时一定要注意,读入路径最短的边即可。
感悟:
今天题好水啊。
我们一定要认真仔细,考虑所有情况。