Question

输入一个n，要求如下：

  • 每个字符串由 0 和 1 组成。
  • 每个字符串长度在 1 到 n 之间，且两两长度不同。
  • 集合中任何一个字符串都不是其他字符串的子串。

输出字符串的个数，然后输出字符串。

Solution

简单构造：特判1,2，其余按00，010,0110,01110，...

Code

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int>P;
const double eps = 1e-8;
const int NINF = 0xc0c0c0c0;
const int INF  = 0x3f3f3f3f;
const ll  mod  = 1e9 + 7;
const ll  maxn = 1e6 + 5;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;cin>>n;
    if(n==1){
        cout<<1<<'\n'<<1<<'\n';
    }
    else if(n==2){
        cout<<2<<'\n'<<0<<'\n'<<11<<'\n';
    }
    else{
        cout<<n-1<<'\n';
        for(int i=2;i<=n;i++){
            for(int j=1;j<=i;j++){
                if(j==1) cout<<0;
                else if(j==i) cout<<0;
                else cout<<1;
            }
            cout<<'\n';
        }
    }
    return 0;
}