CF545C Woodcutters
贪心就是尽可能往左倒
无法向左倒,则尽量往右倒
第一个准则很好理解,但另一个则让人费解
如果向右倒的话,则再右边的那颗树则也可能会向右倒,这样可能会有人会想这样会不会让答案不优
那么我们假设这样之后,我们让一颗树既不能向左也不能向右,也就是造成了负面影响,因为一棵树无论倒不倒,都会让他所在的点无法被接触到,所以说这棵树停在原地等价于向左倒,也就是我们只是面对二择,要么左边,要么右边,对于答案而言是等价的。
故此贪心策略是正确的
Q·E·D
Bear and Prime 100
交互题,让你猜数字是质数还是合数
你可以询问这个数能否被x整除
查询次数最多为20次
数字范围在【2,100】
显然100以内的合数都至少包含2——7中的质数一个,因为不包含这些质数的最小合数是1113=143
那么先枚举这些(4个) 最差是去找94=247 要枚举玩一个2后再从2枚举到47(15个)
刚好20次呢XD