用户工具

站点工具


2020-2021:teams:manespace:codeforces_round_660_div2

codeforces_round_660_div2

A. Captain Flint and Crew Recruitment

题意:定义$nearly prime$数为两个不同的质数的乘积,问给定一个数n,是否存在四个互不相同正数的和是n,且四个数中至少有三个为$nearly prime$数?

题解:最小的三个$nearly prime$数为$6,10,14$,所以只要小于等于30,一定不行,大于30的数,特判一下减30的和是否等于6,10,就或者14,是的话就用$6,10,15$这三个数代替。

B. Captain Flint and a Long Voyage

题意:将一个n位十进制数把每个位上的数写程2进制后拼接在一起,然后去掉最后n个数,问n位十进制为多少时能使处理后得到的2进制数最大?

题解:容易发现,在最后去掉的n位中,如果最后的n位能尽可能长,去掉的数站的比例会越小,所以只考虑二进制后为4位数的8和9,如果n是死的倍数,最后$\frac{n}{4}$位全部填8,之前全部填9,其余情况,最后$\frac{n}{4}+1$位全部填8,之前全部填9。可以证明这就是最有情况。

C. Uncle Bogdan and Country Happiness

题意:垃圾题意,看了半天不知所云,推荐看样例说明https://codeforces.com/contest/1388/problem/C

题解:可以从每个叶节点出发,向上回溯,发现由预测出的$h_i$和经过这里总人数$p_i$可以算出开心的人数和悲伤的人数,之后只要检验能否由那两个量算出正整数解,而且,所有叶节点开心总人数是否比父节点开心总人数低即可。其实可以更严谨的列方乘解出,由开心转悲伤的人数,留下来的开心和悲伤的人数,然后验证是否是正整数,但是貌似判断到上面说的那样已经可以限制死了。所以就没有必要了。

2020-2021/teams/manespace/codeforces_round_660_div2.txt · 最后更改: 2020/07/31 16:57 由 iuiou