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)\)
方法
-
求导推式子
当遇到形如 \(f'(x)=f(x)+g(x)\) 的式子时，若 \(g(x)\) 已知，则可以 \(\mathcal O(n)\) 求得 \(f(x)\) 前 \(n\) 项
-
生成函数，在多项式形式的上下界进行修改，其实是限制了方案。