251 P9139 [THUPC 2023 初赛] 喵了个喵 II
场上以为是一个数学题，结果竟然是这种题！！
题意相当于将相同的数配对，使得所有 pair 排序后两维均递增，那么就是不存在两个 pair 有包含关系。
我们考察一个颜色四个位置 \(1,2,3,4\)，共有三种匹配方式 \((1-2,3-4),(1-3,2-4),(1-4,2-3)\)，但注意到第三种不合法，因此每个颜色只有两种状态。
两种状态，且有限制可以联想到 2-SAT，包含关系事实上就是二维偏序，主席树优化建图就好了，复杂度 \(O(n\log n)\)。
252 P7571 「MCOI-05」幂积
min25 求块筛，具体就是把那个 dfs 直接写成 dp。过程大概是先把合数筛掉，然后从后往前按照最小素因子大小顺序依次加入每个合数。
首先考虑素数的筛法，我们发现模 \(4\) 为 \(0,2\) 是平凡的，而模 \(4\) 为 \(1,3\) 相当于一个 bit，被一个奇素数 \(p\) 筛一次就异或一次 \([p\bmod 4=3]\)，很好处理。
加入合数时就写一个 \(\bmod (x^4-1)\) 的循环卷积就好了，复杂度 \(O(\frac{n^{\frac 34}}{\log n})\)。
253 P5540 [BalkanOI2011] timeismoney | 最小乘积生成树
很神奇的算法！
我们将一个生成树方案的 \(a\) 之和与 \(b\) 之和作为二维平面上的一个点，我们无非找到 \(x\times y\) 最小的一个点，注意到这个点一定在所有点的下凸壳上。
我们找到 \(x\) 坐标最小的点 \(A\) 以及 \(y\) 坐标最小的点 \(B\)（这只需求两次 MST），找到 \(AB\) 左下方距离 \(A,B\) 最远的点 \(C\)，容易发现 \(C\) 一定在凸壳上，然后可以递归 \(AC,BC\) 处理。
这样复杂度是 \(O(凸包点数)\) 的，根据结论 \([1,R]^2\) 内整点凸壳点数是 \(O(R^{\frac 23})\) 的，因此问题转化为了快速找到一个这样的 \(C\)。
距离 \(AB\) 最远的点 \(C\) 一定满足 \(S_\triangle ABC=-\frac{\vec{AB}\times\vec{AC}}{2}\) 最大，推一推可知 \((y_A-y_B)x_C+(x_B-x_A)y_C+x_Ay_B-x_By_A\) 最小，后面是常数，我们只需将前面的东西设为一条边的边权后再求一次 MST。
254 P8501 [NOI2022] 二次整数规划问题
没反应过来有些情况一定能取到某些最值，差点就会了！！
只考虑 \(k=5\)，\(k\) 更小可以类似处理。
注意到若不是固定取值的数，取 \([2,4]\) 一定更优，若我们将唯一取值的数当成常数，可能的选择方案只有 \(\{2,3\},\{3,4\},\{2,3,4\}\)，限制也只有“某个数与某个数不能一个是 \(2\)，一个是 \(4\)”。
我们假设选择了 \(x\) 个 \(2\)，\(y\) 个 \(4\)，那么我们相当于最大化 \(Ax+By+C-Dxy\)，这个东西可以联想到最小乘积生成树，但是我们要最小化一个 \((x-P)(y-Q)\) 形式的式子。
一个很重要的观察：假设 \(\min x/y,\max x/y\) 是理论最大 \(x/y\) 值，那么 \([\min x,\min y],[\min x,\max y],[\min y,\max x]\) 这些组合一定存在。（可以贪心）
手玩可以证明如果最值不取到这三个点，\((P,Q)\) 一定在所有点的右上方，此时问题形式就与最小乘积生成树基本一致了。我们可以使用上面的算法，那么问题变为选一个 \(2\) 有代价，选一个 \(4\) 有代价，某些点对不能同时取到 \(2,4\)，写一个类似切糕的最小割就好了。
255 CF1182F Maximum Sine / CF1098E Fedya the Potter
比较拉跨的题。
第一个问题相当于最小化 \(|2px\bmod 2q-q|\)，二分一下就相当于是否有 \(2px\bmod 2q\in[L,R]\)，这个根据经典转化（ABC283H）可以变成 \(\lfloor\frac{2px-l}{2q}\rfloor-\lfloor\frac{2px-r-1}{2q}\rfloor\)，类欧算就好了。
第二个问题更套路，区间的 \(\gcd\) 使用扫描线计算出 \(O(n\log n)\) 个颜色段的数组 \(b\)，二分中位数的值，双指针计算和不超过 \(mid\) 的区间数量，注意到
256 CF839E Mother of Dragons
标签：frac,2q,min,2px,被光,最小,43,2023,bmod From： https://www.cnblogs.com/xiaoziyao/p/17195843.html