BZOJ1393 [Ceoi2008]knights

题意。。。上ceoi官网看吧。。。

首先打一下sg函数发现必胜态和必败态的分布位置是有规律的

于是我们只要知道最长步数的必胜态和最长步数的必败态哪个更长就可以了

然后再打一下步数的表。。。发现必败态的最长步数非常好确定，那么必胜态的步数搜一下就可以了！

 /**************************************************************

     Problem: 1393

     User: rausen

     Language: C++

     Result: Accepted

     Time:992 ms

     Memory:2372 kb

 ****************************************************************/

 #include <cstdio>

 #include <algorithm>

 using namespace std;

 const int dx[] = {-, -, -, };

 const int dy[] = {, -, -, -};

 const int N = 2e5 + ;

 const int inf = 1e8;

 int n, k;

 int Ans, ansx[N], ansy[N];

 inline int read();

 inline void print (const int &);

 inline bool calc_sg(int x, int y) {

     if ((x %  ==  || x %  == ) && (y %  ==  || y %  == )) return ;

     if (n %  ==  && ((x == n && y != n - ) || (y == n && x != n - ))) return ;

     if (n %  ==  && x == n && y == n) return ;

     return ;

 }

 inline bool in(const int &x, const int &y) {

     return (x >  && y >  && x <= n && y <= n);

 }

 #define X x + dx[k]

 #define Y y + dy[k]

 inline int find_lose(int x, int y) {

     if (x == n || y == n) return  * ((int) (x + y - ) / );

     return  * ((int) (x + y - ) / );

 }

 inline int find_win(int x, int y) {

     int k, res = ;

     for (k = ; k < ; ++k)

         if (in(X, Y) && calc_sg(X, Y) == )

             res = max(res, find_lose(X, Y));

     return res + ;

 }

 inline int calc_lose(int x, int y, int i) {

     int k, tmp = inf;

     for (k = ; k < ; ++k)

         if (in(X, Y) && calc_sg(X, Y) ==  && find_win(X, Y) < tmp) {

             tmp = find_win(X, Y);

             ansx[i] = X, ansy[i] = Y;

         }

 }

 inline int calc_win(int x, int y, int i) {

     int k, tmp = -;

     for (k = ; k < ; ++k)

         if (in(X, Y) && calc_sg(X, Y) ==  && tmp < find_lose(X, Y)) {

             tmp = find_lose(X, Y);

             ansx[i] = X, ansy[i] = Y;

         }

 }

 #undef X

 #undef Y

 int main() {

     int i, x, y, tmp, max_lose = , max_win = ;

     k = read(), n = read();

     for (i = ; i <= k; ++i) {

         x = read(), y = read();

         tmp = calc_sg(x, y);

         if (tmp == ) {

             max_lose = max(max_lose, find_lose(x, y));

             calc_lose(x, y, i);

             continue;

         }

         max_win = max(max_win, find_win(x, y));

         calc_win(x, y, i);

     }

     if (max_lose > max_win) puts("NO"); else {

         puts("YES");

         for (i = ; i <= k; ++i) {

             print(ansx[i]), putchar(' ');

             print(ansy[i]), putchar('\n');

         }

     }

     return ;

 }

 inline int read() {

     int x = ;

     char ch = getchar();

     while (ch < '' || '' < ch)

         ch = getchar();

     while ('' <= ch && ch <= '') {

         x = x *  + ch - '';

         ch = getchar();

     }

     return x;

 }

 inline void print(const int &x) {

     static int tot, pr[], t;

     t = x, tot = ;

     while (t)

         pr[++tot] = t % , t /= ;

     if (!tot) putchar('');

     while(tot)

         putchar('' + pr[tot--]);

 }