。。。。6.5 / 10 。。好像还不如上个月。。撞墙死了算了。。。）。。。
Level 1:
Little Elephant and Bombs
。。签到题。。略。。）
Delivery Boy
。。Floyd 。。
Range of Data
。。树状数组 + offset 。。 ）。。没有离散化 T 了一次。。
Lucky Driving
。。矩阵优化的动态规划。。（暴力的话把各种子函数预处理起来也能过。。
Level 2:
Block Game
给定 n 个人 n 个点。。给定每个人到每个点的时刻。。（。互不相同。。
现在要求给每个人选择一个 block 点，使得任意一个点被 block 之后就不再被访问。。。
——————————
。。考想法的题。。大概能猜测到时贪心。。我一直在想是不是按照某种顺序依次决定 block 点。。。
。。。。但是始终没什么想法。。其实看到两组 Rank 数组的话大概应该要想到往稳定婚姻问题上面靠了。。
。（。做法大概就是延迟认可。。。一组 block 方案不合法等价于其对应的稳定婚姻模型中存在不稳定匹配。。。
Machine Gun
机关枪 (Machine Gun) 的攻击范围是自己的四个角。。类似象棋中的象。。。并且如果中间位置有障碍的话攻击不过去。。
。。。初始地图 700 * 700， 问最多还能再放多少挺机关枪。。。.
————————————————
。。（。。大概就是棋盘上互不攻击的象。。比较明显的二分图最大独立集模型。。
。。注意规模大大大大大。。要使用适合稀疏图的 Hopcroft_karp 算法。。。。
Game count
多对多拔河比赛问题。。n 个点无限条边。。要求。有边的点之间度数都相同。。。
。。图必须可平面。。问度数不超过 k 时的连线方案总数。。
————————
。。（。平面图首先想到 Kuratowski 定理。。不可平面图一定同胚于 K5 或者 K3,3。。。
。。但是没办法直接使用这个定理。。后来想到对于任何可平面图。。一定满足 E <= 3n - 6。。（可以由平面图的欧拉公式推得。。
。。因此实际只存在两种合法的结构。。一种是 1v1。。。一种是 n 个人的环图。。（n >= 3 。。。
这样对于 k 。。其实只有 0、1、>= 2 三种情况。对后面两种情况。。搞出两张表出来就行了。。。
____________________
A001006: Motzkin numbers
A000108: Catalan numbers
Level 3：
。。本期 Level 3 的两题都是与图论有关的博弈问题。。
——————
A Game of Thrones
博弈问题，给定 n 个数 Ai，每个数可以使用 Ci 次。。
两人轮流取数，每次删掉上一个人取的数并取一个与之相邻的数，
这里的相邻定义为，相互之间相差一个素因子，问是否有必胜策略。
——————
。。首先对相邻数连边。那么原问题等价于一个 Daizhengyang Chess 。。。
。。对于 Daizhengyang Chess 。。要点在于找图中的完备匹配。。。。
。那么这里似乎需要一个一般图多重匹配的模板。。这个好像可以改带花树模板里面的 Link 。。改成 Pair 数组。。
。。。（或者如果有线性规划求多重匹配的模板的话改起来更容易一些？。。
、但是这个图实际上是个二分图。。（根据对应数字素因子指数和的奇偶性。。。。
。。。因此可以直接用网络流来做就可以了。QAQ。。。
Two Magicians
。。。给定一个无向图，两个人轮流移动。初始位置固定。。每个回合分为三个阶段。。。
。。阶段 I。。从当前位置出发到连通区域里的任意一点。。
。。如果这个点恰好是另一个玩家，则宣告胜利。。
(。。也就是说在第一阶段只要和另一个玩家同处于一个连通区域里既可宣告胜利。。)..
。。阶段 II。。新建一条边，当无法新建边的时候直接判负。。。。
。。。阶段 2 的存在确保了游戏终止。。
。。阶段 III。。如果 MP 不为 0 。。那么可以消耗 1 点魔法值施展传送。。
。。传送的意义主要在于在不同的连通块之间穿梭。。
。。注意传送不会判定胜利。因此不会发生主动传送到对面所在的连通块的情况。。
。。初始时双方 MP 均为 P。。。。问先手方是否存在必胜方案。。
————————
不会做。。。
Level 4…
Eastern Draughts
。。本期的附加题是跳棋问题。。给定初始局面。。要求所有棋子都贴近左上角。。
。。最小化总的移动代价。。。。
。。。Step 1。。先写个暴力骗分。只要求得到分就好。
。。Step 2.。。为了最大化跳的收益应该进可能的先移动较靠后的棋子。。
。。。Step 3.。。寻找一些可以加分的模式。。例如。。。两个棋子之间交替跳跃前进。。若干棋子在必经之路上搭桥。。。。
。。。。。
