标签 构造 下的文章

题意:构造一个长度小于200的字符集为1到100的串,使它的全部非空子序列中恰好有n个为一个好串,其中好串为一个相同的串复制一遍接到后面得到的串。

考虑一个串$$p_1p_2...p_n 1 2 3 4 ... n$$,其中$$p_1p_2...p_n$$为一个排列,子序列中好串数量为排列的不下降子序列数
注意到在一个排列前加一个最大的数导致好串+1,在后面加导致*2

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n;
int cnt;
vector<int>q1,q2;
int main()
{
    //freopen("tt.in","r",stdin);
    scanf("%lld",&n);n++;
    int now=100;
    while(n!=1)
    {
        if(n&1)n--,q1.push_back(now--);
        else n>>=1,q2.push_back(now--);
        cnt++;
    }
    printf("%d\n",cnt*2);
    for(int i=0;i<q1.size();i++)printf("%d ",q1[i]);
    for(int i=q2.size()-1;i>=0;i--)printf("%d ",q2[i]);
    for(int i=now+1;i<=100;i++)printf("%d ",i);
    return 0;
}