solution

一道非常经典的双向搜索题目，先将前3个未知数枚举一遍得到方程的前半部分所有可能的值，取负存入第一个队列中再将后3个未知数枚举一遍，存入第二个队列中。这样我们只要匹配两个队列中相同的元素即可使方程为零。方法：将两个队列排序，用尺取法+乘法原理扫一遍即可。

=>

code：

#include<iostream>

#include<cstdio>

#include<iomanip>

#include<algorithm>

#include<cstring>

#include<cstdlib>

#include<ctime>

#include<cmath>

#include<vector>

#include<queue>

#include<map>

#include<set>

#define ll long long

#define db double

#define inf 0x7fffffff

#define rg register int

using namespace std;

int ans;

int n,m,l,t1,t2;

int k[7],p[7];

int a[3500001];

int b[3500001];

inline int qr(){

	char ch;int sign=1;

	while((ch=getchar())<'0'||ch>'9')

		if(ch=='-')sign=-1;

	int res=ch^48;

	while((ch=getchar())>='0'&&ch<='9')

		res=res*10+(ch^48);

	return res*sign;

}

inline int fast(int x,int y){

	int res=1;

	while(y){

		if(y&1)res*=x;

		x*=x; y>>=1;

	}return res;

}

inline void dfs(int t,int tot){

	if(t>l){a[++t1]=-tot;return ;}

	for(rg i=1;i<=m;++i)

		dfs(t+1,tot+k[t]*fast(i,p[t]));

}

inline void dfs2(int t,int tot){

	if(t>n){b[++t2]=tot;return ;}

	for(rg i=1;i<=m;++i)

		dfs2(t+1,tot+k[t]*fast(i,p[t]));

}

int main(){

	//freopen("equation.in","r",stdin);

	//freopen("equation.out","w",stdout);

	n=qr(),m=qr();l=n/2;

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

		k[i]=qr(),p[i]=qr();

	dfs(1,0); dfs2(l+1,0);

	sort(a+1,a+t1+1);

	sort(b+1,b+t2+1);

	for(rg i=1,j=1,su,x,y;i<=t1;++i){

		if(a[i]<b[j])continue;

		while(b[j]<a[i]&&j<=t2)++j;

		if(j>t2)break;

	    if(a[i]==b[j]){

			su=a[i]; x=y=0;

			while(a[i]==su&&i<=t1)++i,++x;

			while(b[j]==su&&j<=t2)++j,++y;

			ans+=x*y;--i;

		}

	}

	printf("%d\n",ans);

	return 0;

}

巴特西

NOI2001 方程的解数（双向搜索）

solution

=>

code：

最新文章

热门文章