我到底做了些什么题啊

来记些完成的任务计划中的一些题。

### 20250716
P6775 [NOI2020] 制作菜品：Zzzcr 给的题，$m=n-1$ 是好做的，直接贪心即可，必然有解，$m=n-2$ 就直接通过背包划分成两个 $m=n-1$ 的情况即可，用 bitset 优化。
### 20250718
P11364 [NOIP2024] 树上查询：区间 lca 深度为相邻 lca 深度之区间 min，二分+主席树即可，卡常懒得卡了。

CF1876G Clubstep：可以从后往前贪心，多组询问就扫描线，在 $r$ 处加入，使用 dsu 维护每种 $x$ 对应的询问，每次相当于 $x\to \lfloor\frac {x+a_i}2\rfloor$，直接暴力处理每种 $x$ 的势能是对的。

AGC039F Min Product Sum：从小往大加行列最小值，可以计算贡献，不易计算矩阵方案数，考虑进行容斥，设有 $x$ 行 $y$ 列被容斥，系数为 $(-1)^{x+y}$，容斥后方案数也容易计算，且容易将整个过程塞进 dp，设 $f_{i,j,k}$ 为，$\le i$ 的数填了 $j$ 行 $k$ 列，转移枚举放几行/列，复杂度 $O(nmk\max(n,m))$。
### 20250722
P10221 [省选联考 2024] 重塑时光：典型的容斥类图论计数，随机排列+分段等价于分集合等价于图上缩点，每次选一个 **缩完后** 入度为 $0$ 的集合，设缩成了 $c$ 个则容斥系数为 $(-1)^{c+1}$。然后把过程套进 dp，设 $f_S$ 为 $S$ 的拓扑序数，$g_{S,i}$ 为 $S$ 缩成 $i$ 个点的方案数，$h_{S,i}$ 为 $S$ 缩成 $i$ 个点，且入度均为 $0$ 的方案数，复杂度 $O(3^nn^2)$，可拉格朗日插值优化 dp。
### 20250723
CF1684H Hard Cut：猜测 popcnt 不为 $0$ 则有解，设 popcnt 为 $k$，考虑构造，假定和是 $2^{\lceil\log_2 k\rceil}$，显然可以尝试把 $1$ 均匀分开分治往下做。但在 $k=2^t+1$ 时会递归到 $k=2^{t-1}$ 而和为 $2^t$ 的情况，但是 $k=4,s=8$ 可以分讨得到解。此时若解决 $k=5,s=8$ 就赢了，但是又发现有且仅有 $11111$ 是无法得到 $8$ 的，所以还要解决 $k=9,10,11$，分类讨论构造方案即可（
### 20250724
P10441 [JOISC 2024] 乒乓球（Day4）：根据度数序列，容易求出竞赛图三元环个数为 $\binom n3-\sum \binom{d_i}{2}$（一个非三元环恰好有一个二度点。）考虑调整构造，初始令 $d_i$ 尽量均匀，可以最大化个数。若 $d_x=d_y$，则将一个减一另一个加一可使三元环数量减一，直接做可 $O(n^3)$ 构造度数序列，但是可以取最小的 $n_0\le n$ 满足 $n_0$ 个点可满足要求并在此基础上构造度数序列，可 $O(n^2)$ 构造。根据度数序列构造竞赛图就每次取 $deg$ 最小的点并向 $deg$ 最小的若干个连边，然后将这个点删去，可做到 $O(n^2\log n)$。

P13275 [NOI2025] 集合：近年最容易的 D2T2（），$[a=b]$ 要硬拆成 $\sum\limits_{x\subseteq a}\sum\limits_{y\subseteq b}f(x,y)$ 才好做，拆二进制位分析得到 $f(x,y)=(-1)^{|x|+|y|}2^{|x\text{ and }y|}$，又有 $2^{|x\text{ and }y|}=2^{|x|+|y|-|x\text{ or }y|}$，最后式子可以搞成只与 $x,y,x\text{ or } y$ 有关的形式，FWT 即可，但是分母为 $0$ 会绷不住，套路的括域成 $x\times0^y$ 就行。
### 20250728
P12536 [XJTUPC 2025] 我永远喜欢希儿·芙乐艾：换根无用，可通过分讨去除。对操作序列分块，散块依次模拟操作，维护路径加，子树和，可以通过一些推狮子后分块维护。整块离线考虑限制，对每个点的贡献是确定的，扫一遍询问，统计次数。可以做到 $O(m(\sqrt{n_1}+\sqrt{n_2}))$。

正在渲染内容...