复赛四:魔法阵(magic)

洛谷:P2119
OJ:I2119

条件转换:

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

  1. xa < xb < xc < xd
  2. (xb – xa = 2 * (xd – xc)
  3. xb – xa < (xc – xb)/3

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

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

Xd−Xc=t
Xb−Xa=2t
Xc−Xb>6t

Xd-Xa>9t

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

桶排序

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

前缀和

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

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

1. 输入处理与初始化

首先,代码通过 cin 读取两个整数 nm,分别表示魔法值的范围和物品的数量。接着读取每个物品的魔法值,并存入 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]],分别表示该物品作为 ABCD 出现的次数。

代码逻辑分析

  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;
}
Scroll to Top