【省选模拟赛】小奇分糖果

2015年12月18日1,7742

原题:【泉七培训-黄施霖】分球

【题目背景】

小奇将糖果都装回了同一个口袋里,现在它想把糖果分到一些口袋中,以便送给它的小伙伴。

【问题描述】

小奇有n个口袋,标号从1到n。第1个口袋装着m个糖果,现在小奇要对糖果进行移动,使得第i个口袋正好有ai个糖果。

小奇手头有一个半自动分糖机。每次它可以选择两个标号a,b(要求口袋a的糖果数为偶数),然后分糖机会将口袋a中的糖果分成相等数量的两份,然后将其中的一份取出来放入口袋b。

小奇想知道,如何操作能达到它的目标呢?

【输入格式】

第一行包含一个正整数T,表示数据组数。
每组数据的第一行包含两个正整数n,m。

第二行有n个非负整数,a1,a2…an,保证∑ai = m。

【输出格式】

对于每组数据,第一行输出一个字符串,若可以通过适当的操作达到小奇的目标,输出yes,否则输出no。

第二行为一个非负整数p,表示你给出的方案的操作次数,如果上一行为no,则p为0。

接下来的p行,依次给出操作方案,每行两个整数a,b,表示一次操作。

(方案可能有很多种,你只需输出任意一种即可,对方案的最优性不作要求。若存在解,则最优解的p不会超过1000000,为防止输出文件过大,你的方案中p不得大于1000000。)

【样例输入】

3

2 4

1 3

3 24

3 6 15

2 5

1 4

【样例输出】

yes

2

1 2

1 2

yes

3

1 3

1 2

1 2

no

0

【数据范围】

对于30%的数据,若数据有解,则最少操作步数不超过10。

对于另外20%的数据,将ai排序后的序列{bn},满足:

b1 = b2 = … = bn

b1 = b2,bi = 2bi-1 (i >= 3)

对于100%的数据 n <= 10000,1 <= m < 2^31。

【评分标准】

对于每个测试点,按照下列标准评分。

若有某组数据可行性判断错误或输出格式不符合要求,得0分。

所有数据可行性判断均正确,得4分。

所有数据可行性判断均正确,且均给出了合法方案,得10分。

【题解】

30%的数据,暴力迭代深搜

对于20%的特殊情况,容易构造解。

1.b1 = b2 = … = bn时

显然n = 2 ^ K 才有解,考虑逆操作,每次将两个大小相同的数合并,注意要将编号大的并给编号小的,这样才会最终到第一个位置。

2.b1 = b2,bi = 2bi-1 (i >= 3)

考虑逆操作,将b1和b2合并,然后和b3合并,以此类推

对于100%的数据

令d = gcd(ai),可以证明若m = d * 2^k问题才有解。

令a1 = b1d , a2 = b2d … 找出所有bi为奇数的i,两两配对进行逆操作,如此所有的bi将变为偶数,d的值将倍增,直到等于m为止,复杂度O(nlogm)

30分

100分

 

  • sunzeyu2015年12月20日 下午10:00 回复

    黄学长你今天写的那个SPJ是在Lemon下的,Cena用不了,可以给个Cena的评测包么?谢谢

    #1  
    • hzwer2015年12月20日 下午11:48 回复
      admin

      你打开spj,把主函数开头注释前的部分删掉,把注释恢复回来

      #11