2024.4 第一周做题记录

\(2024.4.2\) CF1336D Yui and Mahjong Set

题意：

初始有一个值域在 \([1,n]\) 的多重整数集 \(S\)，且每个元素重复次数最多为 \(n\)，定义 \(\operatorname{triple}(S)\) 表示 \(S\) 中相同无序三元组数量，\(\operatorname{straight}(S)\) 表示 \(S\) 中连续整数的无序三元组数量，告诉你初始 \(\operatorname{triple}(S)\) 和 \(\operatorname{straight}(S)\)，每次你可以选择加入一个 \([1,n]\) 内的整数并会返回修改后的两项权值，要求在不超过 \(n\) 次操作后求出 \(S\)​。

\(4\leq n\leq 100\)。

题解：

solution.

code.

\(2024.4.2\) ABC306Ex Balance Scale

题意：

给一个大小为 \(n\)​ 的无向图，可以将一些点合并，求所有合并再将每条边定向后无环的方案数。

\(1\leq n\leq 17\)，时限 \(3s\)。

题解：

先不考虑合并点，设 \(f_s\) 表示 \(s\) 的导出子图定向后无环的方案数。

考虑枚举一个其定向后无环的某个图的极大入度为 \(0\) 的点集 \(t\)，即将所有 \((u,v)\) 满足 \(u\in t,v\in s\) 定向为 \(u\rightarrow v\)，那我们首先要保证 \(t\) 为独立集。

其次我们发现难以去要求其是极大的，所以考虑再将其容斥，显而易见有独立集的子集仍为独立集，又由于 \((\forall s)\sum\limits_{t\subseteq s}[t\neq\emptyset](-1)^{|t|+1}=[s\neq\emptyset]\)，因此容易有 \(f_s=\sum\limits_{t\subseteq s}[t\neq\emptyset][t\text{ 为独立集}](-1)^{|t|+1}f_{s-t}\)。

然后再考虑合并点操作，也就是把枚举到的 \(t\) 中连通块缩点即可。

预处理下每个子集中连通块数量再枚举子集计算即可，时间复杂度 \(O(3^n)\)​。

code.

\(2024.4.3\) 欧贝里斯克的巨神兵

题意：

给一个大小为 \(n\) 的有向图，求其生成无环子图数量。

\(1\leq n\leq 17\)，时限 \(4s\)。

题解：

思路同上一题，容易推得转移方程 \(f_s=\sum\limits_{t\subseteq s}[t\neq\emptyset](-1)^{|t|+1}2^{\operatorname{edges}(t,s-t)}f_{s-t}\)，其中 \(\operatorname{edges}(s,t)=|\{(u,v)|(u\in s)\land(v\in t)\}\cap E|\)，可以在固定 \(s\) 的情况下从小往大从低位转移，时间复杂度 \(O(3^n)\)。

code

\(2024.4.3\) 「PKUSC2018」最大前缀和

题意：

求一个序列 \(a\) 任意排列的最大前缀和之和。

\(1\leq |a|\leq 20\)。

题解：

首先为了防止计重，当有多个前缀和同时为最大时，我们钦定选择最靠前的。

设 \(b\) 为 \(a\) 的某个排列，\(s\) 是 \(b\) 的前缀和。那 \(s_i\) 最大当且仅当 \((\forall x\in [2,i]\cap\mathbb{Z})(s_i-s_{x-1}>0)\land(\forall x\in(i,n]\cap\mathbb{Z})(s_x-s_i\leq0)\)，即 \(b_{\{2,i\}}\) 后缀和全正，\(b_{\{i+1,n\}}\) 前缀和全非正。

因此维护 \(f_s\) 为点集为 \(s\) 且前缀和全非正的排列数，\(g_s\) 为点集为 \(s\) 且后缀和全正的排列数，\(f\) 枚举排列最后一位、\(g\) 枚举排列第一位，递推维护即可。最后枚举 \(b_1\) 再枚举 \(b_{\{2,i\}}\) 更新答案即可，时间复杂度 \(O(n2^n)\)。

code.

\(2024.4.4\) 「清华集训2014」主旋律

题意：

求一个有向图 \(G=(V,E)\) 的生成强连通子图数。

\(1\leq|V|\leq 15\)

题解

设 \(f_s\) 表示 \(s\) 的生成强连通子图数，答案即为 \(f_{V}\)。

强连通图等价于缩点后结点个数为 \(1\) 的图，容斥一下变成计数缩点后结点个数大于 \(1\) 的图。

类似前文 DAG 计数的思路，枚举缩点后入度为 \(0\) 的强连通分量集合再容斥，考虑到容斥系数的底数是 \(-1\)，次数是强连通分量数加一，于是维护每个点集划分为奇偶数个的强连通分量，转移时将前者减去后者再乘上 \(2\) 以起点不在这个入度为 \(0\) 的强连通分量内的边数次幂即可（因为对剩下的点没有要求，相关的边乱选即可）。至于每个点集划分为奇偶数个的强连通分量方案数，就是钦定最后一次一定选含编号最小的点的强连通分量，胡乱转移即可。因要枚举子集，所以复杂度 \(O(3^n)\)。

code