洛谷:P2119
OJ:I2119
条件转换:
这段代码的目标是统计每个魔法物品分别作为四元组中的 A、B、C、D 物品出现的次数。题目中给定了一些特定条件,四个物品编号分别是 a, b, c, d
,它们对应的魔法值分别为 xa, xb, xc, xd
,要求:
第一个条件告诉我们,选择的四元组必须是一个严格递增的。
对于后两个条件,先转换成数学模型,不难发现其中Xd−Xc是最小的单位,所以我们可以令t=Xd−Xc,则整理式子后可以写成:
Xd−Xc=t
Xb−Xa=2t
Xc−Xb>6t
Xd-Xa>9t
Xa的最小值为1,Xd的最大值为n,所以我们可以尝试着枚举t,用t来表示各个魔法值的值。
桶排序:
由于魔法值的范围是有限的(小于等于 n
),可以用桶排序来统计每个魔法值的出现次数。这样可以有效应对相同魔法值出现多次的情况,利用乘法原理直接计算这些组合。
前缀和:
为了避免重复计算,前缀和的引入能帮助我们快速累积已经计算过的部分。在每次计算时,利用已经处理的值来减少重复计算的开销,这样可以加速整个过程。
代码通过两次扫描处理所有可能的四元组,具体解题逻辑如下:
首先,代码通过 cin
读取两个整数 n
和 m
,分别表示魔法值的范围和物品的数量。接着读取每个物品的魔法值,并存入 val
数组中,同时使用 num
数组来记录每个魔法值的出现次数。
主逻辑使用了两个嵌套循环,分别从两个方向(前向和反向)进行累加,统计符合条件的四元组。这里的倍数关系是通过变量 i
来控制。
通过 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
物品的次数。通过 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
物品的次数。代码最后通过遍历 val
数组,输出每个物品的四种角色出现次数,即 a[val[i]]
、b[val[i]]
、c[val[i]]
和 d[val[i]]
,分别表示该物品作为 A
、B
、C
、D
出现的次数。
i
控制了魔法物品之间的倍数关系,并通过内层循环处理每个可能的组合。sum
变量在前向和反向遍历时被逐步累加,用来记录符合条件的组合对数。xa < xb < xc < xd
,并且通过内层的多重累加逻辑满足其他两个条件:xb - xa = 2 * (xd - xc)
和 xb - xa < (xc - xb)/3
。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; } |