幸せな明日を願うけど 底なしの孤独をどうしよう もう うめき声しか出ない わたし ぎゅうぐらりん
强度最低的一集。 考虑一个点 $(p_1,...,p_k)$ 的距离应该怎么算。 不难发现只可能是他们奇/偶最短路的最大值。也就是在距离最大的点到达前,其他所有的点都在某条边上来回横条。 记 $f_{u,0/1}$ 表示点 $u$ 的偶/奇最短路,那么答案就是 $$\sum_{S=\{p_1,...,p_k\}}{\min(\max_{u\in S}(f_{u,0}),\max_{u\in S}(f_{u,1}))}$$ 既有min又有max,不是很好算。考虑min-max容斥,则答案为 $$\sum_S{\max_{u\in S}(f_{u,0})}+\sum_S{\max_{u\in S}(f_{u,1})}-\sum_S{\max_{u\in S}(\max(f_{u,0},f_{u,1}))}$$ 注意到三者完全等价,我们只考虑第一项。 考虑将 $u$ 按 $f_{u,0}$ 升序排序后依次扫,那么问题转化为: 每次往某个组加入一个点,求从每个组中各选出一个点的方案数。 预处理逆元,容易做到线性复杂度。
题目3559 [USACO21Jan Platinum]Sum of Distances
6
评论
2024-03-29 22:04:35
|
|
あがいた梦を捨てて揺れる今日は眠って誤魔化せ 失くした言葉を知らないなら 各駅停车に乗り込んで
非常好凸包题,我不会一点。 首先尝试将答案写的形式化一点。令路径依次经过 $(i,a_i)$,则 $a_0=1,a_x=y,a_i\le a_{i-1}$,答案为 $$\sum_{i=1}^{x-1}{C_{a_i}}+\sum_{i=1}^{x}{(a_i-a_{i-1})i^2} =x^2y-1 +\sum_{i=1}^{x-1}{C_{a_i}-(2i+1)a_i} $$ 令 $f_{i,j}$ 表示 $a_i=j$ 时的最小答案,根据斜率优化,决策点应该在 $(j,c_j)$ 的下凸包在斜率 $2i+1$ 的切点。 而我们注意到,随着 $i$ 的增大,$2i+1$ 也增大,那么决策点会单调右移。 如果从 $f_{x,y}$ 开始倒序模拟决策过程,那么就是在 $1\sim y$ 的下凸包上,先找到斜率 $2x+1$ 的切点 $p$,之后不断在 $p$ 原地决策,直到 $2i+1$ 小于 $p$ 与 $p-1$ 之间的斜率后,决策点会变为 $p-1$,然后重复…… 注意到除了最开始的 $p$,再往后的决策是固定的,可以直接预处理贡献。而 $p$ 可以凸包二分求出,$p$ 的贡献也是容易计算的。
对于多组询问,注意到不同的只有 $y$ 的限制。考虑将询问离线挂到 $y$ 上,在维护到 $1\sim y$ 的凸包时计算答案。 时间复杂度 $O(q\log n)$。
题目3566 [USACO21Jan Platinum]Minimum Cost Paths
5
评论
2024-03-29 21:45:20
|
|
君よ いっそいっそ いなくなれ 変わらない このままなら
显然题中生成的BST就是笛卡尔树,但是如果因此就往子树合并类的DP想的话就寄了(比如我)。 正确的做法是,将点的深度转化为祖先的个数,进而转化为每个点成为它祖先的方案数。即 $$Ans_u=\sum_v{\sum_{BST} [v\in anc(u) ]}$$ 而 $ [v\in anc(u) ]$ 的充要条件是 $v$ 是 $u,v$ 间的最小值。
如果不考虑 $(u,v)$ 的限制,计算恰有 $k$ 个逆序对的排列数是经典的。令 $f_{i,j}$ 表示 $i$ 个数的排列,已有 $j$ 个逆序对的方案数,枚举 $p_i$ 与前 $i-1$ 位的相对大小,有 $$f_{i,j}=\sum_{k=0}^{i-1} f_{i-1,j-k}$$ 这是可以写作生成函数的,令 $F_i=\sum f_{i,j}x^j$,有 $$F_n=\frac{\prod_{i=1}^n(1-x^i)}{(1-x)^n}$$ 这允许我们 $O(n^3)$ 的计算总方案数。
现在有了 $(u,v)$ 的限制,先考虑 $u>v$ 的情况。 注意到上面的DP实际上是在往排列中一个一个塞数,而往最前端塞和最后端塞实际上是等价的。 那我们可以先将 $u,v$ 间的数先塞完,那么其它数就跟正常一样的。而增加的限制无非就是在塞 $v$ 的时候令 $k=0$,因为 $v$ 最小,无法产生逆序对。记 $L=u-v+1$,那么我们只用撤销第 $L$ 次转移,即 $$G=\frac{\prod_{i=1}^n(1-x^i)}{(1-x)^n} \frac{1-x}{1-x^L}$$ 那么当前的贡献就是 $[x^k]G$。 上面的式子直接算的话是 $O(n^4)$ 的。 我们可以先预处理 $\prod_{i=1}^n(1-x^i)$,并递推求出 $(1-x)^{n-1}G$,然后计算 $[x^k]G$,就可以做到 $O(n^3)$了。
对于 $u<v$ 的情况,无非就是在塞 $v$ 的时候令 $k=L-1$,做法是类似的,不再赘述。 注意到还有 $u=v$ 的贡献,其实就是没有限制的方案数。 于是总时间复杂度 $O(n^3)$。
题目3357 [USACO19 Dec Platinum]Tree Depth
5
评论
2024-03-29 21:07:05
|
|
我等必将复起,古木已发新枝。
前置是Pro3575。 首先把二分图判掉。 回顾一下我们的连边方式可以发现,图中的边只有三类: 1. $(x-1,y-1) \to (x,y)$. 2. $(x-1,y+1) \to (x,y)$. 3. $(x,x+1) \to (x,x+1)$. 显然,每层的方案数互不影响,于是我们可以逐层计算,最后乘在一起即可。
根据有关链头的分析,我们不难得到一个DP: 令 $f_{i,j}$ 表示考虑前 $i$ 个点,且第 $i$ 个点向右留了 $j$ 个链头的方案数。 考虑从 $f_{i-1,k}$ 转移到 $f_{i,j}$。那么 $i$ 中的 $j$ 个点继承前面的链头,剩下 $cnt_i-j$ 个点去连 $fa_i$,那么有 $$f_{i,j} \gets f_{i-1,k} C_{cnt_i}^{j} (2^{cnt_{fa_i}}-1)^{cnt_i-j} g(cnt_{i-1},k,cnt_i,j)$$ 其中 $g(n,x,m,y)$ 表示在数量分别为 $n,m$ 的两组点之间连边,使得第一组的前 $x$ 个点以及第二组的前 $y$ 个点都有连边的方案数。 枚举 $x$ 个点中不合法的个数进行容斥,得到 $$g(n,x,m,y)=\sum_{i=0}^{x}(-1)^i C_{x}^{i} (2^{n-i}-1)^y\ 2^{(n-i)(m-y)}$$ 转移是有条件的。当 $i$ 为层左端时,$j=0$。当 $fa_i$ 不存在时,$j=cnt_i$。
最后是统计答案。 若本层的右端不是 $(x,x+1)$,那么贡献就是 $f_{i,0}$。 否则,$f_{i,j}$ 需要乘上其内部连边的方案数。不难发现就是在 $cnt_i$ 个点间任意连边(可以自环),使得前 $j$ 个点都有连边的方案数,记作 $h(cnt_i,j)$。 类似的容斥,得到 $$h(n,x)=\sum_{i=0}^x (-1)^i C_{x}^{i} 2^{\frac{(n-i)(n-i+1)}{2}}$$ 最终对答案的贡献就是 $\sum f_{i,j}h(cnt_i,j)$。
然后是节点 1 的保留节目。注意到如果节点 1 有自环,那么这个自环在新图中也是必须有的,而我们会当做有无均可计算,所以答案需要 $/2$。 恰当的预处理可以做到时间复杂度 $O(n^3)$。 实际上还有 $O(n^2)$ 的原神做法,但是我不会。一定是原神等级太低导致的。
题目3576 [USACO21Feb Platinum]图的计数(Counting Graphs)
5
评论
2024-03-23 22:42:12
|
|
只要不失去你的崇高,整个世界都将为你敞开。
喜报:本人在写完本文后,由于网站自动注销,且文章没有保存,成功丢失了全稿。现在这篇是本人又码了一遍得到了。令人忍俊不禁。
注意到 $f$ 只与原图的奇/偶最短路有关,那么每个点在两个图上的奇/偶最短路应该都是相同的。 若原图是二分图,那么答案为任意一棵生成树。 否则,所有点的奇/偶最短路均存在,记作 $(x,y)$。又发现两者的顺序无影响,于是不妨令 $x \lt y$。 考虑一个点 $(x,y)$ 的连边方式: 1. $(x-1,y-1) \to (x,y)$. 2. $(x-1,y+1) \to (x,y) \gets (x+1,y-1)$. 3. $(x-1,x+2) \to (x,x+1) \gets (x,x+1)$. 实际上③是②在 $y=x+1$ 时的特殊情况,但是很有用。
注意到②③中 $x+y$ 是不变的,这启示我们将点按照 $x+y$ 分层。而①中又有 $y-x$ 不变,这启示我们在每层中按照 $y-x$ 升序。 此时我们的连边方式就变得直观了。考虑在以 $x+y$ 为横轴,$y-x$ 为纵轴的坐标系中,我们的连边方式体现为: 1. 向正下方的点连边(如果存在)。 2. 向左右的点分别连边 (如果存在)。 3. 每层最右侧的点,若是 $(x,x+1)$,那么它可以和自己连边。 可以画个图理解一下。 显然①是最划算的,但问题是 $(x-1,y-1)$ 可能不存在,此时我们必须使用②③。 分析一下②③,可以发现本质是将一条链不断往右延伸,并最终在 $(x,x+1)$ 内部消化。显然我们应该将链两两配对,来省去一般代价。
现在我们来分讨一下策略。 考虑点 $(x,y)$,记它包含 $cnt$ 个节点,令 $(x-1,y-1)=fa,(x-1,y+1)=lst$,那么: 1. 若 $fa$ 存在, $lst$ 不存在。那么就直接全连①即可,不向后面留任何链头。 2. 若 $fa$ 不存在, $lst$ 存在。那么就只能全连②,并向后留 $cnt$ 个链头。 3. 若 $fa$ 与 $lst$ 均存在。分析一下可以发现,我们应该让前面的链头尽量分散地连到当前点,再向右传递下去。如果还有剩的,就用①连。 4. 若 $fa$ 与 $lst$ 均不存在。显然这是不可能出现的,因为原图的存在实际上已经为有解做了保障。 可以发现,只有②会产生链头。 最后我们会到达本层的最右端。 若它为 $(x,x+1)$。记它后面还有 $c$ 个链头,通过两两配对,只需要 $\left \lceil \frac{c}{2} \right \rceil $ 的代价。 否则,因为有解,本层一定不存在任何链头。
其实还没完,由于节点 1 并不需要连边,需要特殊处理。要留意一下节点 1 有自环的情况。 可以用 map 之类的实现,时间复杂度 $O(n\log n)$。
题目3575 [USACO21Feb Platinum]Minimizing Edges
5
评论
2024-03-23 22:39:14
|
|
在与牢大战斗两个多月后,“引爆逆天力量,追寻圆环之理的神藏奥秘”系列堂堂打赢复活赛。看来扣1真的有用! 直接做明显没前途,考虑容斥。 注意到位置 $i$ 不合法当且仅当 $a_i<a_{i-1}$ 且 $a_i|a_{i-1}$,即 $a_i$ 为 $a_{i-1}$ 的非自身因数。 考虑有一些非法位置,其他位置随便放,然后钦定非法位置的数为上一位的非自身因数。 然而注意到非法位置的方案数是不好算的,因为可能出现多个非法位置连着的情况,此时各个非法位置是不独立的。 幸运的是,由于 $a_i\le a_{i-1}/2$,每个非法位置连续段的长度不会超过 $\log m$,那我们就可以直接枚举连续段的长度进行DP。 记 $f_i$ 表示 $i$ 作为连续段结尾的容斥贡献,$s_i$ 表示前 $i$ 位的容斥贡献和,那么有 $$f_i=\sum_{j=1}^{\log m} g_j s_{i-j-1} (-1)^j$$ $$s_i=f_i+ s_{i-1}m$$ 其中 $g_i$ 表示连续 $i$ 个非法位置,且前一个合法位置随便放的方案数,容易 $O(m\log m)$ 预处理。 显然DP可以矩阵优化,于是做到了 $O(\log^3 m \log n)$ 的复杂度。可能爆标了? Bonus: 注意到DP是一个线性递推,使用 BM 算法可以做到 $O(\log m \log n \log\log m)$。
题目2293 [HZOI 2015]EX_香蕉
8
1 条 评论
2024-02-27 21:15:06
|