【AtCoder Regular Contest 084 E】Finite Encyclopedia of Integer Sequences | Mrsrz's blog

构造。

题目大意：

给定 $N,K$，假设所有长度为 $1\sim N$，每个位置的数是 $1\sim K$ 的数组有 $S$ 个，求字典序排名第 $\frac S 2$ 个的数组。

题解：

如果 $K$ 是偶数，则数组就是 $\frac K 2,K,K,K,\cdots$。

如果 $K$ 是奇数，则我们考虑一个数组 $b=\frac{K+1}{2},\frac{K+1}{2},\frac{K+1}{2},\cdots$。

考虑一个数组 $a$，令 $f(a)=\{K-a_1,K-a_2,K-a_3,\cdots\}$。

可以发现，一个 $a$ 和 $f(a)$ 唯一对应，且当 $a$ 不为 $b$ 的前缀时，$a$ 和 $f(a)$ 总是一个小于 $a$，一个大于 $a$。

我们不难得出最后 $b$ 的排名为 $\frac S 2+\frac N 2$。

往前暴力推 $\frac N 2$ 个位置即可。

Code：

#include<cstdio>
const int N=3e5+5;
int k,n,a[N];
int main(){
    scanf("%d%d",&k,&n);
    if(k&1){
        for(int i=1;i<=n;++i)a[i]=k+1>>1;
        for(int i=1,it=n;i<=n/2;++i){
            if(a[it]==0){
                --a[it-1];
                if(a[it-1]==0)--it;else{
                    for(int i=it;i<=n;++i)a[i]=k;
                    it=n;
                }
            }else --a[it];
        }
        for(int i=1;i<=n;++i)if(a[i])printf("%d ",a[i]);
    }else{
        printf("%d",k/2);
        for(int i=1;i<n;++i)printf(" %d",k);
    }
    return 0;
}