新闻资讯

SCOI2011飞镖

来源:手机赌钱app-手机赌钱平台-手机赌钱网站发布时间:2019-06-11 11:22:22浏览:5

  题目大意:给出k,m,x,需要你做如下操作,你可以选择1-k以内的任何一个数,乘以1,2或3,或者选择m,2*m,询问在3次操作以内是否可以凑出x(几次操作选择的数之和),并且最后一次选择必须选2*某个数(可以为m)。

  据说当时那场是把这道题放在了第二天第三题。但却是全场最简单的一道题,更恶心的是,其他两道题都难得变态。估计很多人看到了前两题都被吓着了,想都不敢想这题。

  还好我们老师有良心。。考模拟赛的时候把这题放在了第一题的位置。

  不废话开始说题了

  首先我们抛开m不论。

  不难发现一个性质:两次分别选择2*k,3*k,就可以凑出2*k+3*k以内除了2*k+3*k-1以外所有的数。证明起来很简单,要凑2*k+3*k-1,就必须得用2*(k+1)+3*(k-1),可是k+1超过了范围,必发88官网不合法。

  2*k+3*k-2,即2*(k-1)+3*k.

  2*k+3*k-3,即2*k+3*(k-1).

  2*k+3*k-4,即2*(k-1)+3*k.

  2*k+3*k-5,即2*(k-1)+3*(k-1).

  此后每5个数即为一次循环,都能够凑出来(1是特例,但可以直接用一次1*1得到,所以不用在意)

  那么能凑出比2*k+3*k还大的数,就只能选3*a+3*b这种方式,这种方式能凑出来的数规律很显然,即为3的倍数,且小于等于3*k+3*k。

  所以,对于任何一个数,用这两种方式凑都是最优的。

  因此,我们将x-2*k,看是否可以用2*a+3*b来凑

  并且找到x-2*k1,为k1<=k且x-2*k1为3的倍数,看是否可以用3*k+3*k来凑

  那么现在加入m

  总结一下,有m参与的共计有11种情况:(i表示选1-k中的数,乘的倍数不论,竖线后为最后一次,前两次操作的顺序随意)

  ①m i | i

  ②2m i | i

  ③m m | i

  ④m 2m | i

  ⑤2m 2m | i

  ⑥i i | 2m

  ⑦m i | 2m

  ⑧2m i | 2m

  ⑨m m | 2m

  ⑩m 2m | 2m

  ?2m 2m 必发88 |2m

  将m与2m看做同一种数,可以将1,2归为一类,记为A

  3,4,5归为一类,记为B

  6单独为一类,记为C

  7,8为一类,记为D

  9,10,11为一类,记为E

  对于A类,只需要将x-m或2m,因为最后一次必为2*a,所以用2*a+3*b的方法判定即可(注意!这里x-m,x-2m不可为0!因为题目要求的是从1-k内的数中选,如果m==x就会出现不合法的局面)

  对于B类,将x-2m(m+m)或3m(m+2m)或4m(2m+2m),看剩下的数是否为2的倍数且在2*k范围内

  对于C类,将x-2m后,看能否用2*a+3*b,或者3*a+3*b的方法即可

  对于D类 ,将x-2m或3m后,是否为1-k中某个数本身或2倍,3倍

  对于E类,直接看x是否等于4m,5m,6m。


必发88 必发88官网
 
手机赌钱app-手机赌钱平台-手机赌钱网站