题解：P17127 [ICPC 2025 Shanghai R] Gemcrate

· · 题解

题意

给定 n 颗宝石，每颗宝石上写有一个正整数 a_i，需要将所有宝石划分为若干个非空组，每个组的亮度定义为组内所有宝石数值的异或和，整个划分方案的价值是所有组亮度的按位与结果，找出所有划分方案中能得到的最大价值。

思路

高位贪心枚举+异或线性基校验‌：

  1. 枚举‌：
    从第 60 位开始向低位逐位尝试，尽可能把每一位设为 1，构造候选掩码 x，判断是否存在合法的划分方案，使得所有组的亮度的按位与结果，在掩码 x 覆盖的二进制位上全部为 1。
  2. ‌校验规则‌：
    对于候选掩码 x，只保留所有 a_i 中和 x 按位与不为零的部分，就是把所有 a_i 截取为仅保留 x 中为 1 的二进制位。
  3. 剪枝‌：
    • 如果处理完所有元素后，有效元素个数为 0，直接返回不合法。
    • 如果所有截取后元素的异或和既不为 0，也不等于候选掩码 x，直接判定该候选掩码无法实现。
  4. 校验‌：
    将所有截取后的有效元素构建异或线性基，判断候选掩码 x 是否可以被线性基中的元素线性表出。
    如果可以表出，说明总有一种方案，让所有分组的亮度在掩码 x 的位上全部为 1 ，该候选掩码合法。

  5. 更新答案‌：
    如果当前候选掩码校验通过，我们就保留这一位的 1，继续向下一位枚举。
    遍历完所有 60 位后，最终得到的 ans 就是全局最大的可行价值。

    时间复杂度：

    ## 代码： ```cpp #include<bits/stdc++.h> using namespace std; typedef long long ll; int b[65]; bool check(ll n,vector<ll>& a) { if(!n)return 1; memset(b,0,sizeof b); ll s=0,c=0; bool f=0; // 第一遍遍历：截取候选掩码的有效位，快速做前置剪枝 for(ll i:a) { ll x=i&n; if(x) { s^=x; c++; } } if(!c||s&&s!=n)return 0; // 第二遍遍历：构建异或线性基 for(ll i:a) { ll x=i&n; if(!x)continue; f=1; for(int j=60;j>=0;j--) { if((x>>j)&1) { if(!b[j]) { b[j]=x; break; } x^=b[j]; } } } ll m=n; // 校验候选掩码是否可被线性基表出 for(int i=60;i>=0;i--) { if((m>>i)&1) { if(!b[i])return 0; m^=b[i]; } } return 1; } int main() { ios::sync_with_stdio(0); cin.tie(0);cout.tie(0); int T; cin>>T; while(T--) { int n; cin>>n; vector<ll>a(n); for(int i=0;i<n;i++)cin>>a[i]; ll ans=0; // 从最高位到最低位贪心枚举每一位是否可以为 1 for(int i=60;i>=0;i--) { ll x=ans|(1ll<<i); if (check(x,a))ans=x; } cout<<ans<<'\n'; } return 0; } ```