模拟(55pts)

• 储存编号以后将所有数按照魔法值大小从小到大排序，分别枚举物品作为$a,b,c,d$的次数

#include<bits/stdc++.h>
using namespace std;
const int N=15010,M=40010;
typedef pair<int,int> PII;
#define x first
#define id second
PII X[M];
int cnt[M][4];
int main()
{
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>X[i].x; //记录数值
        X[i].id=i; //记录下标
    }
    sort(X+1,X+m+1);
    /*
    for(int i=1;i<=m;i++)
    {
        cout<<a[i].x<<" ";
    }
    */
    for(int a=1;a<=m;a++)
    {
        for(int b=a+1;b<=m;b++)
        {
            for(int c=b+1;c<=m;c++)
            {
                for(int d=c+1;d<=m;d++)
                {
                    if(X[a].x<X[b].x&&X[b].x<X[c].x&&X[c].x<X[d].x
					&&X[b].x-X[a].x==2*(X[d].x-X[c].x)&&
					X[b].x-X[a].x<(X[c].x-X[b].x)/3.0)
                    //判断条件
                    {
                        cnt[X[a].id][1]++;
                        cnt[X[b].id][2]++;
                        cnt[X[c].id][3]++;
                        cnt[X[d].id][4]++;
                    }
                }
            }
        }
    }
    for(int i=1;i<=m;i++)
    {
        cout<<cnt[i][1]<<" "<<cnt[i][2]<<" "<<cnt[i][3]<<" "<<cnt[i][4]<<endl;
    }
    return 0;
}

枚举+前缀和+乘法原理($\frac {n^2} 9$)

一个魔法阵如下

A和B之间的距离是$2t$，B和C之间的距离是$6t+k$，C和D之间的距离是$t$，其中$t, k$均为正整数。

左边红色部分框出的A和B是绑定的，右边绿色部分框出的C和D也是绑定的。 因此整个系统共有三个自由度：$t$、红色部分、绿色部分。

同时枚举三个自由度的计算量过大。在1秒内，我们只能枚举其中两个自由度。

首先枚举$t$。接下来并列枚举绿色部分和红色部分：

从左到右枚举绿色部分，当绿色部分固定后，则C应该累加的次数是所有满足要求的A和B的 cnt[A] * cnt[B] 的和，再乘以cnt[D]。其中cnt[A], cnt[B], cnt[D]是A, B, D出现的次数。所有满足要求的A和B就是整个线段左边的某个前缀，因此可以利用前缀和算法来加速计算。cnt[D]同理可得。 从右到左枚举红色部分可做类似处理。

#include<bits/stdc++.h>
using namespace std;
const int N=15010,M=40010;
int n,m;
int cnt[N];
int a[N],b[N],c[N],d[N],x[M];
int main()
{
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        cin>>x[i];
        cnt[x[i]]++;//统计x出现的次数
    }
    for(int t=1;t*9+2<=n;t++)
    {
        int sum=0;
        for(int D=t*9+2;D<=n;D++) //从前往后枚举D
        {
            int A=D-t*9-1;
            int B=A+t*2;
            int C=D-t;
            sum+=cnt[A]*cnt[B]; //累加前缀和
            c[C]+=sum*cnt[D];
            d[D]+=sum*cnt[C];
        }
        sum=0;
        for(int A=n-t*9-1;A;A--) //从后往前枚举A
        {
            int B=A+t*2;
            int D=A+t*9+1;
            int C=D-t;
            sum+=cnt[C]*cnt[D];
            a[A]+=sum*cnt[B];
            b[B]+=sum*cnt[A];
        }
    }
    for(int i=1;i<=m;i++)
    {
        cout<<a[x[i]]<<" "<<b[x[i]]<<" "<<c[x[i]]<<" "<<d[x[i]]<<endl;
    }
    return 0;
}