简答题 偏难
#23601

魔法阵 (magic) 【问题描述】 六十年一次的魔法战争就要开始了,大魔法师准备从附近的魔法场中汲取魔法能 量。 大魔法师有 m 个魔法物品,编号分别为 1,…

魔法阵 (magic)

【问题描述】

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

大魔法师有 m 个魔法物品,编号分别为 1, 2, . . . , m 。每个物品具有一个魔法值,我 们用xi  表示编号为 i 的物品的魔法值。每个魔法值xi  是不超过n 的正整数,可能有多 个物品的魔法值相同。

大魔法师认为,当且仅当四个编号为a, b, c, d 的魔法物品满足 xa  < xb  < xc  < xd  , xb - xa  = 2(xd - xc ) ,并且 xb - xa  < (xc - xb ) ÷ 3 时,这四个魔法物品形成了一个魔法阵, 他称这四个魔法物品分别为这个魔法阵的A 物品,B 物品,C 物品,D 物品。

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

【输入格式】

从文件magic.in 中读入数据。

输入文件的第一行包含两个空格隔开的正整数 n 和m 。

接下来 m 行,每行一个正整数,第 i + 1 行的正整数表示xi  ,即编号为 i 的物品的 魔法值。

保证每个 xi  是分别在合法范围内等概率 随机生成的。

【输出格式】

输出到文件magic.out 中。

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

保证标准输出中的每个数都不会超过

每行相邻的两个数之间用恰好一个空格隔开。

【样例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

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

【样例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

【子任务】

每个测试点的详细数据范围见下表。

未登录也能判分,登录后才会记录
答案与解析
正确答案:<p style="text-align: left;">#include &lt;bits/stdc++.h&gt;</p><p style="text-align: left;">using namespace std;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int n,m;</p><p style="text-align: left;">int a[40001];</p><p style="text-align: left;">int f[5][15001]/*作为第i个物品时,魔法值为j的次数*/;</p><p style="text-align: left;">int d[15001]/*魔法值为i的物品个数*/;</p><p style="text-align: left;">int sum=0,cnt=0;</p><p><br style="text-align: left;"/></p><p style="text-align: left;">int main(){</p><p style="text-align: left;">    memset(f,0,sizeof(f));</p><p style="text-align: left;">    scanf("%d%d",&amp;n,&amp;m);</p><p style="text-align: left;">    for(int i=1;i&lt;=m;i++){</p><p style="text-align: left;">        scanf("%d",&amp;a[i]);</p><p style="text-align: left;">        d[a[i]]++;</p><p style="text-align: left;">    }</p><p style="text-align: left;">    for(int t=1;t*9+2&lt;=n;t++){</p><p style="text-align: left;">        sum=0;cnt=0;</p><p style="text-align: left;">        for(int dd=9*t+2;dd&lt;=n;dd++){</p><p style="text-align: left;">            int cc=dd-t;//第三个物品</p><p style="text-align: left;">            int bb=cc-6*t-1;//第二个物品</p><p style="text-align: left;">            int aa=bb-2*t;//第一个物品</p><p style="text-align: left;">            sum+=d[aa]*d[bb];//递推计算前缀和</p><p style="text-align: left;">            f[3][cc]+=sum*d[dd];//魔法值为d的个数可能不是/不止1个</p><p style="text-align: left;">            f[4][dd]+=sum*d[cc];//同理</p><p style="text-align: left;">        }</p><p style="text-align: left;">        for(int aa=n-9*t-1;aa&gt;=1;aa--){</p><p style="text-align: left;">            int bb=aa+2*t;//第二个物品</p><p style="text-align: left;">            int cc=bb+6*t+1;//第三个物品</p><p style="text-align: left;">            int dd=cc+t;//第四个物品</p><p style="text-align: left;">            cnt+=d[cc]*d[dd];</p><p style="text-align: left;">            f[1][aa]+=cnt*d[bb];</p><p style="text-align: left;">            f[2][bb]+=cnt*d[aa];</p><p style="text-align: left;">        }</p><p style="text-align: left;">    }</p><p style="text-align: left;">    for(int i=1;i&lt;=m;i++){</p><p style="text-align: left;">        for(int j=1;j&lt;=4;j++){</p><p style="text-align: left;">            printf("%d ",f[j][a[i]]);</p><p style="text-align: left;">        }</p><p style="text-align: left;">        printf("\n");</p><p style="text-align: left;">    }</p><p style="text-align: left;">    return 0;</p><p style="text-align: left;">}</p>
这道题暂未补解析。