APIO2018练习赛 题解

PDF题面

C(无提交地址 未知来源)

解法是贪心+特判

每个先分0.00 \cdots 01 然后剩下的全补到最小的那个去

注意几种特判(以下“最小的”统一指最小的那几块蛋糕重量)

第一是不行,这个包括超过1  和  最小的凑不齐没法进位(最小份只有一份)

还有就是分了11个最小的然后进位很尬尴

拆掉一个0.00 \cdots 01 补到某另外一个最小的就行。

第三个是各种进位处理,还要注意特殊处理那个不是0.00 \cdots 01 的蛋糕的输出。

这玩意实在讲不清楚,只能代码说话

D (Cf Round 402 Div1 D)

Cf链接

我们考虑从上到下从左到右处理这些方块

然后把始终状态都向中间状态靠拢

也就是全是横着的 或者全是竖着的

————  |||||

————  |||||

这两种(具体取决于 n \; m 哪个是奇数

然后对于不在正确位置的递归处理(注意是向右下递归处理,把当前块当左上块

有一个很显然也很容易证明的性质是如果这个东西转不动

那就递归处理碍事的一部分

最后一定能递归到能转的那个。

然后就这么递归一下就完了。

E. (Cf Round 467 Div1 C)

考虑一种构造方法。

n=13
1234x56789abc
cba987651234x (1)
x432156789abc (2)
cbax432156y89 (3)
98ycbax432156 (4)
65123498ycbax (5)

我们可以从abc轻松构造出ycbax , 加两个字符就需要五步。

这样从中间开始构造目标串就好了

注意处理奇数的情况,好好想想就会发现一共有四种情况。

然后完了。注意特判一些不用reverse的情况

这题真难写可写死我了

发表评论

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

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据