DS 相关
-
Qry：区间询问是否存在和为 \(x\) 的数，\(x\) 给定，强制在线，带修，\(5 \times 10^5,4s\)。
Sol：考虑 \(pre_i\) 为前面第一个 \(a_j+a_i = x\)，静态直接 ST 表即可，带修改的时候发现修改一个位置会涉及修改它本身的 \(pre\) 以及 \(pre\) 是它的位置，单次修改量可以达到 \(O(n)\)，故考虑 转化维护量来降低修改量，即：若 \(pre_i \lt lst_i\)（上一个 \(=i\) 的位置），那么就不需要知道 \(pre_i\) 只需要知道 \(pre_{lst_i}\)，将 \(pre_{i}\) 赋值 \(0\) 即可，这样修改的时候对后面的修改量是 \(O(1)\) 的，只需查询一段前缀中 \(v\) 的最后一次出现位置 / 一段后缀中 \(v\) 的最早一次出现位置，对每个值维护一个
set即可，时间复杂度 \(O((n+q) \log n)\)。70：给出定值多次 “查询区间是否存在……” 可以直接预处理出每个位置前 / 后第一个满足条件的 \(j\) 转化为 \(\text{RMQ}\) 问题（常见，而且见过）；观察是否可以舍弃不必要维护的地方从而降低修改量。
-
Qry：全局询问是否可以每次选出 \(c\) 个正数减少 \(1\)，连续进行 \(s\) 次操作，\(c,s\) 不定，带修，\(10^{6},1s\)。
Sol：想不到怎么好形容这个东西，但是先固定 \(cnt\) 个 \(\ge s\) 的位置，剩下的空位直接整体看成 \((c-cnt)s\)，查 \(\lt s\) 的数的和是否 \(\ge\) 它即可。
策略不知道怎么证明正确性，但是看起来就很对啊。70：瞎猜贪心，找到最优方案，证明可以感性。
-
Qry：给出长度为 \(n\) 的数组 \(\{a\},\{b\}\)，求最大的正整数 \(k\) 使得存在 \(a_{i \sim i+k-1}\) 满足这个区间里出现过的任何数出现次数都 \(\ge b_k\)。\(n \le 10^6,a_i \in [0,n],b_i \in[1,n+1]\)，且 \(\forall i \lt j,b_i \ge b_j\)。
Sol：让我们从数据范围倒着看，显然这个 \(i \lt j \iff b_i \ge b_j\) 暗藏玄只因。如果正着考虑往合法区间加数，发现还是不能直接判断新区间的合法性，所以考虑对不合法区间进行分析。不难发现，如果一个数 \(x\) 使得这个区间不合法，那么任何包含 \(x\) 的子区间都是不合法的。所以只有不跨过这些数的子区间可能合法，也就是说，去除区间中所有出现次数 \(\lt b_{len}\) 的数后，划分出的若干子区间就是可能合法的新区间。
据此考虑一个分治：每次扫描当前区间，找到区间里所有出现次数 \(\lt b_{len}\) 的数，然后以这些数为界递归进入子区间；如果不存在这样的数，说明这个区间合法，我们可以直接拿来更新答案。分析复杂度，每次只有删除一个数才会递归进去，不同的出现次数是 \(O(\sqrt{n})\) 种，所以复杂度 \(O(n \sqrt{n})\)。
考虑优化，考虑每次只找到其中一个数然后从这个数的第一次出现位置把区间剖成两部分，这样就好写很多，但是复杂度变成了 \(O(n^2)\)。假设每层我们分成两个区间 \(L,R\) 递归进去，如果我们单层能做到 \(\min(L,R)\)，复杂度就会变成启发式合并的复杂度 \(O(n \log n)\)。于是考虑从两端点向中间同时开始找这个数，这部分复杂度为较短区间的长度；然后清空较短区间的贡献，递归长区间；然后把贡献加回来再递归短区间。对于没有找到这个数的区间，我们直接暴力清空整个区间的贡献。容易发现这样复杂度变为 \(O(n \log n)\)，可以通过。
70：分治的两种复杂度平衡方式；理性分析操作的开销
DP 相关
-
CF258D Little Elephant and Broken Sorting：
Qry：有一个 \(1 \sim n\) 的排列，会进行 \(m\) 次操作，操作为交换 \(p_{a_i},p_{b_i}\)。每次操作都有 \(50\%\) 的概率进行，求进行 \(m\) 次操作以后的期望逆序对个数，\(n,m \le 1000\)。
Sol：考虑期望线性性，设 \(f_{x,y}\) 表示 \(p_x \gt p_y\) 的概率，则答案为 \(\begin{aligned} \sum_{x=1}^{n}\sum_{y=x+1}^{n}f_{x,y} \end{aligned}\)，考虑赚肄：首先初值 \(f_{x,y} = [p_x \gt p_y]\)，如果执行一对 \(x,y\) 的交换，先执行 \(f_{x,y}:=f_{y,x}:=0.5\)，然后考虑只含有 \(x,y\) 中某一个的 dp 值如何改变，\(f_{i,x} := f_{i,y} := \dfrac{f_{i,x}+f_{i,y}}{2}\)（和不变，均分），然后再据此更新 \(f_{x/y,i}\)，时间复杂度 \(O(nm)\)。
70：期望的线性性是很好的切入点；考虑转移前后 \(\text{dp}\) 值的特性，包括需要修改的项的和 / 积不变等。
-
[ARC121F] Logical Operations on Tree：
Qry：\(n\) 个节点的树，每个点权值可以是 \(0/1\)，每条边可以是 \(\text{AND } / \text{ OR}\)，在所有 \(2^{n+n-1}\) 种填法中，求出有多少种满足：存在一种缩边的顺序，使得每次把一条边的两个端点缩成一个点，权为原端点与边的运算值，最终点的权为 \(1\)，\(n \le 10^5\)
Sol：考虑对一个点的四种操作情况：\(1\text{ AND}\) 和 \(0\text{ OR}\) 相当于没有操作，也就是出现这种叶子整棵树还是合法的当且仅当它连接的那边本来就是合法的；\(0 \text{ AND}\) 如果放到最后操作会使得整棵树不合法，但是放到中途就还是当连接的那边合法（这里的合法比前两个要严格一点，但是 可以看作近似的约束）；只有 \(1 \text{ OR}\) 放到最后一定可以使得整棵树变合法，也就是说只要出现这种叶子整棵树就一定合法，所以考虑对它单独讨论来计数：容斥，总方案数 - 不含 \(1 \text{ OR}\) 边的树的数量 + 不含 \(1 \text{ OR}\) 边但是合法的树的数量，这个可以 \(\text{dp}\)，\(f_{u}\) 表示 \(u\) 子树中不含 \(1 \text{ OR}\) 边的树的数量（就是只考虑 \(u\) 子树这个结构满足条件的方案数），\(g_u\) 表示 \(u\) 子树中不含但是合法的树的数量，\(\begin{aligned} f_u = \prod_{v \in son_u} 2f_{v} - g_v \end{aligned}\)（\(-g_v\) 表示去掉 \(val_v=1\) 并且边选 \(\text{OR}\) 的情况），\(\begin{aligned} g_u = \prod_{v \in son_u} f_v \end{aligned}\)（这个转移的意义在于，这个子树 \(u\) 必须合法，所以 1. \(val_v = 0\)，那么边必须是 \(\text{OR}\)；2. \(val_v = 1\)，因为不能出现 \(1 \text{ OR}\) 所以这条边必须是 \(\text{AND}\)，所以两个取值都有唯一对应的边的取值，并且要合法所以 \(u\) 只能取 \(1\)），然后就做完了，时间复杂度 \(O(n)\)。
More：（赚老师的做法）考虑一棵树合法还可以表述为，其内部存在一个连通块权值为 \(1\) 且没有向外连的 \(\text{AND}\) 边（？），然后对此计数即可，考虑方程的过程和上面的差不多所以不记方程了，复杂度也是 \(O(n)\)。
70：计数题的几个方向：1. 正难则反，2. 容斥计算，3. 挖掘性质，4. 分拆贡献；考虑推导强有力的结论来设计 \(\text{dp}\)。
-
Qry：给一棵 \(n\) 个点、带边权的树，刚开始每个点都是白色。现在需要在选择一些点染黑，使得对于每个点 \(u\) ，至少有一个黑点距离 \(u\) 不超过 \(d[u]\)。现在给出在每个点的约束 \(d[u]\)，以及把每个点染黑的花费 \(c[u]\)，请你选择一些点染黑，使得每个点的约束得到满足，并且总花费最小。\(n \le 1000\)。
Sol：观察到对于子树 \(u\) 的所有点，其配对黑点至多只有 \(1\) 个在子树外，因为如果有多个可以只留距离 \(u\) 点最近的，所以考虑设 \(g_{u,i}\) 表示 \(u\) 子树和 \(i\) 进行匹配的最小花费，则子树里的要么和 \(i\) 匹配要么在内部匹配，所以 \(\begin{aligned} g_{u,i} = c_i+\sum_{v \in son_u}\min(\min_{j=1}^{n}g_{v,j},g_{v,i}-c_i) \end{aligned}\)（注意这里为什么意义是 \(v\) 和 \(v\) 子树内的点匹配，但是可以直接取 \(\min_{j=1}^{n} g_{v,j}\)：假设转移到 \(g_{u,i}\) 的是不在 \(v\) 子树内的 \(g_{v,j}\)，那么 \(g_{u,i}\) 一定不比 \(g_{u,j}\) 优，可以直接忽略。），预处理 \(dis(u,v) \le d_u\) 的 \(v\) 集合，设 \(f_u = \min g_{u,i}\) 即可做到 \(O(n^2)\)，最后答案是 \(f_{1}\)。
70：混乱邪恶树上问题尝试去归纳问题，找到统一性，使得更容易设计 \(\text{dp}\)；\(\text{dp}\) 转移的时候可以尝试模糊化一些状态的意义，分析这样做的正确性，如果可行将会大大简化转移过程。
-
冒泡排序：
Qry：给出长度为 \(n\) 的排列或圆排列 \(A\)，定义 \(f(A)\) 为将 \(A\) 升序排序所需的最小操作次数，每次操作中，你可以选择一个元素并向前冒泡若干次，一次冒泡定义为：若这个元素小于前一个元素，则可以交换它与前一个元素。当某次无法冒泡时，这次操作立即停止。否则可以连续冒泡任意次。给定 \(n,k,type\)，你需要：在 \(type=1\) 时求有多少长为 \(n\) 的排列 \(A\) 满足 \(f(A)=k\) ；在 \(type=2\) 时求有多少长为 \(n\) 的圆排列 \(A\) 满足 \(f(A)=k\) 。对 \(10^9+7\) 取模。
Sol：据说 \(type = 1\) 差不多就是第一类斯特林数
，但是可以做到更劣的 \(\text{dp}\)（？），\(f_{i,j,k}\) 表示填了前 \(i\) 个空位，前缀最大值 \(j\)，最小操作次数为 \(k\) 的排列数量，发现转移大概是 \(f_{i,j,k}\) 对 \(f_{i+1,j+1 \sim n,k}\) 有贡献，那么直接差分刷表就行了复杂度 \(O(n^2K)\) 非常啥币（，写了还调半天。\(type = 2\) 时很神奇阿，首先圆排列的 \(f\) 就相当于枚举每个位置作为开头的排列的 \(f\) 的最小值，然后我们考虑不停往圆排列里面插当前最小的数，假设插到了位置 \(x\) 前面，那么每个位置作为开头的 \(f\) 变化如下：1. 新增一个以这个数为开头的 \(f\)，等于 \(f_x\)；2. 其它位置（包括 \(x\)）的 \(f\) 加上 \(1\)，因为需要把这个数放到开头。由于这个对其它所有数修改的行为不是很友好（？），所以考虑 \(f \to now-1-f\)（\(now\) 表示当前插入了多少个数），那么相当于 1. 新增一个 \(f_x+1\)；2. 其它 \(f\) 都不变。然后需要数 \(\max f = n-1-K\) 的方案数。观察这个形式，考虑可以看作树上插点，相当于每次插入一个节点作为某个节点的儿子然后求树高恰好为 \(n-1-K\) 的方案数，那么设 \(f_{i,j}\) 表示树高 \(\le i\)，点数为 \(j\) 的树的个数（注意这里每个节点有一个编号表示插入的是哪个数。因为对于同一个树结构，两个点插入的顺序不同则这两个点实际在圆排列中的数也就不同，是不同的方案），注意到每条链上的标号都是从根到链底降序的，但是不好得知 \(u\) 的两个儿子 \(v_1,v_2\) 的标号大小，我们考虑加强顺序限制，钦定每个 \(u\) 的所有儿子编号小的放到左边，这样每次考虑给根节点最右边新增一棵子树，这棵子树的根在构建这棵树的操作序列中就一定在第二个（第一个是整棵树的根），这样我们就可以直接归并两棵树剩下的操作序列，方案数 \(\dbinom{now-2}{x-1}\)（\(now\) 是合并后整棵树的大小，\(x\) 是合并的子树大小），那么转移就是 \(\begin{aligned} f_{i,j} = \sum_{k=1}^{j-1} f_{i,j-k} \times f_{i-1,k} \times \dbinom{j-2}{k-1} \end{aligned}\)，预处理组合数即可做到 \(O(n^3)\)。
70：
数学相关
-
Qry：给出 \(A,B,d \lt 2^{30}\)，输出任意一个 \(X \lt 2^{60}\) 使得 \(d \mid (A \text{ OR }X) \land d \mid (B \text{ OR }X)\)。
Sol：构造题的一些底层思路：尽量找到不难为自己的构造方案。所以考虑直接让 \(A \text{ OR } X = B \text{ OR } X = X\)，首先如果 \(X\) 的最低位比 \(d\) 的最低位（假设是 \(2^K\) 这一位）低则无解，否则 \(X\) 可以表述为 \(X = \overline{p0111 \dotsb 000}\)，\(p\) 是从高到低的前 \(30\) 位的值，这里我们为了更加方便直接让 \(X\) 的第 \(K \sim 29\) 位都是 \(1\) 且第 \(30\) 位是 \(0\)，这样一定满足 \(A,B \subseteq X\)，然后解这个 \(p\)：\(X = 2^{K}(2^{30-K}p+2^{30-K}-1) \equiv 0 \pmod{d = 2^{K}d_2} \iff p \equiv 2^{K-30}-1 \pmod{d_2}\)，因为 \(d_2\) 一定 \(\lt 2^{30}\) 所以 \(X\) 一定 \(\lt 2^{60}\)，直接带回原式算出 \(X\) 即可。
70：构造方案从简，尝试先粗暴确定形式再分析可行性和通解。
void Solve(){
int A,B,C,d; rd(A),rd(B),rd(d),C=A|B;
const int K = __builtin_ffs(d)-1; d>>=K;
for(int i=0,bit=1;i<K;++i,bit<<=1) if(C&bit) return (void)puts("-1");
int tmp = (Pow(Inv(2,d),30-K,d)+d-1)%d;
ll X = (1ll<<30)*tmp+((1ll<<30)-(1ll<<K));
writeln(X); //assert(A|X==X),assert(B|X==X),assert(X%d==0);
}
-
Qry：有 \(n\) 个人，\(m\) 个学科，每个学科给出一个分数上限 \(U_i\)，称 \(A\) 被 \(B\) 碾压当且仅当 \(B\) 所有学科的分数都 \(\ge A\)，已知有 \(K\) 个人被 \(1\) 号碾压（自己不算）；再给出 \(1\) 号每个学科的排名，求可能的情况方案数，对 \(10^9+7\) 取模，\(n,m \le 100,U_i \le 10^9\)。
Sol：因为恰好 \(K\) 个人被碾压，不太能做所以容斥，\(\begin{aligned} ans = \sum_{i=1} \dbinom{n-1}{i}(-1)^{i} \sum_{j=1}^{m}\dbinom{n-i-1}{R_j-i-1}\sum_{x=1}^{U_j}x^{n-R_j}(U_j-x)^{R_j-1} \end{aligned}\)，啊写起来好累啊等会再写吧。
70：
-
CF1423J Bubble Cup hypothesis：
Qry：给定正整数 \(m\)，求有多少不同的多项式 \(P\) 使得 \(P(2)=m\) 且任意一项的系数 \(0 \leq a_i \leq 7\)，对 \(10^9+7\) 取模。
Sol：考虑 \(8\) 进制，\(\sum_{i=0}a_i2^{i}=m \iff (a_0+a_38^1+\dotsb)+2(a_1+a_48^1+\dotsb)+4(a_2+a_58^1+\dotsb)=m \iff A+2B+4C=m\)，这是因为这三个括号里都可以看作是一个 \(8\) 进制数，那么直接转化为简单计数 \(\begin{aligned} ans = \sum_{C=0}^{\lfloor \dfrac{m}{4} \rfloor}(\lfloor \dfrac{m-4C}{2} \rfloor+1) \end{aligned}\)，首先可以无脑类欧但是这个 \(C\) 可以提出去，所以 \(\begin{aligned} ans = \sum_{C=0}^{\lfloor \dfrac{m}{4} \rfloor}(\lfloor \dfrac{m}{2} \rfloor -2C +1) = (\lfloor \dfrac{m}{4} \rfloor+1)(\lfloor \dfrac{m}{2} \rfloor-\lfloor \dfrac{m}{4} \rfloor+1) \end{aligned}\)，直接算就行了。
70：如果数位的数据范围特殊考虑进制转化。
-
Baby Ehab Plays with Permutations：
Qry：你有一个长度为 \(n\) 的序列 \(p\) 满足 \(p_i=i\)，你可以进行 \(x\) 次操作，每次操作找到两个不同的 \(i,j\) 并且交换 \(p_i,p_j\)，问最终有几个可能的序列。对于 \(1 \le i \le k\) 中的每个 \(i\)，求出当 \(x=i\) 时的答案，\(1 \le n \le 10^9,1\le k \le 200\)。
Sol：逆向考虑，可以看作是把乱序排列排成升序，那么只要求出一个排列最少需要的操作次数 \(x\)，它对 \(x+2k(k \ge 0)\) 均有贡献，现在的问题就是求出最少需要 \(x\) 次的排列数量，算出来之后奇偶分别做前缀和就行了。由于一个排列最少需要的操作数 = 不在合法位置的个数 - 环的数量，所以考虑枚举环的个数：\(\begin{aligned} f(x) = \sum_{i=0}^{x}\dbinom{n}{x+i}g(x+i,i) \end{aligned}\)，其中 \(g(x,y)\) 表示把 \(x\) 个元素划分成 \(y\) 个大小至少为 \(2\) 的环的方案数，考虑第一类斯特林数（将 \(n\) 个数划分成 \(m\) 个圆排列的方案数），那么这个 \(g(x,y)\) 可以容斥得到：\(\begin{aligned} g(x,y) = \sum_{i=0}^{x}(-1)^{i}\dbinom{x}{i}{x-i \brack y-i} \end{aligned}\)，这个稍微预处理一下，\(\begin{aligned} {n\brack m} = {n-1\brack m-1}+(n-1){n-1 \brack m} \end{aligned}\)，然后直接算就行了，复杂度 \(O(k^3 \log p)\)（组合数很大不能预处理）。
70：逆向考虑对序列的操作过程；挖掘性质。