NOIP2016 普及組第四題 魔法陣

瘋狂的函數 2022-01-07 20:32:25 阅读数:928

noip2016 noip 普及 第四 魔法

題目描述

 

六十年一次的魔法戰爭就要開始了,大魔法師准備從附近的魔法場中汲取魔法能量。

大魔法師有m個魔法物品,編號分別為1,2,...,m。每個物品具有一個魔法值,我們用xix_ixi錶示編號為i的物品的魔法值。每個魔法值xix_ixi是不超過n的正整數,可能有多個物品的魔法值相同。

大魔法師認為,當且僅當四個編號為a,b,c,d的魔法物品滿足xa<xb<xc<xdx_a<x_b<x_c<x_dxa<xb<xc<xd,xb−xa=2(xd−xc)x_b-x_a=2(x_d-x_c)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≤n1 \le n \le 15000, 1 \le m \le 40000, 1 \le x_i \le n1≤n≤15000,1≤m≤40000,1≤xi≤n。每個xi是分別在合法範圍內等概率隨機生成的。

輸出

共輸出m行,每行四個整數。第i行的四個整數依次錶示編號為i的物品作為A, B, C, D物品分別出現的次數。

保證標准輸出中的每個數都不會超過10910^9109。

每行相鄰的兩個數之間用恰好一個空格隔開。

樣例輸入

30 8
1
24
7
28
5
29
26
24

樣例輸出

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個數之和都應等於魔法陣的總數。所以,如果你的輸出不滿足這個性質,那麼這個輸出一定不正確。你可以通過這個性質在一定程度上檢查你的輸出的正確性。

【子任務】

每個測試點的詳細數據範圍見下錶。

程序實現

#include<bits/stdc++.h>
int X[16000],a[40005],S[16000];
int A[40005],B[40005],C[40005],D[40005];
int main()
{
int n,m;
scanf("%d %d",&n,&m);
for(int i=1;i<=m;i++)
{
scanf("%d",&a[i]);
X[a[i]]++;
}
for(int i=1;i*9<n;i++)
{
memset(S,0,sizeof(S));
for(int j=2*i+1;j<=n-7*i-1;j++) S[j] = X[j - 2*i] * X[j];
for(int j=1;j<=n;j++) S[j] += S[j-1];
for(int j=9*i+1;j<=n;j++) D[j] += S[j - 7*i - 1] * X[j - i];
for(int j=7*i+1;j<=n-i;j++) C[j] += S[j - 6*i -1] * X[j + i];
memset(S,0,sizeof(S));
for(int j=9*i+1;j<=n;j++) S[j] = X[j - i] * X[j];
for(int j=n;j>=1;j--) S[j] += S[j+1];
for(int j=2*i+1;j<=n-7*i-1;j++) B[j] += S[j + 7*i + 1] * X[j - 2*i];
for(int j=1;j<=n-9*i-1;j++) A[j] += S[j + 9*i +1] * X[j + 2*i];
}
for(int i = 1;i<=m;i++)
printf("%d %d %d %d\n",A[a[i]],B[a[i]],C[a[i]],D[a[i]]);
}

版权声明:本文为[瘋狂的函數]所创,转载请带上原文链接,感谢。 https://gsmany.com/2022/01/202201072032245246.html