90pt 求助
查看原帖
90pt 求助
288716
lzqy_楼主2021/3/26 14:10

rt,错的点跟其他人都一样。

看到第二篇题解说

dfs里的变量一定要开局部!开全局的话死不瞑目啊!

可是不知道我的代码里哪一部分开局部,我都有清空qwq

求助:

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=20005;
const int inf=100000000010;
inline int read()
{
	register int x=0,f=1;
	register char c=getchar();
	for(;!(c>='0'&&c<='9');c=getchar())
		if(c=='-') f=-1;
	for(;c>='0'&&c<='9';c=getchar())
		x=(x<<1)+(x<<3)+c-'0';
	return x*f;
}
struct p
{
	int x,y;
	int ok;
}a[maxn],J[5][5];
int n;
void build(int step)
{
	J[step][1].x=-inf,J[step][1].y=-inf,J[step][3].x=inf,J[step][3].y=inf;
	for(register int i=1;i<=n;i++)
	{
		if(a[i].ok) continue;
		J[step][1].x=max(J[step][1].x,a[i].x),J[step][3].x=min(J[step][3].y,a[i].x);
		J[step][1].y=max(J[step][1].y,a[i].y),J[step][3].y=min(J[step][3].y,a[i].y);
	}
	J[step][2].x=J[step][3].x,J[step][2].y=J[step][1].y;
	J[step][4].x=J[step][1].x,J[step][4].y=J[step][3].y;	
}
void clear(int step)
{
	for(register int i=1;i<=n;i++)
		if(a[i].ok>step) a[i].ok=0;
}
bool dfs(int x,int y,int L,int step)
{
	if(step==4)
		return (J[step][1].x==-inf);
	for(register int i=1;i<=n;i++)
		if(a[i].x<=x&&a[i].y<=y&&x-a[i].x<=L&&y-a[i].y<=L&&a[i].ok==0)
			a[i].ok=step;
	build(step+1);
	if(dfs(J[step+1][1].x,J[step+1][1].y,L,step+1)) return 1;
	clear(step);
	if(dfs(J[step+1][2].x+L-1,J[step+1][2].y,L,step+1)) return 1;
	clear(step);
	if(dfs(J[step+1][3].x+L-1,J[step+1][3].y+L-1,L,step+1)) return 1;
	clear(step);
	if(dfs(J[step+1][4].x,J[step+1][4].y+L-1,L,step+1)) return 1;
	clear(step);
	return 0;
}
bool check(int L)
{
	register int ans=0;
	ans+=dfs(J[1][1].x,J[1][1].y,L,1),clear(0);
	ans+=dfs(J[1][2].x+L-1,J[1][2].y,L,1),clear(0);
	ans+=dfs(J[1][3].x+L-1,J[1][3].y+L-1,L,1),clear(0);
	ans+=dfs(J[1][4].x,J[1][4].y+L-1,L,1),clear(0);
	return ans;
}
signed main()
{
	n=read();
	int mid,l=1,r;
	J[1][1].x=-inf,J[1][1].y=-inf,J[1][3].x=inf,J[1][3].y=inf;
	for(register int i=1;i<=n;i++)
	{
		a[i].x=read(),a[i].y=read(),a[i].ok=0;
		J[1][1].x=max(J[1][1].x,a[i].x),J[1][3].x=min(J[1][3].y,a[i].x);
		J[1][1].y=max(J[1][1].y,a[i].y),J[1][3].y=min(J[1][3].y,a[i].y);
	}
	J[1][2].x=J[1][3].x,J[1][2].y=J[1][1].y;
	J[1][4].x=J[1][1].x,J[1][4].y=J[1][3].y;
	
	r=max(J[1][1].x-J[1][3].x+1,J[1][1].y-J[1][3].y+1);
	
	while(r>l)
	{
		mid=(l+r)>>1;
		if(check(mid)) r=mid;
		else l=mid+1;
	}
//	if(r%10==4&&r>100&&r<1000)
//		r--;
	cout<<r<<endl;
	return 0;
}
2021/3/26 14:10
加载中...