codevs1735 方程的解数(meet in the middle)

题意

Sol

把前一半放在左边，后一半放在右边

meet in the middle一波

统计答案的时候开始想的是hash，然而MLE了两个点

实际上只要排序之后双指针扫一遍就行了

#include<bits/stdc++.h>

using namespace std;

const int MAXN = 7, MAX = 1e7 + 10;

int K[MAXN], P[MAXN], N, M, ans;

int a1[MAX], c1, a2[MAX], c2, cnt[MAX];

int fp(int a, int p) {

	int base = 1;

	while(p) {

		if(p & 1) base = base * a;

		a = a * a; p >>= 1;

	}

	return base;

}

void dfs(int x, int Lim, int opt, int sum) {

	if(x == Lim + 1) {

		if(!opt) a1[++c1] = sum;

		else a2[++c2] = -sum;

		return ;

	}

	for(int i = 1; i <= M; i++) dfs(x + 1, Lim, opt, sum + K[x] * fp(i, P[x]));

}

int main() {

	ios::sync_with_stdio(false);

	cin >> N >> M;

	for(int i = 1; i <= N; i++) cin >> K[i] >> P[i];

	if(N <= 2) {

		a1[++c1] = 0;

		dfs(1, N, 1, 0);

	} else {

		dfs(1, N / 2, 0, 0);

		dfs(N / 2 + 1, N, 1, 0);

	}

	sort(a1 + 1, a1 + c1 + 1);

	sort(a2 + 1, a2 + c2 + 1);

	int j = 1;

	for(int i = 1; i <= c2; i++) {

		if(i != 1 && (a2[i] == a2[i - 1])) {cnt[i] = cnt[i - 1]; continue;}

		while(a1[j] <= a2[i] && j <= c1) {

			if(a1[j] == a2[i]) cnt[i]++;

			j++;

		}

	}

	/*

	for(int i = 1; i <= c1; i++)

		for(int j = 1; j <= c2; j++)

			ans += (a1[i] == a2[j]);

	*/

	for(int i = 1; i <= c2; i++) ans += cnt[i];

	cout << ans;

	return 0;

}

巴特西

codevs1735 方程的解数(meet in the middle)

题意

Sol

最新文章

热门文章