NOIP2016普及组第四题 魔法阵

魔法阵

题目描述

六十年一次的魔法战争就要开始了，大魔法师准备从附近的魔法场中汲取魔法能量。 大魔法师有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物品的次数。

输入格式

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

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

输出格式

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

样例

输入数据 1

308
1
24
7
28
5
29
26
24

Copy

输出数据 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

Copy

提示

NOIP2016普及组第四题

#include <cstdio>
#include <algorithm>
using namespace std;
inline int read(){int x=0,f=1;char c=getchar();while(c<'0'||c>'9'){if(c=='-')f=-f;c=getchar();}while(c>='0'&&c<='9'){x=(x<<1)+(x<<3)+c-'0';c=getchar();}return x*f;
}
#define N 50010
int n,m;
int a[N],b[N],c[N],d[N];
int x[N],vis[N];
int main(){n=read();m=read();for(int i=1;i<=m;i++)x[i]=read(),vis[x[i]]++;for(int t=1;t*9<n;t++){int sum=0;for(int D=9*t+2;D<=n;D++){int A=D-9*t-1;int B=A+2*t;int C=D-t;sum+=vis[A]*vis[B];c[C]+=vis[D]*sum;d[D]+=vis[C]*sum;}sum=0;for(int A=n-9*t-1;A;A--){int B=A+2*t;int C=B+6*t+1;int D=A+9*t+1;sum+=vis[C]*vis[D];a[A]+=vis[B]*sum;b[B]+=vis[A]*sum;}}for(int i=1;i<=m;i++){printf("%d %d %d %d\n",a[x[i]],b[x[i]],c[x[i]],d[x[i]]);}return 0;
}
///test