社区讨论

谁能解释一下一个玄学错误

P5030长脖子鹿放置参与者 2已保存回复 6

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
5 条
当前快照
1 份
快照标识符
@mm77k32y
此快照首次捕获于
2026/03/01 11:46
上周
此快照最后确认于
2026/03/03 20:10
7 天前
查看原帖
rt. wa 代码:
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,k,all,tot,a[201][201],vis[40001],mat[40001],f[8][2]={{-3,-1},{-3,1},{-1,-3},{-1,3},{1,-3},{1,3},{3,-1},{3,1}};
int h[900001],to[900001],ne[900001],cnt;
inline void adde(int x,int y){
	to[cnt]=y,ne[h[x]=cnt++]=h[x],swap(x,y);
	to[cnt]=y,ne[h[x]=cnt++]=h[x];
}
inline int _21(int x,int y){return (x-1)*m+y;}
inline void add(int x,int y){
	for(int i=0;i<8;i++){
		int tx=x+f[i][0],ty=y+f[i][1];
		if(1<=tx&&tx<=n&&1<=ty&&ty<=m&&!a[tx][ty]) adde(_21(x,y),_21(tx,ty));
	}
}
inline bool dfs(int x){
	for(int i=h[x];i;i=ne[i])
		if(!vis[to[i]]){
			vis[to[i]]=1;
			if(!mat[to[i]]||dfs(mat[to[i]])){mat[to[i]]=x;return 1;}
		}
	return 0;
}
int main(){
	cin>>n>>m>>k,all=n*m;
	for(int i=1,x,y;i<=k;i++){
		cin>>x>>y;
		if(!a[x][y]) a[x][y]=1,all--;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!a[i][j]&&!(i&1)) add(i,j);
	for(int i=1;i<=n*m;i++) memset(vis,0,sizeof vis),tot+=dfs(i);
	cout<<all-tot/2;
	return 0;
}
ac 代码:
CPP
#include<bits/stdc++.h>
using namespace std;
int n,m,k,all,tot,a[201][201],vis[40001],mat[40001],f[8][2]={{-3,-1},{-3,1},{-1,-3},{-1,3},{1,-3},{1,3},{3,-1},{3,1}};
int h[900001],to[900001],ne[900001],cnt;
inline void adde(int x,int y){
	to[++cnt]=y,ne[h[x]=cnt]=h[x],swap(x,y);
	to[++cnt]=y,ne[h[x]=cnt]=h[x];
}
inline int _21(int x,int y){return (x-1)*m+y;}
inline void add(int x,int y){
	for(int i=0;i<8;i++){
		int tx=x+f[i][0],ty=y+f[i][1];
		if(1<=tx&&tx<=n&&1<=ty&&ty<=m&&!a[tx][ty]) adde(_21(x,y),_21(tx,ty));
	}
}
inline bool dfs(int x){
	for(int i=h[x];i;i=ne[i])
		if(!vis[to[i]]){
			vis[to[i]]=1;
			if(!mat[to[i]]||dfs(mat[to[i]])){mat[to[i]]=x;return 1;}
		}
	return 0;
}
int main(){
	cin>>n>>m>>k,all=n*m;
	for(int i=1,x,y;i<=k;i++){
		cin>>x>>y;
		if(!a[x][y]) a[x][y]=1,all--;
	}
	for(int i=1;i<=n;i++)
		for(int j=1;j<=m;j++)
			if(!a[i][j]&&!(i&1)) add(i,j);
	for(int i=1;i<=n*m;i++) memset(vis,0,sizeof vis),tot+=dfs(i);
	cout<<all-tot/2;
	return 0;
}
区别:
CPP
//wa:
inline void adde(int x,int y){
	to[cnt]=y,ne[h[x]=cnt++]=h[x],swap(x,y);
	to[cnt]=y,ne[h[x]=cnt++]=h[x];
}
//ac:
inline void adde(int x,int y){
	to[++cnt]=y,ne[h[x]=cnt]=h[x],swap(x,y);
	to[++cnt]=y,ne[h[x]=cnt]=h[x];
}
请问有人知道为啥吗,玄关

回复

6 条回复,欢迎继续交流。

正在加载回复...