好久没发博客了，发一篇。
A
求出每个 \(0\) 与往前 / 往后最近的 \(1\) 的距离即可。
时间复杂度 \(\mathcal{O}(n)\)。
B
\((x, y) \to (x + y, y) \to (x + y, -x) \to (y, -x) \to (y - x, -x) \to (y - x, -y) \to (-x, -y)\)。
时间复杂度 \(\mathcal{O}(n)\)。
C
开个栈模拟即可。
时间复杂度 \(\mathcal{O}(n)\)。
D
若钦定选择一个人，则使用 FWT 可以在 \(\mathcal{O}(n + p 2^p)\) 的时间复杂度内求出答案。
随机 \(100\) 次即可。
时间复杂度 \(\mathcal{O}(T(n + p 2^p))\)，其中 \(T = 100\)。
E
看成出现连续 \(k\) 个 \(1\)，耽误了半个多小时 /cf
即对于所有排列，统计按照排列顺序操作第一次不合法的位置之和。所以对于一个有 \(i\) 个 \(1\) 的合法情况，其出现次数为 \(i!(n - i)!\)。
考虑在这 \(i\) 个 \(1\) 之间塞 \(0\)。中间的 \(i - 1\) 个空至少塞 \(k - 1\) 个，其余任意，于是方案数为 \(\binom{n - (i - 1)(k - 1)}{i}\)。
时间复杂度 \(\mathcal{O}(n)\)。
F
不难想到状压 dp。但是不太好设状态。首先把任务按照时间排序，若设 \(f_{i, j, S, 0/1}\) 表示最后完成的任务是 \(i\)，已经完成了 \(j\) 个任务，已经激活的传送门集合为 \(S\)，当前在第 \(i\) 个任务 / 传送门 所需的最小时间的话，转移还需枚举上一个完成的任务，无论如何会带上 \(m^3 2^n\)，寄。
我们考虑转移的过程。如果直接从任务走到任务，\(S\) 是不变的；如果中间从任务走到传送门了，就与上一个完成的任务没关系了。这引导我们把两种转移分开。
设 \(f_{i, S}\) 表示完成了 \(i\) 个任务，已经激活的传送门集合为 \(S\) 所需的最小时间；\(g_{i, S}\) 表示最后完成的任务是 \(i\)，已经激活的传送门集合为 \(S\) 最多能完成多少个任务。
按照 \(i\) 从小到大转移，则我们先用 \(f\) 和 \(g\) 更新 \(g\)，再用 \(g\) 更新 \(f\) 即可。但是每一次更新 \(f\) 的复杂度为 \(\mathcal{O}(n m 2^n)\)，总时间复杂度为 \(\mathcal{O}(nm^2 2^n)\)，还是过不掉。
可以按照 \(S\) 从小到大转移，这样 \(f\) 的更新就能放在一起做了，时间复杂度 \(\mathcal{O}((n + m) m 2^n)\)。
需要预处理一些东西，这是容易的。
G
考虑第一个选择的区间 \([l, r]\)，其把 \([1, n]\) 分为了 \([1, l - 1]\) 和 \([r + 1, n]\) 两个相互独立的区间，形成了分治结构。我们需要支持的操作是查询一个被一个区间包含的所有区间中编号最小的那个，使用树套树实现。
因为至多选择 \(\left \lfloor \frac{n}{x} \right \rfloor\) 个区间，所以时间复杂度是 \(\mathcal{O}(n \log^3 n + m \log^2 n)\)。
H
首先考虑 \(k = 0\)。设 \(f_{i, j}\) 表示从 \(i\) 开始走 \(2^j\) 步能走到的最远的位置。显然，\([i, f_{i, j}]\) 内的所有位置都是可达的，所以转移就是
\[f_{i, j} = \max_{p \in [i, f_{i, j - 1}]} f_{p, j - 1} \]查询依然考虑倍增。令 \(j : \left \lfloor \log n \right \rfloor \to 0\)，依次考虑答案加上 \(2^j\) 是否可行即可，也是区间 \(\max\) 查询。
加上 \(k\) 之后，实际上再加一维表示当前用了几次操作、转移加个背包即可。
若区间 \(\max\) 直接使用 ST 表优化，空间复杂度为 \(\mathcal{O}(nk \log^2 n)\)，无法接受。但是发现求 \(f\) 是 \(j \to j + 1\)；求答案是 \(j \to j - 1\)，于是每一层做完以后更新 ST 表即可，空间复杂度变为 \(\mathcal{O}(nk \log n)\)，可以接受。
时间复杂度 \(\mathcal{O}(n k \log^2 n)\)，需要卡常。我把 ST 表的两维交换就过了，大概是内存访问更连续吧。
标签：everyone,log,传送门,Spring,复杂度,任务,时间,mathcal,Div From： https://www.cnblogs.com/Scintilla/p/17370606.html