双向搜索94pts超时求助
查看原帖
双向搜索94pts超时求助
457518
czy_0021楼主2024/7/9 12:44
#include<bits/stdc++.h>
using namespace std;
#define int long long 
const int N=1024*1024+10;
const int M=50;
struct node{
	int x;
	int y;
	int k;
	int s;
}f[N];
int xx,yy,cnt;
int n,a[M],b[M];
int p,ans[M];
bool cmp(const node &x,const node &y){
	return x.x<y.x||(x.x==y.x&&x.y<y.y);
}
bool cmp2(const node &x,const node &y){
	return x.s>y.s;
}
void dfs(int x,int y,int k,int s){
	if(s==n/2+1){
		cnt++;
		f[cnt].x=x;
		f[cnt].y=y;
		f[cnt].k=k;
		f[cnt].s=1;
		return;
	}
	dfs(x+a[s],y+b[s],k+1,s+1);
	dfs(x,y,k,s+1);
	return;
}
void find(int x,int y,int k){
	int l=1,r=p,mid,s=0;
	while(l<=r){
		mid=(l+r)/2;
		if(f[mid].x<x||(f[mid].x==x&&f[mid].y<=y))s=max(s,mid),l=mid+1;
		else r=mid-1;
	}
	while(s&&f[s].x==x&&f[s].y==y){
		ans[f[s].k+k]+=f[s].s;
		s--;
	}
	return;
}
void ask(int x,int y,int k,int s){
	if(s==n/2)return find(x,y,k);
	ask(x-a[s],y-b[s],k+1,s-1);
	ask(x,y,k,s-1);
	return;
}
signed main(){
	//freopen("robot.in","r",stdin);
	//freopen("robot.out","w",stdout); 
	cin>>n>>xx>>yy;
	for(int i=1;i<=n;i++)
	cin>>a[i]>>b[i];
	dfs(0,0,0,1);
	sort(f+1,f+1+cnt,cmp);
	for(int i=cnt;i>=1;i--)
	if(f[i].x==f[i-1].x&&f[i].y==f[i-1].y&&f[i].k==f[i-1].k)
	f[i-1].s+=f[i].s,f[i].s=0;
	sort(f+1,f+1+cnt,cmp2);
	p=cnt;
	for(int i=cnt;i>=1;i--)
	if(f[i].s==0)
	p=i-1;
	sort(f+1,f+1+p,cmp);
	ask(xx,yy,0,n);
	for(int i=1;i<=n;i++)
	cout<<ans[i]<<endl;
} 
2024/7/9 12:44
加载中...