二模07day1解题报告

时间:2021-10-20 21:03:49

T1.种树(tree)

有n棵树,各有高度,要求每棵树的高度都小于它到其他树的距离(可能种一起)。求砍掉的总高度是多少。

Ok,那么可以想到,只要满足每棵树和最近的树满足条件就可以保证和其他树满足了。所以只要按pos排个序,去重,然后一棵一棵砍,就好了。

T2.统计方案(count)

有n个数,取出一部分,相乘mod p=c,求方案树。

还是暴力求解。。。。

正解是非常神的。由于16的数据是可以比较快的解出来的,所以就可以把所有可能达到的值全都算出来。

然后可以用类似的办法求出另一组中的可能积b,使得a*b%p=c,而a可以通过逆元得到,再给ans加上保存好的a的方案数。In this way,就可以算出ans了。

但是,要注意c==1的情况是要-1的,而c>=p当然是无解的啦。

逆元的具体求法如下:

二模07day1解题报告

二模07day1解题报告

need就是所需要的a了。

T3.魔棒(magic)

初始hp的人将受到n次伤害,他有魔棒(冷却时间为cd)可以回复hp(受到一次伤害积累一点能量,每次使用消耗全部能量,回复15*能量点数的hp)。求cd的最大值。

一开始想到的明显是二分答案,判断可行性,然而判断的方法类似dfs肯定会超时。所以只过了50%

正确的判断方法要用到差分约束,将判断过程转化为求最短路判负环的问题。二模07day1解题报告

就这样吧。。