codeforces round #638 题解(A-D)

成功只是激发态,失败才是基态 ——曾勃

算法竞赛就像修仙,一时懈怠就会根骨尽废……还是要多打比赛啊

A. Phoenix and Balance

把2^1 2^2 2^3……2^n平均分为两组,使得两组数字和之差最小
因为2^1+2^2+……+2^(n-1) < 2^n,所以把2^n和最小的n/2-1个数,组在一起是最优的。

B. Phoenix and Beauty

被骗得好惨……
本来是想着:遇到不一样的就填入一个数字,如果连续填入了>m个数字就说明无解,应该是可以写出来的,但是写跪了
仔细看数据范围:n*k都可以过,就可以用奇怪的构造方法了
举个例子:4 6 7 5 7 5 4,m=4,由于插入数字数量不限,可以构造成:
(4)567 45(6)7 456(7) 4(5)67 456(7) 4(5)67 (4)567
所以只要把出现过的数字输出n遍就可以了,稍微注意一下细节

C. Phoenix and Distribution

按顺序做题真的会死的
题意:给一个小写字母字符串,要求把里面的字符组合成k个字符串,顺序不限,但不能有空串,求所有串里字典序最大串的最小值
构造题,先排序,看最小的字母是否有k个,如果有则把所有的串都加一个最小的字母,如果没有k个,则输出排序后的第k个字母。
接着看剩下的n-k个字母是否相同,如果完全相同则平均地加到各个串中,如果不相同则将所有的字母都放入答案串中。
输出答案串。

D. Phoenix and Science

题意可以等价为,设x初始值为1,tot初始值为1,每次将x变成[x,x*2]的任意数字,然后加入到tot中,问使得tot=n的最少操作次数
最后想不出C才看的D,其实不难(比C简单啊!!按顺序做题真的太惨了qwq
还是二进制分解,每次都把x*2(这是最快的方式)加进目前的和tot中,记录一下我们每次都给tot加了多少,直到tot+x*2>n,再把剩下的n-tot加进去。
把所有的操作sort一下,很容易证明最后加入的n-tot可以在前面的操作中加进去。
相邻元素间的差值就是答案(其实也很好想,如果有x个细菌分裂了,就相当于每回合的增长速率+x)
写法和上面文字中的说法有一点点区别,但思路是一样但。

点赞

发表评论

电子邮件地址不会被公开。 必填项已用*标注