这种题目，说水也不算水，写起来还是挺麻烦的。每一步都很简单，但是每一步都需要注意细节。写起来比较耗时间，所以习惯要好才行。

这道题给我的教训是，返回对象的时候，那个对象不能太大。寒假刚开始的时候看了一下操作系统，里面涉及了一些 C 和汇编交叉编译的东西，就大概知道 C 的函数调用约定下，返回值是要存在 [.SECTION stack] 的。而且似乎 C 是不能够返回“太大”的东西的，C++ 才行。我猜 C++ 的调用约定应该也是类似的，所以返回大东西会有问题。这一次具体地表现在，对那个需要返回的对象的修改无法进行。

阅读全文

这种博弈问题我做得很少，开始在纸上推，还是比较复杂。看了别人的题解才大概知道应该怎么做。大体上是把问题等价地简化，然后就有点类似动态规划了：先把边界搞清楚，然后记忆化递归看是必胜还是必败。

从这道题的规则上看，每次操作要么让一组数减 1, 要么把两组数合并成一组。其实还有一个特别的地方，那就是，如果有某组数是 1, 如果有一方让这组数减 1, 这组数就被抹掉了，组数同时也少了 1. 所以如果有一组数是 1 的话，将其减 1 的操作，相当于平时操作了两下，就改变了奇偶性。

阅读全文

这道题还是比较水的。如果用手掰的话，不管怎么掰，每次掰块数都会增加 1. 比如说，一开始是一整坨巧克力，然后掰一下，变成 2 坨，再掰，成 3 坨。一直掰到 N · M · K 坨，需要掰 N · M · K – 1 下。然后用刀切，对于一个面来说，切一次，少一条缝；切两次，少 3 条缝……总之，大概就是切个 [latex] \lceil \log_{2}{N} \rceil + \lceil \log_{2}{M} \rceil + \lceil \log_{2}{K} \rceil [/latex] 下。

注意这题的数据范围，每个数最大 2000, 三个数一乘，可以到 80 亿。所以用个 64 位整型才行。还有就是算对数的时候，可以用位运算，比 math 库里那些快多了。

阅读全文

这是一道阴险的水题。现场赛的时候是队长 Wideas 过的，似乎过得也没有太大障碍。但是赛后我自己写，感觉题意比较模糊。如果没有看样例测试数据，可能怎么错的都不知道。

主要注意的有几点，一个是，在某处如果射了 2 箭，其实只会产生一个洞，所以重复给出的点只能算一个；还有一点，如果所有三角形的集合是 A, 以“相似关系”划分这个集合，即有 A = A₁ ∪ A₂ ∪ … ∪ A_n, 其中集合 A_i 中的三角形互相相似，那么题目要求的东西是 max { |A_i| }.

阅读全文

类似于图论的次小生成树。现场赛过程中，在 WH 的提示下，Wideas 敲的这题。赛后 WH 回忆到，比赛时他想起暑假的时候郭炜说：“你们一定要懂次小生成树啊！”结果就想出了这题……

首先生成图的最小生成树，然后，枚举任意两点 u, v: 如果边 (u, v) 就在最小生成树里，那么就算一下把 (u, v) 当成 magic road 时，［人口 / 其余路径长度］的值（即 A / B 的值）；如果边 (u, v) 不在最小生成树里，那么此时如果连接 u 和 v, 就会形成一个环，在环上找到除 (u, v) 外最大的一条边，删除之，再以 (u, v) 为 magic road, 计算 A / B 的值。记录下每次计算出来的值中的最大值，输出之。

阅读全文

这道题的题意是，一些学生说出他们各自的排名范围（不存在并列），然后有的学生说谎了，结果就产生了矛盾。比如有 3 个学生分别都说自己的排名是 1 ~ 2 名，那么肯定至少有一个学生说谎。题目要求计算出最多有几个学生说了真话，并且把那些说真话的学生序号输出。如果有多种情况，输出字典序最高的那种。

数据范围，最多有 100 cases, 学生最多 60 名。排名的话，以区间 [x, y] 表示，其中 1 ≤ x ≤ y ≤ 100000.

阅读全文

这道象棋模拟题其实还是比较简单的，但是写起来要注意的地方非常多。测试数据据说不太刁钻，比如那种黑方能够直接获胜的棋局（表现为一开始将帅之间就没有任何棋子而相对）是没有的。不过为了内心的宁静，我在代码里还是加上了这些特判内容。

赛后练习时提交了三次才 AC, 原因是判断红方马的时候不小心判断到了黑方 boss 的原来位置上（而正确的判断方法应该是黑方 boss 走一步之后的那个位置），后来检查了几遍才看出来。

阅读全文

不错的计算几何题。题目输入若干个简单多边形（允许存在凹多边形，但是多边形的边不会交叉），它们的质量是均匀的。要求计算每个多边形在水平线上有多少种稳定的摆放方式。其中一个比较特别的地方就是，如果重心和支撑线段所作的垂心与支撑线段的端点重合，视为不稳定的状态。具体原题的配图中说得很清楚，就不多说了。多边形的边数可能达到 50000 条。

思路应该是比较清晰的：首先求多边形的凸包，然后求多边形的重心；再枚举凸包上的每一条边，从重心向枚举的边作垂线；如果所作的垂线能够与边规范相交，那么这种情况是一种稳定情况。

阅读全文

这道题目是一道不错的计算几何题，题意是在一个平面上，有若干个圆（题目中称为商场）。然后需要以这些圆中的某一个圆的圆心为圆心画一个圆（题目中称为伞），使得新画的这个圆能够覆盖任何一个其它的圆的至少一半的面积。求这个圆的最小半径。

这道题的思路是，枚举每一个圆的圆心，然后以它为圆心画圆。用二分法处理半径，每枚举一个半径就尝试看能不能满足覆盖条件。然后找到最短的半径就行了。

这道题有至多 10 个 cases, 至多 20 个圆。圆心的坐标范围是 [-10000, 10000], 半径范围是 [1, 2000], 输入数据都是整数。输出要求精确到 1e-4 这样。

阅读全文

这道题是一道水的模板题，就是求个单源最短路。而且一开始我还想多了，还以为有负权环，结果居然没有。所以整道题就水了。SPFA 水过，唯一与模板不同的地方，就是它里面的节点有一个属性，叫做“是否是海滨城市”。求得单源最短路之后，要把所有的海滨城市的结果进行比较，取其中距离最短的那个。

阅读全文