题目 还是看官网吧 我们先分析单个游戏
发现很有规律 最后一行一列要特判 写出来就是这样啦
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 Tlose(int x, int y) { if (x==n || y==n) return (x+y-2)/4*2; return (x+y-1)/4*2;}至于必胜态 我们只要枚举操作决策就好了
#include<cstdio>#include<cstdlib>#include<algorithm>using namespace std;inline char nc(){ static char buf[100000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;}inline void read(int &x){ char c=nc(),b=1; for (;!(c>='0' && c<='9');c=nc()) if (c=='-') b=-1; for (x=0;c>='0' && c<='9';x=x*10+c-'0',c=nc()); x*=b;}const int N=200005;int n,K;int x[N],y[N],sg[N];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 Tlose(int x, int y) { if (x==n || y==n) return (x+y-2)/4*2; return (x+y-1)/4*2;}const int dx[]={-2,-2,-1,1};const int dy[]={1,-1,-2,-2};inline int Twin(int x,int y){ int maxl=0; int sx,sy; for (int k=0;k<4;k++){ sx=x+dx[k]; sy=y+dy[k]; if (sx<1 || sy<1 || sx>n || sy>n) continue; if (!SG(sx,sy)) maxl=max(maxl,Tlose(sx,sy)); } return maxl+1;}inline void Plose(int x,int y){ int minw=1<<30; int sx,sy,nx,ny; for (int k=0;k<4;k++){ sx=x+dx[k]; sy=y+dy[k]; if (sx<1 || sy<1 || sx>n || sy>n) continue; if (SG(sx,sy) && Twin(sx,sy)<minw) minw=Twin(sx,sy),nx=sx,ny=sy; } PRintf("%d %d/n",nx,ny);}inline void Pwin(int x,int y){ int maxl=-1<<30; int sx,sy,nx,ny; for (int k=0;k<4;k++){ sx=x+dx[k]; sy=y+dy[k]; if (sx<1 || sy<1 || sx>n || sy>n) continue; if (!SG(sx,sy) && Tlose(sx,sy)>maxl) maxl=Tlose(sx,sy),nx=sx,ny=sy; } printf("%d %d/n",nx,ny);}int main(){ int maxt=0; freopen("t.in","r",stdin); freopen("t.out","w",stdout); read(K); read(n); for (int i=1;i<=K;i++){ read(x[i]),read(y[i]); if (sg[i]=SG(x[i],y[i])) maxt=max(maxt,Twin(x[i],y[i])); else maxt=max(maxt,Tlose(x[i],y[i])); } if (~maxt&1) printf("NO/n"); else{ printf("YES/n"); for (int i=1;i<=K;i++) if (sg[i]) Pwin(x[i],y[i]); else Plose(x[i],y[i]); } return 0;}新闻热点
疑难解答
