Solutions

Reversi

根据观察，可以得到如下结论：

1. 因为棋子一定是相连的，故只要棋盘上还存在两种颜色的棋子，一定有一方玩家可以操作。
2. 由1结论可知：游戏结束状态一定是所有棋子都变成了某一颜色的。
3. 连续的同色棋子可以被视作一个该颜色的棋子，为方便表述，将这个等价的棋子称作“同色段”。
4. 每执行一步操作，同色段的数量必定减一。结合结论1、2可知，同色段数量为1时游戏结束，且哪个玩家操作后达到这一状态，则哪个玩家获胜。
5. 特例，如果一开始只有一个同色段，则获胜玩家取决于同色段的颜色。
6. 当第一个玩家操作后（注意：第一个玩家不一定是题面意义上的先手玩家，因为有可能初始状态仅对于先手玩家是无法操作的），后续回合双方玩家一定都能操作，而不需要跳过回合，直到游戏结束。
7. 如果计算出同色段的数目为x，则双方的操作就是轮流对x减1，直到遇到x=1状态的玩家输掉游戏。

综上所述，计算同色段x，之后确定实际意义上的“先手玩家”，再根据x的奇偶性就可以判断输赢，时间复杂度。

上述的做法已经能够通过这道题目，但是我们可以更进一步，经过分类讨论并结合上面的结论可以发现，只有当两侧都是白子时白方才能获胜，其余情况黑方一定能获胜，这一方法可以通过时间进行检查。

Baba is You

1. 注意到道具不会产生碰撞
2. 注意到道具可以移出边界
3. 起始位置全已知

首先考虑移动操作，假设整张地图上摆满了同一种物品，之后进行次移动，每次移动枚举的物品，这样在时间上很显然是不可行的。这时注意到我们关心的实质上是物品从初始位置到终止位置的位移，使用向量表示，假设一个物品初始位置是，其在若干次操作中向下移动了次、向右移动了次（取负值则表示向相反方向移动），记作位移向量，则物品最终的位置一定是，这样问题就变得容易处理了，上下左右四个移动可以用四个单位向量表示，位移向量则是对该物品进行的多个移动对应的单位向量的线性叠加，即对于每次移动，可以用时间更新位移向量，所有操作结束后再用一次时间来计算物品的最终位置即可。

接下来的问题就是如何处理物品种类的变更了。注意到物品种类的变更不仅仅需要维护合并信息，合并前的移动信息也需要想办法维护下来，使得最后能够一并更新所有物品的位置。可以使用链表来实现，对于每种物品，引出一个链表，链表结点上记录位移向量，这个位移向量的含义是，在这条链表上，当前结点之后（包括当前结点）的所有结点的坐标都会加上这个位移向量，当将一种物品a变成另一种物品b时，可以将a物品的链表加入到b链表的头部，同时为了维护变更前a、b各自的位移向量的正确性，将b的首部的位移向量减去a的链表尾部的位移向量。而每次移动操作只需要更新链表首结点的位移向量即可。最后遍历所有链表计算所有道具最终的位置。

Nitori and Stack-Tech

因为没有重复元素，所以贪心模拟即可，使用一个栈，如果遇到当前能够放置的零件的时候就弹出，直到栈空或者栈顶元素当前不能放置，这时就需要继续压栈，如果遍历完整个序列后栈为空，则说明可以满足要求，反之不能满足要求。

Triangle

分形图形，与递归结构有着天然的对应关系，所以采用递归的方法来绘制图形并预存下来就可以完成。

Sweet

令得到糖果的人的位置为，得到饼干的人的位置为，问题等价于希望知道有多少对二元组使等式成立，整理一下就是，熟悉配属等式的选手应当能很快看出来这时一个形如的等式，可以通过扩展欧几里得算法求解。若令，当且仅当时有解，如果是一组解，则仍然是解，可以发现对于每一个存在于解中的有且仅有一个存在于解中的与之对应，只需要对单侧计数即可，于是可以计算得到可取最小值与最大值，之后计算这中间有多少个可取的即是答案。

UPD：这道题要向各位选手道个歉，耽误了大家很多时间，这道题原本有Easy和Hard两个版本，题面是Easy版本的，而数据却放成了Hard版本，由此产生了一系列问题，非常抱歉，再次向大家道歉。

Pipe

不如将与多边形在与管道壁垂直方向上的长度称作这个多边形的“有效长度”。

作为阻挡的一方，一定希望这个有效长度尽可能大，同时他一定要采取站在管道中央的策略，使得两侧可通过的距离尽可能短。

作为希望通过的一方，一定希望自身的有效长度尽可能小，从而通过。

于是问题就在于求解两个多边形最大、最小的有效长度。

对于多边形上的每个点和边，计算他到其他点和边的最大距离，一方选取其中的最小值作为有效长度，另一方选取其中的最大值作为有效长度，使用旋转卡壳的方法来实现时间的计算，这样就可以解决问题。

Gangstar

将顶点1视作树根，逃跑的策略就只有两种，一种是直接往更深的方向跑来拖延时间，另一种是先往深度小的地方跑之后在被追捕到之前进入到更深的子树中往深处跑拖延时间。所以只需要先通过搜索来计算所有结点的深度，之后再搜索一次，对于逃跑者能够到达的所有地点，计算其中耗时最大的那个即可。

Stable Fusion

使用dp可以解决，用f(u, x)表示顶点取值时子树调整代价，最后只需要从根节点获得代价最小值作为答案。形式化地说，转移条件为：

.

边界条件（叶节点代价）：

，其中是叶节点。

答案为：

。

The Flower of Hope

问题比其表面看起来要简单。

容易发现，若，则。证明可以采用分类讨论的思路，若，则余数是显然满足条件；若，有，由此可知，取模后的结果必定小于，因此满足条件，于是问题简化成有多少子区间和大于等于，使用尺取法，或枚举左端点之后二分右端点都可以解决问题。

Fuse the Cube Fragment

问题可概括为寻找任意两数不满足整除关系的最大子集。

首先考虑第一个方案，容易想到，可以倒序选取最后的个数，可以发现其中任意两个数都无法整除对方。

接下来可以确认一下这种方法获得的数是否是最大的，将每个数写成形如的形式，其中不含有因子，根据的值，将个数划分到不同的集合中，使得每个新集合内的数具有相同的，暂时不考虑所在的集合，从其它集合中任选两个集合，从中各自任意选取一个数，可以发现二者总是无法整除对方，也就是说，上述划分将所有数划分到了许多个不相交集合中，再考虑特殊的的集合，可以发现这个集合中的数都形如，只要满足选取的数的严格大于其它集合中选取数的的指数，就可以保证无法互相整除，的取值是范围内的所有奇数，因此这样的集合有，根据鸽巢原理，如果选取了个数，必然至少有两个数落到了同一集合中，在同一集合中的两个数的差别仅在形式中的值上，因此二者中较小者一定可以整除对方，所以选取个就是选取数量最多的方案，这证实了第一个方案的正确性。

接下来可以考虑第二个方案，根据上述的证明过程，可以发现，每个集合选取一个数，并让的集合的的指数严格大于其它集合选取数的的指数，就可以达到同样的目的。更进一步说，不如选取除之外的全部奇数，再从的集合中选取，这样一定与第一种方案不同，至此第二种方案也已经完成。

Star Map

因为点数和操作数都是1e5，所以不能对点暴力更新，于是考虑将点的坐标与操作分离开，使得查询时能够通过某种信息，从点的原始坐标快速计算出操作后坐标。

介绍两种思路。

第一种思路是，因为平移相当于对坐标加上常数，旋转可能产生x与y的互换，所以最后的坐标一定可以表示为，而是这个点的原始坐标，于是只需要知道六元组就可以知道最后的坐标，初始情况下这个六元组是，考虑一下缩放、旋转、平移后这六个参数会发生什么变化：

旋转：

假设逆时针旋转了角度，为了方便描述，记, ，记, ，则旋转后的新坐标为，于是可知新的参数分别是, , ，同理有，即新的参数分别是，，。

缩放：

, ，其中是缩放倍率。

即, , , , , 。

平移：

, 。

即, , , , , 。

预处理一棵线段树出来，之后遍历个叶子结点，依此将输入的操作按照上述规则更新初始六元组，当一个结点的两颗子树都已更新，就将两颗子树的操作合并到当前结点，最后线段树表示的每个区间的操作的着六个参数都是明确的。

于是考虑合并两段区间操作的方法，因为左结点表示的操作发生在右结点操作之前，所以相当于是左结点的操作先施加于原坐标之上，而右结点的操作施加与这个结果之上，假设左结点将坐标由变成了，记, ，则右结点的操作施加后会变成，整理形式可以将新的六个参数表示出来，即：

，，，

，，。

所以合并后区间操作的六个参数也计算了出来，这样建立的线段树就可以通过时间复杂度单次查询任意区间的六个参数，最后作用于查询的点的坐标上即可计算出最终坐标，有q个询问，则时间复杂度是，而建立线段树可以通过一次遍历所有结点完成，这个构建操作的时间复杂度。

第二种思路，熟悉代数或几何的选手应该能很容易想到。变换的操作可以与矩阵乘法对应起来，只要能够预先计算出所要进行的变换矩阵的积，最后乘上原始坐标向量，就可以以矩阵乘法的时间计算出最终坐标。因为存在平移，即变换过程中需要“凭空”给原坐标增加新的量，二维向量表示坐标是不足够的，这时候可以给向量增加一维，变成，这个也被叫做齐次坐标，于是构造三种操作的变换矩阵。

缩放：

旋转：

平移：

使用符号表示这个变换矩阵，而为表示原始坐标的向量，对这个坐标施加变换等价于计算。

记输入的第个操作的变换矩阵为，则通过计算的结果就是变换后的结果，形式为，此次询问的答案就是和。

矩阵乘法具有结合律，因此可以优先计算左侧的矩阵乘积，不如计算变换矩阵的前缀积，即，为了获取区间矩阵积，还需要计算逆矩阵前缀积，即，则计算，这个正是需要的查询的区间全部操作的变换矩阵。特别地，是人为添加的单位阵，方便编码，避免了对时的分类讨论。

最后考虑一下如何求逆矩阵，首先证明一下逆矩阵的存在，可以手工计算发现这三种矩阵的行列式在题目给出的数据范围下均不为，这是逆矩阵存在的充要条件。一种求解办法就是用高斯消元法求解，对于的矩阵，计算不会花费太多的时间。不过这里也可以考虑另外一种做法，假设变换矩阵为，假设它作用于一个向量，将这个变换施加到向量上，得到，两边同乘它的逆可以知道，第二个等号的含义是，对向量施加变换得到就是原始向量，即如果表示的是放大倍，则就表示缩小倍；如果表示逆时针旋转角度，则表示顺时针旋转角度；如果表示平移，则就表示反向平移等距离，即平移，因此构造原矩阵与逆矩阵的方法是一致的，只是具体数值上的差别，实现在代码上可以通过相同的方法构造出来。预处理前缀矩阵积的时间复杂度是，单次询问时间复杂度，次询问复杂度，这里忽略了矩阵乘法带来的常数影响。

The Scarborough Fair

因为要求购买全部物品，所以贪心地用尽可能小的代价尝试购买每个物品，只要遇到某个物品无法购买，即可直接明确无法达成需要。如何贪心地购买，很简单，如果可以通过不兑换货币就完成购买，那就直接购买，如果不够则尝试用其它货币2换1兑换，如果还不够就尝试用其它货币4换1。

Cappuccino ~ the end of journey

贪心即可，两种可能，全部单买（即方式1），或先全部按套装买（即方式2）再单买。

如果想要更具体的分析的话，考虑两种方式各自的单价，决定哪边更划算，先买划算的那边，如果有剩下的钱再买另一边。

时间复杂度：