P2119 魔法阵

倚窗倾听风吹雨

https://www.luogu.org/problemnew/show/P2119


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

大魔法师有 mm 个魔法物品，编号分别为 1,2,...,m。每个物品具有一个魔法值，我们用 X_i 表示编号为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 物品的次数。

输入输出格式
输入格式：
第一行包含两个空格隔开的正整数 n,m

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

保证 1≤n≤15000 , 1≤m≤40000 ,1≤Xi≤n 。每个Xi 是分别在合法范围内等概率随机生成的。

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

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

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

吴语林

1. #include <algorithm>
   
2. #include <iostream>
   
3. #include <cmath>
   
4. #include <cstring>
   
5. #include <map>
   
6. #include <string>
   
7. #include <vector>
   
8. #include <queue>
   
9. #include <stack>
   
10. #include <cstdio>
    
11. #include <cstdlib>
    
12. using namespace std;  
    
13. int a[4][15005],mo[40005],cnt[15005],x,all,n,m;
    
14. int main()  
    
15. {  
    
16.     scanf("%d%d",&n,&m);
    
17.     for(int i=1;i<=m;i++)
    
18.     {
    
19.         scanf("%d",&mo[i]);
    
20.         cnt[mo[i]]++;
    
21.     }
    
22.     for(int i=1;i<=n/9;i++)
    
23.     {
    
24.         x=1+9*i,all=0;
    
25.         for(int j=2+9*i;j<=n;j++)
    
26.         {
    
27.             all+=cnt[j-x]*cnt[j-x+i+i];
    
28.             a[3][j]+=all*cnt[j-i],a[2][j-i]+=all*cnt[j];
    
29.         }
    
30.         x=8*i+1,all=0;
    
31.         for(int j=n-9*i-1;j>=1;j--)
    
32.         {
    
33.             all+=cnt[j+x]*cnt[j+x+i];
    
34.             a[0][j]+=all*cnt[j+i+i],a[1][j+i+i]+=all*cnt[j];
    
35.         }
    
36.     }
    
37.     for(int i=1;i<=m;i++)
    
38.         printf("%d %d %d %d\n",a[0][mo[i]],a[1][mo[i]],a[2][mo[i]],a[3][mo[i]]);
    
39.     return 0;
    
40. }

复制代码

倚窗倾听风吹雨

暴力 O(n^4) 40分

1. #include<iostream>
   
2. using namespace std;
   
3. int n,m;
   
4. struct node
   
5. {
   
6.     int a,b,c,d;
   
7.     double mfz;
   
8. }sub[210];
   
9. int main()
   
10. {
    
11.     cin>>n>>m;
    
12.     for(int i=1;i<=m;i++)
    
13.         cin>>sub[i].mfz;
    
14.     for(int i=1;i<=m;i++)
    
15.         for(int j=1;j<=m;j++)
    
16.             for(int k=1;k<=m;k++)
    
17.                 for(int l=1;l<=m;l++)
    
18.                 if(sub[i].mfz<sub[j].mfz && sub[j].mfz<sub[k].mfz && sub[k].mfz<sub[l].mfz && sub[j].mfz-sub[i].mfz==sub[l].mfz+sub[l].mfz-sub[k].mfz-sub[k].mfz && sub[j].mfz-sub[i].mfz<(sub[k].mfz-sub[j].mfz)/3)
    
19.                     {
    
20.                         sub[i].a++;
    
21.                         sub[j].b++;
    
22.                         sub[k].c++;
    
23.                         sub[l].d++;
    
24.                     }
    
25.     for(int i=1;i<=m;i++)
    
26.         cout<<sub[i].a<<" "<<sub[i].b<<" "<<sub[i].c<<" "<<sub[i].d<<" "<<endl;
    
27. }
    
28. 
    

复制代码

AC

1. #include<iostream>
   
2. #include<algorithm>
   
3. using namespace std;
   
4. const int N=15010,M=40010;
   
5. int n,m,a[N],b[N],c[N],d[N],sub[M],num[N];
   
6. int main()
   
7. {
   
8.     cin>>n>>m;
   
9.     for(int i=1;i<=m;i++)
   
10.     {
    
11.         cin>>sub[i];
    
12.         num[sub[i]]++;
    
13.     }
    
14.     for(int i=1;i*9+1<=n;i++)
    
15.     {
    
16.         int sum=0;
    
17.         for(int j=9*i+2;j<=n;j++)
    
18.         {
    
19.             sum+=num[j-7*i-1]*num[j-9*i-1];
    
20.             c[j-i]+=num[j]*sum;
    
21.             d[j]+=num[j-i]*sum;
    
22.         }
    
23.         sum=0;
    
24.         for(int j=n-9*i-1;j>=1;j--)
    
25.         {
    
26.             sum+=num[j+8*i+1]*num[j+9*i+1];
    
27.             b[j+i+i]+=sum*num[j];
    
28.             a[j]+=sum*num[j+i+i];
    
29.         }
    
30.     }
    
31.     for(int i=1;i<=m;i++)
    
32.         cout<<a[sub[i]]<<" "<<b[sub[i]]<<" "<<c[sub[i]]<<" "<<d[sub[i]]<<endl;
    
33.     return 0;
    
34. }
    
35. 
    

复制代码