题解：P13617 [ICPC 2024 APC] Bit Counting Sequence

思路

不难发现，其实

p

函数就是

\text{popcount}

，虽然没有什么意义。楼下很多大佬都直接看出性质了，由于本人太菜，所以给一个特别中规中矩的方法。

与别的方法不同，这个方法从

a

数组最后往最前遍历。

最开始也就是在

a_n

的时候，最优答案一定是

2^{a_n}-1

。对于

a_1

至

a_{n-1}

的情况，有几种可能：

如果 $a_i$ 为 $0$ ，上一位答案为 $1$ 则可以减，否则无解。
如果 $a_{i+1}-a_i>1$ ，显然无解。因为发生进位 $1$ 的个数是不增的，而不发生进位 $1$ 的个数只能加 $1$ 。
如果 $a_{i+1}-a_i=1$ ，答案的最低二进制位一定为 $1$ ，我们直接看答案能不能减 $1$ 即可。
如果 $a_{i+1}-a_i \le 0$ ，一定发生了进位，且进位之后答案末尾只有 $a_i-a_{i+1}+1$ 个 $0$ 。我们只需在答案最末尾补齐 $0$ 然后看能不能减 $1$ 即可。

最后非常重要的：从头到位扫一遍，看看可不可以满足整个序列。

引用机房神犇 gaozeju 的话讲：检查满不满足原因就是假定序列是合法的，但是序列有可能不合法。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N(5e5+5);
int T,n,a[N];
ll ans;
inline int getpos(ll x){
	for(int d(0);x;){
		if(x&1)return d;
		x>>=1;
		++d;
	}return -1;
}
inline int cnt(ll x){
	int res(0);
	for(;x;x>>=1){
		if(x&1)++res;
	}return res;
}
inline void solve(){
	cin>>n;
	for(int i(1);i<=n;++i)cin>>a[i];
	ans=1;ans<<=a[n];--ans;
	for(int i(n-1);i>=1;--i){
		if(a[i]==0){
			if(ans==1)--ans;
			else{cout<<-1<<'\n';return ;}
		}else if(a[i+1]-a[i]>1){cout<<-1<<'\n';return ;}
		else if(a[i+1]-a[i]==1){
			if(ans>=1)--ans;
			else{cout<<-1<<'\n';return ;}
		}else{
			int pos=getpos(ans),chg=a[i]-a[i+1]+1;
			if(pos==-1){cout<<-1<<'\n';return ;}
			if(pos>chg){cout<<-1<<'\n';return ;}
			ans<<=(chg-pos);
			if(ans-1>=0)--ans;
			else{cout<<-1<<'\n';return ;}
		}
	}ll tmp=ans;
	for(int i(1);i<=n;++i){
		if(cnt(tmp)==a[i])++tmp;
		else{cout<<-1<<'\n';return ;}
	}cout<<ans<<'\n';
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>T;
	for(;T;--T)solve();
	return 0;
}

题解：P13617 [ICPC 2024 APC] Bit Counting Sequence

文章操作

思路

代码

相关推荐

评论

题解：P13617 [ICPC 2024 APC] Bit Counting Sequence