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;
}
}
上一篇: MATLAB实现分段线性插值
下一篇: 上婚外情网站?你可能在和机器人谈恋爱