题目：[[2024.9.24 题目]] ## 集合 给定正整数 $n$，有集合 $S={1,2,\cdots,n}$，对于 $S$ 的子集 $s$，计算 $\prod s$，对 $998,244,353$ 取模。 --- 首先，这道题我们自然不能从选择的方案入手，因为枚举选择的方案数量会达到 $2^n$ 这个量级，而 $n\le 200$，因此我们可以从子集的和入手，因为不同的子集可能会有同样的和，而和的数量也仅仅只有 $\cfrac{n(n+1)}{2}$。 令 $dp_{i,j}$ 表示为已经选了 $1\sim n$ 中的若干个数，和为 $j$ 的方案数量。我们枚举 $i$，则对于任意的 $j$，不管它是怎么达到 $j$ 的和的，我们都可以把所有达到 $j$ 的和的子集加入一个元素 $i$，便是 $dp_{i,j+i}\gets dp_{i,j+i}+dp_{i,j}$，或者写成 $dp_{i,j}\gets dp_{i,j}+dp_{i,j-i}$ $(j\le i)$。可以使用压数组+倒序枚举 $j$ 的方式将其压至一维。 现在我们已经知道任选若干个元素，和为 $j$ 的方案数了，我们需要将其乘起来，因此枚举 $j$，我们每次将答案乘上 $j^{dp_j}$ ，因为有 $dp_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\limits_{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 九月/2024.9.23 模拟赛]]，较好； - **问题**：树形 dp、序列 dp 能力较差。