lp5030 长脖子鹿放置

观察这一题的攻击方式，我们可以发现一个特点——所有奇数行的长颈鹿都攻击不到偶数行的长颈鹿，反之亦然。
所以，我们对奇偶的长颈鹿分开考虑，这显然是一张二分图。
于是类同于骑士共存问题，我们建一个二分图，跑匈牙利。
对于\(200\)的数据范围，匈牙利的小常数是可以卡过去的。
但是T了两个点，获得了80分的好成绩。
然后我们考虑一个对于vis数组的常数优化。
对于vis数组，我们定义一个变量dep，表示当前是第dep次匹配。这样就不必每次都清空vis数组了。
第二个就是，由于连的边是确定的，故而我们可以在线计算目的边，这样可以减少很多寻址时间。
另外就是对图的遍历顺序的优化。用了出题人的松松松顺序之后最终通过此题。

#include<iostream>
#include<cstdio>

const int dx[8]={3,3,-3,-3,1,1,-1,-1};
const int dy[8]={-1,1,-1,1,3,-3,3,-3};

bool mp[205][205];
int vis[40405],dep=0;
int n,m,q,usd[40405];
//注意数组大小。 

inline int calc(int X,int Y){
	return (X<=0||Y<=0||X>n||Y>m||mp[X][Y])?0:X*m+Y;
} 

inline bool dfs(int X){
	int v;
	for(int i=0;i<8;++i){
		v=calc((X-1)/m+dx[i],(X-1)%m+1+dy[i]);
//		注意还原信息。 
		if(v&&vis[v]!=dep){
			vis[v]=dep;
			if(!usd[v]||dfs(usd[v])){
				usd[v]=X;
				return 1;
			}
		}
	}
	return 0;
}

void init(){
//	mp[n][m]->mp[x][y] 
	scanf("%d%d%d",&n,&m,&q);
	int x,y;
	for(int i=1;i<=q;++i){
		scanf("%d%d",&x,&y);
		mp[x][y]=1;
	}
	int ans=n*m-q;
	for(int i=1;i<=n;i+=2){
		for(int j=1;j<=m;++j){
			if(mp[i][j]){
				continue;
			}
			++dep;
			ans-=dfs(calc(i,j));
		}
	}
//	for(int i=0;i<=n+1;++i){
//		for(int j=0;j<=m+1;++j){
//			printf("%2d ",calc(i,j));
//		}
//		puts("");
//	}
	printf("%d\n",ans);
}

int main(){
	init();
	return 0;
}