CF1942

A

构造一个长度为 \(n\) 的数组，使得它的 \(n\) 个循环右移中，恰好有 \(k\) 个是升序排序的。或判断不存在。

如果 \(k=1\)，输出 1 2 3 ... n；如果 \(k=n\)，输出 \(n\) 个 \(1\)。否则不存在满足要求的数组。

B

有一个 \(0\sim n-1\) 的排列 \(p\)。令 \(a_i=mex(p_1\sim p_i)-p_i\)。给定 \(a_i\)，构造一个 \(p\) 满足 \(a\) 的限制。

注意到 \(a_n=n-p_n\)，所以可以求出 \(p_n\)，然后一路往小推过去。

C1

有一个正 \(n\) 边形，给定了 \(x\) 个点。在这 \(x\) 个点之间任意连若干条不相交的线，会把多边形分成若干块。问最多分成多少个三角形。

只考虑这 \(x\) 个点构成的 \(x\) 边形。

以这种方式切分一定是最优解。能分出 \(x-2\) 个三角形。

所以答案就是 \(x-2+\text{原本就被割出来的三角形个数}\)。

C2

相较于 C1，我们可以额外选择 \(y\) 个点加入原来的 \(x\) 个点中（变成在这 \(x+y\) 个点间连边）。问此时最多分成多少个三角形。

考虑原本两个关键点之间的距离 \(d\)。如果 \(d=2\)，一开始就累加进答案；如果 \(d=1\)，跳过，都没有能连的地方。

1. \(d=2k(k>1)\)。一个隔一个标记，标记 \(x\) 个贡献 \(2x\)。如果 \(x=k\)，额外贡献 \(1\)。

2. \(d=2k+1\)。同上，但是无额外贡献。

综上，前一种情况更优。把所有 \(d_i\) 按奇偶性分成两组，分别从小到大排序，贪心地先选偶数再选奇数，可以证明是最优的。

D

有 \(n\) 个格子，编号为 \(1\sim n\)，初始时都是无色的，你可以对其中一些格子进行染色。

给定一个 \(n\times n\) 的矩阵 \(a_{i,j}\) 中 \(i\le j\) 的部分，一个染色方案的权值定义为：若该染色方案中被染色的块编号的集合等于 \(\displaystyle\bigcup_{i=1}^{m} [l_i,r_i]\)，其中 \(l_m\le r_m,\forall 1\le i<m,l_i\le r_i<l_{i+1}-1\)，则该方案的权值为 \(\displaystyle\sum_{i=1}^{m} a_{l_i,r_i}\)。求所有 \(2^n\) 种染色方案中权值前 \(k\) 大的值。每个测试点 \(t\) 组测试用例。

这个题一看就很像动态规划，但是有一个前 \(k\) 大，我们不是很好处理，所以我们考虑设 \(f_i\) 为前 \(i\) 格能获得的前 \(k\) 大权值，也就是每个状态是一个数组。

转移的时候就是从 \(f_{1\sim i-1}\) 的数组中取出最大的 \(k\) 个。于是这个题就变成序列合并。复杂度 \(O(nk\log n)\)。时限是 \(4.5s\) 可以通过。