筱玛爱游戏——线性基

链接:https://ac.nowcoder.com/acm/contest/946/E
来源:牛客网-----------------------------------------------------------------------------------------------

题解:
  一.首先得先学“线性基”。
    不知道的可以不用往下看了。
   
这里只说下要用到的关于“线性基”的性质:线性基集合中的任何子集的异或和都不会为0
  
   
二.如果 插入的这个数的二进制 第i位 为 1,而 线性基集合 的二进制位数刚好没有 第 i 位,
     则说明该数可以选,并且不会使得线性基集合子集

     异或和 位 0 的情况出现。我们就可以统计一下有多少个数可以选的,然后根据可选个数判断奇偶性就可以知道是先手还是后手赢了。
//#pragma comment(linker, "/STACK:1024000000,1024000000")
//#pragma GCC optimize(2)
//#include <bits/stdc++.h>
#include <algorithm>
#include <iostream>
#include<sstream>
#include<iterator>
#include<cstring>
#include<string>
#include<cstdio>
#include<cctype>
#include<vector>
#include<deque>
#include<queue>
#include<stack>
#include<map>
#include<list>
#include<set>

using namespace std;
typedef double dou;
typedef long long ll;
typedef pair<int, int> pii;

#define pai acos(-1.0)
#define M 200005
#define inf 1e18
#define mod 1000000007
#define left k<<1
#define right k<<1|1
#define W(a) while(a)  
#define ms(a,b) memset(a,b,sizeof(a))

ll num[M];
ll ans, n, m, t;

int insert(ll x)
{
    for (int i = 61; i >= 0; i--)
    {
        if (x >> i & 1)
        {
            if (!num[i])//如果线性基二进制中没有这一位,那就是可以选这个数
            {
                num[i] = x;
                return 1;//可选数+1
            }
            x ^= num[i];
        }
    }
    return 0;//如果这个数的每一位都和线性基二进制重合,那么就是不可以选的
}

int main()
{
    ios::sync_with_stdio(false);
    cin >> n;
    for (int i = 1; i <= n; i++)
    {
        cin >> t;
        ans+=insert(t);//插入线性基
    }
    if (ans&1)    cout << "First" << endl;
    else    cout << "Second" << endl;
    
    return 0;
}


全部评论

相关推荐

点赞 收藏 评论
分享
牛客网
牛客企业服务