第一道题大意：
一次操作：指定一个树的高度不变，其他树加一
求多少次操作之后，所有树的高度一样
思路：
这题可以反过来看，
一次操作：将一个树的高度减一，其他树不变
求多少次操作之后，所有树的高度一样
这么问，就很简单了，让所有树都减去最低的那个树，剩下所有树的和就是答案了 写的时候，可以在输入的时候，记录最小值，同时统计所有树的和 sum。
其实 sum 只是比答案多了 n 个最小值
输入完成之后
答案 = sum - (n * 最小值)
第二题大意：
给定一个只含数字的字符串，
输入 n 行 a 和 b
每行代表将 a 字符换成 b 字符
这题本来想着会用什么邻接表，建树，等等，后来发现，我是真的蠢
思路：
要是按照正常的操作：每输入一行就遍历一遍字符串，肯定超时，简单的有优化基本没用，没get到出题的点
其实你仔细研究几个样例就知道了
不管输入几行交换数据，针对最后的结果，只有十种情况，因为他只有十种数字
1. 原字符串中的 0 最后要换成什么
2. 原字符串中的 1 最后要换成什么
。。。
。。。
10. 原字符串中的 9 最后要换成什么
这么说的话，我们可以先将 n 行数据进行处理，处理之后，在对原字符串进行替换
可以定义一个大小为十的数组 s[10]，，， 其中s[2]就表示最后要吧 2 换成 s[2]
初始让每个元素都等于自己的下标，因为自己换成自己嘛
接下来每输入一行 a b ，就遍历一遍这个数组
将对应存储的值为 a 的，全换成 b
例子：
假设：有4行输入（0,2）（3,0）（0,4）（4,1）
第一行之后，
s[0]的值等于0，所以
s[0]=2;
其他不变
第二行之后，
s[3]的值等于3，所以
s[3]=0
第三行之后
s[3]的值等于0，所以
s[3]=4
第四行之后
s[3]和s[4]的值都是4，所以
s[3]=1
s[4]=1
输入全部完成之后
遍历原字符串
针对每个字符
将他替换成s数组对应的就可以
看一下复杂度：
输入的同时遍历s数组，这个复杂度是在n的基础上乘10
n好像是1e6，乘10也就1e7
然后就是输出了，字符串的长度好像也是1e6
除此之外就没别的操作了
总复杂度11*n
1e7的复杂度，C++完全罩得住
深信服非要挑七夕笔试，我觉得可能是在明示：有对象的人不要来，我们不要
全部评论
(0) 回帖