【CodeVS1735】方程的解数

发表于 | 分类于 ， | 评论数： | 阅读次数：
meet in the middle的模板题

题面不贴了，http://codevs.cn/problem/1735/

这是meet in the middle的模板题，注意最后合并的时候用two-pointer的方法，可以先用离散化思想将相同的合并掉，用空间换常数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
#include<cstdio>
#include<algorithm>
using namespace std;

const int maxn=3500000;
typedef long long ll;
int n,m,a[10],p[10],s1[maxn],s2[maxn],tot1,tot2,ans,sum1,sum2,mid;
struct node
{
	int val,cnt;
}t1[maxn],t2[maxn];

ll qp(int a,int b)
{
	ll res=1;
	for (;b;b>>=1)
	{
		if (b&1)
			res*=a;
		a*=a;
	}
	return res;
}

void dfs(int x,ll now,int *s,int &tot)
{
	if (x>mid)
	{
		s[++tot]=now;
		return;
	}
	for (int i=1;i<=m;i++)
		dfs(x+1,now+a[x]*qp(i,p[x]),s,tot);
}

int main()
{
	int i,j;
	scanf("%d%d",&n,&m);
	for (i=1;i<=n;i++)
		scanf("%d%d",&a[i],&p[i]);
	mid=n/2;
	dfs(1,0,s1,tot1);
	mid=n;
	dfs(n/2+1,0,s2,tot2);
	sort(s1+1,s1+tot1+1);
	sort(s2+1,s2+tot2+1);
	for (i=1;i<=tot1;i++)
	{
		if (t1[sum1].val==s1[i])
			t1[sum1].cnt++;
		else
			t1[++sum1]=(node){s1[i],1};
	}
	for (i=1;i<=tot2;i++)
	{
		if (t2[sum2].val==s2[i])
			t2[sum2].cnt++;
		else
			t2[++sum2]=(node){s2[i],1};
	}
	j=sum2;tot1=tot2=0;
	for (i=1;i<=sum1;i++)
	{
		while (j>1&&t2[j].val+t1[i].val>0)
			j--;
		if (t1[i].val+t2[j].val==0)
			ans+=t1[i].cnt*t2[j].cnt;
	}
	printf("%d\n",ans);
	return 0;
}
显示 Gitment 评论