2024 10 做题笔记
做题重心可能逐渐转向模拟赛以及补题，会在其他博客里写到，因此做题笔记就不按日期排序，随缘更新。
P11146 「SFMOI Round I」Strange Train Game
比较巧妙的转化性质题，写了题解。
P11094 [ROI 2021 Day 2] 砍树
这类“每个点权都有一个固定的生效范围”类题目最近好像遇到了很多次，主要思路貌似都是利用单调性求出这个合法范围。
不难发现一棵树如果最后向左倒下，那么它右边的树怎么倒对它其实都是没影响的，右边倒下同理，并且我们还可以发现如果把区间左端点拉得越长，这棵树越有可能倒下。
因此考虑求出左端点能使得每棵树倒下的最小取值，由于此时区间内的树是可以向左或向右倒下的，你不能直接对覆盖到的树的 \(L_i\) 取 \(\max\)，但是哪些树可以向右倒下是好维护的，单调栈即可，剩下的必须向左，线段树维护。
还有一种求法是直接整体二分，这样写起来更方便，最后就是容斥一下加个二维数点。
P11095 [ROI 2021 Day 2] 旅行
题目里给的限制是不能走走过的边，这实际上启发我们对原图缩边双，以 1 为根建圆方树，路径上割边是必须经过的，剩下的就是对每个方点求点到点的贡献。
但是方点的贡献还是二元的，不是很方便操作，直接考虑暴力钦定一方，发现钦定最大值比较方便，剩下的就是问路径边权最小值。
我们直接从小到大遍历每条边，每次加入，如果连接的两个点不连通就直接合并，否则相当于路径上点双合并然后更新权值，注意到实际上子树内每个点都能被修改到，因此就是简单的子树修改，然后用最小和最大更新答案。
P3226 [HNOI2012] 集合选数 & AT_arc184_b [ARC184B] 123 Set
两题一个套路，就一起讲了。最后的答案肯定是从指数上得来的，因此先把所有数分解成 \(q\cdot 2^x \cdot 3^y\) 的形式。
首先不同的 \(q\) 一定相互不影响，而如果我们选中一个 \(q\cdot 2^x \cdot 3^y\) 就会对 \(q\cdot 2^{x+1} \cdot 3^y\) 和 \(q\cdot 2^x \cdot 3^{y+1}\) 造成影响，观察指数，如果把 \((x,y)\) 看做平面点对，这相当于覆盖上面和右边的点。
考虑这张图的形态，你发现它长宽都很小，因此可以直接上装压 dp，P3226 就做完了。
数据范围更大呢？更细致地分析一下，你会发现 \(\lfloor \frac{n}{q}\rfloor\) 一样的 \(q\) 图形态也是一样的，因此整除分块一下就能做到比较好的复杂度了，可以通过 [ARC184B]。
AT_arc132_f [ARC132F] Takahashi The Strongest
题目看上去就很能容斥，先固定一组小 C 的策略算方案，设小 C 的策略为 \(T\) 的答案为 \(h(T)\)，设 \(f(S)\) 和 \(g(S)\) 分别表示小 A 的策略和小 B 的策略包含集合 \(S\) 的方案数，这里的包含指的是恰好在对应位置选了对应数，我们就能得到 \(h(T)=\sum_{S \subset T,s\neq \emptyset} (-1)^{|S|-1}f(S)g(S)\)。
先考虑怎么算 \(f(S)\) 和 \(g(S)\)，你会发现这个东西本质上就是一个高维前缀和，把连续两个二进制位压缩表示一个状态，分别是剪刀石头布或者通配符，跟普通的高维前缀和一样做就行。
算出来 \(f\) 和 \(g\) 之后对应位置作乘法，倒着变换回去也是类似的，记得加上容斥系数。