[NOIP 2016 普及组] 魔法阵

GitHub 跳转原题关系图返回列表

固定差值 q，把四元组化成左右两类值对，再用前缀累计和后缀累计统计四种位置贡献。

OJ: luogu

题目 ID: P2119

难度:普及+/提高

标签:数学计数枚举推导noip

日期: 2026-06-20 12:30

题意

有 m 个魔法物品，第 i 个物品的魔法值是 X_i，且 1 <= 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 出现的次数。

思路

先看一个可以直接验证想法的朴素解：

cpp

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
49
50
51
52
53// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

const int MAXM = 205;

int n, m;
int x[MAXM];
long long ans_a[MAXM], ans_b[MAXM], ans_c[MAXM], ans_d[MAXM];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x[i];
    }

    // 直接枚举四个不同的物品，按定义判断是否构成魔法阵。
    // 复杂度 O(m^4)，只适合很小的数据，但逻辑最直接。
    for (int a = 1; a <= m; a++) {
        for (int b = 1; b <= m; b++) {
            if (b == a) continue;
            for (int c = 1; c <= m; c++) {
                if (c == a || c == b) continue;
                for (int d = 1; d <= m; d++) {
                    if (d == a || d == b || d == c) continue;

                    int xa = x[a];
                    int xb = x[b];
                    int xc = x[c];
                    int xd = x[d];

                    if (!(xa < xb && xb < xc && xc < xd)) continue;
                    if (xb - xa != 2 * (xd - xc)) continue;
                    if (xb - xa >= (xc - xb) / 3.0) continue;

                    ans_a[a]++;
                    ans_b[b]++;
                    ans_c[c]++;
                    ans_d[d]++;
                }
            }
        }
    }

    for (int i = 1; i <= m; i++) {
        cout << ans_a[i] << ' ' << ans_b[i] << ' ' << ans_c[i] << ' ' << ans_d[i] << '\n';
    }

    return 0;
}

这个暴力做法直接枚举四个物品，复杂度是 $O(m^4)$ ，只能用于小数据或对拍。

关键在于把条件改写成更适合计数的形式。

设 q = X_d - X_c，由题意可得：

X_b - X_a = 2q
X_b = X_a + 2q
X_d = X_c + q

第三个条件继续化简：

2q < (X_c - X_a - 2q) / 3
X_c - X_a > 8q

由于都是整数，所以等价于：

X_c >= X_a + 8q + 1

于是一个合法四元组的值一定长成：

A = a
B = a + 2q
C = c
D = c + q
c >= a + 8q + 1

这样就可以按值来统计，而不是按物品四元组来枚举。

记 cnt[v] 为魔法值等于 v 的物品个数。

对固定的 q：

左边的 A-B 值对 (a, a+2q) 可以产生 cnt[a] * cnt[a+2q] 种选择；
右边的 C-D 值对 (c, c+q) 可以产生 cnt[c] * cnt[c+q] 种选择。

接下来只剩下一个连接条件：

c >= a + 8q + 1

这说明：

如果固定左边 (a, a+2q)，我们需要知道右边从 a + 8q + 1 开始有多少个合法 C-D 值对，适合做后缀累计；
如果固定右边 (c, c+q)，我们需要知道左边到 c - 8q - 1 为止有多少个合法 A-B 值对，适合做前缀累计。

所以对每个 q：

从右往左预处理 suffix_pair[c] = sum(cnt[i] * cnt[i+q])；
从左往右扫描 c，同步维护已经合法的 prefix_pair = sum(cnt[a] * cnt[a+2q])；
用 prefix_pair 更新当前值作为 C,D 的贡献；
用 suffix_pair[c + 8q + 1] 更新当前值作为 A,B 的贡献。

由于题目中的判定只和魔法值有关，所以同魔法值的物品答案完全相同。最后按输入顺序输出对应魔法值的统计结果即可。

代码

cpp

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
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89#include <bits/stdc++.h>
using namespace std;

const int MAXN = 100000 + 5;

int n, m;
int x[MAXN];          // 第 i 个物品的魔法值
long long cnt[MAXN];  // cnt[v] 表示魔法值等于 v 的物品个数

long long ans_a[MAXN]; // ans_a[v]：魔法值为 v 的物品，作为 A 出现的次数
long long ans_b[MAXN]; // ans_b[v]：魔法值为 v 的物品，作为 B 出现的次数
long long ans_c[MAXN]; // ans_c[v]：魔法值为 v 的物品，作为 C 出现的次数
long long ans_d[MAXN]; // ans_d[v]：魔法值为 v 的物品，作为 D 出现的次数

long long suffix_pair[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        cin >> x[i];
        cnt[x[i]]++;
    }

    // 设 q = Xd - Xc，则 Xb - Xa = 2q。
    // 因为 Xb - Xa < (Xc - Xb) / 3，
    // 代入 Xb = Xa + 2q 后可化成：Xc - Xa > 8q。
    // 由于都是整数，所以等价为：Xc >= Xa + 8q + 1。
    //
    // 于是一个合法魔法阵的值一定长成：
    // Xa = a, Xb = a + 2q, Xc = c, Xd = c + q，且 c >= a + 8q + 1。
    //
    // 对固定 q：
    // 1. 先统计所有 (c, c + q) 这类 C-D 值对，做成后缀和；
    // 2. 再从左到右维护所有满足 a <= c - 8q - 1 的 A-B 值对前缀和。
    int max_q = (n - 1) / 9;
    for (int q = 1; q <= max_q; q++) {
        int max_c = n - q;

        // suffix_pair[c] = sum_{i >= c} cnt[i] * cnt[i + q]
        suffix_pair[max_c + 1] = 0;
        for (int c = max_c; c >= 1; c--) {
            suffix_pair[c] = suffix_pair[c + 1] + cnt[c] * cnt[c + q];
        }

        long long prefix_pair = 0; // 当前已经加入的所有 cnt[a] * cnt[a + 2q] 之和
        int next_a = 1;

        for (int c = 1; c <= max_c; c++) {
            int limit_a = c - 8 * q - 1;

            // 把所有满足 a <= c - 8q - 1 的 A-B 值对加入前缀。
            while (next_a <= limit_a && next_a + 2 * q <= n) {
                prefix_pair += cnt[next_a] * cnt[next_a + 2 * q];
                next_a++;
            }

            long long right_pair = cnt[c] * cnt[c + q];
            if (right_pair != 0 && prefix_pair != 0) {
                // 当前值 c 作为 C，值 c + q 作为 D。
                ans_c[c] += cnt[c + q] * prefix_pair;
                ans_d[c + q] += cnt[c] * prefix_pair;
            }

            // 反过来，统计值 c 作为 A、值 c + 2q 作为 B 时，右侧能配多少组 C-D。
            if (c + 2 * q <= n) {
                int first_c = c + 8 * q + 1;
                if (first_c <= max_c) {
                    long long right_sum = suffix_pair[first_c];
                    if (right_sum != 0) {
                        ans_a[c] += cnt[c + 2 * q] * right_sum;
                        ans_b[c + 2 * q] += cnt[c] * right_sum;
                    }
                }
            }
        }
    }

    // 题目要求按物品输出。由于公式只依赖物品的魔法值，
    // 所以同魔法值的物品答案完全相同，直接按 x[i] 取即可。
    for (int i = 1; i <= m; i++) {
        int v = x[i];
        cout << ans_a[v] << ' ' << ans_b[v] << ' ' << ans_c[v] << ' ' << ans_d[v] << '\n';
    }

    return 0;
}

复杂度

设 q 的枚举上界为 Q，则 Q = (n - 1) / 9。

每个 q 只做两次线性扫描，所以总时间复杂度是 $O(nQ)$ ，空间复杂度是 $O(n)$ 。

总结

这道题的难点不在实现，而在于先把四元组条件改写成固定 q 的值对关系。

一旦得到：

左边是 (a, a+2q)
右边是 (c, c+q)
中间满足 c >= a + 8q + 1

整题就可以自然地转成“前缀统计左值对，后缀统计右值对”的计数题。

P2119 [NOIP 2016 普及组] 魔法阵

题目背景

NOIP2016 普及组 T4

题目描述

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

大魔法师有 $m$ 个魔法物品，编号分别为 $1,2,\ldots,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 \le n \le 15000$ ， $1 \le m \le 40000$ ， $1 \le X_i \le n$ 。每个 $X_i$ 是分别在合法范围内等概率随机生成的。

输出格式

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

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

输入输出样例 #1

输入 #1

text

输出 #1

text

输入输出样例 #2

输入 #2

text

输出 #2

text

说明/提示

【样例解释 $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$ 个数之和都应等于魔法阵的总数。所以，如果你的输出不满足这个性质，那么这个输出一定不正确。你可以通过这个性质在一定程度上检查你的输出的正确性。

【数据规模】

[NOIP 2016 普及组] 魔法阵

目录

题意

思路

代码

复杂度

总结