题解：P14571 「LAOI-11」Ice Block

liangliang517 · 2025-11-23 09:51:54 · 题解

思路：

首先我们考虑 n 为 2^i-1 的情况，对于这种情况显然是需要构造一个这样的序列就可以了：2^0,2^1 \dots 2^{i-1}。

那么对于多余的数怎么办呢？此时我们发现 m 最大为 2^{\left \lfloor \log_{2}(n) \right \rfloor+1}-1，也就是将 n 转为二进制下的是 0 的位全部变成 1。我们设这个二进制数的位数为 l，那么对于多余的数我们可以使得它们为 2^l-1,2^l-2,2^l-3 这样子从大到小排下去。

我们可以直接暴力计算出最少需要的数，可以证明得出来的数字的数量最多为 38（当 n 为 2^{20}-1 时可以使得数字的数量最多，也就是 38 个）。

代码

#include<bits/stdc++.h>
using namespace std;
long long t,n,m,l,l2,num,ans,flag,a[1100010],b[1100010],c[1100010];
vector<long long> v;
int main(  ){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>t;
    while(t--){
        cin>>n;
        l=1;
        while(l<=n){
            l*=2;
        }
        l2=l/2;
        l--,l2--;
        num=1,ans=0;
        for(int i=1;i<=l2;i++){
            if(a[i]==0){
                c[++ans]=i;
                for(int j=1;j<=num;j++){
                    if(a[b[j]|i]==0){
                        v.push_back(b[j]|i);
                        a[b[j]|i]=1;
                    }
                }
                for(int j=0;j<v.size( );j++){
                    b[++num]=v[j];
                }
                v.clear( );
            }
        }
        for(int i=l-n+l2+1;i<=l;i++){
            if(a[i]==0){
                c[++ans]=i;
                for(int j=1;j<=num;j++){
                    if(a[b[j]|i]==0){
                        v.push_back(b[j]|i);
                        a[b[j]|i]=1;
                    }
                }
                for(int j=0;j<v.size( );j++){
                    b[++num]=v[j];
                }
                v.clear( );
            }
        }
        cout<<ans<<endl;
        for(int i=1;i<=ans;i++){
            cout<<c[i]<<" ";
        }
        cout<<endl;
        for(int i=1;i<=l;i++){
            a[i]=0;
        }
    }
    return 0;
}