洛谷 P2119 魔法阵 题解

Analysis

这道题也是考试题，我也依然打了个n三次方暴力。正解是先枚举差，再枚举c和d，a和b用乘法原理优化，这样就能大大减少时间。

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #define max_n 50010

 using namespace std;

 int n,m,maxn=,minn=;

 int a[max_n],book[max_n],ansa[max_n],ansb[max_n],ansc[max_n],ansd[max_n];

 inline int read()

 {

     int x=;

     bool f=;

     char c=getchar();

     for(; !isdigit(c); c=getchar()) if(c=='-') f=;

     for(; isdigit(c); c=getchar()) x=(x<<)+(x<<)+c-'';

     if(f) return x;

     return -x;

 }

 inline void write(int x)

 {

     if(x<){putchar('-');x=-x;}

     if(x>)write(x/);

     putchar(x%+'');

 }

 int main()

 {

     n=read();m=read();

     for(int i=;i<=m;i++)

     {

         a[i]=read();

         book[a[i]]++;

     }

     for(int cha=;cha*<n;cha++)

     {

         int sum=;

         for(int d=*cha+;d<=n;d++)

         {

             int a=d-*cha-;

             int b=a+*cha;

             int c=d-cha;

             sum+=book[a]*book[b];

             ansc[c]+=sum*book[d];

             ansd[d]+=sum*book[c];

         }

         sum=;

         for(int a=n-*cha;a>=;a--)

         {

             int b=a+*cha;

             int c=b+*cha+;

             int d=c+cha;

             sum+=book[c]*book[d];

             ansa[a]+=sum*book[b];

             ansb[b]+=sum*book[a];

         }

     }

     for(int i=;i<=m;i++)

     {

         printf("%d %d %d %d\n",ansa[a[i]],ansb[a[i]],ansc[a[i]],ansd[a[i]]);

     }

     return ;

 }

请各位大佬斧正