Educational Codeforces Round 84
赛后补题
A题:
题意:输入一个数n,还有一个数k,问能不能将n拆成由k个奇数组成的数
比如 6 2;6可以拆成1 5;注意这k个奇数不能相同
思路:
易得结论1:n与k必须同奇偶性,可以简单证明一下,比如n=11;k=4;时4个奇数相加一定是偶数,它们不同奇偶性,反之也是,比如n=12;k=3;3个奇数相加一定是奇数,所以得保证,同奇偶性
结论2:k*k<=n 通过等差数列前n项和可以推出,如果超过了则不存在了,(1+(2k-1)k就是k平方,得小于n
代码:
1 |
|
B
一道模拟题
题意:有n个公主,然后每个公主有其想要嫁去的国家,一个国家只能接纳一个公主,问如何添加使得嫁出去公主最多。无需添加则输出OPTIMAL,就行了。
思路:国家的王子匹配公主,如果王子没被匹配上的话,就给公主匹配上,判断有几个公主匹配上了,如果总数为n,则不用添加匹配了,如果不为n,则得添加,那个没有匹配上的公主,和没有匹配上的国家王子
代码:
1 |
|
C
cf的套路真的是活啊。。。。
题意:在一个 NM 的矩阵中,给你 k 个起始点和 k 个目标点,你可以进行移动操作,每次可以让所有起始点向同一个方向移动一格,要让每个点至少走一遍它对应的目标点,总移动次数不超过 2N*M 次。
题解:走到最左上端,然后来回摆动,奇数往右跑,偶数回来,绝对不超过,2mn次数移动
代码:
1 |
|
E
???OEIS???