线上OJ：
一本通：http://ybt.ssoier.cn:8088/problem_show.php?pid=1976 (opens in a new tab)
AcWing：https://www.acwing.com/solution/content/139842/ (opens in a new tab)
洛谷：https://www.luogu.com.cn/problem/P2119 (opens in a new tab)
本题作为第四题，想拿满分有难度。但是暴力拿些分还是做得到的。
满分需要用 前缀和 来化简for循环。
核心语句：
①
②
③
核心思想：
由于魔法值 n 不超过 15000，但魔法球的数量 m 可达到40000。
所以选择反向枚举答案：即对所有的魔法值进行枚举（先找出 n 范围内所有符合上述三个公式的魔法组合数字），这样可避免对魔法球进行排序。
另外，由于魔法球的魔法数值可能相同，所以在计算每一个数字的出现次数时，要考虑其他数字的 组合 出现情况。如下图所示：
上图中，1# 魔法球在物品A中出现的次数为6次，分别为：
1#，2#，3#，4#
1#，2#，7#，4#
1#，2#，9#，4#
1#，6#，3#，4#
1#，6#，7#，4#
1#，6#，9#，4#
所以每一个魔法球在某个位置出现的 次数 = 剩余位置魔法球数量的乘积（组合思想）
题解代码：
解法一、
解法一、（反向枚举的暴力代码 - 70% 分数）：
#include <bits/stdc++.h>
#define MAXN 40005
using namespace std;
struct Node
{
int val, id; // 存储节点的值和 id。 id用于最终的输出
};
Node node[MAXN];
int n, m; // m 个魔法物； 魔法值不超过 n
int ge[MAXN]; // 记录val为i的魔法物的个数。用于计算组合
int cnta[MAXN], cntb[MAXN], cntc[MAXN], cntd[MAXN]; // cnta[i]表示val为i的魔法物在A位置出现的次数
// cntb[i]表示val为i的魔法物在B位置出现的次数, cntc[i]表示val为i的魔法物在C位置出现的次数 等
// 暴力枚举 70% 分数。
int main()
{
scanf("%d%d",&n, &m);
int x;
for(int i = 1; i <= m; i++)
{
scanf("%d", &x);
node[i].val = x;
node[i].id = i;
ge[x]++; // 统计魔法值为x的物品个数
}
// 反向枚举结果：对所有的魔法值进行枚举（即先找出 n 范围内所有符合要求的魔法组合数字），可避免排序。
// 不是对每个魔法球的魔法值进行枚举（每一轮都是枚举40000和枚举15000的区别）
for(int ai = 1; ai <= n - 3; ai++)
for(int bi = ai + 1; bi <= n - 2; bi++)
for(int ci = bi + 1; ci <= n - 1; ci++)
for(int di = ci + 1; di <= n; di++)
if( ( (bi-ai) == 2*(di-ci) ) && ( 3*(bi-ai) < (ci-bi) ) )
{ // 如果找到一组符合要求的魔法值，则更新各数字在对应位置出现的次数
// 考虑到不同的魔法球会有相同的魔法值，所以在作组合计算时对其余位置作数量的乘法
cnta[ai] += ge[bi] * ge[ci] * ge[di];
cntb[bi] += ge[ai] * ge[ci] * ge[di];
cntc[ci] += ge[ai] * ge[bi] * ge[di];
cntd[di] += ge[ai] * ge[bi] * ge[ci];
break; // 1个abc只能对应1个d，如果找到了，直接退出循环
}
for(int i = 1; i <= m; i++)
{
int t = node[i].val;
printf("%d %d %d %d\n",cnta[t], cntb[t], cntc[t], cntd[t]);
}
return 0;
}以上暴力代码比较简单，只要注意 反向枚举，就可以在考场上快速拿到70%的分数。