2024.6.25

lupengheyyds / 2024-11-13 / 原文

2024.6.25

题目T2,3,4只想到了算法，却不知道具体该如何设计

T1最后使用了没有证明的常数优化，导致错误

T1

题面

给长为 $n$ 的序列 $\{a\}$ 和整数 $d$，你需要找到 $l,r$ 使得 $l\le r\le l+d$，构造序列 $\{b\}$，其中

\[b_i=\left\{ \begin{aligned} l,&&a_i\le l\\a_i,&&l<a_i<r\\r,&&a_i\ge r \end{aligned} \right. \]

求出 $\sum_{i=1}^{n-1}|b_{i+1}-b_i|$的最大值

$1\le n\le 2\times 10^5$

解法

可以看作是一个人在数轴上奔跑，那么每次应该为计算 $l\sim r$ 中的距离，一段距离可以看作区间加一，那么用差分就可以了,$\mathcal O(n\log n)$，瓶颈在离散化。

方法

数形结合
差分

T2

题面

给定一棵有根树，保证标号为一个合法的 dfs 序。把树的所有叶子按照编号顺序取出，设为 $u_1,u_2,\cdots,u_m$
当 $m>1$ 时额外添加 m 条形如 $(u_i,u_{i+1})$ 的无向边 $(u_{m+1}=u_1)$ 。求新图的匹配个数，对 $998244353$ 取模。
匹配：一个边集 S 满足其所有边的所有端点两两不同。匹配个数即位合法的边集个数（重边算不同的边）。

$1\le n\le 10^5$

解法

直接做树形 dp，$dp[u][0/1][0/1][0/1]$ 表示以 $u$ 为⼦树，$u$ 是否匹配，$u$ ⼦树编号最⼩的叶⼦是否匹配，$u$ ⼦树编号最⼤的叶⼦是否匹配的⽅案数。做树形 dp ，每次将新考虑的子树合并。注意最后 $(u_1,u_m)$ 这条边需要额外考虑。时间复杂度 $\mathcal O(n)$ 。

因为只要子树状态不一样，其方案就是不一样的，所以实现的时候可以直接 $2^6$ 枚举所有的子树状态，再对这些状态进行判断，避免重复计算

方法

类树形背包

T3

题面

有一张 $2×n$ 的网格图，你要从左上角 $(1,1)$ 走到右下角 $(2,n)$ 。每条边有边权，并且有额外的 $m$ 条限制。每条限制形如：给定 $i,j,c$ ，如果你同时走了 $(1,i)$ 到 $(1,i+1)$ 和 $(2,j)$ 到 $(2,j+1)$ 这两条边，那么你就需要额外 $c$ 的代价。求走过的边权和加上代价的最小值。

$1\le n\le 500,1\le m\le 1000$

解法

相当于对每个 $i$，我们需要在 $(1,i)$ 到 $(1,i+1)$ 与 $(2,i)$ 到 $(2,i+1)$ 之间选择⼀个。选每⼀种需要⼀个代价，如果 $i-1$ 和 $i$ 选择了不同的⾏，那么就需要额外付出 $(1,i)$ 到 $(2,i)$ 之间边的代价。再加上 $m$ 条限制，是⼀个⼩型的切糕模型，直接建图跑⽹络流即可。

方法

最小割——切糕模型

有 $n$ 个变量，每个变量有若干种取值，两两变量取值相互之间会存在影响，求和最小的方案

T4

题面

给定 $n,m$，对所有长度为 $n$，值域为 $[1,m]$ 的序列求众数出现次数之和。对 $10^9+7$ 取模。多组数据。

$1\le n\le 1000,1\le m\le 10^9,1\le T\le 10$

解法

欲求众数出现次数 $k$ 的方案数，利用 $等于=小于等于-小于$，转化为求众数出现次数 $\le k$ 的方案数，也就是所有数出现次数都 $\le k$ 的方案数。利用生成函数求排列的知识，只需要将 $\sum_{i=0}^\infin\frac {x^i}{i!}$ 设置一个上限，改为 $e(x)=\sum_{i=0}^k\frac{x^i}{i!}$，即可，那么答案就是 $n![x^n]e^m(x)$。

考虑如何快速求解，我们知道 $e(x)$ 其实是在 $e^x$ 的展开上设置了上限，然而 $e^x$ 有一个特殊性质为 $(e^x)'=e^x$，于是类似的，有 $e'(x)=e(x)-\frac {x^k}{k!}$，于是根据求导法则

\[(e^m)'(x)=me^{m-1}(x)(e(x)-\frac{x^k}{k!})=me^m(x)-\frac{mx^k}{k!}e^{m-1}(x) \]

这是一个可以 $\mathcal O(n)$ 递推的式子，由于我们只关注 $(e(x))^m$ 的前 $n$ 项，所以只需要求得 $(e(x))^{m-1}$ 的前 $n-k$ 项，一直到我们已知的 $[x^0](e(x))^{m-n/k}=1$，复杂度为 $\mathcal O(\frac {n^2}k)$。对于每个 $k\in [1,n]$ 执行上述过程，复杂度 $\mathcal O(Tn^2\log n)$