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

· · 题解

思路

不难发现，其实 p 函数就是 \text{popcount}，虽然没有什么意义。楼下很多大佬都直接看出性质了，由于本人太菜，所以给一个特别中规中矩的方法。

与别的方法不同，这个方法从 a 数组最后往最前遍历。

最开始也就是在 a_n 的时候，最优答案一定是 2^{a_n}-1。 对于 a_1 至 a_{n-1} 的情况，有几种可能：

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

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

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

代码

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