题解 | 魔法阵-NOIP2016普及组复赛A题

题目描述

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

大魔法师有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<(xc-xb)/3时，这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这个魔法阵的A物品，B物品，C物品，D物品。

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

输入描述:

输入文件的第一行包含两个空格隔开的正整数n和m。
接下来m行，每行一个正整数，第i+1行的正整数表示xi，即编号为i的物品的魔法值。
保证 1 ≤ n ≤ 15000 , 1 ≤ m ≤ 40000 , 1 ≤ Xi ≤ n 。每个 $x_i$ 是分别在合法范围内等概率随机生成的。

输出描述:

共输出m行，每行四个整数。第i行的四个整数依次表示编号为i的物品作为A,B,C,D物品分别出现的次数。
保证标准输出中的每个数都不会超过 $10^9$ 。
每行相邻的两个数之间用恰好一个空格隔开。

示例1

输入

30 8
1
24
7
28
5
29
26
24

输出

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

说明

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

示例2

输入

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

输出

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

备注:

解答

首先可以发现每个x都小于n，而n最大值只是15000，所以可以开一个桶来存每个魔法值出现的次数

回忆一下3个约束条件

$xa<xb<xc<xd$ ①

$xb−xa=2(xd−xc)$ ②

$xb−xa<(xc−xb)/3$ ③

现在魔改一下这三个式子

设 $t=xd−xc$

所以②可化为 $xb−xa=2t$ ④

将④代入③

$2t<(xc−xb)/3$

移项一下，就变成

$6t<xc−xb$ ⑤

再魔改一下

设 $6t+k=xc−xb$ （就是把差的部分补上去）

于是可以画出来一个图

显然，A的最小值为1，D的最大值为n

由图可得 $AD=9t+k$

所以我们可以尝试着枚举t，用t来表示各个魔法值的值

由上易得t的范围为 $1\leq t\leq(n−1)/9$

再枚举D，因为我们已经枚举出了t，所以C的值是可以直接算出来的

$C=D−t$

又因为使A,B,C,D满足条件的k的最小值为1，所以对于当前的C和D，最大的A和B为 $A=D−9t−1,B=D−7t−1$

那么如果A和B更小怎么办？

观察到在其他条件不变的情况下，只要CC和BB满足 $Xc−Xb>6t$ ，那么这个魔法阵就一定成立，所以当 $(a1<a2,b1<b2)$ 时，只要a2和b2能够和C,D组成魔法阵，a1,b1也一定能和C,D组成魔法阵，所以可以使用前缀和优化

然后又由乘法原理可得，当前魔法值作为DD物品的个数为 $SumD=SumA\times SumB\times SumC$

所以我们利用前缀和优化 $SumA\times SumB$

C的情况可以顺便在算D的时候算出来

那么还有一个问题是，我们枚举的D的范围是多少？

因为要统计前缀和，所以一定是要顺推下去的，由上面那张图我们可以知道，D的最大值为n，最小值则为当k=1且A=1的时候，所以D的最小值为 $9∗t+2$ ，再小是无法组成魔法阵的

同理可以枚举A

但是这个的情况又和枚举D的情况有一点不同

在其他条件不变的情况下，只要C和B满足 $Xc−Xb>6t$ ，那么这个魔法阵就一定成立，所以当 $(c1<c2,d1<d2)$ 时，只要c1和d1能够和A,B组成魔法阵，c2,d2也一定能和A,B组成魔法阵，所以可以使用后缀和优化

因为需要统计后缀和，所以需要逆推

枚举的范围：A的最大值为 $(n−t\times9−1)$ (因为当k=1，D=n的时候A才最大)，A的最小值则为1

所以就可以算出每个魔法值作为A,B,C,D物品的次数了，输出时直接输出当前魔法物品的魔法值的次数就可以了

代码：

#include<bits/stdc++.h>
using namespace std;
const int MAXN=15000+10;
const int MAXM=40000+10;
int n,m;
int x[MAXM],v[MAXN];
int a[MAXN],b[MAXN],c[MAXN],d[MAXN];
inline int read()
{
    int tot=0;
    char c=getchar();
    while(c<'0'||c>'9')
        c=getchar();
    while(c>='0'&&c<='9')
    {
        tot=tot*10+c-'0';
        c=getchar();
    }
    return tot;
}
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        x[i]=read();
        v[x[i]]++;
    }
    for(int t=1;t<=(n-1)/9;t++)
    {
        int sum=0;
        for(int D=9*t+2;D<=n;D++)
        {
            int A=D-9*t-1,B=D-7*t-1,C=D-t;
            sum+=v[A]*v[B];
            c[C]+=v[D]*sum;
            d[D]+=v[C]*sum;
        }
        sum=0;
        for(int A=n-9*t-1;A>=1;A--)
        {
            int B=A+2*t,C=8*t+1+A,D=9*t+1+A;
            sum+=v[C]*v[D];
            a[A]+=v[B]*sum;
            b[B]+=v[A]*sum;
        }
    }
    for(int i=1;i<=m;i++)
    cout<<a[x[i]]<<" "<<b[x[i]]<<" "<<c[x[i]]<<" "<<d[x[i]]<<endl;
    return 0;
}

来源：hulean