CF 原题大赛

CF545C Woodcutters

贪心就是尽可能往左倒
无法向左倒,则尽量往右倒
第一个准则很好理解,但另一个则让人费解
如果向右倒的话,则再右边的那颗树则也可能会向右倒,这样可能会有人会想这样会不会让答案不优
那么我们假设这样之后,我们让一颗树既不能向左也不能向右,也就是造成了负面影响,因为一棵树无论倒不倒,都会让他所在的点无法被接触到,所以说这棵树停在原地等价于向左倒,也就是我们只是面对二择,要么左边,要么右边,对于答案而言是等价的。
故此贪心策略是正确的
Q·E·D

Bear and Prime 100

交互题,让你猜数字是质数还是合数
你可以询问这个数能否被x整除
查询次数最多为20次
数字范围在【2,100】
显然100以内的合数都至少包含2——7中的质数一个,因为不包含这些质数的最小合数是1113=143
那么先枚举这些(4个) 最差是去找94=2
47 要枚举玩一个2后再从2枚举到47(15个)
刚好20次呢XD


  转载请注明: wenjing233的小站 CF 原题大赛

 上一篇
USACO原题大赛 USACO原题大赛
T1有N个单词,每个单词长c个字,韵律为k,你要用这些单词作诗,每个诗句长度必须为len诗的某些句子必须是相同的韵脚这样的句子组不超过26个 很显然的是,我们只要做一次背包DP推出每种韵脚,长度为len的句子有几个然后快速幂统计一下答案就好
下一篇 
CF 原题大赛 CF 原题大赛
CF849A显然,奇数乘奇数还是奇数,如果两边是偶数,无论怎么划分,他永远都在边界上,是不合法的 CF849B第一个点要么自己一人,要么肯定和另一个点在一起,枚举即可O(n*n) CF848A显然每个点合并时都要和其他点计数一次,所以是n*