GHOJ 234 飞镖

题目描述

小明喜欢玩飞镖游戏，他会把每次的得分都记录在数组中。今天有个飞镖大奖，得奖的规则是：如果你4次飞镖的得分先后是（a，b，c，d），满足a×b×c=d。

小明准备把记录里的其他项删除，只留下满足获奖条件的4个分数，他想问你有多少种不同方案？

输入输出格式

输入格式

第一行，一个整数N。(N <= 2000)

第二行，N个整数，每个整数范围在[1...

输出格式

一行，一个整数，代表方案数。

输入输出样例

输入样例一

10 2 2 7 40 160

输出样例一

输入样例二

128 64 32 16 8 4 2 1

输出样例二

题解

暴力枚举a，b，c，求d是否存在，可以做到O(n³)的时间复杂度，但是显然并不能满足这题的数据范围。

我们可以从另一个角度出发。由题的a*b=d/c，我们可以先枚举a*b，记录b出现的位置，然后枚举d/c，根据c的位置来找满足b的位置符合题意的情况数，这样看起来也是O(n³)，但实际上用二分查找优化可以做到O(n²logn)，刚好可以通过这题。

#include <iostream>
#include <vector>

#define MAX_N 2000
#define PTS 1000000

using namespace std;

int n;
int a[MAX_N | 1];
vector<int> c[PTS | 1];
long long ans;

inline int BS(int x, int p)
{
    int len = c[x].size();
    int lt = 0, rt = len - 1, mid;
    while(lt <= rt)
    {
        mid = lt + rt >> 1;
        if(c[x][mid] >= p) rt = mid - 1;
        else if(mid + 1 < len && c[x][mid + 1] < p) lt = mid + 1;
        else return mid + 1;
    }
    return 0;
}

int main()
{
    cin >> n;
    for(register int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    for(register int i = 2; i + 2 <= n; ++i)
    {
        for(register int j = 1; j < i; ++j)
        {
            if((long long)a[i] * a[j] > PTS) continue;
            c[a[i] * a[j]].push_back(i);
        }
    }
    for(register int i = 3; i < n; ++i)
    {
        for(register int j = i + 1; j <= n; ++j)
        {
            if(a[j] % a[i]) continue;
            ans += BS(a[j] / a[i], i);
            // cout << i << " " << j << " " << ans << endl;
        }
    }
    cout << ans;
    return 0;
}

参考程序O(n²logn)版

然而，当数据范围再放大一些的时候，上面的做法就不行了。我们可以看看上面的做法的缺点，在于需要查找b的位置，如果我们可以在枚举d/c的时候同时枚举a*b，就可以做到O(n²)的时间复杂度，而这真的可以实现，只需要利用b的位置在c的位置前面这个特性即可，具体可以参考下面的程序。（而且这个做法还更好写。。）

#include <iostream>

#define MAX_N 2000
#define PTS 1000000

using namespace std;

int n;
int a[MAX_N | 1];
int c[PTS | 1];
long long ans;

int main()
{
    cin >> n;
    for(register int i = 1; i <= n; ++i)
    {
        cin >> a[i];
    }
    for(register int i = 3; i < n; ++i)
    {
        for(register int j = 1; j < i - 1; ++j)
        {
            if((long long)a[i - 1] * a[j] > PTS) continue;
            ++c[a[i - 1] * a[j]];
        }
        for(register int j = i + 1; j <= n; ++j)
        {
            if(a[j] % a[i]) continue;
            ans += c[a[j] / a[i]];
        }
    }
    cout << ans;
    return 0;
}

参考程序O(n²)版