CXOI R5 题解

A

提示 1

不同的左链链顶数量其实是路径上为其父亲右儿子的点数量加一。

提示 2

一个点不可能被操作两次。

正解

考虑算出交换每一个点对答案产生的价值变化量，按照其排序，贪心选取在一定次数以内的最大的一些整数就好了。

注意答案可能超过 int 范围。

B

提示 1

无法获取

n

具体的值，而变量位只有一个，意味着二分法等方法完全失效了，那应当采用什么方法呢？

正解

牛顿迭代可以解决此问题。

具体来说，我们取一个初始值

x

，根据牛顿迭代的式子：

x'\leftarrow x-\frac{f(x)}{f'(x)}

构造函数

f(x)=x^2-n

，那么：

x'\leftarrow x-\frac{x^2-n}{2x}

转化为计算器语言如下：

MR * MR - N / 2 / MR = M-

重复此过程若干次可以通过此题。

C

提示 1

不考虑权值的限制如何做？

提示 2

不考虑权值限制时，将排列划分成若干个升序连续段，则含有逆序对的区间表示出来是怎样的？有什么性质？

提示 3

权值的意义到底是什么？

提示 4

是否存在一种满足若干升序连续段的限制，且同时使得权值最优的构造？

正解

性质

1

：权值是最长下降子序列。证明如下：

考虑这样一种刻画方式：令 $f_i$ 表示当前长度为 $i$ 的下降子序列中，最后一个元素的最大值。初始 $f_i=-\infty$ 。每次加入一个元素 $x$ 后，考虑用其更新所有 $f_i$ ：若 $x>f_{i-1}$ ，不能更新；若 $x<f_{i-1}$ ，那么可以用 $x$ 更新 $f_i$ 。我们注意到 $f$ 是单调下降的，也就是说，实际上只有小于和大于交界处的那次更新是有用的，观察这个过程，发现这恰好和“删除 $S$ 中比它小的数中最大的数”相同，所以最后的 $|S|$ 就是最大的 $i$ 使得 $f_i\neq -\infty$ ，也就是最长下降子序列，于是证明成功了。

性质

2

：划分成若干个极长上升段（长度分别为

a_1,a_2,\dots,a_w

时，含有逆序对的区间个数为

\sum_{1\le i<j \le w}a_ia_j

。这个比较显然。由此我们发现，划分的连续段顺序是无所谓的。

性质

3

：构造

n-a_1+1\sim n,n-a_1-a_2+1\sim n-a_1\dots

这样的序列，既可以满足划分段的条件，也可以使得其在该划分段方案中最长下降子序列最短。这个也不难证明。

至此可以直接整数划分复杂度枚举方案，可以通过本题，也可以采用更优的 dp 做法，在此不做说明。

D

正解

（以下视

n,m,q

同阶）

一个强连通分量内的操作情况应当是相同的，所以先缩点。

此问题严格强于 DAG 可达性，因此复杂度不可能低于

O(\frac{n^2}w)

，直接考虑先 bitset 求出两点可达性。

接下来考虑如何求出

u

的点权，我们可以对于每个询问找到上一个涉及

u

的

1

操作在哪，将这次操作修改成的数和此次操作之后到询问位置所有涉及

u

的

2

操作所操作的数取 gcd，就可以得到当前的点权。

于是变为两个问题：

找上一个涉及 $u$ 的 $1$ 操作：考虑维护每个位置上一次 $1$ 操作的时刻，但是这个较难维护，于是将时间分块，维护到上一个整块结束时的答案，然后每次需要用到的时候在块内寻找是否有 $1$ 操作，然后一个块结束后暴力拓扑排序 $O(n)$ 更新即可，这部分总时间复杂度 $O(nB+\frac{n^2}B)$ 。
找一段时间区间涉及 $u$ 的 $2$ 操作的 gcd：同样对于时间分块，散块暴力，整块在块结尾拓扑排序更新，每次就可以直接查询，这部分总复杂度 $O(n(B+\log^2 V)+\frac{n^2\log V}B)$ 。

前面这个东西是这样的原因是，一个数不停取 gcd 只会有

\log V

次有用的更新。

（我也不知道分析的对不对，但是不会比这个大了）

然后并没有做完，因为

n^2

大小的 bitset 会爆空间，但是发现每次只需要查询某些点到块内点的可达性，于是到每个块给这个块求一个

nB

大小的 bitset 即可。

取

B=\sqrt{n\log V}

，得最优时间复杂度应不超过

O(\frac{n^2}w+n\sqrt{n\log V}+n\log^2 V)

。

文章操作

A

B

C

D

相关推荐

评论

CXOI R5 题解