专栏文章

题解：P14571 「LAOI-11」Ice Block

lliangliang517
P14571题解参与者 2已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@min2jekz
此快照首次捕获于
2025/12/01 19:31
3 个月前
此快照最后确认于
2025/12/01 19:31
3 个月前
查看原文

思路：

首先我们考虑 nn 为 2i−12^i-1 的情况，对于这种情况显然是需要构造一个这样的序列就可以了：20,21…2i−12^0,2^1 \dots 2^{i-1}。
那么对于多余的数怎么办呢？此时我们发现 mm 最大为 2⌊log⁡2(n)⌋+1−12^{\left \lfloor \log_{2}(n) \right \rfloor+1}-1，也就是将 nn 转为二进制下的是 00 的位全部变成 11。我们设这个二进制数的位数为 ll，那么对于多余的数我们可以使得它们为 2l−1,2l−2,2l−32^l-1,2^l-2,2^l-3 这样子从大到小排下去。
我们可以直接暴力计算出最少需要的数，可以证明得出来的数字的数量最多为 3838（当 nn 为 220−12^{20}-1 时可以使得数字的数量最多，也就是 3838 个）。

代码

CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...