~11-13 部分题解。
密码xoi。
因为前几周太摆了。所以题解从后往前写。
11-12
T1 euclid
根号分治，值得注意的是复杂度形式为：
\[ \sum_{p,q} \frac{n}{\max(p,q)}=\sum_{p} \frac{n}{p}*p \]
很是神奇。
T2 euclid
dp。
首先考虑 \(dp\)，我们发现如果记录 \(m!\) 的顺序的信息其实很亏。
那么很经典的拆贡献，考虑 \(x\) 会在那些地方产生贡献。
如果当前这个位置大于等于 \(x\) 的集合为 \(s\)，那么 \(x\) 会在 \(u\subset s,x\in u\) 的集合产生贡献。
考场时我直接对于每一个 \(x\) 开了个mask。
实际上这个可以直接差分一下，在 \(s\) 处加， \(s-x\) 处减。这样再次计算超集和的就是真实答案了。
T3 euclid
to do
我是傻逼考场时候还在“建图”，，没看直接转移。。
首先发现有用的只有这样的向量 \((0,x),(x,0)\)。
然后我们对每一个位置计算最右覆盖他的矩形，最下覆盖他的矩形。
这里你可以发现适当顺序的扫描线可以每次区间取max，全局询问，这样是 \(\sum nm+q\log n\) 的。
然后转移呢？转移形如区间Max和区间=Max的数。这个可以单调队列来做。。。很是震撼。没想到。。
代码没时间写呀/kk
T4 keter
to do
hall 定理，但是没倒出空想。。
11-11
T1 safe
进行了几步转化，首先考虑什么情况不合法？
yy了一下，可以感受到存在四元环是充分必要的，证明不难。
然后看给你了 \(p\) 那我就把 \(p\) 给排成 \([1,2,\cdot n]\) 的。
然后发现从大往下插入 \(q\) 的数，那么每次操作变成了选择一个位置，然后决策是选上还是选下，然后选上就是强制让后面的也选上了。
然后发现我们可以只对 有效的“伸出来的”计数。然后从大往下，从后往前的dp就好了。
（对于阶段的前缀和）。
T2 keter?
没写呀，很懵逼的一个构造题。
正解。。。每次随机若干个前面的小的数，然后用剩余的凑出 \(0\)。
话是这么说，大概是前面的那些组成的情况，很有可能背包出来询问？不太懂。
一个比较让我眼前一亮的做法是：设 \(w(s)\) 为 \(s\) 的答案。
那么 \(w(ks_1+s_2)=w(s_1)\times w(s_2)\) 。感觉很有道理呀。
然后每次乘法，加法，，，，类推。。。
T3 safe
比较萌萌的一个题，可以边跑边记录答案，可是有点难写。
所以最后popc分块做的。\(2\log\) 的。
T4 safe?
没写。考虑求出 \((a,b)\to (a+1,b)\) 这样相邻的能走过去的最大宽度。
然后大概就是最小生成树了？
11-10
T3
数学题。不知道如何想到最最最key的point。
单位元三角形的内心=将角分线延长后，与圆的交点形成的三角形的垂心。
然后典中典垂心坐标 \(\alpha+\beta+\gamma\)。
然后角分线对应的单位复数就是 \(\sqrt{(\alpha\beta)}\) （角分线同样将弧也分成两半）。
然后发现很好拆贡献，完事了。
T4
未写
只能说这个题太牛逼了，我也不太知道是怎么想到的。
这样有限制的题，我们就要去考虑描述限制。
网络流的最小割模型就是可以理解成，选择割的边云云。
这个题呢？乍一看，如果直接转成集合的话，那也太难了。
考虑一条边平行于 \(x\) 轴的平四可以被描述成啥。当时我考场时候在想染色，可惜呀没想到最后的。
然后？？你会发现我现在要删点呀，那我就拆点，连权值的边，割掉就表示选择，如果选择，那么平四的限制也就没了。。。
所以就是一个分层然后最小割。
11-8
T1 safe?
基础dp？
还是考虑双射，对于每一个结束状态，我们考虑如何得到这个状态的。
我们强制让这个按顺序得到。
这样限制变成了，这个数不小于前一个数。所以记录一下前一个数加了多少就好了。
T2 safe?
还是考虑最终情况。运输过程肯定形成一颗有向树。
并且我们希望对于一个集合，如果他们的需要，真实值差大于最小生成树就能合法。
原因大概就是对于每条树边，左右必有一个集合权值大于0（因为加和减去这条边边权后大于0）.然后变成更小的子问题。归纳就行。
然后找到所有合法的集合，SOSdp合并。
T3 euclid
感觉很经典的题呀，还是没有考场做出来，
首先考虑让一个点合法的区间，大概发现是一个 L
字型的。
然后每次加上的贡献就是这个区间内的。
其实就不难发现这样这可以看成二维平面，然后扫描线。
我当时以为 \(dp\) 这样不规范的更改就做不了，现在发现确实很好做。
T4 keter。
首先二分，判定性问题就是贪心，把 \(\le mid/2\) 的全选，剩下的在区间里选一个最小的。
很有趣的一点是我们确实可以随便选，但是选最小的的确更好刻画。
然后 \(2\log\) 不难了。
然后熊熊说要转化一下限制，一个中间的点合法当且仅当，他的上一个比它小的数，下一个比它小的数和他加起来小于 \(k\)。
现在更加神奇的事情发生了，我们找到了一种判据，或者说每个点的“属性”。
这样通过整体二分，就能 \(1\log\)。
实际上发现如果信息可以减去的话，我们的整体二分，每次可以看成每次向左走，集合分裂，信息不变；向右走，集合分裂，信息与向左走的合并。
如图： img1 ----
一个更加精妙的做法是，现在问题就是多少个判据<=mid 这种，我们甚至可以不二分，转化为查询区间 \(k\) 大这种问题。 很是厉害。