[CF2120C] Divine Tree

我们先考虑能构造出来的最小值和最大值。

先考虑最小值，由于 d(u)≥1d(u)\ge 1 天然成立，如果我们把 11 放到根，那么 d(u)=1d(u)=1，所以最小值就是 nn。

再考虑最大值，由于 d(u)d(u) 是 uu 到根上的编号最小值，那么 d(u)≤ud(u)\le u 一定成立，如果把 nn 放到根上，做一个菊花图，那么每一个 d(u)=ud(u)=u 就成立，所以最大值就是 ∑u=1nu=n(n+1)2\sum_{u=1}^n u=\cfrac{n(n+1)}{2}。

那我们接下来，对于给定的 mm，需要构造出恰好 ∑u=1nd(u)=m\sum_{u=1}^n d(u)=m，这怎么办？

自然地，从特殊的树形态入手，看一条链会怎么样。如果想让一条链是最小值 nn，只需要把 11 放到根上；如果想让它是最大值，那么需要从根到叶子按照 n,n−1,n−2,…,1n,n-1,n-2,\dots,1 的顺序排列。

考虑把 1,2,…,n1,2,\dots,n 进行重排，由于我们希望较少的元素会被影响，所以一个自然的想法是把 11 作为屏障来使用：

2,1,3,…,n↦n+13,1,2,…,n↦n+24,1,2,…,n↦n+3⋮n,1,2,…,n−1↦n+n−1n,2,1,3,…,n−1↦n+n−1+1n,3,1,2,…,n−1↦n+n−1+2\begin{aligned} 2,1,3,\dots,n&\mapsto n+1\\ 3,1,2,\dots,n&\mapsto n+2\\ 4,1,2,\dots,n&\mapsto n+3\\ &\vdots\\ n,1,2,\dots,n-1&\mapsto n+n-1\\ n,2,1,3,\dots, n-1&\mapsto n+n-1+1\\ n,3,1,2,\dots, n-1&\mapsto n+n-1+2 \end{aligned}

这样构造出来的方式的值一点点增加，所以按照这个想法做下去就可以了。

AC Code。

[CF1758C] Almost All Multiples

对于这种题目，首先的想法应该是如果没有他令的 p1=x,pn=1p_1=x,p_n=1 会怎么样？

很快就会发现，如果没有这个限制构造出来的一定就是 1,2,…,n1,2,\dots,n。

类比这个想法，如果第一项是 xx，那么 2∼x−12\sim x-1 的位置，一定就是 2,3,…,x−12,3,\dots,x-1，这是因为如果前面不放这些数，后面不可能能放这些数，所以它们的位置是定死的。

接下来考虑 xx 位置填什么。我们只要想一下如果填了 2x,3x2x,3x 等等，不妨设填的是 kxkx，接下来 x+1∼kx−1x+1\sim kx-1 的位置和 2∼x−12\sim x-1 类似，都是唯一固定好的，只能填 x+1,x+2,…,kx−1x+1,x+2,\dots,kx-1，然后 kxkx 面临的处境和之前一样。

问题是，什么时候是个头？我们知道每次填写的 kxkx 都要满足 ≤n\le n，只要它小于 nn 就会面临上面所说的相似的局面，并且下一次填的数一定比这一次更大，所以最终一定填的是 nn。

这样这个问题就被解决掉了，首先一定要 x∣nx\mid n，否则无解；令 d=xnd=\cfrac{x}{n}，那么每一次乘的都是 dd 的因子，我们取它最小的非平凡因子 ii，然后 d←d/id\gets d/i，显然这样生成的序列字典序是最小的。

AC Code。

[CF1761C] Set Construction

给定的矩阵可以看作邻接矩阵，那么它一定是一个 DAG，可以先进行一个拓扑排序，从末尾开始考虑。

我们希望，一个集合包含它所有的子孙，被它的祖先包含，同时又不能包含别的集合。

对于不能包含，只需要让每一个集合有一个独特的元素，然后处理包含关系的时候再并入这个元素就能做到了。

这样的话，如果 uu 不是 vv 的子孙，那么 uu 一定有一个独特的元素，并且 vv 没有，那么这里就没有包含关系。

具体地说，只要令每一个集合初始的时候加上自己的编号这个元素就可以做到这一点。

代码里用 int128 来二进制地表示一个集合。

AC Code。

[CF1733D1] Zero-One (Easy Version)

我们可以把 aa 与 bb 每一个位置异或一下，构造一个新的二进制串 A1,A2,…,AnA_1,A_2,\dots,A_n。

那么给定的操作就是选定两个 l,rl,r 并且翻转 Al,ArA_l,A_r，问将 AA 串变成全 00 需要的最小花费。

容易知道这个操作并不会改变 AA 串中 11 的数量的奇偶性，并且如果有偶数个 11，我总可以两两配对全部消掉。

因此可以将 AA 串变成全 00 当且仅当 11 的个数是偶数，设个数是 SS。

这个版本的题目中，保证了 x≥yx\ge y，即如果能隔项消除，我们一定不会邻项消除。

所以，如果 S≥4S\ge 4，直接交叉着消即可。

为什么？原因是，假设有 SS 个 11，那么消除它们至少需要 S2\cfrac{S}{2} 步，每一步的费用至少是 yy，而我们交叉消的费用就是 S2y\cfrac{S}{2}y，所以这就是最小花费。

如果 S=2S=2，比较一下邻项消除和借助一个隔着的节点消的费用即可；如果 S=0S=0 自然输出 00。

AC Code。

[CF1733D2] Zero-One (Hard Version)

如果 x≥yx\ge y，直接复用上个题目的代码即可，下面我们考虑 x<yx<y 的情况。

此时我们不能直接构造出一个最小花费了，所以我们重新审视这个抽象出来的数学模型。

我们最终的目的是让 AA 变成全 00，每一次操作有可能让 11 的个数 SS 进行 +2,0,−2+2,0,-2。

执行 +2+2 的操作一定是不优的，所以我们真正执行的只有 00 和 −2-2，并且最后一步一定是 −2-2。

那么 SS 的变化序列可能如下：0,0,−2,0,0,−2,−2,0,…,−20,0,-2,0,0,-2,-2,0,\dots,-2。

我们把连续的 00 和 −2-2 放到一起看，这一定是连续若干次邻项消除。为什么？因为如果这些次数有隔项消除，花费是 mx+nymx+ny，不如直接一步到位地一个 yy 消掉两个 11。

如果 −2-2 前面没有 00，那么是一次邻项消除或者一次隔项消除。

所以这样分析下来，我们选择了 S2\cfrac{S}{2} 对 11，进行若干次邻项消除（花费 LxLx，其中 LL 是这对 11 的距离），或者一次隔项消除（花费 yy）。

对于此类数轴模型，通常将匹配的点对视作线段，并考察线段间的几何关系：

  1. 相交但不包含，如 (p,q)(p,q) 和 (a,b)(a,b) 构成 p<a<q<bp<a<q<b，那么我们可以构造出 (p,a)(p,a) 和 (q,b)(q,b) 这两个配对，原始花费一定不会比得到的花费更优。

  2. 嵌套关系：

    • 如果外层使用了若干次邻项消除，说明外层的长度 LL 使得 Lx≤yLx\le y，那么内层长度比 LL 小，它们也都会选择若干次邻项消除，此时花费与距离的和成正比。

      我们可以构造说明一定不会嵌套：这些点按照最近的点两两配对，这样的所有距离之和小于原先最外层一个线段的距离，这样一定比嵌套结构更优。

    • 如果外层使用隔项消除，那么内层如果使用隔项消除，可以将这四个点重新分配成不相交的线段，这样的花费与原先相等；

      如果内层使用若干次邻项消除，根据上文，内层不能再嵌套内层了。

综上所述，最优解如果有嵌套，至多只会嵌套一层，并且外层是隔项，内层是邻项。

我们给 dpdp 加一个状态 0/10/1 表示在最外层或一个线段的内层，那么转移就是：

  1. 最外层邻项消除：dp(i,0)←dp(i−2,0)+x(pi−pi−2)dp(i,0)\gets dp(i-2,0) + x(p_i-p_{i-2})
  2. 关闭一个开放的线段：dp(i,0)←dp(i−1,1)+ydp(i,0)\gets dp(i-1,1)+y
  3. 进入一个线段内部：dp(i,1)←dp(i−1,0)dp(i,1)\gets dp(i-1,0)
  4. 一个线段内部的邻项消除：dp(i,1)←dp(i−2,1)+x(pi−pi−2)dp(i,1)\gets dp(i-2,1)+x(p_i-p_{i-2})

AC Code。

[CF2145D] Inversion Value of a Permutation

注意 inversion value 的定义，它是存在逆序对的 subsegment 的数量，并非逆序对的数量。

存在性的数数一般都不是很好做，我们可以看它的反面，那就是不存在逆序对的 subsegment 的数量，现在我们统计这种 (l,r)(l,r) 的数量。

不存在逆序对，那就是一段 (l,r)(l,r) 满足 al<al+1<⋯<ara_l<a_{l+1}<\cdots<a_r。

很自然地，我们可以对每个满足要求的 (l,r)(l,r) 尽可能向左右延，直到不能延为止。

对于这样一个极大的 (l,r)(l,r)，假设它的长度是 L=r−l+1L=r-l+1，那么它对我们要统计的数量的贡献是 (L2)\binom{L}{2}。

显然，任何一个序列，都是一堆这种极大的 (l,r)(l,r) 拼在一起的。因为你无论如何都能把这个序列划分成若干个极大的首尾相接的 (l,r)(l,r)，并且每一个极大的 (l,r)(l,r) 都是孤立的，即整个序列的贡献就是每一段的贡献之和。

因此，现在的问题就转化成了，我们需要构造一组 L1,L2,…,LkL_1,L_2,\dots,L_k 满足 ∑Li=n\sum L_i=n 且 ∑(Li2)=(n2)−k\sum \binom{L_i}{2}=\binom{n}{2}-k。

设 dpi,j,kdp_{i,j,k} 表示考虑 LL 的值为前 ii 个数，∑L=j\sum L=j，∑(L2)=k\sum\binom{L}{2}=k 是否存在，并且需要记录 prei,j,kpre_{i,j,k} 表示当前状态从哪个状态转移过来。

转移的话，枚举 l≥0l\ge 0 个 i+1i+1，会有 dpi+1,j+l(i+1),k+l(i+12)←dpi,j,kdp_{i+1,j+l(i+1),k+l\binom{i+1}{2}}\gets dp_{i,j,k}

最终构造只要从 n−L+1,n−L+2,…,nn-L+1,n-L+2,\dots,n 这样入手就行了。

AC Code。