bzoj1391 [CEOI2008]knights
every-SG:必胜或必败由步数最长的状态决定。
sg函数和步数打个表找找规律什么的。。。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 | #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;} |
