欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

P2119 魔法阵

程序员文章站 2022-07-05 17:00:13
...

题目

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)

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

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

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

A就是枚举的i
B:A+2t
C:B+6
t+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

既然三重循环还要超时,好,那么继续压一压,两重循环
我们回到那张图P2119 魔法阵
如果把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;
		}
	}