AT2363 [AGC012C] Tautonym Puzzle

louhao088 · 2021-09-25 19:44:26 · 题解

一道好的构造题。

由于是子序列相同，只要顺序相同出现两次就可以。

由于最长 200，我们先放前 100 个为 1 \to 100。

这样题目就变为，怎样满足 一个序列有 N 个严格上升子序列。

这个很容易构造，我们倒着先摆所有偶数（只要隔两个摆就可以，倒着是为了防止多算）。

结合二进制，如果第 x 位是 1 ，那只要放 x \times 2+1 前面必然有 x 个比他小，方案数增加 2^x 次。这样构造必然可以。（这个要从高位到低位）

（至今也没有想通，此题的 spj 是怎么写的）。

#include<bits/stdc++.h>
using namespace std;
//static char buf[1000000],*p1=buf,*p2=buf;
//#define getchar() p1==p2&&(p2=(p1=buf)+fread(buf,1,1000000,stdin),p1==p2)?EOF:*p1++
#define re register
#define int long long
const int maxn=1e5+5,M=34005;
inline int read()
{
    char ch=getchar();bool f=0;int x=0;
    for(;!isdigit(ch);ch=getchar())if(ch=='-')f=1;
    for(;isdigit(ch);ch=getchar())x=(x<<1)+(x<<3)+(ch^48);
    if(f==1)x=-x;return x;
}
inline void print(int x)
{
    static int a[55];int top=0;
    if(x<0) putchar('-'),x=-x;
    do{a[top++]=x%10,x/=10;}while(x);
    while(top) putchar(a[--top]+48);
}
int n,m,a[maxn],t=0,b[maxn],ans;
signed main()
{
    //freopen(".in","r",stdin);
    //freopen(".out","w",stdout);
    n=read();int x=n;
    for(int i=1;i<=100;i++)b[++ans]=i;t=0;
    while(x>=pow(2,t+1)-1ll)t++;
    for(int i=1;i<=t;i++)b[++ans]=i*2;n=n-pow(2,t)+1ll;
    for(int i=t;i>=1;i--)if(n&(1ll<<(i-1)))b[++ans]=i*2-1;
    cout<<ans<<endl;
    for(int i=1;i<=ans;i++)printf("%d ",b[i]);
    return 0;
}