codevs1735 方程的解数(meet in the middle)
程序员文章站
2022-07-08 19:51:05
题意 "题目链接" Sol 把前一半放在左边,后一半放在右边 meet in the middle一波 统计答案的时候开始想的是hash,然而MLE了两个点 实际上只要排序之后双指针扫一遍就行了 cpp include using namespace std; const int MAXN = 7, ......
题意
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; }
下一篇: 冬天天冷