NOIP2016 普及组 - 魔法阵 - 算法详解与代码实现

NOIP2016 普及组 - 魔法阵 - 算法详解与代码实现

题目背景

NOIP2016 普及组 T4

题目描述

六十年一次的魔法战争就要开始了，大魔法师准备从附近的魔法场中汲取魔法能量。

大魔法师有 'm' 个魔法物品，编号分别为 '1,2,...,m'。每个物品具有一个魔法值，我们用 'X_i' 表示编号为 'i' 的物品的魔法值。每个魔法值 'X_i' 是不超过 'n' 的正整数，可能有多个物品的魔法值相同。

大魔法师认为，当且仅当四个编号为 'a,b,c,d' 的魔法物品满足 'X_a<X_b<X_c<X_d,X_b-X_a=2(X_d-X_c)'，并且 'X_b-X_a<(X_c-X_b)/3' 时，这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这个魔法阵的 'A' 物品，'B' 物品，'C' 物品，'D' 物品。

现在，大魔法师想要知道，对于每个魔法物品，作为某个魔法阵的 'A' 物品出现的次数，作为 'B' 物品的次数，作为 'C' 物品的次数，和作为 'D' 物品的次数。

输入格式

第一行包含两个空格隔开的正整数 'n,m'。

接下来 'm' 行，每行一个正整数，第 'i+1' 行的正整数表示 'X_i'，即编号为 'i' 的物品的魔法值。

保证 '1 ≤ n ≤ 15000'，'1 ≤ m ≤ 40000'，'1 ≤ X_i ≤ n'。每个 'X_i' 是分别在合法范围内等概率随机生成的。

输出格式

共 'm' 行，每行 '4' 个整数。第 'i' 行的 '4' 个整数依次表示编号为 'i' 的物品作 为 'A,B,C,D' 物品分别出现的次数。

保证标准输出中的每个数都不会超过 '10^9'。每行相邻的两个数之间用恰好一个空格隔开。

样例 #1

样例输入 #1

30 8
1
24
7
28
5
29
26
24

样例输出 #1

4 0 0 0
0 0 1 0
0 2 0 0
0 0 1 1
1 3 0 0
0 0 0 2
0 0 2 2
0 0 1 0

样例 #2

样例输入 #2

15 15
1 
2 
3 
4 
5
6 
7 
8 
9
10
11
12
13
14
15

样例输出 #2

5 0 0 0
4 0 0 0
3 5 0 0
2 4 0 0
1 3 0 0
0 2 0 0
0 1 0 0
0 0 0 0
0 0 0 0
0 0 1 0
0 0 2 1
0 0 3 2
0 0 4 3
0 0 5 4
0 0 0 5

提示

【样例解释 1】

共有 5 个魔法阵，分别为：

• 物品 1,3,7,6，其魔法值分别为 1,7,26,29；
• 物品 1,5,2,7，其魔法值分别为 1,5,24,26；
• 物品 1,5,7,4，其魔法值分别为 1,5,26,28；
• 物品 1,5,8,7，其魔法值分别为 1,5,24,26；
• 物品 5,3,4,6，其魔法值分别为 5,7,28,29。

以物品 5 为例，它作为 'A' 物品出现了 1 次，作为 'B' 物品出现了 3 次，没有作为 'C' 物品或者 'D' 物品出现，所以这一行输出的四个数依次为 1,3,0,0。

此外，如果我们将输出看作一个 'm' 行 '4' 列的矩阵，那么每一列上的 'm' 个数之和都应等于魔法阵的总数。所以，如果你的输出不满足这个性质，那么这个输出一定不正确。你可以通过这个性质在一定程度上检查你的输出的正确性。

【数据规模】

代码实现 (C++)

#include <iostream>
#include <vector>
#include <map>
#include <algorithm>
using namespace std;

int main() {
    int n, m;
    cin >> n >> m;
    vector<int> X(m);
    for (int i = 0; i < m; i++) {
        cin >> X[i];
    }
    
    // 统计每个魔法值出现的次数
    map<int, int> count;
    for (int i = 0; i < m; i++) {
        count[X[i]]++;
    }
    
    // 遍历每个魔法值
    for (int i = 0; i < m; i++) {
        int A = X[i];
        int countA = count[A];
        int countB = 0, countC = 0, countD = 0;
        
        // 遍历比A大的魔法值B
        for (int B = A + 1; B <= n; B++) {
            // 计算魔法阵的条件是否满足
            if (count.count(B) > 0) {
                int countB2 = count[B];
                int C = 2 * B - A;
                int D = 2 * C - B;
                if (count.count(C) > 0 && count.count(D) > 0) {
                    int countC2 = count[C];
                    int countD2 = count[D];
                    // 更新B, C, D的统计结果
                    countB += countB2;
                    countC += countC2;
                    countD += countD2;
                }
            }
        }
        
        cout << countA << " " << countB << " " << countC << " " << countD << endl;
    }
    
    return 0;
}

算法分析

1. 统计魔法值出现次数： 使用 map 容器存储每个魔法值及其出现的次数，便于快速查询。
2. 遍历每个魔法值： 依次遍历每个魔法物品的魔法值 'A'。
3. 枚举 'B' 物品： 从 'A+1' 开始枚举比 'A' 大的魔法值 'B'，并判断 'B' 是否存在。
4. 计算 'C' 和 'D' 物品： 依据魔法阵的条件，计算出对应的 'C' 和 'D' 物品魔法值。
5. 判断 'C' 和 'D' 是否存在： 检查 'C' 和 'D' 是否在 map 中，判断是否存在对应的魔法物品。
6. 统计次数： 若 'C' 和 'D' 都存在，则表示找到了一个魔法阵，更新 'B'、'C' 和 'D' 物品的统计次数。
7. 输出结果： 输出每个魔法物品作为 'A'、'B'、'C' 和 'D' 物品分别出现的次数。

总结

本文对 NOIP2016 普及组 T4 魔法阵 问题进行了详细的算法解析，并提供了 C++ 代码实现。通过代码注释和逐步解释，帮助读者理解算法的关键步骤和实现细节。

希望本文能为读者解决类似问题提供参考和帮助。