[ARC122E] Increasing LCMs
正序构造的话，我们是不知道前面有什么的，于是我们倒序构造。当我们考虑最后一位时，前面的位都是知道的。设 \(v=\operatorname{lcm}(x_1,\dots,x_{i-1})\)，则有 \(v<\operatorname{lcm}(v,x_i)\)，即 \(\gcd(v,x_i)<x_i\)，这等价于 \(\operatorname{lcm}_{j\ne i}\{\gcd(x_i,x_j)\}<x_i\)。
当 \(i\) 减小时，\(\operatorname{lcm}\) 单调不升，\(x\) 候选集合会不断变大，于是每次随便选一个符合条件的 \(x\) 即可。
CF1656H Equal LCM Subsets
直接找子集很难，转化成在全集上删除。
考虑 \(S_A\) 中一个数 \(a_x\) 是否一定要被删除，设其等于 \(p^{\alpha}\)。设 \(S_B\) 中的数在 \(p\) 这个质因子的指数上是 \(\beta\)，若 \(\alpha>\max\{\beta_i\}\)，则 \(a_x\) 一定要被删除。这等价于 \(\gcd\limits_{j=1}^{|S_B|}\left\{\dfrac{a_x}{\gcd(a_x,b_i)}\right\}>1\)，这可以用开 \(2n\) 棵线段树维护。
开个队列，把要删除的点入队，之后遍历队列，暴力将每个数删除后对另一个集合线段树造成的影响给除去。时间复杂度 \(\mathcal{O}(n^2\log n)\)。
[AGC039D] Incenters
很厉害的几何题！！！
对于 \(\bigtriangleup ABC\) 来说，设内心为 \(I\)，它的每条角平分线延长出去分别交外接圆 \(\odot O\) 于 \(D,E,C\) 三点，则可以证明，点 \(I\) 是 \(\bigtriangleup DEC\) 的垂心。
于是，我们将求内心转化为了求两点弧中点所围成的三角形的垂心。考虑如何求三角形的垂心 \(H\)，如果不会欧拉线，凭借着向量知识也能知道，\(\overrightarrow{OD}+\overrightarrow{OE}+\overrightarrow{OF}=\overrightarrow{OH}\)，因此 \(F=D+E+F\)。
于是我们可以 \(\mathcal{O}(n^2)\) 枚举任意两个点计算贡献，注意弧中点可能在优弧也可能在劣弧，要注意数量的计算。把三角函数拆开可以做到 \(\mathcal{O}(n)\)。
P6240 好吃的题目
猫树分治入门题。可以看出是 \(mid\) 往两边做 01 背包，写 \(pre,suf\) 两个数组被卡空间了……
P9200 「GMOI R2-T3」粒子环游
直接枚举 \(n+1\) 号点的插入位置，设插入第 \(i\) 位。记 \(s_i=\sum\limits_{j=1}^i e_i\)，则答案要求最小化
\[\sum\limits_{i=1}^{n+1}|s_i-s_p|\times c_i \]绝对值很难处理，如果把 \(s_i\) 丢到数轴上，那这个式子的几何意义就是：有 \(n+1\) 一个点，每个点有点权 \(c_i\)，现在要寻找一个点为中心点，使得所有点到这个中心点的加权距离最小。进而，我们可以将点权转化为 \(c_i\) 个重复的点，这样就很显然了，我们只要选择位于中心的点，即在数轴上从左到右第 \(\left\lceil\dfrac{\sum c_i}{2}\right\rceil\) 个点。
思考如何计算答案，对于 \(s_p\) 右边的点，我们维护 \(sum=\sum s\)，\(cnt=\sum c\)，那么右边的答案就是 \(sum-s_p\times cnt\)。左边同理。
我们可以用动态开点线段树维护这个数轴，要支持单点修改、二分查找第 \(k\) 小的数，区间求和，比较简单。
当 \(n+1\) 插入的位置从 \(i\rightarrow i-1\) 时，\(s\) 只有 \(s_i,s_{i-1}\) 发生了变化，简单维护一下即可。时间复杂度 \(\mathcal{O}(n\log n)\)。
P7515 [省选联考 2021 A 卷] 矩阵游戏
容易发现，如果把 \(a\) 的第 \(n\) 行和第 \(m\) 列全部赋值成 \(0\)，那么 \(a\) 可以递推得出。可惜因为 \(a_{i,j}\) 有大小限制，这可能是不合法的。考虑怎么改变使它合法，发现如果在同一行或者同一列同时进行 \(+x,-x+,-x\dots\) 操作，那么对应的 \(b\) 不会变化。
于是，设 \(r_i\) 为第 \(i\) 行的 \(x\)，\(c_i\) 为第 \(i\) 列的 \(x\)，那么可以构造一个表示 \(a_{i,j}\) 变化量的新矩阵 \(A_{i,j}\)
\[\begin{bmatrix}r_1+c_1&-r_1+c_2&r_1+c_3&\dots\\r_2-c_1&-r_2-c_2&r_2-c_3&\dots\\r_3+c_1&-r_3+c_2&r_3+c_3&\dots\\\vdots&\vdots&\vdots&\ddots\end{bmatrix} \]但这样形式不统一，于是我们把偶数行的 \(r\) 和奇数列的 \(c\) 取相反数，那么矩阵就变成
\[\begin{bmatrix}r_1-c_1&c_2-r_1&r_1-c_3&\dots\\c_1-r_2&r_2-c_2&c_3-r_2&\dots\\r_3-c_1&c_2-r_3&r_3-c_3&\dots\\\vdots&\vdots&\vdots&\ddots\end{bmatrix} \]这样，矩阵的每一项都是 \(x-y\) 的形式了，由于 \(0\leq a_{i,j}+A_{i,j}\leq 10^6\)，所以 \(-a_{i,j}\leq x-y\leq 10^6-a_{i,j}\)，这就转化成了差分约束的形式，可以用熟知的算法解决。
P8113 [Cnoi2021] 自我主义的平衡者
原来看错题了…………………………………………
猜想 \(a\) 从小到大排序取最大值，反过来取最小值。
下面钦定 \(a_{i+1}>a_i\)，邻项交换证明前者。
-
若 \(b_i=m\)，\(b_{i+1}=0\)。则 \(s<a_i\)，\(s'=s+\dfrac{m-s}{i}>a_{i+1}\)。交换后
- 若 \(b_i=m\)，则 \(s<a_i<a_{i+1}\)，\(s''=s+\dfrac{m-s}{i}=s'>a_{i+1}>a_i\)，所以 \(b_{i+1}=0\)，没有更优秀。对后续也无影响。
- 若 \(b_i=0\)，则 \(s>a_{i+1}\)，与条件矛盾。
-
若 \(b_i=m\)，\(b_{i+1}=m\)，交换后必然不会更优。
-
若 \(b_i=0\)，\(b_{i+1}=m\)，则 \(s>a_i\)，\(s'=s+\dfrac{-s}{i}>a_{i+1}\)。交换后 \(b_i=0\)，不可能更优\(s>s'>a_{i+1}>a_i\)，\(s''>s>a_i\)，所以 \(b_{i+1}=0\)，没有更优。
-
若 \(b_i=0\)，\(b_{i+1}=0\)，不可能更优。
综上，当 \(a\) 从小到大排序时，取最大值。
后者同理。
P1527 [国家集训队] 矩阵乘法
来学习整体二分。
整体二分就是应用于一些询问可以二分，但是如果单独二分时间复杂度过大，于是整体一起二分来减少时间复杂度的问题。
将所有操作按时间排好序放在数组 \(q\) 里离线下来。设函数 \(solve(l,r,L,R)\) 表示现在到了操作 \(l\sim r\)，答案的值域在 \([L,R]\) 之间，把 \(mid=\dfrac{L+R}{2}\) 左边的值加入。对于询问则查询值域在 \([L,mid]\) 内的数是否大于等于 \(k\)，是就把询问放到左区间，否则令 \(k\leftarrow k-cnt\)，并放到右区间。时间复杂度 \(\mathcal{O}((n^2+q)\log^3 n)\)。
CF1285F Classical?
orz jiangly
套路地变 \(\operatorname{lcm}(a_i,a_j)=\dfrac{a_ia_j}{\gcd(a_i,a_j)}\)。如果 \(\gcd(a_i,a_j)=1\) 就好了，我们发现，如果把 \(a_i\) 的所有约数都放进序列，那必然存在 \(x\mid a_i\)，\(y\mid a_j\)，使得 \(\operatorname{lcm}(x,y)=\operatorname{lcm}(a_j,a_j)=1\)，\(\gcd(x,y)=1\)，并且原答案不会改变。
考虑将数从大到小加入，发现如果扫到 \(x\) 时，集合里存在 \(y\) 使得 \(\gcd(x,y)=1\)，那么所有在 \((x,y)\) 内的数对 \(x\) 都没有贡献。于是拿个栈维护，扫到 \(x\) 时如果栈里有与 \(x\) 互质的数就不断弹栈。那如何判断栈里是否有与 \(x\) 互质的数呢？即 \(cnt_x\) 表示 \(x\) 倍数的个数，那么互质的数的个数为
\[\sum\limits_{d\mid x}\mu(d)cnt_d \]时间复杂度 \(\mathcal{O}(\sum\limits_{i=1}^V{\sigma(i)})=\mathcal{O}(V\ln V)\)。
CF1773D Dominoes
黑白染色，若多米诺骨牌能完全铺满则二分图存在完备匹配。
由于题目规定了一开始存在完备匹配，则黑白点数量相同。所以删除两个同色点必然无解，记有用的点数量为 \(cnt\)，则方案数为 \(2\times \binom{cnt/2}{2}\)。当 \(cnt>2000\) 时已经大于 \(10^6\)，所以有用的点数其实 \(\leq 2000\)。
有解的方案不多，转为计算有解的。枚举删除的第一个点，再重新跑一次二分图匹配。若匹配数小于 \(cnt/2-1\)，则该点是必经点，不存在有解方案。否则就是找二分图另一边非必经点的个数。
求解匹配必经点是经典问题：不妨设左部图较大。从左部每个非匹配点出发，遍历它的所有右部匹配点邻居对应的左匹配点，则所有被遍历到的左匹配点均为非必经点。因为从它们开始存在交错路径使得终点为非匹配点，将匹配边换成路径下一条边即可。
P6130 随机红包
一开始一直想用概率分布函数和密度函数算，发现算不出来。
其实可以直接算概率然后积分，反正就是要求出那个面积。
原问题等价于在 \([0,1]\) 上随机撒点，求第 \(k\) 小的线段的期望长度。
先从 \(k=1\) 开始算。设最短的那一段长度为 \(x\)，则其它段的长度必须大于 \(x\)，这可以看作所有段的长度减去 \(x\) 后再在 \(1-nx\) 上随机撒 \(n-1\) 个点。因此
\[P(x\leq L_{\min})=(1-nx)^{n-1} \]那么
\[\begin{aligned}E(L_{\min})&=\int_{0}^{\frac{1}{n}}(1-nx)^{n-1}\mathrm{d}x\\&=-\dfrac{1}{n}(1-nx)^{n-1}\mathrm{d}(1-nx)\\&=-\dfrac{1}{n^2}(1-nx)^n\Bigg |_0^{\frac{1}{n}}\\&=\dfrac{1}{n^2} \end{aligned} \]现在再来考虑 \(L_2\)，这等价于把所有线段减去 \(L_{\min}\) 最短线段的期望长度再加上 \(L_{\min}\)，因此
\[E(L_2)=\dfrac{1-nE(L_{\min})}{(n-1)^2}+E(L_{\min})=\dfrac{1}{n}\left(\dfrac{1}{n}+\dfrac{1}{n-1}\right) \]同理
\[E(L_k)=\dfrac{1}{n}\sum\limits_{j=0}^{k-1}\dfrac{1}{n-j} \]随便预处理一下即可通过。
[AGC032F] One Third
需要上一题的前置知识。
有一个很牛逼的转化，以第一刀为 \(x\) 轴正半轴将圆三等分，将 \([0,\frac{2\pi}{3})\)，\([\frac{2\pi}{3},\frac{4\pi}{3}),[\frac{4\pi}{3},2\pi)\) 里的刀分别染成红色、绿色、蓝色，之后将它们的角度分别 \(\bmod \frac{2\pi}{3}\)，就可以转化成下列问题：
在 \([0,\frac{1}{3}]\) 上随机选 \(n-1\) 个点，钦定 \(1\) 号点和右边界处的点异色，每个点三颜色随机，求异色点对的距离最小值。
考虑枚举答案是第 \(k\) 小的线段，那么要求前 \(k-1\) 条线段同色，容斥得概率为 \(\frac{1}{3^{k-1}}-[k<n]\frac{1}{3^k}\)。
因此
\[\begin{aligned}ans&=\dfrac{1}{3}\sum\limits_{i=1}^n(\dfrac{1}{3^{i-1}}-[i<n]\dfrac{1}{3^i})E(L_i)\\&=\dfrac{1}{n}\sum\limits_{j=1}^n\dfrac{1}{3^j(n-j+1)}\end{aligned} \]随便求即可。
标签：dots,二分,cnt,frac,记录,dfrac,sum,2024,杂题 From： https://www.cnblogs.com/xishanmeigao/p/18040381