洛谷P2119题解

原题链接：https://www.luogu.com.cn/problem/P2119。

分析

这道题目要求我们找到满足特定条件的四个魔法物品，称为魔法阵。

魔法阵具体条件是：

1. 四个物品的魔法值严格递增：$X_a < X_b < X_c < X_d$。

2. $X_b - X_a = 2 \times (X_d - X_c)$。

3. $X_b - X_a < (X_c - X_b) / 3$。

首先统计每个魔法值出现的次数，这样可以方便后续的计算。

再遍历可能的 $t$：对于每个可能的 $t$，使得 $9\times t < n - 1$。这个 $t$ 是一个关键参数，用于确定四元组的范围。

然后遍历可能的 $a$：对于每个 $a$，使得 $a \times 9 \times t + 1 < n$。这个 $a$ 是四元组中的最小值。

最后统计满足条件的四元组，在内层循环中，统计满足条件的四元组数量，并更新答案数组。

用这样的思路，这道题写代码就非常简单了。

下面是按照上面的步骤写出的代码。

AC 代码

#include<bits/stdc++.h>
using namespace std;
int n, m, cnt[16000], x[41000], ans[40000][5];
int main(){
	cin >> n >> m;
	for(int i = 1;i <= m;i++){
		cin >> x[i];
		cnt[x[i]]++; // 统计每个魔法值出现的次数
	}
	for(int t = 1;9 * t <= n;t++){ // 遍历可能的 t
		int res = 0, a, b, c, d;
		for(a = n - 9 * t - 1;a > 0;a--){ // 遍历可能的 a
			b = a + 2 * t; // 计算对应的 b
			c = a + 8 * t + 1; // 计算对应的 c
			d = a + 9 * t + 1; // 计算对应的 d
			res += cnt[c] * cnt[d]; // 统计满足条件的四元组数量
			ans[a][0] += cnt[b] * res; // 更新答案
			ans[b][1] += cnt[a] * res; // 更新答案
		}
		res = 0;
		for(d = 9 * t + 2;d <= n;d++){ // 第二次操作，同上
			a = d - 9 * t - 1; 
			b = d - 7 * t - 1;
			c = d - t;
			res += cnt[a] * cnt[b];
			ans[c][2] += cnt[d] * res;
			ans[d][3] += cnt[c] * res;
		}
	}
	for(int i = 1;i <= m;i++){
		for(int j = 0;j < 4;j++){
			cout << ans[x[i]][j] << ' ';
		}
		cout << endl;
	}
	return 0;
}

AC 记录：https://www.luogu.com.cn/record/218437099。