CSU-ACM Home Page

2018年5月月赛-暨中南大学暑期集训选拔赛第一场题解

Update Time: 2018-05-28 23:52:47     Recent Editor: Scanf     Create Time: 2018-05-28 23:24:30     Creator: Scanf    


Problem A Wells的明星生活

题目大意:

给定N*N的矩阵,有些点不可走,有些点不仅不可走还会扩大不可走的范围,问最多拖延多久还能从起点到达目的地

问题分析:

求最长能呆多长时间

具体实现:

由于同时有了两个变量:

1是主人公本身在动,每秒可以动S步

2狗仔每秒同时向4个方向动,同时考虑太过复杂。

hint其实是在提示,如果留意了,其实可以看出在确定等待若干秒后在去判定能否到家比要容易,因此我们将计算问题转化为判定性问题,由于两个变量步长完全不一样,同时处理是不太方便的,故可以想到预处理出每一个格子被狗仔占领的最早时间tij,即主人公如果想要经过格子,那么时间必须严格小于tij那么主人公的S步怎么解决呢?其实可以像只能走一步一样利用bfs解决,记停顿时间为tim只要记录从开始走的步数stp,下一步走到的时间至少是(stp + 1)/S,记为T(其实贪心的来看,走得快一定比走得慢要优,所以一定是走S步的,除非离家已经不足S步),枚举主人公下一步走的方向,若满足T + tim < tij那么表示这个状态可走,严格小于保证了下一秒狗仔队抓不住主人公,那么现在就只需要一直扩展状态一直到回到家或者无状态可更新(-1)这个时间复杂度是多少?预处理狗仔到达时间,枚举停留时间,然后去bfs判断,由于保证时间不为无限大则为O(n * n * n * n)=O(n4),在n < =800的情况下无法通过,其实可以发现这个问题具有二分性,若一个时间tim能使得主人公到家,那么小于tim同样也可以,若不能,那么大于tim也不能,因此将上一种做法的枚举时间改为二分时间即可,复杂度(log(n * n)*n * n)=O(n2logn),n < =800绰绰有余

题目评价

考查内容:bfs、二分

时间复杂度:O(n2logn)

Problem B 智慧树

题目大意:

给出n个节点,每个节点对应一个权值,告诉每个节点的父节点编号,求每一层的最大权值。

问题分析:

根据给定的信息,记录节点i对应的层次lv[i]以及最大层数,最后遍历一遍每个节点,求出每一层的最大值即可。

题目评价

考查内容:模拟

时间复杂度:O(n)

Problem C 小Z的培养皿

题目大意

给定n个集合,每个集合中有k种细菌,对于两个集合,当且仅当两个集合中有公共细菌时,才能合并成一个集合,问最后有多少个集合

问题分析

使用并查集,对于每个每个培养皿,合并成一个集合。扫描完全部培养皿即可。最后计算有多少个集合即可。

题目评价

考查内容:并查集

时间复杂度:O(n)

Problem D Bit even number

题目大意

给定m个数,计算这m个数转换成二进制形式后1为偶数的个数有多少个

问题分析

直接按题意进行模拟即可。

题目评价

考查内容:位运算

时间复杂度:O(n)

Problem E 零的执行人

题目大意

对于每个字符串,判断是否能够构成回文串,能则输出Dark,否则输出Elementary。

问题分析

遍历一遍字符串,统计每个字母出现的次数。对于长度为偶数的字符串,要求出现的字母次数均为偶数。对于长度为奇数的字符串,要求出现的字母的次数为奇数的个数不能超过2。

题目评价

考查内容:字符串读入,map

时间复杂度:O(n)