线上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%的分数。