A
记少加一个取地址符怒挂 90pts。
虽然本身也不是正解吧。
先用 A 造个线性姬，然后用这个线性姬把剩下的数变成 B，再用处理好的部分造线性姬，回头处理 A。
上面这个在 \(n\) 较大的时候表现良好，因为用 B 可以造出一个完整的线性基。
上面是没加取地址符挂的 90pts。
（下面的东西大概率是错的）
当 \(n\) 小的时候要用到 A 线性基未处理部分，但是一个问题是如果 A 线性基用掉了第 \(i\) 位，并且 B 线性基还没有第 \(i\) 位，当以后需要第 \(i\) 位时就无解了。然后我们贪心的处理第 \(i\) 位时如果 B 线性基没有第 \(i\) 位就先跳过不处理，最后再跑一遍处理未处理的，然后过了...
好像确实是错的来着哈哈不管了。
B
首先答案下界是
\[\frac{1}{2}\left(\sum_{i = 1}^{n}|a_i - b_i|\right) + cost \times (n - \texttt{环个数}) \]对于第一部分考虑从 \(a_i\) 到 \(b_i\) 至少也要 \(|a_i - b_i|\)，然后由于是双向奔赴最后总答案被算了两次，第二部分是一次交换至多增加一个环，不做负贡献的话至少要交换 \(n - \texttt{环个数}\) 次。
对于两个位置 \(i, j\)，交换后还是答案下界的条件应该是：
\[|a_i - b_i| + |a_j - b_j| = |a_i - b_j| + |a_j - b_i| + |a_i - a_j| \]根据题解解完后是
四个元...不想去绝对值的话感性理解一下，两条线段交换端点并加上两端点的差值，相离血亏，相交不赚。
对每个环分开考虑，把环中 \(b_i\) 最小的 \(i\) 拿出来，那么剩下的位置 \(j\) 已满足 \(a_j \ge b_i, b_j > b_i\)。
那么上面的要求化成 \(a_i \le b_j, a_j < a_i\)。注意到（并没有）对于任意长度 \(> 1\) 的环总能找到这样的 \(j\)。维护两个指针一个顺时针找一个逆时针找。
这样找的次数总是长度较少值（最多找环长一半），时间复杂度 \(O(n \log n)\)。
C
没改动，说一下挂分经历。
对于 \(m = n - 1, x_i = i, y_i = i + 1\) 的链，由于数据只保证了链而没有保证 \(x_i = i\) 挂了 12pts。
对于 \(l_i = r_i\) 简单线段树分治空间开小挂 12pts。
不是 \(n = 10^5, V = 10^9\) 空间左移 \(5\) 不够吗？
还有不删边部分经典整体二分我又去写线段树合并了/kel
这部分没挂。
但是没绑包在神秘点多拿了 3pts。
P4035
在算法竞赛进阶指南看到的，列一个每个点到球心的距离的方程组，然后上下两个方程做差平方差消掉常数和二次项。然后高斯消元。
看看 ai 怎么说
P2421
形式化题意：
求最小的 \(m\) 使
\[\forall i \neq j\ \ \ C_i + P_i x \equiv C_j + P_j x \pmod{m} \\ \]在 \(x\in [0, \min(L_i, L_j)]\) 范围内无解。
由于题目保证 \(m \le 10^6\) 所以直接枚举 \(m\) 然后 exgcd 检验。
P3200
卡特兰数。
挖掘性质，对于偶数位，一定大于左侧所有数。也就是偶数位上的数大于等于下标。
转化题意，从小到大填数，每个数只能放在最前面的偶数位或最前面的奇数位，并且任意时刻偶数位个数不超过奇数位个数。
这个题意很卡特兰数。
然后模数任意用不了逆元，暴力用质数算每个数质因数分解求出答案的质因数组成。
由于时代变了所以卡过去了。
标签：10,题意,处理,29,然后,偶数,24.10,线性 From： https://www.cnblogs.com/KinNa-Sky/p/18514277