双向搜索求助
查看原帖
双向搜索求助
576830
ballpoint_pen楼主2022/3/29 21:06
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll x[50],y[50],n,cntl=0,cntr=0,gx,gy,ans[50];
struct node{
	ll totx,toty,ch;
}l[1<<25],r[1<<25];
bool cmpl(node a,node b){
	if(a.totx!=b.totx) return a.totx<b.totx;
	else if(a.toty!=b.toty) return a.toty<b.toty;
	else return a.ch<b.ch;
}
bool cmpr(node a,node b){
	if(a.totx!=b.totx) return a.totx>b.totx;
	else if(a.toty!=b.toty) return a.toty>b.toty;
	else return a.ch>b.ch;
}
void dfs1(int p,ll totx,ll toty,int ch){
	if(p>(n>>1)){
		cntl++;
		l[cntl].totx=totx;
		l[cntl].toty=toty;
		l[cntl].ch=ch;
		return;
	}
	dfs1(p+1,totx,toty,ch);
	dfs1(p+1,totx+x[p],toty+y[p],ch+1);
}
void dfs2(int p,ll totx,ll toty,int ch){
	if(p>n){
		cntr++;
		r[cntr].totx=totx;
		r[cntr].toty=toty;
		r[cntr].ch=ch;
		return;
	}
	dfs2(p+1,totx,toty,ch);
	dfs2(p+1,totx+x[p],toty+y[p],ch+1);
}
int main(){
	memset(ans,0,sizeof(ans));
	cin>>n>>gx>>gy;
	for(int i=1;i<=n;i++) cin>>x[i]>>y[i];
	dfs1(1,0,0,0);
	dfs2((n>>1)+1,0,0,0);
	sort(l+1,l+cntl+1,cmpl);
	sort(r+1,r+cntr+1,cmpr);
	for(ll i=1,j=1;i<=cntl && j<=cntr;i++){
		while(j<=cntr && l[i].totx+r[j].totx!=gx) j++;
		if(j>cntr) break;
		ll pos=j;
		while(l[i].totx+r[pos].totx==gx&&pos<=cntr){
			if(l[i].toty+r[pos].toty==gy) ans[l[i].ch+r[pos].ch]++;
			pos++;
		} 
	}
	for(int i=1;i<=n;i++) cout<<ans[i]<<endl;
	return 0;
}

rt 只有6分 不知道什么情况

2022/3/29 21:06
加载中...