[COI2007] Sabor
程序员文章站
2022-08-21 18:42:33
下面给出这道一脸不可做的题的鬼畜性质: 1)对于一个点来说,其归属状态是确定的:走不到、A党或B党 。(黑白格染色) 方便起见,将包含所有不可达的点的极小矩形向外扩展一圈,设为矩形M。 2)矩形M的最外圈上相邻两点点到(0,0)的最短曼哈顿距离差值不超过1。 3)矩形M外任意正对于矩形M的点到垂直走 ......
下面给出这道一脸不可做的题的鬼畜性质:
1)对于一个点来说,其归属状态是确定的:走不到、a党或b党 。(黑白格染色)
方便起见,将包含所有不可达的点的极小矩形向外扩展一圈,设为矩形m。
2)矩形m的最外圈上相邻两点点到(0,0)的最短曼哈顿距离差值不超过1。
3)矩形m外任意正对于矩形m的点到垂直走向所正对的边必是到(0,0)的满足曼哈顿距离最小的路径的一条。
4)矩形m外任意非正对于矩形m到最靠近的m的一角必是到(0,0)的满足曼哈顿距离最小的路径的一条。
利用这些性质就可做了。。主要是向外扩展一圈这儿。。
然后就是找找规律的事儿了。。
#include <bits/stdc++.h> #define p 1000 using namespace std; const int fx[]={1,-1,0,0}; const int fy[]={0,0,1,-1}; int b,s; long long cnt[2]; int dis[2005][2005]; int maxx,maxy,minx,miny; queue<int> qx,qy; inline void f1(int x,int y) { cnt[(x+y)&1]+=1ll*((s-dis[x][y])/2)*((s-dis[x][y])/2); cnt[(x+y+1)&1]+=1ll*((s-dis[x][y]-1)/2)*((s-dis[x][y]-1)/2+1); } inline void f2(int x,int y) { cnt[(x+y)&1]+=(s-dis[x][y])/2; cnt[(x+y+1)&1]+=(s-dis[x][y]+1)/2; } int main() { scanf("%d%d",&b,&s); minx=miny=maxx=maxy=p; for(int x,y,i=1; i<=b; ++i) { scanf("%d%d",&x,&y); x+=p,y+=p; dis[x][y]=-1; minx=min(minx,x); maxx=max(maxx,x); miny=min(miny,y); maxy=max(maxy,y); } s++; minx--,miny--; maxx++,maxy++; qx.push(p); qy.push(p); dis[p][p]=1; while(!qx.empty()) { int x=qx.front(); qx.pop(); int y=qy.front(); qy.pop(); if((x==minx||x==maxx) && (y==miny||y==maxy)) f1(x,y); if((x==minx||x==maxx)) f2(x,y); if((y==miny||y==maxy)) f2(x,y); cnt[(x+y)&1]++; if(dis[x][y]==s) continue; for(int nx,ny,k=0; k<4; ++k) { nx=x+fx[k]; ny=y+fy[k]; if(nx<minx||ny<miny||nx>maxx||ny>maxy||dis[nx][ny]) continue; dis[nx][ny]=dis[x][y]+1; qx.push(nx); qy.push(ny); } } printf("%lld %lld\n",cnt[0],cnt[1]); return 0; }