[NOIP2016 普及组] 魔法阵

题目背景

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 Xi \le n$。每个 $X_i$ 是分别在合法范围内等概率随机生成的。

输出格式

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

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

样例 #1

样例输入 #1

30 8
1
24
7
28
5
29
26
24

样例输出 #1

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

样例 #2

样例输入 #2

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

样例输出 #2

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

提示

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

【数据规模】

题目分析

阅读题目，可知题目要求的是，每件物品作为A,B,C,D物品分别出现的次数。

四个元素需要满足的条件为：

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$

条件1表明元素严格单调递增。我们可将元素先进行排序和去重。之后枚举出所有的四元组合，统计各组合中元素出现的个数。

但是统计过程中需要注意的问题是会出现重复的元素。对应位置数值的次数为该数值出现在对应位置的组合数的数量，利用乘法原理可得到组合数量为其他三个元素的出现次数的乘积。

for(int ai=1;ai<=mm;ai++){
    for(int bi=ai+1;bi<=mm;bi++){
        for(int ci=bi+1;ci<=mm;ci++){
            for(int di=ci+1;di<=m;di++){
                if(满足 条件2 和 条件3)｛
                    cnta[x[ai]]+=cnt[x[bi]]*cnt[x[ci]]*cnt[x[di]];
                    cntb[x[bi]]+=cnt[x[ai]]*cnt[x[ci]]*cnt[x[di]];
                    cntc[x[ci]]+=cnt[x[ai]]*cnt[x[bi]]*cnt[x[di]];
                    cntd[x[di]]+=cnt[x[ai]]*cnt[x[bi]]*cnt[x[ci]];
                ｝
            }
        }
    }
}

此时时间复杂为$\Theta(n^4)$,只能获得一部分的分数。

此时尝试对暴力枚举的方式进行优化。首先可以减少枚举的对象，根据条件2，可发现$x_d=\frac{x_b-x_a}{2}+x_c$ 。

那么只需要三重循环即可实现，时间复杂度降为$\Theta(n^3)$ 。

for(int i=1;i<=m;i++){
    for(int j=i+1;j<=m;j++){
        if((x[j]-x[i])%2!=0) continue;//不满足条件2
        for(int k=j+1;k<=m;k++){
            int d=x[k]+(x[j]-x[i])/2;//求出元素d
            if(d<=x[k] || cnt[d]==0 ) continue;//四个数非递增或求出的d不存在则不符合
            if(3*(x[j]-x[i])>=x[k]-x[j]) continue;//不符合条件3

            int num=cnt[x[i]]*cnt[x[j]]*cnt[x[k]]*cnt[d];
            cnta[x[i]]+=num/cnt[x[i]];
            cntb[x[j]]+=num/cnt[x[j]];
            cntc[x[k]]+=num/cnt[x[k]];
            cntd[d]+=num/cnt[d];
        }
    }
}

可过17个测试点。

优化

再次尝试进行优化。仔细观察对应的三个条件。

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$

我们设$t=X_d - X_c$ 。

1. $X_a<X_b<X_c<X_d$

2. $X_b-X_a=2t$

3. $2t<(X_c-X_b)/3$

整理一下，可得到这些关系描述。

1. $X_a<X_b<X_c<X_d$
2. $X_b=X_a+2t$
3. $X_d=X_c+t$
4. $X_c-X_b > 6t$

此时，我们可以枚举t可能出现的值。在确定t的基础上，探讨、确定d的值，从而确定可能的c、d组合的元素值和数量。 再确定a的值，从而确定a、b组合的元素值和数量。

数值的范围为n，所以得到如下的大小关系。

可发现，因为严格递增，所以t最小为1。$d=a+9t+k,k>=1$ 。所以$d\le n$即$9t\le n-2$ 。

a最小为1，所以$9t+2\le d \le n$ 。

此时

• $c=d-t$ 。

确定d、t后，c的值就能固定下来。但a、b的值由于k的不固定，会存在多组。

• $a=d-9t-k$
• $b=a+2t$

$k\ge 1$ ，所以a、b最大的一组为

• $a=d-9t-1$
• $b=a+2t$

对于任意一组四元组,a,b,c,d。根据乘法原理，c,d的次数可以表示为：

$ans_c=cnt_a\times cnt_b\times cnt_d$

$ans_d=cnt_a\times cnt_b\times cnt_c$

若存在m组可行的a、b。对于已固定值的c、d，它们的次数可表示为：
$$ans_c=cnt_{a_1}\times cnt_{b_1}\times cnt_d+\cdots +cnt_{a_m}\times cnt_{b_m}\times cnt_d$$

$$ans_c= \sum_{i=1}^{m}cnt_{a_i}\times cnt_{b_i}\times cnt_d$$

$$ans_d =cnt_{a_1}\times cnt_{b_1}\times cnt_c+\cdots +cnt_{a_m}\times cnt_{b_m}\times cnt_c$$

$$ans_d= \sum_{i=1}^{m}cnt_{a_i}\times cnt_{b_i}\times cnt_c$$

那么所有的a、b组进行前缀和处理即可。

同理，若固定t、a,即可确定a、b的数值，c、d会存在多组。需要注意的是，c、d在a、b的右侧，进行求和需要从右向左，后缀和思想。

for(int t=1;t*9<=(n-1);t++){//遍历 t
    int sum=0;//a与b 组合的个数
    for(int d=t*9+2;d<=n;d++){//遍历 d 的数值
        int a=d-9*t-1;
        int b=a+2*t;
        int c=d-t;
        sum+=cnt[a]*cnt[b];// 统计a,b组合的个数
        cntc[c]+=sum*cnt[d];
        cntd[d]+=sum*cnt[c];
    }

    sum=0;//c,d组合的个数
    for(int a=n-9*t-1;a>=1;a--){//注意顺序
        int b=a+t*2;
        int d=a+9*t+1;
        int c=d-t;
        sum+=cnt[c]*cnt[d];
        cnta[a]+=sum*cnt[b];
        cntb[b]+=sum*cnt[a];
    }
}

此时，整体时间复杂度为$\Theta(\frac{n^2}{9})$ ，可以满足该题目的时间限制。

代码实现

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=4e4+5;
int n,m;
struct node{
    int id,val; 
};
int x[N],rks[5],cnt[N],a[N];
int cnta[N],cntb[N],cntc[N],cntd[N];
int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;++i){
        scanf("%d",&x[i]);
        cnt[x[i]]++;//统计x[i]出现的次数
    }
    //t=d-c
    //a (2*t) b (6*t+k) c (t) d
    for(int t=1;t*9<=(n-1);t++){//遍历 t
        int sum=0;//a与b 组合的个数
        for(int d=t*9+2;d<=n;d++){//遍历 d 的数值
            int a=d-9*t-1;
            int b=a+2*t;
            int c=d-t;
            sum+=cnt[a]*cnt[b];// 统计a,b组合的个数
            cntc[c]+=sum*cnt[d];
            cntd[d]+=sum*cnt[c];
        }

        sum=0;//c,d组合的个数
        for(int a=n-9*t-1;a>=1;a--){//注意顺序
            int b=a+t*2;
            int d=a+9*t+1;
            int c=d-t;
            sum+=cnt[c]*cnt[d];
            cnta[a]+=sum*cnt[b];
            cntb[b]+=sum*cnt[a];
        }
    }
    for(int i=1;i<=m;i++){
        printf("%d %d %d %d\n",cnta[x[i]],cntb[x[i]],cntc[x[i]],cntd[x[i]]);
    }
    return 0;
}