复赛四：魔法阵(magic)

洛谷：P2119
OJ：I2119

条件转换：

这段代码的目标是统计每个魔法物品分别作为四元组中的 A、B、C、D 物品出现的次数。题目中给定了一些特定条件，四个物品编号分别是 a, b, c, d，它们对应的魔法值分别为 xa, xb, xc, xd，要求：

1. x_a < x_b < x_c < x_d
2. (x_b – x_a = 2 * (x_d – x_c)
3. x_b – x_a < (x_c – x_b)/3

第一个条件告诉我们，选择的四元组必须是一个严格递增的。

对于后两个条件，先转换成数学模型，不难发现其中X_d−X_c是最小的单位，所以我们可以令t=X_d−X_c​，则整理式子后可以写成：

X_d−X_c=t
X_b−X_a=2t
X_c−X_b>6t

X_d-X_a>9t

X_a的最小值为1，_Xd的最大值为n，所以我们可以尝试着枚举t，用t来表示各个魔法值的值。

桶排序：

由于魔法值的范围是有限的（小于等于 n），可以用桶排序来统计每个魔法值的出现次数。这样可以有效应对相同魔法值出现多次的情况，利用乘法原理直接计算这些组合。

前缀和：

为了避免重复计算，前缀和的引入能帮助我们快速累积已经计算过的部分。在每次计算时，利用已经处理的值来减少重复计算的开销，这样可以加速整个过程。

代码通过两次扫描处理所有可能的四元组，具体解题逻辑如下：

1. 输入处理与初始化

首先，代码通过 cin 读取两个整数 n 和 m，分别表示魔法值的范围和物品的数量。接着读取每个物品的魔法值，并存入 val 数组中，同时使用 num 数组来记录每个魔法值的出现次数。

2. 主逻辑

主逻辑使用了两个嵌套循环，分别从两个方向（前向和反向）进行累加，统计符合条件的四元组。这里的倍数关系是通过变量 i 来控制。

2.1 前向遍历

通过 for (int i = 1; i * 9 + 1 <= n; i++)，代码在每次遍历中根据魔法值差值的倍数关系来计算四元组：

• 内层循环：从 j = i * 9 + 2 开始遍历，通过累加 num[j-7*i-1] 和 num[j-9*i-1]，逐步增加 sum 值，表示可能的四元组组合。
• 对于每个满足条件的 j，更新 c[j-i] 和 d[j]，分别表示 j 作为 C 物品和 D 物品的次数。

2.2 反向遍历

通过 for (int j = n - i * 9 - 1; j >= 1; j--)，代码进行反向遍历：

• 内层循环：通过 num[j+i*9+1] 和 num[j+i*8+1] 来计算反向的累积和 sum。
• 对每个符合条件的 j，更新 a[j] 和 b[j+2*i]，分别表示 j 作为 A 物品和 B 物品的次数。

3. 输出结果

代码最后通过遍历 val 数组，输出每个物品的四种角色出现次数，即 a[val[i]]、b[val[i]]、c[val[i]] 和 d[val[i]]，分别表示该物品作为 A、B、C、D 出现的次数。

代码逻辑分析

1. 主循环的逻辑：

• 外层循环中的 i 控制了魔法物品之间的倍数关系，并通过内层循环处理每个可能的组合。
• sum 变量在前向和反向遍历时被逐步累加，用来记录符合条件的组合对数。

1. 满足题目条件的四元组：

• 代码通过控制倍数关系来确保 xa < xb < xc < xd，并且通过内层的多重累加逻辑满足其他两个条件：xb - xa = 2 * (xd - xc) 和 xb - xa < (xc - xb)/3。

1. 时间复杂度：

• 外层循环的次数受 n 的限制，最多进行 O(n) 次操作。
• 内层循环最多进行 O(m) 次操作，因此整体的时间复杂度约为 O(m * n)，虽然该算法能处理较大规模的输入，但在某些极限情况下可能性能不足。

代码实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48

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

int n, m;
vector<int> val(40010), num(15010);
vector<int> a(15010), b(15010), c(15010), d(15010);

int main() {
    freopen("magic.in","r",stdin);
    freopen("magic.out","w",stdout);
    // 输入 n 和 m
    cin >> n >> m;

    // 统计每个魔法值的出现次数
    for (int i = 1; i <= m; i++) {
        cin >> val[i];
        num[val[i]]++;
    }

    // 主循环，遍历可能的倍数关系
    for (int i = 1; i * 9 + 1 <= n; i++) {
        int sum = 0;
        
        // 前向遍历，统计符合条件的 c 和 d 角色的数量
        for (int j = i * 9 + 2; j <= n; j++) {
            sum += num[j - 7 * i - 1] * num[j - 9 * i - 1];
            c[j - i] += num[j] * sum;
            d[j] += num[j - i] * sum;
        }
        
        sum = 0;
        
        // 反向遍历，统计符合条件的 a 和 b 角色的数量
        for (int j = n - i * 9 - 1; j >= 1; j--) {
            sum += num[j + i * 9 + 1] * num[j + i * 8 + 1];
            a[j] += num[j + 2 * i] * sum;
            b[j + 2 * i] += num[j] * sum;
        }
    }

    // 输出每个魔法物品作为 A、B、C、D 出现的次数
    for (int i = 1; i <= m; i++) {
        cout << a[val[i]] << " " << b[val[i]] << " " << c[val[i]] << " " << d[val[i]] << endl;
    }

    return 0;
}