华师一附中OI组

标题: P2119 魔法阵 [打印本页]
作者: 倚窗倾听风吹雨    时间: 2018-8-24 11:41
标题: 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 个数之和都应等于魔法阵的总数。所以，如果你的输出不满足这个性质，那么这个输出一定不正确。你可以通过这个性质在一定程度上检查你的输出的正确性。
作者: 倚窗倾听风吹雨    时间: 2018-8-24 11:42
暴力 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. }

复制代码


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. }

复制代码

作者: 吴语林    时间: 2018-8-24 15:31
  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. }
复制代码




欢迎光临 华师一附中OI组 (http://hsyit.cn/) Powered by Discuz! X3.2