社区讨论

本地AC提交WA(在别的评测站上过了luogu却wa了emm)

P3355骑士共存问题参与者 3已保存回复 6

讨论操作

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

当前回复
6 条
当前快照
1 份
快照标识符
@mi7p84u4
此快照首次捕获于
2025/11/21 01:22
4 个月前
此快照最后确认于
2025/11/21 01:22
4 个月前
查看原帖
蒟蒻求助qwq(T了8个,wa了两个,已经写成线性了为什么还是T了啊····)
CPP
#include<bits/stdc++.h> 
using namespace std; 
const int maxn=160000+5,jia[8]={-2,-2,-1,-1,1,1,2,2},jia1[8]={-1,1,-2,2,-2,2,-1,1}; 
bool Map[202][202],mark[maxn];
int Link[maxn],Next[maxn],cnt,End[maxn],Last[maxn];
queue<int> q; 
bool Find(int x) 
{ 
    for (int i=Last[x];i;i=Next[i]) 
    { 
        int j=End[i]; 
        if (!mark[j]) 
        { 
            mark[j]=true; 
            if (Link[j]==0||Find(Link[j])) 
            { 
                Link[j]=x; 
                return true; 
            } 
        } 
    } 
} 
void jian(int a,int b) 
{ 
    cnt++; 
    End[cnt]=b; 
    Next[cnt]=Last[a]; 
    Last[a]=cnt; 
} 
int main() 
{ 
//freopen("ceshi.in","r",stdin);
    int n,m; 
    scanf("%d%d",&n,&m); 
    for (int i=1;i<=m;i++) 
    {int a,b;scanf("%d%d",&a,&b);Map[a][b]=true;} 
    for (int i=1;i<=n;i++) 
	 	for (int j=1;j<=n;j++) 
		if (!Map[i][j]&&(i+j)%2==0) 
    	{  
        	q.push(((i-1)*n+j-1)/2+1);
            //这里就是标点啦,看不懂可以忽略掉emm
        	for (int k=0;k<=7;k++) 
        	{ 
        	    int x=i+jia[k]; 
        	    int y=j+jia1[k]; 
        	    if (Map[x][y]||x>n||x<1||y>n||y<1) 
        	    continue; 
            	jian(((i-1)*n+j-1)/2+1,((x-1)*n+y-1)/2+1); 
        	}
		}
    int tot=0; 
    while (q.size()) 
    { 
        memset(mark,0,sizeof(mark)); 
        if (Find(q.front())) tot++;
		q.pop(); 
    } 
    printf("%d",n*n-m-tot); 
}

回复

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

正在加载回复...