社区讨论
谁能解释一下一个玄学错误
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 条回复,欢迎继续交流。
正在加载回复...