ksm在玩套圈游戏

推论1：

最终答案圆的圆心一定在坐标轴上。

证明：

在圆内含（包括内接）正方形的情况下，圆和正方形相切的点可能有0,1,2,4个

在保证不接触s2的前提条件下，有：

假设最终答案与s1的交点为0个，那么一定可以通过圆心不动，缩小圆的半径的方法，在原有的圆范围内，找到更小的满足答案的圆，直到圆与正方形出现交点。故假设不成立

假设最终答案与s1的交点为1个，我们设交点为a，那么一定可以通过将圆心向a的靠近的方法，缩小圆的半径，并保证缩小后的圆始终在原有的圆内，直到接触到第二个点。故假设不成立。

所以最终答案一定和圆有两个或四个交点。

由圆的性质可得，圆心始终位于圆上任意两点的垂直平分线上，故答案圆心一定位于坐标轴或对角线所在的直线上。

假设最终答案与s1交且仅交于对角线上的两点，即圆心位于对角线上，容易证明不存在除原点外的点，使得四个点均位于圆内。

推论证明完毕。

既然知道我们要找的圆在坐标轴上了，我们怎么找到我们需要的最小圆呢？

如果s2一开始就没有与s1的最小外接圆（即圆心为原点）有公共部分，那直接输出圆心到正方形任意一个角的长度即可。

如果s2一开始有和s1的最小外接圆接触呢？

推论2：

当我们把圆在符合内接s1两点的前提条件下在坐标轴（即反方向两点的中垂线）上移动时，以圆相切两点连成的直线为界，在移动方向反方向，小圆覆盖大圆，在移动方向正方向，大圆覆盖小圆。证明略（当三角形的两条边确定时，这两条边的夹角越接近180°，第三条边越长，越接近0°，第三条边越短）。

通过这条推论我们可以证明，只有当我们把圆心沿着s2与外接圆相切的那段圆弧的反方向移动，才有可能不与s2接触。（由于s2与s1是相离的，s2不可能与s1最小外接圆接两段弧） 很容易就能得到思路，我们直接在可能的方向进行二分答案即可。

但直接二分答案只能得到答案错误，这是为什么呢？

仔细思考，会发现存在一种特殊情况。

在圆沿着坐标轴不断变大的时候，和相交的s1两点附近的那段弧，会趋近于一条直线。如图，如果一开始s2交了上面那段圆弧，但又存在点越过了DC线，那我们二分的区间，就是不单调的，因为当圆半径过小的时候不行，当圆半径过大的时候也不行。

做法1：

那在这种情况下，如果我们能够找到一个点，使得这个点能够保证做出来的圆可行，那我们直接在这个点和原点的区间里面二分找答案，不就行了么？

标程中找到的点，是过c点作垂直于EG的直线，与y点的交点就是我们要找的点。

做法2：

二分时也可以通过考察圆弧与障碍物的交点来决定二分的方向，若交点与一开始所在的圆弧方向不同或者没有交点，则二分(l, mid)。否则，二分（mid, r）

你是银狼

题解：

考虑反悔贪心，用一个大顶堆存挑战过的挑战房间所消耗的生存值。

一、首先奖励房间是一定会拿的。

二、假如到一个挑战房间：

1.可以挑战，那么就贪心的通关房间i，然后将其放入大顶堆中。

2.无法挑战，如果之前通关过挑战房间，就比较堆顶和房间的消耗的生存值，假如撤销后可以挑战当前房间，那么就挑战，将之前挑战的某个房间撤销；否则放弃挑战这个房间。在之前没有通关过挑战房间则只能放弃。

三、如果到了一个事件房间：

1.可以挑战，但是不放入大顶堆。

2.不可挑战，和前面类似，比较堆顶和房间消耗的生存值，不过由于不能放弃，就要一直放弃之前通关的挑战房间，直到这个房间可以通关。如果堆空了也无法通关，就直接退出。

尽管事件房间可能会导致之前挑战的所有房间都被撤销，但是只要能通关这个事件房间，都有可能有更大的答案，所以每一步都要取max，最后答案就是全局最大值。

取糖果

由于每次操作只能对同一种连续的糖果进行操作，所以我们可以考虑只看同一种糖果的情况，对于每种糖果都需要相同的操作，相当于把每种糖果都删光是一次公平组合游戏，并且每种糖果的操作是相互独立的，可以考虑Nim博弈，求SG值

将每种糖果抽象出来，会变成x堆长度为n的01字符串

例如：

5 5

5 1 2 3 4 5

4 1 2 3 4

3 1 2 3

2 1 2

1 1

1号糖果：11111

2号糖果：11110

3号糖果：11100

4号糖果：11000

5号糖果：10000

现在对于每个01字符串，我们只考虑每段连续的1，问题变为了求每次删除一段长度为i的连续1段的SG值，对于同一个字符串中有多段连续的1串，由于它们也是相互独立的，也可以利用Nim博弈求SG值

综上，我们需要求每种糖果操作的SG值，可以通过求每种糖果中，处于连续状态的糖果的SG值

对于，求长度为x的连续的1串的SG值，可以通过打表或者记忆化搜索等方法求解

SG(ans) = SG(S_1)^SG(S_2)^...^SG(S_x)

SG(S_k)指一种糖果构成的01字符串的SG值

SG(S_k) = SG(T_1) ^ SG(T_2)^.....^SG(T_x)

SG(T_k)指一种糖果构成的01串中对连续的1串操作的SG值

其实主要就是我想求SG（111111）就需要到达(l,r)这种状态，如果只是单纯到达L or R 这种单状态的就直接取mex就行了，但是它每次的状态(l,r)都又变成了两种不同的状态，就是说（l,r）是两个有向图游戏，这个状态的SG（l,r） = SG(l)^SG(r),然后继续求SG（l）,SG(r)

结论：长度为x的连续1串，每次只能删除一段连续的1的SG值等于其长度本身

神秘的黑洞

对于每次询问，首先考虑黑洞的吸收问题，通过暴力n方枚举黑洞是否被吸收会超时，可以将黑洞按照半径排序后用set维护出最终剩下的黑洞。

由于没有一样半径的黑洞，所以在一个点上最多只有一个黑洞。

接下来讨论一个人是否能进入黑洞，由于有黑洞的吸收规则存在，不难证明一个人最多只能进入一个黑洞，证明如下：

如果两个黑洞的吸收范围没有交集，那么人跳跃完能进入某个黑洞必须满足两个分身都在其中一个黑洞范围内，如果两个黑洞的吸收范围有交集，那么人跳跃时必须有一个分身在某个黑洞上，由于黑洞是稳定下来的，所以黑洞不会在其他黑洞的吸收半径内，所以人只能跳到这个黑洞上。

所以我们可以考虑枚举黑洞，计算该黑洞能够吸收多少个人，假设黑洞的位置为pos,半径为r，人的位置为i,那么人能进入黑洞的条件：

如果i<=pos，则要满足i>=pos-r/2并且i+a[i]>=pos 如果i>pos，则要满足i<=pos+r/2并且i-a[i]<=pos。

于是问题转化为在区间(pos-r/2,pos)上有多少个i+a[i]>=pos和在区间(pos,pos+r/2)上有多少个i-a[i]<=pos，这个问题可以使用可持久化线段树解决。但是题目有a[i]可以修改的条件，所以可以使用树状数组套权值线段树来解决。复杂度为nlog^2

laoya 的有根树

首先考虑操作三的答案为什么，如果x为叶子节点，答案为-1，否则答案为以i为根的子树中g值最大的两个节点的乘积或者以i为根的子树中g值最小的两个节点的乘积

如果整颗树都知道，不难使用树链剖分维护出每个节点下的最大，次大，最小，次小g值，于是我们可以将操作离线下来先建树，在枚举时动态的修改节点的权值，就能得到答案了。

养猪流

这道题是一个签到，手推一下就可以发现，假设战斗力为a，那么他能够贡献出来的战斗力为a – 1，当a = 0 的时候，则贡献为0， 那么只要让其中战斗力较小的四个人将战斗力全部贡献给初始战斗力最大的那个人即可。

数组划分

进制转换

子串就是后缀的前缀，所以可以枚举每个后缀，计算前缀总数，再减掉重复。 「前缀总数」其实就是子串个数，为。 如果按后缀排序的顺序枚举后缀，每次新增的子串就是除了与上一个后缀的 LCP 剩下的前缀。这些前缀一定是新增的，否则会破坏的性质。只有这些前缀是新增的，因为 LCP 部分在枚举上一个前缀时计算过了。 所以答案为：

世界树拯救计划

由于SPJ的未知问题，这题在搬运到牛客上时出了一点问题，导致这题没有出现在牛客上

由可得。

设a的树上前缀异或和为，有。

则

即只需要确定的值，就可推出所有的值。

因为题目需要各不相同且在范围内，且保证有解，可推出全都不同，所以从0到n-1枚举b[1]，看能否使得，若满足要求，根据鸽笼原理可以得到所有的b[i]均在[0,n-1]范围内，且各不相同。

判断可以用01trie优化。

卡牌游戏

这题是一道非常裸的状压dp，但是重点不是算法，而是时间复杂度的计算，通过人为设置一些小坑点卡掉一些不是那么优的推导方法。

正解的方法是将每个卡牌是否拿到手里进行状压，形成一个长度为n的01串，需要预处理出推导的顺序：从少1的状态推到多1的状态。然后对于每个状态，让其或上每一组牌的种类决定是否可以推导以及推导后的新状态，然后加上诅咒牌的数量作为代价进行转移。时间复杂度为2^n*(3*n/m)。要注意到当n=22，m=1时具体的值最大，为2^22 * 66 = 276,824,064，已经很接近危险值了，所以如果是使用记忆化搜索的同学可能会炸时间复杂度，可以特判m=1进行规避。（出题人的std在不进行任何特判的情况下，最大数据跑了349ms，应该是绰绰有余的）

错误的方法就是以牌组为状态进行转移，在此不再赘述，时间复杂度必炸无疑

电表倒转

模拟题。

可以使用一个队列来存储随从进去手牌的先后顺序，每次放置随从触发冥想时，直接通过遍历队列模拟冥想效果即可。