欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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;
}

上一篇: 素数判定

下一篇: js动态添加对象