题解 CF1059C 【Sequence Transformation】

ouuan

2018-10-06 13:46:59

Solution

考虑规模为 $k$ 的一个问题:$1$ ~ $k$ 的一个排列,求字典序最大的答案序列。 当 $k\le 3$ 时,就是样例;当 $k>3$ 时,为了使答案序列的字典序尽量大,需要删尽量少的数使得 $gcd\neq 1$,此时删掉所有奇数一定是最优的,因为对于任意的 $ k>3,x>2$ 有 $\small\left\lfloor\dfrac{k}{x}\right\rfloor<\left\lfloor\dfrac{k}{2}\right\rfloor$。删掉所有奇数后,剩下的数为都为 $2$ 的倍数(废话...),那么如果将所有数除以二,最优的删数方案是不会变的,而此时剩余的问题被转化成了一个规模为 $\small\left\lfloor\dfrac{k}{2}\right\rfloor$ 的原问题,输出答案时将答案乘二即可。 换句话说,令 $T(k)$ 为 $1,2,3,\cdots,k$ 这个序列的字典序最大的答案序列,那么:$\begin{cases}T(k)=\{1\}\quad(k=1)\\T(k)=\{1,2\}\quad(k=2)\\T(k)=\{1,1,3\}\quad(k=3)\\T(k)=\{1,1,\cdots,1\}(\small\text{共}\left\lceil\dfrac{k}{2}\right\rceil\text{个 1})\normalsize+T\left(\small\left\lfloor\dfrac{k}{2}\right\rfloor\right)\text{的每一项乘二}\normalsize\quad(k>3)\end{cases}$ 实现时并不需要递归地实现,详见代码: ``` #include <cstdio> #include <iostream> using namespace std; int n; int main() { int i,qaq=1; cin>>n; while (n>=4) { for (i=0;i<(n+1)/2;++i) { cout<<qaq<<' '; } n/=2; qaq*=2; } if (n==3) { printf("%d %d %d",qaq,qaq,qaq*3); } else if (n==2) { printf("%d %d",qaq,qaq*2); } else { printf("%d",qaq); } return 0; } ```