分析

这道题看上去很恶心，实际上只用记录四坨东西就能打DP了：y坐标最小的向上射的点、y坐标最大的向下射的点、y坐标最大和最小的向右射的点，转移显然。注意，如果该状态的值为零就可以略过，否则会超时。

#include <cmath>

#include <cstdio>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <cstring>

using namespace std;

int a[60][3],f[2][57][57][57][57],xz[55],xy[55],ys[55],yx[55];

int n,m,tot;

void q(int l,int r)

{

	int i=l,j=r,mid=a[(l+r)/2][1],e;

	while(i<j)

	{

		while(a[i][1]<mid) i++;

		while(a[j][1]>mid) j--;

		if(i<=j)

		{

			e=a[i][1];

			a[i][1]=a[j][1];

			a[j][1]=e;

			e=a[i][2];

			a[i][2]=a[j][2];

			a[j][2]=e;

			i++;

			j--;

		}

	}

	if(i<r) q(i,r);

	if(l<j) q(l,j);

}

void q1(int l,int r)

{

	int i=l,j=r,mid=a[(l+r)/2][2],e;

	while(i<j)

	{

		while(a[i][2]<mid) i++;

		while(a[j][2]>mid) j--;

		if(i<=j)

		{

			e=a[i][1];

			a[i][1]=a[j][1];

			a[j][1]=e;

			e=a[i][2];

			a[i][2]=a[j][2];

			a[j][2]=e;

			i++;

			j--;

		}

	}

	if(i<r) q1(i,r);

	if(l<j) q1(l,j);

}

int main()

{

	cin>>n;

	int i,j,k,l,p,x,y;

	for(i=1;i<=n;i++)

	{

		cin>>a[i][1]>>a[i][2];

		xz[i]=xy[i]=ys[i]=yx[i]=56;

	}

	xz[0]=xy[0]=ys[0]=yx[0]=56;

	q1(1,n);

	tot=0;

	p=-2000000000;

	for(i=1;i<=n;i++)

	{

		if(a[i][2]==p)

		{

			a[i][2]=tot;

		}

		else

		{

			p=a[i][2];

			a[i][2]=++tot;

		}

	}

	q(1,n);

	tot=0;

	p=-2000000000;

	for(i=1;i<=n;i++)

	{

		if(a[i][1]==p)

		{

			a[i][1]=tot;

		}

		else

		{

			p=a[i][1];

			a[i][1]=++tot;

		}

		if(xz[a[i][2]]==56)

			xz[a[i][2]]=a[i][1];

		else

		    xz[a[i][2]]=min(xz[a[i][2]],a[i][1]);

		if(xy[a[i][2]]==56)

			xy[a[i][2]]=a[i][1];

		else

		    xy[a[i][2]]=max(xy[a[i][2]],a[i][1]);

		if(yx[a[i][1]]==56)

			yx[a[i][1]]=a[i][2];

		else

		    yx[a[i][1]]=min(yx[a[i][1]],a[i][2]);

		if(ys[a[i][1]]==56)

			ys[a[i][1]]=a[i][2];

		else

		    ys[a[i][1]]=max(ys[a[i][1]],a[i][2]);

	}

	int mo=998244353;

	f[0][n+1][0][0][n+1]=1;

	int ans=0;

	for(i=0;i<=n;i++)

	{

		memset(f[(i+1)%2],0,sizeof(f[(i+1)%2]));

		for(int up=0;up<=n+1;up++)

			for(int down=0;down<=n+1;down++)

				for(int mx=0;mx<=n+1;mx++)

					for(int mn=0;mn<=n+1;mn++)

						if(f[i%2][up][down][mx][mn])

						{

							int sum=0;

							int t=f[i%2][up][down][mx][mn];

							//上

							if(a[i+1][2]==ys[a[i+1][1]] && mx<a[i+1][2])

								(f[(i+1)%2][min(up,a[i+1][2])][down][mx][mn]+=t)%=mo,(sum+=t)%=mo;

							//下

							if(a[i+1][2]==yx[a[i+1][1]] && mn>a[i+1][2])

								(f[(i+1)%2][up][max(down,a[i+1][2])][mx][mn]+=t)%=mo,(sum+=t)%=mo;

							//左

							if(a[i+1][1]==xz[a[i+1][2]] && up>a[i+1][2] &&  down<a[i+1][2])

								(f[(i+1)%2][up][down][mx][mn]+=t)%=mo,(sum+=t)%=mo;

							//右

							if(a[i+1][1]==xy[a[i+1][2]])

								(f[(i+1)%2][up][down][max(mx,a[i+1][2])][min(mn,a[i+1][2])]+=t)%=mo,(sum+=t)%=mo;

	    					if(i==n-1) ans=(ans+sum)%mo;

	    				}

	}

	cout<<ans;

}

巴特西

【C】题解（五校联考3day2）

分析

最新文章

热门文章

巴特西

【C】题解 （五校联考3day2）

分析

最新文章

热门文章

【C】题解（五校联考3day2）