题解：P17247 【Gensokyo OI Round 2】奇迹的诅咒

· · 题解

位运算题。

Problem.

给定序列 a_1,a_2,......,a_n，定义划分 k（1\le k<n）的价值为前 k 个数按位或的值与后 n-k 个数按位与的值相等时的这个公共值，若不等则价值为 -1。序列的价值为所有划分价值的最大值。允许进行任意次操作：选择 x<y，将 a_x 改为 a_x \operatorname{and} a_y，a_y 改为 a_x \operatorname{or} a_y（操作后原 a_x,a_y 的二进制位不变，只是 1 的位置移动）。求操作后序列价值的最大值。

Solution.

显然的，对于任何二进制位，操作不会改变该位上 1 的总数，只可能把 1 从左边移到右边。

设第 i 位 1 的个数为 \text{cnt}_i，后缀长度为 m=n-k。

若划分合法，则对每一位 i：

因此，当且仅当不存在 i 使得 \text{cnt}_i=m 时，该划分才可能合法。此时价值为所有 \text{cnt}_i > m 的位的或。

注意到合法的 m 必须满足 1 \le m \le n-1 且 m \notin \{\text{cnt}_i\}，价值随 m 增大单调不增，所以取最小的合法 m 即可。

若不存在这样的 m，输出 -1。

时间复杂度 \Omicron(\sum n \log \max\{a_i\})，实际跑得飞快。

:::info[代码]

#include<bits/stdc++.h>
#define BUF 1<<20
#define IL inline
#define ll long long
#define ri register int
#define F(i,a,b) for(ri i=a;i<=b;i++)
#define FF(i,a,b) for(ri i=b;i>=a;i--)
#define u64 uint64_t
#define ull unsigned long long
#define i128 __int128
#define vec vector
#define vi vector<int>
#define vll vector<ll>
#define vb vector<bool>
#define prq priority_queue
#define pii pair<int,int>
#define pill pair<int,ll>
#define plli pair<ll,int>
#define um unordered_map
#define mii map<int,int>
#define us unordered_set
#define pb(x) push_back(x)
#define fi first
#define se second
#define fr() front()
#define bk() back()
#define beg() begin()
#define Fill(a,b) memset(a,b,sizeof(a))
using namespace std;
const int N=50;
const ll inf=0x3f3f3f3f3f3f3f3fLL;
const double eps=1e-9;
char buf[BUF],*p1=buf,*p2=buf;
#define getchar_unlocked() ((p1==p2)&&(p2=(p1=buf)+fread(buf,1,BUF,stdin),p1==p2)?EOF:*p1++)
int T,n,x,b,t,cnt[N],ans;
IL int read(){
    int k=0,f=1;
    char c=getchar_unlocked();
    while(c<'0'||c>'9'){
        if(c=='-') f=-1;
        c=getchar_unlocked();
    }
    while(c>='0'&&c<='9') k=k*10+c-'0',c=getchar_unlocked();
    return k*f;
}
IL void write(int x){
    if(x<0) putchar('-'),x=-x;
    if(x<10) putchar(x+'0');
    else write(x/10),putchar(x%10+'0');
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
//  freopen(".in","r",stdin);
//  freopen(".out","w",stdout);
    T=read();
    while(T--){
        ans=0,t=-1,Fill(cnt,0);
        n=read();
        F(i,1,n){
            x=read();
            while(x){
                b=__builtin_ctz(x);
                cnt[b]++;
                x&=(x-1);
            }
        }
        F(i,1,n-1){
            bool fl=1;
            F(b,0,30){
                if(cnt[b]==i){
                    fl=0;
                    break;
                }
            }
            if(fl){
                t=i;
                break;
            }
        }
        if(t==-1){
            write(-1);
            putchar('\n');
            continue;
        }
        F(i,0,30){
            if(cnt[i]>t) ans|=(1<<i);
        }
        write(ans);
        putchar('\n');
    }
    return 0;
}

:::