理解题意

       一个无聊的人拿四个物品制造魔法阵，这四个物品满足题目给出的三个式子，输出一个矩阵，记录每个物品作为魔法阵中A，B，C，D物品的次数

 

稳定情绪

        莫得慌，博    主    是    一    个   极   其不负   责    任   的   歪   星   人

 

题解

 Part 1  50‘  暴力

暴力枚举  四层for循环  

       首先记录每件物品的魔法值和物品编号（按输入的顺序就好啦）

       由于魔法阵的四个物品是按照递增顺序来的，所以按照魔法值从小到大sort一遍

       然后四层枚举for循环，check函数判断是否符合题意的三个式子，满足则记录下来每个物品作为魔法阵中对应ABCD物品的次数+1

       最后还要按照物品编号排回来，输出每个物品对应作为魔法阵ABCD物品的次数

 

50‘  暴力代码

#include
     
      using namespace std;int n,m;struct node{    int x,num;    int a,b,c,d;}obj[40010];bool cmp1(node aa,node bb){    return aa.x 
     

 

然后就hin开心的T成酱紫

 

 

Part2  下面谈正解

上面50'暴力之后发现一个问题，n根本没有什么用！！！

那么n真的没有用么？？

n看上去是个青铜，其实他已经是个王者啦

 

 实际上这是一个数学推断题

我们来看这三个式子

暗中观察，仔细思索

<1> A   B  C  D四个物品的魔法值是严格递增的

<2> X_d - X_c 是最小单位 ，我们假设它是 t 

然后得到以下关系式

 X_d - X_c = t

 X_b - X_a = 2t

 X_c - X_b > 3(X_b-X_a) = 6t

 

于是我们想到把这些魔法值在一个坐标轴上表示出来（泥萌看n现在有用了吧）

 

考虑怎样枚举

枚举的话一定要枚举 t

把A，B看成一个整体，当我们知道了A或B中其中一个，就可以准确求出另一个

把C，D看成一个整体，当我们知道了C或D中其中一个，就可以准确求出另一个

so，把暴力枚举A B C D转化为枚举 t  A或B  C或D

窝枚举 t  A  D  （知三求五）

注意此处枚举的是魔法值：

因为前面三个式子是又魔法值推出来的，窝推出来的枚举也是建立在魔法值的基础上推出来的，所以枚举的都是魔法值鸭

 

 

看着这个图：

枚举 t ，最外层枚举

考虑枚举范围： 1 ~ n/9 

因为 AD>9t ，A最小为1 ，D最大为n ，最极端的情况就是A在1处，D在n处，9t 一定满足<n

为了避免枚举的时候出现除法，枚举范围就变成了：t：1 ~ 9t<n

 

枚举D

枚举范围：9t+2 ~ n

                 (1+9t+1 ~ n)

当我们枚举出了一个 D1 ，就会确定一个C1 （t 在最外层枚举）

那么由于BC的距离并不确定，只知道他们>6t，所以并不能准确地得到A，B

我们先考虑距离C1，D1最近的A1，B1，也就是假设BC之间的距离最小，也就是 6t+1 ，于是乎确定了A1，B1

（所以当BC之间的距离增大怎么办？？）

那么当我们继续往后枚举D，得到一个新的D2，新的D2比原来的D1魔法值更大

那么对应的C2 ，B2，A2都会整体在数轴上右移，此时我们发现B1，C2的距离比B2，C2 的更大，那么当然也可以和新的D2构成一个魔法阵

D还会继续往后枚举，启发我们可以维护一个前缀和

 

由以上推断我们就可以确定出D的枚举顺序：从小到大

同时维护一个前缀和

 

数组记录实现

d[D]记录  魔法值为D的物品作为魔法阵D物品的次数

（回到图）

对于当前的这个D，数轴对应着A，B，C

但是A，B，C的数量是不确定的（因为题面描述可能会有相同的魔法值，对于这些相同的魔法值处理当然一摸一样）

但是无论取A，B，C中各类的哪一个，都会满足一个合法的魔法阵

由乘法原理可得

d[D]=sum[A]*sum[B]*sum[C]

同理得到C

c[C]=sum[A]*sum[B]*sum[D]

我们枚举D的时候只记录更新D和C，因为由D可以准确确定C，却不能准确确定A和B

由于BC距离不同，我们还要把前缀和维护加进去（就是前面讲到的维护前缀和） 

 

那么式子就变成了：

注意累加（+=）

sum是维护的前缀和

tong 是用桶排序记录了每个魔法值有几个，也就是上面提到的数量不确定

 

同理，枚举A

枚举范围：A：n-9t-1~1

那么A的枚举顺序就是从大到小

维护后缀和 c,d

 

输出答案

for（1~m）

对于这m个物品，对应着一个魔法值

对于每一个魔法值，都对应着成为魔法阵A B C D 物品的次数

输出即可

 

特判

（回到图）

因为t最小是1（递增的ABCD物品），A最小是1

那么n一定要大于10，否则就会无解啊，就找不到d了啊

 

 

AC代码了解一下：

变量介绍：

x[ i ]   i 物品的魔法值

tong[ i ]  用桶记录魔法值为i的物品的数目

a[ i ]  魔法值为 i 的物品作为魔法阵的A物品的次数

b[ i ]  魔法值为 i 的物品作为魔法阵的B物品的次数

c[ i ]  魔法值为 i 的物品作为魔法阵的C物品的次数

d[ i ]  魔法值为 i 的物品作为魔法阵的D物品的次数

sum  维护的前缀和，后缀和 

AC代码

#include
     
      using namespace std;const int maxn=15010;int n,m;int x[40010],tong[maxn];int a[maxn],b[maxn],c[maxn],d[maxn];inline int read(){    int ans=0;    char last=' ',ch=getchar();    while(ch<'0'||ch>'9') last=ch,ch=getchar();    while(ch>='0'&&ch<='9') ans=ans*10+ch-'0',ch=getchar();    if(last=='-') ans=-ans;    return ans;}int main(){    n=read();m=read();        if(n<11)    {        for(int i=1;i<=m;i++)            printf("0 0 0 0\n");        return 0;    }        for(int i=1;i<=m;i++)    {        x[i]=read();        tong[x[i]]++;    }          for(int t=1;t*9
      
       0;A--)        {            int B=A+t*2;            int C=A+8*t+1;            int D=A+9*t+1;            sum+=tong[C]*tong[D];            a[A]+=sum*tong[B];            b[B]+=sum*tong[A];        }    }        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;}
      
     

 

 

-----------------------            The  End           --------------------

 xiang quan ao sai tong xue xie zui