题目描述
小明喜欢玩飞镖游戏，他会把每次的得分都记录在数组中。今天有个飞镖大奖，得奖的规则是：如果你4次飞镖的得分先后是（a，b，c，d），满足a×b×c=d。
小明准备把记录里的其他项删除，只留下满足获奖条件的4个分数，他想问你有多少种不同方案？
输入输出格式
输入格式
第一行，一个整数N。(N <= 2000)
第二行，N个整数，每个整数范围在[1...10^6]。
输出格式
一行，一个整数，代表方案数。
输入输出样例
输入样例一
6
10 2 2 7 40 160
输出样例一
2
输入样例二
8
128 64 32 16 8 4 2 1
输出样例二
0
题解
暴力枚举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 1000000using 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; }
然而，当数据范围再放大一些的时候，上面的做法就不行了。我们可以看看上面的做法的缺点，在于需要查找b的位置，如果我们可以在枚举d/c的时候同时枚举a*b，就可以做到O(n²)的时间复杂度，而这真的可以实现，只需要利用b的位置在c的位置前面这个特性即可，具体可以参考下面的程序。（而且这个做法还更好写。。）
#include <iostream>#define MAX_N 2000 #define PTS 1000000using 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; }
