题意：
在一块N*N的棋盘上有K个骑士，它们只能朝四个方向移动，每一回合，玩家必须把所有能动的骑士移动一格，当一个玩家没有任何骑士可以移动的时候它就输了，问是否先手必胜，如果是，给出一种可行的每个棋子的第一步的方案。
solution:
这是一个every-sg游戏，对于每个局面，如果先手必胜，那么先手必定是想尽可能地多走几步，否则，先手肯定是想尽可能早地结束这场游戏。
那么定义stepi，为局面i执行最优决策时的步数。对于所有局面，先手必胜，当且仅当先手必胜局中step的最大值大于先手必败局中step的最大值，证明很显然的。。。
最后打表找找这张图中sg值和step值的规律就行了
先看先手必败点的分布，总结一下sg值，总结一下step即可
#include<iostream> #include<cstdio> #include<algorithm> #include<cmath> #include<cstring> #include<vector> #include<queue> #include<set> #include<map> #include<stack> #include<bitset> #include<ext/pb_ds/priority_queue.hpp> using namespace std; const int maxn = 2E5 + 20; const int INF = ~0U>>1; const int dx[4] = {-2,-2,-1,1}; const int dy[4] = {1,-1,-2,-2}; struct Point{ int x,y; Point(){} Point(int x,int y): x(x),y(y){} }p[maxn]; int n,m,Win,Lose; inline int getint() { char ch = getchar(); int ret = 0; while (ch < '0' || '9' < ch) ch = getchar(); while ('0' <= ch && ch <= '9') ret = ret * 10 + ch - '0',ch = getchar(); return ret; } char s[10]; inline void Print(int x) { int len = 0; while (x) s[++len] = x % 10,x /= 10; for (int i = len; i; i--) putchar(s[i] + '0'); } inline int min(const int &x,const int &y) {return x < y ? x : y;} inline int max(const int &x,const int &y) {return x > y ? x : y;} inline int Sg(int x,int y) { if (n % 4 == 0 && x == n && y == n) return 0; if (n % 4 == 1 && x == n && y != n - 1) return 0; if (n % 4 == 1 && x != n - 1 && y == n) return 0; if ((x % 4 == 1 || x % 4 == 2) && (y % 4 == 1 || y % 4 == 2)) return 0; return 1; } inline int LoseStep(int x,int y) { return (x + y - ((x == n || y == n) ? 2 : 1)) / 4 * 2; } inline int WinStep(int x,int y) { int ret = 0; for (int i = 0; i < 4; i++) { int xx = x + dx[i],yy = y + dy[i]; if (xx < 1 || xx > n || yy < 1 || yy > n) continue; if (Sg(xx,yy)) continue; ret = max(ret,LoseStep(xx,yy)); } return ret + 1; } void Print_Ans() { for (int i = 1; i <= m; i++) Print(p[i].x),putchar(' '),Print(p[i].y),puts(""); } int main() { #ifdef DMC freopen("DMC.txt","r",stdin); #endif cin >> m >> n; for (int i = 1; i <= m; i++) { int x = getint(),y = getint(); int sg = Sg(x,y),tmp; if (sg) { tmp = -1; for (int j = 0; j < 4; j++) { int xx = x + dx[j],yy = y + dy[j]; if (xx < 1 || xx > n || yy < 1 || yy > n) continue; if (Sg(xx,yy)) continue; int now = LoseStep(xx,yy); if (now > tmp) p[i] = Point(xx,yy),tmp = now; } Win = max(Win,tmp + 1); } else { tmp = INF; for (int j = 0; j < 4; j++) { int xx = x + dx[j],yy = y + dy[j]; if (xx < 1 || xx > n || yy < 1 || yy > n) continue; int now = WinStep(xx,yy); if (now < tmp) p[i] = Point(xx,yy),tmp = now; } Lose = max(Lose,tmp + 1); } } if (Win < Lose) puts("NO"); else puts("YES"),Print_Ans(); return 0; } 