【NOIP2016普及组】洛谷2119 魔法阵的解析（数学分析+枚举优化）_luogu魔法阵

题目：luogu2119.
题目大意：给定一个长度为$m$的序列$x_i$，要求求出满足$x_a<x_b<x_c<x_d，x_b-x_a=2(x_d-x_c)$且$x_b-x_a<\frac{x_c-x_b}{3}$的$a,b,c,d$的数量.
1 ≤ n = max ⁡ { x i } ≤ 1.5 ∗ 1 0 4 , 1 ≤ m ≤ 4 ∗ 1 0 4 1\leq n=\max \{x_i\}\leq 1.5*10^4,1\leq m\leq 4*10^4 1≤n=max{xi​}≤1.5∗104,1≤m≤4∗104.

首先这道题可以直接用一个桶，先把所有数塞进这个桶里.

然后我们可以开始$O(n^4)$枚举答案.

但我们发现$x_d=\frac{x_b-x_a+2x_c}{2}$，所以我们可以省去以为的枚举，做到$O(n^3)$枚举，实测在洛谷上能拿到85分.

到这一步优化的代码如下：

#include<bits/stdc++.h>
  using namespace std;
#define Abigail inline void
typedef long long LL;
const int N=15000,M=40000;
int n,m,x[M+9];
LL num[N+9][4],cnt[N+9];
Abigail into(){
  scanf("%d%d",&n,&m);
  for (int i=1;i<=m;i++){
    scanf("%d",&x[i]); 
    cnt[x[i]]++;
  }
}
Abigail work(){
  for (int a=1;a<=n;a++)
    for (int b=a+1;b<=n;b++)
      for (int c=b+1;c<=n;c++){
        if (b-a&1||3*b-3*a>=c-b) continue;
        int d=b-a+c*2>>1;
        LL ans=cnt[a]*cnt[b]*cnt[c]*cnt[d];
        num[a][0]+=ans;num[b][1]+=ans;num[c][2]+=ans;num[d][3]+=ans;
      }
  for (int i=1;i<=n;i++)
    for (int j=0;j<4;j++)
      num[i][j]/=cnt[i]?cnt[i]:1;
}
Abigail outo(){
  for (int i=1;i<=m;i++){
    for (int j=0;j<3;j++)
      printf("%lld ",num[x[i]][j]);
    printf("%lld\n",num[x[i]][3]);
  }
}
int main(){
  into();
  work();
  outo();
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40

接下来的优化需要将$x_b-x_a<\frac{x_c-x_b}{3}$变式，改成$3(x_b-x_a)<x_c-x_b$.

然后我们设$t=x_d-x_c$，那么$2t=x_b-x_a,6t<x_c-x_b$.

然后我们在设$6t+k=x_c-x_b$，那么就可以画一个图：

我们发现$x_d-x_a=9t+k$，由于所有数都是整数，所以$k$的最小值为$1$.

现在我们枚举$t$和$x_a$，我们就可以计算出$x_b=x_a+2t$，然后$C$的最小值为$x_a+2t+6t+k_{min}=x_a+8t+1$，$D$的最小值为$x_a+8t+1+t=x_a+9t+1$.

我们发现若$t$和$x_a$确定了，那么我们就可以确定只有$k$的问题了，我们发现$k$取$[1,n-9t]$内的任意一个数都是可以的，那我们就可以维护一个前缀和数组$vis[i][t]$表示$c$为$i$，$d$为$i+t$的时候有多少种.

由于这样会占用很大内存导致MLE，所以我们在推的时候处理，这样就可以确定$c$和$d$的数量了.但是要注意，由于我们要边处理边推，所以我们要逆推.

而$a$和$b$的确定和$c$和$d$很像，换成顺推就可以了.

而这样做的时间复杂度为$O(n^2)$，还是不能拿到满分.

接下来我们就进行一些细节的优化，我们发现$x_a+9t+k<=n$，而$x_a,k>=1$，所以我们可以发现其实$t<=\frac{n-2}{9}$，所以$t$只需要枚举到$\frac{n-2}{9}$就可以了.但是这样写代码会有除法，比较慢，所以我们写成$9t<=n-2$.

那么这个算法的时间复杂度就是$O(\frac{n^2}{9})$，可以过了，可能需要一定的常数优化（然而并没有什么可以优化的地方）.

所以大致的算法流程如下：
1.枚举$t=1\to \frac{n^2}{9}$.
2.枚举$D=n\to 2+9t$，可以推出$C=D-t$，之后可以设$A$为$A$的最大值，$B$为$B$的最大值，得到$B=C-6t-1,A=6t-1$.
3.在2的同时，记录一个$sum$初始为$0$，表示当前$D$时，$A$和$B$的情况有多少种.
4.同样，枚举$A=n-9t-1\to 1$.
5.同样，到这处理前缀和.

代码如下：

#include<bits/stdc++.h>
  using namespace std;
#define Abigail inline void
typedef long long LL;
const int N=15000,M=40000;
int n,m,x[M+9],num[4][N+9],cnt[N+9];
Abigail into(){
  scanf("%d%d",&n,&m);
  for (int i=1;i<=m;i++){
    scanf("%d",&x[i]); 
    cnt[x[i]]++;
  }
}
Abigail work(){
  int sum,A,B,C,D;
  for (int t=1;t*9<n;t++){
    sum=0;
    for (D=9*t-2;D<=n;D++){
      C=D-t;
      B=C-6*t-1;
      A=B-2*t;      //知道D，计算出A,B,C 
      sum+=cnt[A]*cnt[B];    //计算当前A和B的情况 
      num[2][C]+=cnt[D]*sum;    //num[2][C]+=cnt[A]*cnt[B]*cnt[C]
      num[3][D]+=cnt[C]*sum;    //num[3][D]+=cnt[A]*cnt[B]*cnt[D]
    }
    sum=0;
    for (A=n-9*t-1;A;A--){
      B=A+2*t;
      C=B+6*t+1;
      D=C+t;      //知道A，计算出B,C,D
      sum+=cnt[C]*cnt[D];    //计算当前C和D的情况
      num[0][A]+=cnt[B]*sum;    //num[0][A]+=cnt[B]*cnt[C]*cnt[D]
      num[1][B]+=cnt[A]*sum;    //num[1][B]+=cnt[A]*cnt[C]*cnt[D] 
    } 
  }
}
Abigail outo(){
  for (int i=1;i<=m;i++){
    for (int j=0;j<3;j++)
      printf("%d ",num[j][x[i]]);
    printf("%d\n",num[3][x[i]]);
  }
}
int main(){
  into();
  work();
  outo();
  return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49