2020-team12-039

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team12 返回]

[[Image(2021-0320standings.png, 1000px)]]
[[Image(2021-0320submissions1.png, 1000px)]]
[[Image(2021-0320submissions2.png, 1000px)]]




== 问题 ==

前期节奏垮，全程就很难提的起状态。 最后的J疑似被卡常实属可惜。



== 题解 == 

简版题解：https://codeforces.com/blog/entry/63729

A: 签到。

B: 贪心。设f(p)为使得n*(n+1)/2>=p的最小n，则最优策略应该是让一只怪死在第f(p)秒，后一只怪死在第f(p+q)秒。
需要做先杀死哪只怪的决策，然后进行比较；比较后贪心输出策略。在两种决策答案一样时需要特殊处理。

C: 又是“题目要点在关键字”系列。首先行和列可以单独考虑，可以发现所有车构成的矩形会不断缩小，一个棋子一旦到了边界就再也不会扩展矩形。
考虑把二维拆成两个一维，把每一步所有车的移动看成是棋盘边界移动，每次移动一步就把会到边界上的棋子记录并修改，在维护两条边界与实际值偏差多少（右移k或左移k，且有边界)；询问时直接输出棋子横纵坐标与实际值偏差的和即可。
至于碰撞，正是由于所有车起始位置，两个车会相撞当且仅当他们同时触碰到同样的两维边界（也即我们的边界的四个角）。对四个角记录有多少车撞到，输出时讨论几个角有没有被缩成一起并输出排列数即可。注意可能有同时撞到两个相邻角（因为另一维已经合并了）的情况，需要特判，每个车只记撞到一个角。

D: 签到，纸笔几何题

E: 签到，找规律后高精度乘和辗转相除法。板子得整理了，szb现写不很熟练。


F: 较易题，处理好这个奇葩蜂巢然后bfs即可....但是ctc数组开小到最后才发现

G: 待补

H: SA，szb

I:签到

J: 待szb写，被卡常卡的十分痛苦。

K: 待补

L：待补

[/wiki/2020-team12 返回]