bzoj1391 [CEOI2008]knights

every-SG:必胜或必败由步数最长的状态决定。

sg函数和步数打个表找找规律什么的。。。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;

const int MAXN=2e5+5;

const int d[4][2]={{-2,+1},{-2,-1},{-1,-2},{+1,-2}};

int k,n;

inline bool isMove(int x,int y){
	if(x<1||x>n)return 0;
	if(y<1||y>n)return 0;
	return 1;
}

inline int sg(int x,int y){
	if((x%4==1||x%4==2)&&(y%4==1||y%4==2))return 0;
   	if(n%4==1&&((x==n&&y!=n-1)||(y==n&&x!=n-1)))return 0;
    if(n%4==0&&x==n&&y==n)return 0;
	return 1;
}

inline int dis(int x,int y){
	if(!sg(x,y)){
		if(x==n||y==n)return (x+y-2)/4*2;
		return (x+y-1)/4*2;
	}
	int res=0;
	for(int i=0;i<4;++i){
		int dx=x+d[i][0];
		int dy=y+d[i][1];
		if(!isMove(dx,dy)||sg(dx,dy))continue;
		res=max(res,dis(dx,dy)+1);
	}
	return res;
}

inline void find(int x,int y){
	int l=dis(x,y),s=sg(x,y);
	for(int i=0;i<4;++i){
		int dx=x+d[i][0];
		int dy=y+d[i][1];
		if(!isMove(dx,dy)||(s&&sg(dx,dy)))continue;
		if(l==dis(dx,dy)+1){
			printf("%d %d\n",dx,dy);
			return;
		}
	}
}

int x[MAXN],y[MAXN];

int maxl,ans;

int main(){
	freopen("knights.in","r",stdin);
	freopen("knights.out","w",stdout);
	scanf("%d%d",&k,&n);
	for(int i=1;i<=k;++i){
		scanf("%d%d",x+i,y+i);
		int tmp=dis(x[i],y[i]);
		int s=sg(x[i],y[i]);
		if(maxl<tmp||(maxl==tmp&&s))
			maxl=tmp,ans=s;
	}
	if(ans){
		puts("YES");
		for(int i=1;i<=k;++i)
			find(x[i],y[i]);
	}
	else puts("NO");
	return 0;
}