SPOJ4580 ABCDEF(meet in the middle)
程序员文章站
2022-03-17 13:52:51
题意 "题目链接" Sol 发现abcdef是互不相关的 那么meet in the middle一下。先算出abc的,再算def的 注意d = 0的时候不合法(害我wa了两发。。) cpp include define LL long long using namespace std; const ......
题意
sol
发现abcdef是互不相关的
那么meet in the middle一下。先算出abc的,再算def的
注意d = 0的时候不合法(害我wa了两发。。)
#include<bits/stdc++.h> #define ll long long using namespace std; const int maxn = 101, ss = 2e6 + 10; map<ll, ll> mp; int n; ll a[maxn], ans; int a1[ss], c1, a2[ss], c2, cnt[ss]; int main() { // ios::sync_with_stdio(false); cin >> n; for(int i = 1; i <= n; i++) cin >> a[i]; sort(a + 1, a + n + 1); for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= n; k++) a1[++c1] = a[i] * a[j] + a[k]; for(int i = 1; i <= n; i++) for(int j = 1; j <= n; j++) for(int k = 1; k <= n; k++) if(a[i] != 0) a2[++c2] = a[i] * (a[j] + a[k]); sort(a1 + 1, a1 + c1 + 1); sort(a2 + 1, a2 + c2 + 1); for(int i = 1, j = 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 <= c2; i++) ans += cnt[i]; cout << ans; return 0; }