♐ CSP_J 组真题
2016年
4. 魔法阵

线上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循环。

核心语句:

xa<xb<xc<xdx_a < x_b < x_c < x_d
xbxa=2(xdxc)x_b - x_a = 2(x_d - x_c)
xbxa<(xcxb)/3x_b - x_a < (x_c - x_b)/3

核心思想:

由于魔法值 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%的分数。