SG函数

参考博客
参考博客
题目链接

#include<stdio.h>
#include<stdlib.h>
#include<algorithm>
#include<string.h>
//#define ll long long 
#define MAXN 100010
#define INF 0X3f3f3f3f
#include<iostream>
#include<vector>
#include<stack>
#include<bits/stdc++.h>
typedef long long ll;
const ll mod=1000000007;
const ll inf=1e18;
using namespace std;
int n,m,k,t;

int X[MAXN];/*
int sg[MAXN];
int mex1(int x){
	//k是奇数
	if(sg[x]!=-1)return sg[x];
	if(x==0) return sg[x]=0;
	if(x==1) return sg[x]=1;
	int vis[100]={0};
	vis[mex1(x-1)]=1;
	if(x%2==0)vis[mex1(x/2)]=1;
	for(int i=0;;i++){
		if(!vis[i])return sg[x]=i;
	}	
} 

int mex2(int x){
	//k是偶数 
	if(sg[x]!=-1)return sg[x];
	if(x==0) return sg[x]=0;
	if(x==1) return sg[x]=1;
	int vis[100]={0};
	vis[mex1(x-1)]=1;
	if(x%2==0)vis[0]=1;
	for(int i=0;;i++){
		if(!vis[i])return sg[x]=i;
	}
	
}*/

int mex1(int x){
	if(x<=4){
		if(x&1)return 1;
		if(x==2)return 0;
		return 2;
	}
	else if(x&1)return 0;
	int temp=mex1(x/2);
	if(temp==1)return 2;
	return 1;
}

int mex2(int x){
	if(x<=2)return x;
	else if(x&1) return 0;
	else return 1;
}

int main(){
	std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int a,b;
//	memset(sg,-1,sizeof(sg));
//	memset(sg,-1,sizeof(sg2));
//	for(int i=0;i<=100;i++)cout << "i=" << i << " " << mex2(i) << "\n";
	cin >> n >> k;
	for(int i=1;i<=n;i++){
		cin >> X[i];
	}
	if(k&1){
		int ans=0;
		for(int i=1;i<=n;i++){
			ans^=mex1(X[i]);
		}
		if(ans!=0)cout << "Kevin";
		else cout <<"Nicky";
	}
	else{
		int ans=0;
		for(int i=1;i<=n;i++){
			ans^=mex2(X[i]);
		}
		if(ans!=0)cout << "Kevin";
		else cout <<"Nicky";
	}
	//cin >> n >> a >> b;	
}	 

本文地址：https://blog.csdn.net/weixin_45826833/article/details/107581543