2022/07/14 做题记录

Posted on 2022-07-14 Disqus:

模拟赛 T2

http://47.92.197.167:5283/contest/236/problem/2

发现一次行走中按的编号最大的按钮只会被按一次（赛时想到了这一点但并没有想到可以用这个来转移 dp），于是设 dp[i][j][k] 表示从 j走到 k ，按下的按钮编号小于等于 i 的方案数，dp[i] 首先加上 dp[i-1]，之后只需要考虑按下的最大按钮编号恰好为 i 的方案数，这个按钮只会被按一次，于是枚举在哪个点 p 按的，记 out[q] 为从 q 走到 p，按下的按钮编号小于 i 的方案数，容易直接枚举统计，注意要给 out[p] 加上 1，因为可以直接从 p 这个点开始，前面不接路径，in[q] 同理，之后可以枚举 p,q 更新 dp 数组。

但是我们还要处理每个询问钦定的第一次和最后一次按什么，可以新建 q 个结点，认为 out[x] 的含义是在从 x 到 p ，且允许在 p 这个节点按 i 按钮的方案数（in[x] 同理），这样可以比较方便的对于每一个询问特殊处理，让 q 向询问起点，询问终点向 q 转移，于是把每个询问转化成一条从新建结点开始，到新建结点结束的回路，时间复杂度 $\mathrm{O}(n^4)$ 。

code: http://47.92.197.167:5283/submission/101045

AGC048E

https://atcoder.jp/contests/agc048/tasks/agc048_e

设 $c_i = a_i + T*b_i$

可以发现 $c_1=a_1$ ，于是下面可能混用。

对于一个 a 序列，假设给出一个 b 序列的前缀，一定存在一个完整的 b 序列字典序大于它

考虑归纳证明，假设对于任意一个前缀都能填前 i-1 位，考虑第 i 位，设 f(x) 表示下一个填 x，的时候， $\sum_{j=1}^{i-1} [c_j<c_i]$ ，发现 $f(0) \ge 0$ ，当 x 取足够大时一定有 $f(x)=i-1$ ,即 $f(x)<x$ ，首先证明下面这个结论

任意两个 $c_i$ 不可能相等

考虑如果两个 $c_i$ 相等，将 i 较大的那一个的 $b_i$ 增加 1，根据归纳假设可以证明一定有一种填到第 i-1 位的方法，于是可以得到一个字典序更大的前 i-1 位的填法。

于是 x 每增加 1 ， $f(x)$ 的变化量小于等于 1，于是一定存在一个 x 使得 $f(x)=x$ ，这个 x 就是下一位的 $b_i$ 。

对于任何一个最优解的 c 序列， $(c_1-T,c_1]$ 中除了 $c_1$ 不会有其它的数

如果存在的话，找到 $i$ 最小的一个，将其 $b_i$ 加 1，可以发现依然合法，将后面填完之后这个 b 序列一定比原 b 序列字典序大。

对于任何一个最优解，删除下标 1，并将所有满足 $c_i > c_1$ 的 $b_i$ 减 1，仍是一个最优解

由于上述性质，删除之后 $c_i$ 的大小关系不会改变，于是这个 b 序列一定合法，且无法通过任何方式增大字典序（因为不改变任何一个数与 $c_1$ 的大小关系显然是不可能的（因为这样在原序列也可以进行相同的操作），而通过加上 $x*T$ 使得一个数从左边到右边能使答案更优的话，在原序列中加上 $(x+1)*T$ 也一定合法，于是也不可能）。

上面这条性质实际上是在说每一个最优解都可以通过后缀的最优解生成。

因为这些性质的存在，所以每一个最优的 b 序列都可以通过一个只包含下标 2~n 的最优 b 序列以如下方法生成：

在 b 序列开头添加 0
对于 $c_i > a_1-T (i>1)$ ，给 $b_i$ 加 1

发现 $b_x$ 只与当前的 $c_x$ ，当前插入的 $a_i$ ,与插入前的 $b_x'$ 有关，其中 $c_x$ 可以用 $b_x'*T +a_x$ 计算。

于是枚举 $x,a_x$ ,设 dp[i][j] 表示当前插入了下标 i~x 的数， $b_x$ 当前为 j 的方案数。

最后还要考虑下标为 i+1~n 的数，显然对于每一种填法使后面字典序最大的填法有且仅有一种，于是乘 $k^{n-x}$ 即可。

时间复杂度 $\mathrm{O}(n^5)$

code : https://atcoder.jp/contests/agc048/submissions/33222729