CF2047D Move Back at a Cost
要使字典序最大，每次都要找到最小的数，把它前面的数都后移.
因为可以钦定后移的顺序使得后移的数按升序排列，所以每个数最多被移位一次.
定序后开两个队列模拟即可.
CCPC2024 上海F 羁绊大师
将羁绊相同的英雄相连，因为英雄至多 \(2\) 个羁绊，所以度数不超过 \(2\).
因为度数不超过 \(2\)，所以只有环和链. 先选环，然后从大到小选链.
如果恰好能选满选中环上的点，那么是最优的，接下来考虑怎么处理这个背包问题.
用 bitset 进行 dp 数组移位，时间复杂度为 \(O(\frac{n^2}{w})\)，\(w\) 是字长，足够通过本题.
因为 \(\sum i = n\)，所以重复的 i 可以多项式快速幂转移，并不会算复杂度，反正过了（设定阈值 k=16，重复次数小于 k 正常转移），对于每个 \(i\)，设其重复了 \(k\) 次，将 \(k\) 二进制分组，拆成 \(k=2^0+2^1+\cdots+2^x+(k-2^{x+1}+1)\) 的 \(O(\log k)\) 个数，这些数恰可以表示 \(i\) 被选了 \(0\sim k\) 次，最劣情况 \(k\) 全相同，总复杂度是 \(O(\frac{n}{w}\sqrt\frac{n}{k}(\log k+1))\)，\(k=1\) 时有复杂度为 \(O(\frac{n^\frac{3}{2}}{w})\).
CF2047E Adventurers
二分答案 \(k\)，按 \(x\) 坐标升序枚举 \(x_0\)，用大根堆加删点维护保证至少 \(k\) 个点在各自的区域即可. 复杂度 \(O(n\log^2 n)\). 离散化后把大根堆换成桶做到 \(O(n\log n)\).
CF2050G Tree Destruction
设 \(f_{u}\) 表示在 \(u\) 为根的子树中删除端点是 \(u\) 的路径能得到的最大联通块个数.
设 \(S\) 是 \(u\) 的子节点集，转移即为 \(f_u=\max\limits_{v\in S} f_v -1+|S|\).
再考虑端点的 LCA 是 \(u\) 的路径，处理 \(u\) 的子节点对应 \(f\) 的最大和次大值即可.
Ucup '3 S1 C Cherry Picking
把每个连续的 \(01\) 段看成一个联通块，枚举 \(r_i\) 删除 \(r_i\) 对应的位置，每当联通块被删完，用并查集合并联通块，维护左右端和大小即可.
Ucup '3 S1 D Dwarfs' Bedtime
首先询问 \(0\) 时刻的状态，然后找到状态不同的时刻.
考虑询问过了时间 \(x\) 后的状态不同，那么最多只要再询问 \(x-1\) 次.
所以可以在询问 \(0\) 时刻后的第 \(i\) 次询问询问过了时间 \(50-1-i\) 的时刻的状态.
Ucup '3 S1 J First Billion
因为是随机数据，讲一下 VP 场上乱搞的做法，把 \(n\) 个数等分成两个集合 \(A\) 和 \(B\)，每次随机 \(A\) 中的一个数并从 \(B\) 中选一个数交换使得 \(A\) 的和与 \(10^9\) 的差的绝对值最小. 交了一发就过了，跑了 1805ms，后来测了一下大概有 \(20\%\) 的概率能跑进 2s.
考虑确定性算法，即 meet in the middle，把 \(n\) 个数分成两部分，分别计算两部分和的可能取值，可以做到 \(O(n2^{n/2})\) .
考虑 \(n\) 个数一共能凑出 \(2^n\) 种和，\(2^n\) 远大于和的上界 \(2\times10^9\).
所以可以把 \(n\) 个数并成 \(x\) 个数，在 \(O(x2^{x/2})\) 的复杂度凑出和是 \(10^9\) 的方案.
和大概可以认为是均匀分布的，所以凑不出 \(10^9\) 的概率大概为 \((1-5\times10^{-10})^{2^x}\)，当 \(x = 36\) 时约等于 \(1.2\times10^{-15}\).
ICPC2022 沈阳A Absolute Difference
把两个区间分裂使得所有区间不交或者相等.
对于不交的区间前缀和处理，对于相等的区间算区间长度除以 \(3\) 的贡献即可.
需要单独考虑所有区间和为 \(0\) 时区间取到的概率.
ICPC2022 沈阳F Half Mixed
一维情况下子矩阵的个数是 \(\sum\limits_{i=1}^ni=\frac{n(n+1)}{2}\)，所以有解的必要条件是 \(n(n+1)\) 是 \(4\) 的倍数.
令 \(a_i\) 表示矩阵的极大连续 \(01\) 段长度，有 \(\sum a_i=n\)，Pure 子矩阵的个数为 \(\sum \frac{a_i(a_i+1)}{2}\).
要解 \(\sum a_i^2 = \frac{n(n+1)}{2}\)，初始置 \(a_i\) 全为 \(1\)，贪心的让 \(a_i\) 取到最大值，发现总有解.
于是二维情况复制一维情况即可.
CF1966D Missing Subsequence Sum
将 \(k-1\) 二进制分组可以构造出 \(1 \sim k-1\).
加入 \(L_0=k+1\)，能够表示 \([k+1, 2k]\). 加入 \(L_1=2k+1\)，能够表示 \([2k+1,4k+1]\backslash\{3k+1\}\).
于是考虑加入 \(3k+1\). 下次再加入 \(L_n=2L_{n-1}=2^{n-1}(2k+1)\) 时，本来不能表示的 \(L_n+k\) 可以用 \((L_n-(2k+1))+(3k+1)\) 表示，其中 \(L_n-(2k+1)=(2^{n-1}-1)(2k+1)\) 是可以不使用 \(3k+1\) 就能得到的，因为只有 \(L_n+k=2^n(2k+1)+k\) 会用到 \(3k+1\).
ICPC2019 徐州J Loli, Yen-Jen, and a graph problem
注意迹（trial）可以重复经过相同点.
使用增量法：假设已经构造好了 \(n=k\) 的情形，考虑 \(n+2\) 的情形怎么构造.
也就是往 \(n\) 的完全图里加两个点，得到长度为 \(n\) 和 \(n+1\) 的迹.
CF2048D Kevin and Competition Memories
记 Kevin 的 rating 为 \(x\) 如果能全选难度 \(\leq x\) 的题目就全选.
否则排名只取决于最简单的题目，选完难度 \(\leq x\) 的题目尽可能选大的题目即可.
所以可以把难度 \(\leq x\) 的题目难度设成 \(+\infin\)， 双指针计算 Kevin 的排名.
CF2048E Kevin and Bipartite Graph
\(n\) 种颜色对应 \(n\) 个森林，一个森林最多有 \(|V|-1=2n+m-1\) 条边.
最多染 \(n(2n+m-1) \geq 2nm\) 条边，所以 \(m\leq 2n-1\).
构造考虑右边每个点每种颜色连 \(2\) 条边，左边 \(2n-2\) 个点被连 \(2\) 次，首尾两个点被连 \(1\) 次.
CF2048F Kevin and Math Class
按 \(b_i\) 从大到小构建并查集，如果左右的并查集已经构建好就进行合并，维护 \(dp_{i,j}\) 表示在 \(i\) 的并查集中 \(j\) 次除法得到最小最大值.
再维护 \(g_{i,j}\) 表示在 \(i\) 的并查集中不使用最小 \(b_i\) 进行 \(j\) 次除法得到的最小最大值.
然后就可以合并了，先计算不使用最小 \(b_i\) 对应的 \(ndp,ng\)，再用最小 \(b_i\) 做除法转移. 一次复杂度 \(O(\log^2a_i)\).
实际上相当于在笛卡尔树中先计算左右子树再用根节点转移，这样比较自然，且不用辅助数组.
标签：11,3k,12,frac,复杂度,个数,2024,sum,2k From： https://www.cnblogs.com/Lcyanstars/p/18678081