8.6 模拟赛
盖世计划--C班--潍坊营--8月6日 - 比赛 - 梦熊联盟 (mna.wang)
盖世计划--C班--潍坊营--8月6日【订正】 - 比赛 - 梦熊联盟 (mna.wang)
太久没打真实的模拟赛了，今天有些不适应【】
时间是 8.6 的 8:00~12:00，时间分配出了大问题。主要问题是 T3 的 5k 线段树调起来困难无比。最后也没调完。导致暴力分少了 100 多【】
赛后发现挂的地方是一个局部变量没赋初值【】
A 线段
一开始没看懂题。过了很长时间后看懂了一点，觉得 \(n \le 5\) 的 dfs 很快就能写完就没管这题。此时正在写 T3 就没管它。快结束时想写这题暴力又忘了题意是啥了【】。
\(0+100\)。
题意
数轴上有 \(n\) 个点，构成了 \(\frac{n(n+1)}2\) 个线段。令所有线段为全集。问有多少子集，满足这个子集内的线段，在两两不交的情况下能选出的最多线段数恰好为 \(k\)。\(k \le n \le 500\)。
做法
如果暴力 dfs，那么 check 的做法是经典贪心。即将所有线段按照右端点排序，然后顺次判断能不能选这条线段。见 AcWing 908.。
数据范围不大，考虑狠狠地 DP。
设 \(f(i, j)\) 表示当前贪心得到的最大右端点的位置 \(\le i\)，且最优策略中选择的线段数量为 \(j\) 时的总方案数。
或者，\(f(i, j)\) 即有多少个原题的答案的线段集合，使得这个集合的最优选择中最靠右的线段的右端点 \(\le i\)，且最优方案选择的线段数量为 \(j\)。
转移。枚举倒数第二大的最优选择中的线段的右端点 \(p\)。我们考虑线段 \([l, r]\)（\(l \le r \le i\)）：
- 若 \(r \le p\)：那么这条线段在 \(f(p, j - 1)\) 中已经被计算过了。
- 若 \(l \le p\) 且 \(p < r < i\)：这条线段一定不在 \(f(i, j)\) 的最优选择中。所以这样的线段可有可无，方案是 \(2^{p (i-p-1)}\)。
- 若 \(p \le l < r < i\)：这条线段如果存在，就不满足「最优选择中最靠右的线段的右端点为 \(i\)」这个条件。所以这样线段不能出现。
- 若 \(l \le p\) 且 \(r = i\)：这条线段一定不在 \(f(i, j)\) 的最优选择中。所以这样的线段可有可无，方案是 \(2^p\)。
- 若 \(p < l\) 且 \(r = i\)：这条线段可能是 \(f(i, j)\) 状态中所说的「最优选择中最靠右的线段的右端点为 \(i\)」的线段，但是这条线段只能有一条，而剩下的线段可有可无。方案是 \((2^{i-p} - 1)\)。
综上转移：
\[f(i, j) = \sum_{p=0}^{i-1} f(p,j-1)\times 2^{p(i-p-1)} \times 2^p \times (2^{i-p}-1) \]初始化：
- \(f(i, 0)\)：表示最优方案选择的线段数量为 \(0\)。显然只用空集一个，答案为 \(1\)。
- \(f(0, i)\)：表示线段右端点为 \(0\)。仍然只用空集一个，答案为 \(1\)。
快速幂是过不掉的。我们考虑预处理一些 \(2\) 的幂：
- \(2^p\)，\(2^{i-p}\)：线性递推。
- \(2^{p(i-p-1)}\)：设 \(g_{i, j} = 2^{ij}\)，那么转移 \(g_{i, j} = g_{i - 1, j} \times 2^j\) 或 \(g_{i, j} = g_{i, j - 1} \times 2^i\)。
B 计算
这场比赛开的第一道题。因为第一眼，原！
显然这两道题不一样【】
涨了很多见识，数论题也是可以 DP 的！
\(40+100\)。
题意
给定 \(k\) 个两两互质的正整数，求 \(1 \sim n\) 中有多少数不能被任意一个数整除。
做法
「多少数不能被任意一个数整除」= $n - $ 「多少数能被任意一个数整除」。
考虑 DP。设 \(f(n, k)\) 表示有多少个 \(1 \sim n\) 的数，能被 \(a_1,a_2\dots a_k\) 中的任意一个数整除。
很妙的转移！
\[f(n, k) = \lfloor n / a_k\rfloor + f(n, k - 1) - f(\lfloor n / a_k\rfloor, k - 1) \]其中，\(\lfloor n / a_k\rfloor\) 表示 \(1 \sim n\) 中能被 \(a_k\) 整除的数的个数，\(f(n, k - 1)\) 表示 \(1 \sim n\) 中能被 \(a_1\dots a_{k-1}\) 整除的数的个数。
显然这两个集合可能有交，即 \(1 \sim n\) 中既能被 \(a_k\) 整除，又能被 \(a_1 \dots a_{k-1}\) 中任意一个数整除的数。
如果一个数 \(x\) 是这两个集合的交，那么 \(\frac x{a_k}\) 一定能被 \(a_1 \dots a_{k-1}\) 中任意一个数整除。那么 \(\frac x{a_k}\) 的数量为 \(f(\frac x{a_k},k-1)\)。因为 \(x\) 和 \(\frac x{a_k}\) 一一对应，所以 \(x\) 的数量也是 \(f(\frac x{a_k},k-1)\)。
直接用 (u)map 转移空间复杂度会爆。优化方案有两种：
方法一：整除分块。
前排提醒，这种做法在时间上被卡常乐【】
对于每一个有效的状态 \(f(i, j)\)，这个 \(i\) 一定是由给定的 \(n\) 开始，不断除以某个 \(a_k\) 下取整得到的。根据 知识 我们得知这样的 \(i\) 的数量是根号级别的。
因此我们可以双指针得到 \(n\) 除以某个数下取整可能的得到的值（如上所述，数量是根号级别的），将其离散化即可。
离散化后转移可以双指针，一个指向 \(n\)，一个指向 \(\lfloor n / a_k\rfloor\)。
而且这个状态的第二维可以滚动优化。空间复杂度做到了根号。
后排提醒，这种做法在时间上被卡常乐【】
方法二：暴力 + 记忆化。
我们设一个阈值 \(B\)，然后记忆化转移。对于状态 \(f(i, j)\) 若 \(i < B\) 则用数组记忆化。否则直接转移不记忆了。这里我取的 \(B = 10^6\)。不难（？）证明这样的复杂度是正确的。
C 球
罪魁祸首。
这是一个难想+难写+难调的做法。最终代码 5KB。
\(0+100\)。
题意
做法
我们给每个空隙一个属性：
\[a_i = \left\{ \begin{matrix} 1&, s_i = \texttt {//} \\ -1 &,s_i = \texttt{\\\\} \\ +\infty&,s_i = \texttt{/\\}\\ -\infty&,s_i = \texttt{\\/}\end{matrix}\right. \]其中 \(s_i\) 表示与空袭 \(i\) 相邻的两个边的状态。
模拟一下可以发现，如果要反转边 \([l, r]\)，首先我们可以分类讨论出 \(a_l\) 和 \(a_{r+1}\) 的变化，其次 \(a_{l+1}\dots a_r\) 都会变成它的相反数。
考虑询问。如果在两个相邻的山峰（\(a_i=+\infty,s_i = \texttt{/\\}\)）间扔球，那么这些球都有相同的归宿。所以答案为 \([l-1, r]\) 中相邻的两个 \(+\infty\) 的下标差的最大值。
写一颗 5KB 线段树即可。
在查询之前我们可以先将 \(a_{l-1}\) 和 \(a_r\) 设成 \(+\infty\)。显然现在我不知道当时我这么写的原因了，反正这样写能烧掉很多特判。
D 数列
神秘题，数学推导没听懂。
\(0+40\)。
说一下 40 分暴力：对于每个 \(k \in [1, 100],n\in[1,10^5]\) 预处理一张答案表。预处理总复杂度是 \(10^7\) 级别的，即暴力枚举每一次加数。
\(x+y+z\) 表示赛时预计 \(x\) 分，实际 \(y\) 分，赛后补了 \(z\) 分。
8.7 模拟赛
4.5 小时 5 道题。
有一道炼石的题，那场我们打过，当时那题场切了。但是现在不会做了【】
有一道 CF 某 div.2 F 的弱化。没做出来【】
T1. 降温
赛时想出了做法，拍了一点小数据。但是最后被浮点数的精度和 __int128 挂了。
\(60+100\)。
题意
有 \(n\) 个装置，每个装置有初始温度 \(t_i\)。
给定正整数 \(A, B\)，一次降温操作可以将一个装置温度降低 \(A\)，剩下 \((n - 1)\) 个装置温度降低 \(B\)。
求至少需要多少次降温操作才能让所有温度严格小于 \(0\)。
My Solution
我们称将一个数减少 \(A\) 为特殊操作，减少 \(B\) 为特殊操作。显然特殊操作的最小次数即答案。
不妨令对 \(i\) 进行了 \(x_i\) 次特殊操作。我们二分它们的和 \(\sum x_i = X\)，即答案。
对于 \(i\) 而言，它的特殊操作次数为 \(x_i\)，普通操作次数为 \(X - x_i\)。那么它被减少的量为 \(x_i \cdot A + (X - x_i) \cdot B\)。只有这个值 \(> t_i\) 才能满足要求。
那么 check 要做的就是判断是否存在一个这样的 \(x\) 数组，使得每项均为非负整数，且所有数的和为 \(X\)，且：
\[x_i \cdot A + (X - x_i) \cdot B > t_i \]做一些简单的推导：
\[x_i \cdot (A - B) > t_i - X \cdot B \]不等式上做除法不太好做。考虑分类讨论：
若 \(A = B\)，那么在最开始特判即可。答案为 \(\max\{ \lfloor \frac{t_i}A \rfloor +1\}\)。
若 \(A > B\)，那么直接除：
\[x_i > \dfrac{t_i - X \cdot B}{A - B} \]右边是个常数。我们可以求出在这样的情况下 \(x_i\) 的最小值。若每个 \(x_i\) 的最小值之和 \(\le X\) 则 check 合法。
若 \(A < B\)，除过去要变号：
\[x_i < \dfrac{t_i - X \cdot B}{A - B} \]同理我们可以求出每个 \(x_i\) 的最大值。若每个 \(x_i\) 的最大值之和 \(\ge X\) 则 check 合法。
std Solution
一次降温操作是选择一个减 \(A\)，剩下全减 \(B\)。那么我们可以将所有数先全减 \(B\)，在选择某个数加上 \(A - B\)。
仍然二分答案 \(X\)。令 \(a_i = t_i - B \cdot X\)。此时我们需要判断，能否执行 \(X\) 次操作，每次操作会选择一个数加上 \(A - B\)，使得最终整个序列均为负。
\(A = B\) 太水了。我们考虑：
- \(A > B\)：这样的操作是劣的。因此我们每次找当前的最大值执行这样的操作。
- \(A < B\)：这样的操作是优的。因此我们每次找当前的最小值执行这样的操作。
真的操作复杂度不对。
- \(A > B\)：维护 \(b_i = \left\{ \begin{matrix} 0 &,a_i \ge 0 \\ \left\lfloor \dfrac{-a_i}{A-B} \right\rfloor + 1&,a_i < 0 \end{matrix}\right.\)。问题等价于 \(\sum b_i \le X\)。
- \(A < B\)：同理。不写了。
代码没写。
T2. 数学题
\(70+40+100\)。
以为会 70。但是 \((10^4)^2 \times 10 \times 10\) 你觉得能不能过？
题意
求 \(L, R\) 内有多少数的数码种类为 \(A\)。\(L, R\) 位数都为 \(n \le 2 \times 10^5\)。
做法
差分转化。考虑 \(1 \sim x\) 的答案。
数位 DP 套路地枚举 \(y \in [1, x]\) 的第一个与 \(x\) 不同的位置 \(i\)，并枚举这一位填什么。这样我们就得到了 \(y\) 的前 \(i\) 位，且 \(i + 1 \sim n\) 位都可以 \(0 \sim 9\) 任意填。
我们可以求出前 \(i\) 位的种类数 \(B\)。如果 \(B > A\) 那么不可能。否则如果想让 \(y\) 的数码种类为 \(A\)，那么 \(y\) 的 \(i + 1 \sim n\) 位中，一定存在恰好 \((A - B)\) 个与前 \(i\) 位不同的数。这个的方案是 \(\dbinom {10-B}{A-B}\)。
接下来的问题是，在 \((n - i)\) 位中，每个数都有 \(A\) 种填法，但是有 \(B\) 个数至少出现一次。求方案数。
我们容斥枚举，有多少个必选的数没出现。式子：
\[\sum_{c=0}^B (-1)^c\dbinom Bc (A-c)^{n-i} \]复杂度 \(10^2n\)。
T3. 均衡区间
去年做过，而且场切了。现在不会了。
\(30+30+100\)。
题意
给定序列 \(a\)，\([l, r]\) 是均衡的当且仅当这个区间的最大值和最小值都不等于 \(a_l\) 和 \(a_r\)。分别求以 \(i\) 为左端点和右端点的均衡区间个数。
\(n \le 10^6\)。
做法
可以轻易求出 \(i\) 左/右边第一个比自身大/小的位置，单调栈维护。然后我们可以维护 \(f(i)\) 表示当 \(i\) 为右端点时，只要左端点在 \([1, f(i)]\) 内右端点就不是区间最大值或最小值。同理 \(g(i)\) 表示左端点，右端点在 \([g(i), n]\) 就合法。
那么 \([l, r]\) 合法等价于 \(l \le f(r)\) 且 \(g(l) \le r\)。固定 \(r\)。剩下的是二维数点，即平面上在 \((f(r), r)\) 下面的 \((l, g(l))\) 的数量。
T4. 几何题
原 CF1991F。
但是仍然不会做。
但是即使会做这题也被卡常乐。
\(45+45+100\)。
题意
维护 \(n\) 根木棍长度。单点修改，求区间内的木棍组成的三角形的最大周长。
做法
首先 CF1991F，我们得知当区间长度 \(\ge 50\) 时一定有解。那么不妨取出前 \(50\) 大的数。这些数也一定有解，而且最大。
暴力做长度 \(50\) 也是 CF1991F。只需要判断每相邻三个即可。
所以我们要做的是求区间前 \(50\) 大。可以线段树归并排序，也可以每次取最大值，再把最大值的位置设为 \(-1\)。
T5. 集合题
神秘题。
\(30+30+30\)。
8.8 讲课 状压 DP、数位 DP
P1896 状压 DP。模板题。有一种神秘的轮廓线做法 dan shi wo tai cai le。
CF1209E12 状压 DP。很妙的题。两个巧妙的关键点（去最大值限制、将 \(m\) 降到 \(n\)）都没想到。
P9131 状压 DP + 高维前缀和。想到了一半。
CF55D 数位 DP。用到了一些整除性质。
CF1245F 数位 DP。以前做过。
标签：WF,le,10,线段,8.19,端点,整除,MX,DP From： https://www.cnblogs.com/2huk/p/18349844