P2119 魔法阵

题目

40pts

我们可以考虑暴力枚举出这四个点，然后对这四个点进行条件判断复杂度O(n^4)期望得分40

for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) for(int k=1;k<=n;k++) for(int z=1;z<=n;z++) if(a[i].x<a[j].x&&a[j].x<a[k].x&&a[k].x<a[z].x) if(a[j].x-a[i].x==2*(a[z].x-a[k].x)) if(a[j].x-a[i].x<(a[k].x-a[j].x)/3.0) { vis[i][1]++; vis[j][2]++; vis[k][3]++; vis[z][4]++; }

55pts

思考还是四重循环的情况，最四重循环进行简化。我们可以发现第一个组成魔法阵的条件是Xa<Xb<Xc<Xd。所以可以先排个序，保证是上升的，那么就可以从上一重循环+1开始枚举

for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++) for(int k=j+1;k<=n;k++) for(int z=k+1;z<=n;z++) if(a[i].x<a[j].x&&a[j].x<a[k].x&&a[k].x<a[z].x) if(a[j].x-a[i].x==2*(a[z].x-a[k].x)) if(a[j].x-a[i].x<(a[k].x-a[j].x)/3.0) { vis[i][1]++; vis[j][2]++; vis[k][3]++; vis[z][4]++; }

85pts

想要降低时间复杂度，那么肯定要减少循环的次数，所以我们先想想把四重循环怎么降到三重观察条件

我们假设Xc和Xd之间的距离为t ，那么（Xd-Xc）就是t

因为 Xb-Xa=2(Xd-Xc) 所以 Xb-Xa=2t

Xb-Xa<(Xc-Xb)/3 两边同时3 3（Xb-Xa)<Xc-Xb 所以 6t<Xc-Xb Xc-Xb=6t+k (k>0)

然后我们发现了我们可以枚举A的位置，然后枚举t的大小，k的大小就可以算出其它的值，然后我们确定枚举的范围

A:(1<=i<=n) 因为当k为1时整个魔法阵的长度最小并且最右端要<=n所以 9t+i+1<=n t<=(n-1-i)/9 k和t也是同样的道理 9t+i+k<=n k<=(n-i-9*t)

确定了循环，那么开始确定点的位置

A就是枚举的i B:A+2t C:B+6t+k D:C+t

最后就是累加答案： 如果一个数有好几个，那么可以和其它进行组合，所以答案就是和其他有几个数相乘

#include<bits/stdc++.h> #define maxn 15010 using namespace std; inline int read() { int res=0,f=1;char ch=getchar(); while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();} while(isdigit(ch)){res=(res<<1)+(res<<3)+(ch&15);ch=getchar();} return res*f; } int n,m,a[maxn*4]; int vis[maxn]; int ans[maxn*4][5];//表示i魔法值作为第j的个数 int p[maxn]; int main() { n=read();m=read(); for(int i=1;i<=m;i++)a[i]=read(),vis[a[i]]++; for(int i=1;i<=n;i++) { if(vis[i]) for(int j=1;9*j+i+1<=n;j++) { if(vis[i+2*j]) { for(int k=1;k+9*j+i<=n;k++) { int B=i+2*j; int C=B+6*j+k; int D=C+j; ans[i][1]+=vis[B]*vis[C]*vis[D];//统计 ans[B][2]+=vis[i]*vis[C]*vis[D]; ans[C][3]+=vis[i]*vis[B]*vis[D]; ans[D][4]+=vis[i]*vis[B]*vis[C]; } } } } for(int i=1;i<=m;i++) { for(int j=1;j<=4;j++) cout<<ans[a[i]][j]<<' '; cout<<endl; } return 0; }

100pts

既然三重循环还要超时，好，那么继续压一压，两重循环 我们回到那张图 如果把k都当成1，然后D在可行的范围内移动，那么就可以算出ABC的值了，并且可以求出在第三四个的答案

同理，A在可行的范围内移动，那么就可以算出BCD的值了，并且可以求出在第一二个的答案

因为答案数=其他三个的个数相乘，所以我们可以把其中两个先用前缀和维护，然后直接求

核心代码 for(int t=1;t*9<n;t++){ int sum=0; for(int D=9*t+2;D<=n;D++){//枚举D找第三四个的值 int A=D-9*t-1; int B=A+2*t; int C=D-t; sum+=vis[A]*vis[B];//前缀和维护 c[C]+=vis[D]*sum; d[D]+=vis[C]*sum; } sum=0; for(int A=n-9*t-1;A>=1;A--){//枚举A找第一二个的值 int B=A+2*t; int C=B+6*t+1; int D=A+9*t+1; sum+=vis[C]*vis[D]; a[A]+=vis[B]*sum; b[B]+=vis[A]*sum; } }