2024.9.24 模拟赛

题目：2024.9.24 题目

集合

给定正整数 $n$，有集合 $S=1,2,\cdots ,n$，对于 $S$ 的子集 $s$，计算 $\prod s$，对 $998,244,353$ 取模。

---

首先，这道题我们自然不能从选择的方案入手，因为枚举选择的方案数量会达到 $2^n$ 这个量级，而 $n\le 200$，因此我们可以从子集的和入手，因为不同的子集可能会有同样的和，而和的数量也仅仅只有 $\frac{n(n+1)}{2}$。

令 $d{p}_{i,j}$ 表示为已经选了 $1\sim n$ 中的若干个数，和为 $j$ 的方案数量。我们枚举 $i$，则对于任意的 $j$，不管它是怎么达到 $j$ 的和的，我们都可以把所有达到 $j$ 的和的子集加入一个元素 $i$，便是 $d{p}_{i,j+i}\leftarrow d{p}_{i,j+i}+d{p}_{i,j}$，或者写成 $d{p}_{i,j}\leftarrow d{p}_{i,j}+d{p}_{i,j-i}$ $(j\le i)$。可以使用压数组+倒序枚举 $j$ 的方式将其压至一维。

现在我们已经知道任选若干个元素，和为 $j$ 的方案数了，我们需要将其乘起来，因此枚举 $j$，我们每次将答案乘上 $j^{d{p}_j}$ ，因为有 $d{p}_j$ 种方案和为 $j$。注意取模（$dp$ 数组的取模需要摸 $mod-1$，因为费马小定理）。时间复杂度为 $\mathcal{O}(n^3)$。

出租

有 $n$ 栋楼，编号 $1\sim n$，每栋楼 $k$ 个空房间，每房间住一人。对于喜好为 $x$ 的租客，它只能住在编号为 $x\sim x+d$ 的楼中。现有 $m$ 次询问，询问为 $(x,y)$ 的形式，表示来了 $y$ 个喜好为 $x$ 的租客，$y$ 为负代表租客离开。每次询问你要回答是否能住下所有租客。

---

由于答案只会有有解、无解的情况，因此我们考虑判断无解。对于任意一段租户 $[l,r]$，如果它们的总人数大于 $k(d+r-l+1)$ 时，便有人住不到房间，就是无解的情况。对其作差，得到不等式 $\sum _{i=l}^r(a_i-k)>k\times d$。因此，我们可以搞出一个序列 $b_i=a_i-k$，只需要维护 $b_i$ 的最大字段和，询问的时候看一下是否大于 $k\times d$ 即可。

维护最大字段和的数据结构可以选可爱的线段树。由于只有单点修改，不需要打懒标记，甚至都不需要写区间查询，只需要访问 $t_0$ 就行了。最重要的是要开 $4$ 倍。

联通块

有一棵根为 $1$ 的树，点的编号为 $1\sim n$，第 $i$ 个点的权值为 $a_i$，dfs 序为 $d_i$。你需要在树上找到权值和最大的联通块，满足 $m$ 个 $(u,v)$ 的性质：$u,v$ 若同时存在于连通快内，$d_u$ 与 $d_v$ 不能相邻。输出最大和。

---

暴力思路：枚举所有顶点选择的可能，判断一下是否在一个联通块内（使用并查集），然后判断 dfs 序是否相邻，如果都满足条件就可以直接加起来取最值了。时间复杂度 $\mathcal{O}(2^n(n\cdot \alpha (n)+m))$，成功骗到 $20$ 分。

跳棋

有 $1\times n$ 的棋盘，每一个格子里最初的形式为 $0,1$ 或 $?$。$0$ 表示该格子没有棋子，$1$ 反之，$?$ 表示不知道。一个棋子可以跳过它旁边的棋子，到它旁边的棋子的下一个位置，仅当那个位置没有棋子。对于所有可能的开局，你可以操作若干包括 $0$ 步，问你每一种开局下面结束状态的数量，的和。

---

对于每一个 $?$ 的方格，我们枚举所有的可能性，然后使用记忆化搜索搜出所有可能的结束状态（用状态压缩将 $01$ 序列压缩到整数内），所有加起来即可。时间复杂度 $\mathcal{O}(2^q\times 2^n\times n)$。成功骗到 $20$ 分。

总结

• 排名：$2$；
• 比赛分数：$240/400$；
• 情况：相比与 2024.9.23 模拟赛，较好；
• 问题：树形 dp、序列 dp 能力较差。