p_b_p_b的博客

博客

Public Round #7 题解

2022-07-31 19:46:16 By p_b_p_b
  • 搬题人:
    • A, B:p_b_p_b
    • C:ezoilearner
  • 组题人:p_b_p_b
  • 题解:p_b_p_b, ezoilearner

大凯的疑惑

题目来源:

  • Petrozavodsk Winter 2020. Day 8. Almost Algorithmic Contest, Problem I

QOJ 链接:https://qoj.ac/contest/448/problem/1462

正解不对拍,爆零两行泪。

$$ \begin{aligned} (a+d)^k-a^k=\sum_{i=1}^k {k\choose i}d^ia^{k-i} \end{aligned} $$ 设 $f_i={k\choose i}d^i$ ,列出前后几项:$f_1=kd, f_2=k(k-1)d^2/2,\cdots,f_k=d^k$ 。

不难发现答案的质因子一定都是 $d$ 的质因子,对 $d$ 的每个质因子 $p$ 分别考虑。设 $C(x)=\max\{i\mid p^i|x\}$ ,即 $x$ 里面 $p$ 的次数。

引理:当 $i\le p^{C(k)}$ 时, $C({k\choose i})=C(k)-C(i)$ 。

证明:$C(k-t)=C(t), 1\le t<p^{C(k)}$ 。

因此就有 $C(f_i)=iC(d)+C(k)-C(i), 1\le i\le p^{C(k)}$ 。并且由于 $C(d)\ge 1$ ,所以可以感性理解得到 $C(f_i)$ 大致是递增的,最小值是 $C(f_1)$ 。并且不难证明,如果 $C(f_1)$ 是唯一的最小值,那么答案就是 $p^{C(f_1)}$ 。

如果这个感性理解是正确的,那么答案就是 $kd$ 中 $d$ 的所有质因子,即 $\gcd(d^{\infty},kd)$ 。

事实上这个感性理解的并没有太大问题,只是在 $i$ 特别小的时候需要修一下。当 $p=2,C(d)=1,2|k$ 时,$C(f_2)=C(f_1)=C(kd)$ ,所以答案要多乘一个 $2$ 。

道路重建

题目来源:

  • 2021-2022 ICPC Asia Pacific - Yokohama Regional, Problem E
  • Moscow Pre-Finals Workshops 2022 Day 4, Problem E

QOJ 链接:https://qoj.ac/contest/912/problem/3798

显然可以先把城市内的最小生成树求出来,只有这上面的边是有用的。进一步,按照边权从小到大的顺序合并连通块时,如果至少一边没有枢纽车站,那么这条边一定会被计入答案,也不需要考虑了。

进行这些预处理之后可以认为 $m=n-1$ 且所有火车站都是枢纽车站。

人脑模拟 kruskal 的过程:

  • 在考虑到第一条高铁线路之前,每个城市都在按照相同的顺序合并,只是速度有快有慢。
  • 按 $a$ 从小到大考虑每个城市。
    • 不妨假设 $\arg \min a_i=1$ ,且 $b_1<b_2$ 。
    • 显然城市 $1$ 连的边是城市 $2$ 连的边的超集。因此城市 $2$ 目前的每个连通块都会向城市 $1$ 连恰好一条高铁线路。
    • 连接之后,我们发现两个火车站 $i,j$ 连通当且仅当对应编号在城市 $1$ 中连通,而与这两个火车站实际在城市 $1$ 还是城市 $2$ 无关!并且城市 $2$ 里面也不会连接新的动车线路了。
    • 因此接下来可以令 $a_1:=a_2$ ,然后忽略城市 $2$ 继续做。

复杂度 $O(n\log n)$ 。

杜杜和DUDU

题目来源:

  • Petrozavodsk Winter 2022. Day 6. 2022 ICPC Training Camp powered by Huawei — Day 1, Problem F

QOJ 链接:https://qoj.ac/contest/824/problem/2610

考虑按 $x$ 从小到大扫描线,维护哪些 $(x,y)$ 可达。

当我们扫完 $x\leq K$ 的时候,扫完的点有 $(x_1,y_1),\cdots,(x_q,y_q)$ .

定义 $g_y=\max(x_i|y_i\leq y)$ ,如果 $(x,y)$ 可达但 $x<g_y$ 那么 $(x,y)$ 没必要保留,因为 $(g_y,y)$ 不可达意味着 $(x,y)$ 不能一次到 $(g_y,y)$ ,注意按照定义一定存在 $(g_y,z),z\leq y$ 的点,所以 $(x,y)$ 到 $(g_y,y)$ 是有转移的,进一步这意味着 $(x,y)$ 不能一次转移到一个横坐标超过 $K$ 的点,因为这样的代价一定不少于 $(x,y)$ 到 $(g_y,y)$ 的代价。

我们需要设计的算法已经很明显了,扫的过程中我们维护一个序列 $seq$ , $seq_y=1$ 表示 $(g_y,y)$ 可达,反之不可达。假设我们现在扫完了小于 $K$ 的部分,现在要加入横坐标为 $K$ 的点,假设其中纵坐标最小的点是 $(K,z)$。

考虑可能的操作形式,一种是横坐标扩大到 $K$ ,但纵坐标不变,这种我们对于 $g_y$ 相同部分的 $y(y\geq z)$ 统一处理,按照势能分析这样的次数是 $O(n)$ 级别的,分析类似单调栈。

还有可能横纵坐标都加大,变成 $(K,z)$ ,这种只要对于每种 $g_y$ 维护可达的最大 $(g_y,y)$ .

在执行完上面两种转移后,我们还可能执行横坐标不变,纵坐标加大的操作,用线段树容易维护 $(K,y)$ 最多往上跳到哪。但我们是不是要对上面两种转移得到的 $(K,y)$ 都执行下这种操作呢。想一想,其实只要转移第一种转移每段转移后得到的最大 $y$ (更小的 $y$ 要么不会增加新的可达点,要么新增的和最大的 $y$ 一样)和第二种的 $(K,z)$ 就好了(如果 $(K,z)$ 可达的话)。

但其实因为我们可能会增加新的纵坐标,所以上面的分析不充分。假如我们新增了 $(K,h)$ ,其中 $h$ 是以前没有出现过的纵坐标,找到在已经出现过的纵坐标中 $h$ 的前驱 $p$,如果 $(K,p)$ 可达且 $(K,p)$ 到 $(K,h)$ 的转移合法,那么可以扩展 $(K,h)$ 了。

具体算法看 std 效果更佳哦。

评论

暂无评论

发表评论

可以用@mike来提到mike这个用户,mike会被高亮显示。如果你真的想打“@”这个字符,请用“@@”。