简介
一大堆毒瘤构造题中夹杂着几道其他题目……
题目
CF1348D Phoenix and Science
Description
Solution
考虑最快情况，即 \(1 \rightarrow 2 \rightarrow 4 \rightarrow 8 ····\)
但是我们发现如果前期分裂太多，后面可能会出现不可控的情况，即超出题目要求达到的数量，所以我们在前期合适的位置要控制一下。
那么是在哪里呢?
我们把 \(n\) 减去 2 的幂的前缀和之后的数放到 2 的幂数组中比它小的最大的数的位置后面即可。
只看文字不好理解，结合代码理解一下吧。
点击查看代码
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int T, n;
int a[50], cnt;
int main(){
scanf("%d", &T);
while(T--){
int tmp = 1;
cnt = 0;
scanf("%d", &n);
while(n > 0){
a[++cnt] = n > tmp ? tmp : n;
n -= tmp;
tmp <<= 1;
}
sort(a + 1, a + 1 + cnt);
printf("%d\n", cnt - 1);
for(int i = 2; i <= cnt; ++i)
printf("%d ", a[i] - a[i - 1]);
puts("");
}
return 0;
}
CF1348B Phoenix and Beauty
Description
Solution
emm……一开始没什么思路，去看样例。
发现第 4 组数据可以直接输出原数组的啊，为啥样例要输出这么多？
然后就发现样例输出在输出一个有循环节的数字串，那是不是可以推广一下？
确实是可以的。
不难发现，如果原数组中的不同数字的个数大于 \(k\)，那显然是无解的，直接输出-1。
接着我们尝试构造循环节，发现构造一个长度为 \(k\)，只包含不同数字（每个数字只出现一次），且包含原数组中所有不同数字的数组，把它当作循环节，然后直接循环输出 \(n\) 遍即可。
\(n,k \leq 100\)，所以 \(n \times k \leq 10000\)，符合条件。
CF1304D Shortest and Longest LIS
Description
Solution
题目要求我们构造符合条件的最长和最短的 \(LIS\)。
既然要最长和最短的，我们就先构造出来。
-
对于最长的：构造一个 \(1 \sim n\) 的序列。
-
对于最短的：构造一个 \(n \sim 1\) 的序列
然后我们按照题意把不合法的段取个反即可。
CF1312E Array Shrinking
Description
Solution
题意比较迷，主要是刚开始把 两步操作 看成了 两种操作 QwQ。
那么题意大概就是你可以选择两个相邻的且相同的数合并，合并后的权值是原本权值 +1。
蒟蒻一开始想了半天都构造，结果没想出来/kk。
看了一眼题解之后，哦，原来是区间 \(dp\) 啊，那没事了（做构造做魔怔了属于是）。
设 \(dp_{i,j}\) 表示区间 \([i,j]\) 最少能合并成几个数，转移方程显然：
\[dp_{i, j} = dp_{i,k} + dp_{k + 1, j} \]再记录一个数组 \(f_{i,j}\) 表示区间 \([i,j]\) 合并之后的数是多少。
如果 \(dp_{i,k}\) 和 \(dp_{k + 1, j}\) 都是 1，且 \(f_{i,k} = f_{k + 1, j}\)，那么 \(dp_{i,j} = 1\)，同时 \(f_{i,j} = f_{i,k} + 1\) 即可。
CF1110E Magic Stones
Description
Solution
神仙结论题，当然还是要推一下的。
我们对 \(c_i\) 做一个差分，\(a_i = c_{i + 1} - c_i\)，\(a_{i + 1} = c_{i + 2} - c_{i + 1}\)。
那么对于 \(c_i\) 的一次操作之后：
\[c_i' = c_{i + 1} + c_{i - 1} - c_i \]\(a_i\) 和 \(a_{i + 1}\) 就变成了：
\[a_i = c_{i + 1} - (c_{i + 1} + c_{i - 1} - c_i) \] \[a_{i + 1} = c_{i + 2} - (c_{i + 2} + c_{i} - c_{i + 1}) \]开一下括号，就变成了……
\[a_i = c_i - c_{i - 1} \] \[a_{i + 1} = c_{i + 1} - c_i \]惊不惊喜？意不意外？
没错，我们只要判断 \(c\) 数组和 \(t\) 数组的差分数组排完序之后是否一样就行了。
CF1110C Meaningless Operations
Description
Solution
神仙打表找结论题。
就是打表，暴力计算每一个数的答案。
打完表发现对于 \(2^{i - 1} < x < 2^i - 1\) 答案就是 \(2^i - 1\)。
对于 \(x = 2^i - 1\)，提前把答案表打出来，询问的时候直接输出即可（似乎有个式子可以直接算出来，但我没去推）。
CF540C Ice Cave
Description
Solution
混在构造题里的搜索……
爆搜就完了，没什么好说的。
实在不会的话，详见博客CF540C Ice Cave 题解 - xixike - 博客园 (cnblogs.com)
CF989C A Mist of Florescence
Description
Solution
一开始想的是 \(A,B,C,D\) 交叉放，但是很难写……
然后发现可以直接构造一个 \(40 \times 50\) 的矩阵，每个字母 10 行。
然后把当前字母插入到上一个字母形成的矩阵中即可。
例如：
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
假设 B需要 5 个联通块，那么就插成这样：
ABABABABAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
由于数据范围允许，我们可以插一行跳一行，还好写一点，具体来讲：
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
AAAAAAAAAA
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
假设B需要 7 个联通块，那么：
ABABABABAB
AAAAAAAAAA
ABAAAAAAAA
AAAAAAAAAA
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
BBBBBBBBBB
注意：第 3 行第 2 列变成了 B。
J - Beauty Of Unimodal Sequence
这题洛谷上没有，而且也还不会做，咕咕咕了。