记录编号	559555	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	[NOIP 2016PJ]魔法阵	最终得分	100
用户昵称	锝镆氪锂铽	是否通过	通过
代码语言	C++	运行时间	0.073 s
提交时间	2021-03-17 18:59:28	内存使用	0.58 MiB

#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int maxN = 2e4 + 10; 
 
int n, m, dis, y;
int a[maxN], b[maxN], c[maxN], d[maxN];//a，b，c，d分别表示每件物品四个位置的个数
int h[maxN << 1], w[maxN << 1];//h表示物品的魔法值，w表示每个魔法值出现的次数
int main(void){
	freopen("magicb.in", "r", stdin);
	freopen("magicb.out", "w", stdout);
	scanf("%d%d",&n,&m);
	for (int i = 1; i <= m; i ++){
		scanf("%d", &h[i]);
		w[h[i]] ++;
	}
	for (int i = 1; i <= n / 9; i ++){
		dis = 8 * i + 1;
		y = 0;//dis表示A到C的最小距离，y表示A、B的个数
		for (int j = n - 9 * i - 1; j >= 1; j --){
			y += w[j + dis] * w[j + dis + i];//A、B的个数取决于C、D有多少对，所以用C、D个数来乘
			a[j] += y * w[j + i + i];
			b[j + i + i] += y * w[j];
		}
		dis = 9 * i + 1;
		y = 0;//dis表示D到A的最小距离，y表示C、D的个数
		for (int j = 9 * i + 2; j <= n; j ++){
			y += w[j - dis] * w[j - dis + i + i];//C、D的个数取决于A、B有多少对，所以用A、B个数来乘
			c[j - i] += y * w[j];
			d[j] += y * w[j - i];
		}
	}
	for(int i = 1; i <= m; i ++){
		printf("%d %d %d %d\n",a[h[i]],b[h[i]],c[h[i]],d[h[i]]);
	}
}