| by XianKa | No comments

【高斯消元】牛客19寒假R1C

链接:https://ac.nowcoder.com/acm/contest/317/C

来源:牛客网


题目要求有大小顺序,所以可以先把值在第一个最后一个之间的所有数筛选出来;

由于可以进行多次异或操作,所以数字集合也是有一个最大独立集的概念的(有一些数字可以由另一些数字异或得到)。异或是按位计算,所以对数字集合做一遍高斯消元,最多得到15个无关的数字。并且都是阶梯排列的。复杂度可以低到O(15*N)。

接下来可以暴力枚举一遍。但更好的方法是以每一位来看,从最高为到最低位,如果可以为1那么就变成1,否则只能不管。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e4;
int n;
int p[maxn];
vector<int> v;
int main()
{
    scanf("%d",&n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&p[i]);
    }
    if(n==1) {printf("%d",p[0]);return 0;}
    if(p[n-1]>=p[0]) {printf("-1"); return 0;}
    for(int i=1;i<n-1;i++)
    {
        if(p[i]>p[n-1] && p[i]<p[0]) v.push_back(p[i]);
    }
    int ans=p[0]^p[n-1];
    if(v.size())
    {
        for(int i=14,k=0;i>=0;i--)
        {
            for(int j=k;j<v.size();j++)
            {
                if(v[j]>>i & 1) 
                {
                    swap(v[j],v[k]);
                    break;
                }
            }
            if(v[k]>>i & 1)
            {  
                for(int j=k+1;j<v.size();j++)
                {
                    if(v[j]>>i && 1) v[j]^=v[k];
                }
                k++;
            }
        }
        for(int i=14,k=0;i>=0;i--)
        {
            if(v[k]>>i & 1)
            {
                if(!(ans>>i & 1)) ans^=v[k];
                k++;
            }
        }
    }
    printf("%d\n",ans);
}

 

发表评论