提高组数学专题 1 做题记录
A [CF1909F1] Small Permutation Problem（Easy Version）
首先推性质，发现若令 \(d_i=a_i-a_{i-1}\)，则：
- 若 \(d_i=0\)，那么 \(1\sim i-1\) 位置上的空位不能放 \(i\)，\(i\) 位置上不能放 \(\le i\) 的数。所以 \(i\) 位置成为一个空位。
- 若 \(d_i=1\)，那么要么在 \(1\sim i-1\) 的空位中放一个 \(i\)，要么在 \(i\) 位置上放一个 \(\le i\) 的数。
- 若 \(d_i=2\)，那么既要在 \(1\sim i-1\) 的空位中放一个 \(i\)，又要在 \(i\) 位置上放一个 \(< i\) 的数。
于是设 \(dp(i,j)\) 表示放到第 \(i\) 位，当前剩下 \(j\) 个空位的方案数。那么根据上面的分讨有：
- 若 \(d_i=0\)，则 \(dp(i,j)=dp(i-1,j-1)\)。
- 若 \(d_i=1\)，则 \(dp(i,j)=dp(i-1,j)\times j+dp(i-1,j)\times (j+1)\)。
- 若 \(d_i=2\)，则 \(dp(i,j)=dp(i-1,j+1)\times (j+1)\times (j+1)\)。
发现复杂度是 \(O(n^2)\) 的。不过实际上我们最终的状态就只有 \(dp(n,0)\)，并且每一步都可以通过 \(d\) 推算出上一步走到 dp 值的第二维，所以迭代 / 递归去实现复杂度其实是 \(O(n)\) 的。
*B [CF1909E] Multiple Lamps
首先我们观察到这样一个性质：如果将所有 \(n\) 个开关全部按一遍，最后亮起来的只有平方数，因为只有他们有奇数个因子。那么按照这样的策略去按我们最后会剩下 \(\lfloor\sqrt n\rfloor\) 个数，在 \(n\ge 20\) 的时候这个值恰好不超过 \(\lfloor\dfrac n5\rfloor\)，因此直接全部输出即可。
在 \(n\le 19\) 的时候，我们预处理一下，利用状压算出使亮灯数量合法的按开关状态，每一次询问的时候暴力判断是否满足限制要求即可。
C [HAOI2017] 方案数
首先考虑到格子总数过多，但是障碍格子少。这是经典的容斥 dp，设 \(f(i)\) 表示走合法路径走到第 \(i\) 个障碍物的方案数，那么会有转移方程：
\[f(i)=\{[0,0]\to[x_i,y_i]\}-\sum f(j)\times\{[x_j,y_j]\to [x_i,y_i]\} \]其中 \(\{[x_i,y_i]\to[x_j,y_j]\}\) 表示从 \((x_i,y_i)\) 走到 \((x_j,y_j)\) 的方案数。现在问题就是怎么求这个。
发现题目中所给出的转移本质上和具体数值无关，而只和坐标的 \(\text{popc}\) 值有关。所以我们就设 \(dp(x,y,z)\) 表示从 \((0,0,0)\) 走到满足 \(\text{popc}(i)=x,\text{popc}(j)=y,\text{popc}(k)=z\) 的 \((i,j,k)\) 的方案数。枚举当前这一步增加了多少 \(\text{popc}\) 然后分三种转移计算即可。总复杂度 \(O(\log^4 n+o^2)\)。
^D [CF1917E] Construct Matrix
大力分讨的构造题。
-
容易观察到，\(k\bmod 2=1\) 时必然无解。因此 \(k\bmod 2=0\)。所以接下来考虑将 \(k\) 按对 \(4\) 取模的结果分类。
-
\(k\bmod 4=0\) 时：
- 容易发现我们挨个去填 \(2\times 2\) 的正方形一定有解。
-
\(k\bmod 4=2\) 时：
-
当 \(k=2\) 或 \(k=n^2-2\) 时，如果 \(n\ne 2\)，则必然无解，否则有解。
-
当 \(k=6\) 时，可以在左上角构建一个如图所示的 \(4\times 4\) 的图案即可：
1 1 0 0 1 0 1 0 0 1 1 0 0 0 0 0 -
否则，我们先在刚才的图案中加入 \(4\) 个格子：
1 1 0 0 1 1 1 1 0 1 1 0 0 1 0 1然后剩下的部分挨个去填 \(2\times 2\) 的正方形即可。
-
E [CF1891E] Brukhovich and Exams
考虑贪心的思路。
首先我们一定是先将同时与相邻两个数都互质的数改成 \(0\)，这样每一次答案都可以减 \(2\)。接下来还有一种情况可以使得答案减 \(2\)，就是将序列中间连续的一段 \(1\) 全部改成 \(0\)。所以将这样的序列按长度从小到大贪心选即可。
剩下的所有数怎么改单次都只能使答案减 \(1\) 了，对于不是 \(1\) 的数，直接改成 \(0\) 即可，答案对应减 \(1\)；否则，剩下的 \(1\) 一定都在两边，此时应该从内向外去修改才能达到最优。
暴力模拟这个过程即可，复杂度 \(O(n\log V)\)。
*F [CF1886E] I Wanna be the Team Leader
观察样例发现假如我们对 \(a\) 从大到小排序，那么对于每一个项目，其所选的程序员在排序后的序列上是一个连续段。那么这个时候我们就悔得到一个最简单的 dp：设 \(dp(i,S)\) 表示到第 \(i\) 个人已经完成分配的项目集合是 \(S\) 的可行性。转移是简单的，复杂度 \(O(nm2^m)\)，炸成大粪了。
再考虑一个贪心的思路，对于一个集合 \(S\)，如果它对应选择的程序员正好是一个连续段的话，我们一定会让这一段的结尾更靠前。也就是说我们不必关心每一个人对于每一个集合的可行性，只需要关注每一个集合的终止位置。于是设当前已经分配的项目集合为 \(S\)，我们要求出最小的 \(dp(S)\)，使得将这些项目可以分配给 \([1,dp(S)]\) 中的人。转移方程比较简单：
\[dp(S\cup\{i\})=\min\{g(dp(S)+1,i)\} \]其中 \(g(i,j)\) 表示分配第 \(j\) 个项目时，若从 \(i\) 开始分配连续段，至少要分配 \([i,g(i,j)]\) 这个连续段才合法。这个可以简单 \(O(nm)\) 预处理出来，总复杂度即为 \(O(nm+m2^m+n\log n)\)。
标签：popc,专题,记录,text,复杂度,times,数学,即可,dp From： https://www.cnblogs.com/UKE-Automation/p/18563342