题解 CF1059C 【Sequence Transformation】
ouuan
2018-10-06 13:46:59
考虑规模为 $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;
}
```