【Problem description】
六十年一次的魔法战争就要开始了，大魔法师准备从附近的魔法场中汲取魔法能量。
大魔法师有m个魔法物品，编号分别为1,2,...,m。每个物品具有一个魔法值，我们用Xi表示编号为i的物品的魔法值。每个魔法值Xi是不超过n的正整数，可能有多个物品的魔法值相同。
大魔法师认为，当且仅当四个编号为a,b,c,d的魔法物品满足xa<xb<xc<xd，Xb-Xa=2(Xd-Xc)，并且xb-xa<(xc-xb)/3时，这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这个魔法阵的A物品，B物品，C物品，D物品。
现在，大魔法师想要知道，对于每个魔法物品，作为某个魔法阵的A物品出现的次数，作为B物品的次数，作为C物品的次数，和作为D物品的次数。
输入格式
输入文件的第一行包含两个空格隔开的正整数n和m。
接下来m行，每行一个正整数，第i+1行的正整数表示Xi，即编号为i的物品的魔法值。
保证1<=n<=15000,1<=m<=40000,1<=xi<=n。每个Xi是分别在合法范围内等概率随机生成的。
【Input format】
输入文件的第一行包含两个空格隔开的正整数n和m。
接下来m行，每行一个正整数，第i+1行的正整数表示Xi，即编号为i的物品的魔法值。
保证1<=n<=15000,1<=m<=40000,1<=xi<=n。每个Xi是分别在合法范围内等概率随机生成的。
【Output format】
共输出m行，每行四个整数。第i行的四个整数依次表示编号为i的物品作 为A,B,C,D物品分别出现的次数。
保证标准输出中的每个数都不会超过10^9。
每行相邻的两个数之间用恰好一个空格隔开。
【Algorithm design】
Optimized Enumeration
【Problem analysis】
这题有个很坑的地方：xb-xa<(xc-xb)/3 “/3”是个实数计算
当然可以移到左边化为整型计算
然后是思路处理
首先当然是暴力四重枚举
复杂度 O（40000^4）
TLE45
发现在枚出abcd任意三者的情况下可以直接求出另一个数字
因为求出的是数值
所以不妨把所有的物品都化成数值
相同数值的只要在hash上累加即可
三重循环复杂度O(40000^3)
TLE85
在尝试各种剪枝都无效的情况下
要想新算法
设xd-xc=i，xb-xa=2i，xc-xb>6i
可见i<n/9
再看其实每一组d，c都是可以对应多组a，b存在的
并且在相同i的情况下 在右的d,c是要比左面的对应组数多的
A，b反之
这就可以用前缀和思想来搞
核心代码（优化前）：
for(int sub_a=1;magic[sub_a]+gap*9<magic[cnt_num];sub_a++)
exist_left[magic[sub_a]+gap*2]=exist_magic[magic[sub_a]]*exist_magic[magic[sub_a]+gap*2];
for(int sub_d=cnt_num;magic[sub_d]-gap*9>magic[1];sub_d--)
exist_right[magic[sub_d]-gap]=exist_magic[magic[sub_d]]*exist_magic[magic[sub_d]-gap];
for(int i=magic[1];i<=magic[cnt_num];i++)
cnt_left[i]=cnt_left[i-1]+exist_left[i];
for(int i=magic[cnt_num];i>=magic[1];i--)
cnt_right[i]=cnt_right[i+1]+exist_right[i];
for(int sub_a=1;magic[sub_a]+gap*9<magic[cnt_num];sub_a++){
cnt[0][magic[sub_a]]+=cnt_right[magic[sub_a]+8*gap+1]*exist_magic[magic[sub_a]+gap*2];
cnt[1][magic[sub_a]+gap*2]+=cnt_right[magic[sub_a]+8*gap+1]*exist_magic[magic[sub_a]];}
for(int sub_d=cnt_num;magic[sub_d]-gap*9>magic[1];sub_d--){
cnt[2][magic[sub_d]-gap]+=cnt_left[magic[sub_d]-7*gap-1]*exist_magic[magic[sub_d]];
cnt[3][magic[sub_d]]+=cnt_left[magic[sub_d]-7*gap-1]*exist_magic[magic[sub_d]-gap];}
核心代码（优化后）：
for(int gap=1;gap*9<max_mag;gap++)
{
int cnt_left[bnd_mag];
int cnt_right[bnd_mag];
memset(cnt_left,0,sizeof(cnt_left));
memset(cnt_right,0,sizeof(cnt_right));
for(int a=1;a+gap*9<max_mag;a++)
{
int b=a+gap*2;
int least_c=b+gap*6+1;
cnt_left[least_c]+=cnt_mag[a]*cnt_mag[b];
}
for(int c=gap*8+2;c+gap<=max_mag;c++)
{
int d=c+gap;
int least_b=c-gap*6-1;
cnt_right[least_b]+=cnt_mag[c]*cnt_mag[d];
cnt_left[c]+=cnt_left[c-1];
cnt[2][c]+=cnt_left[c]*cnt_mag[d];
cnt[3][d]+=cnt_left[c]*cnt_mag[c];
}
for(int a=max_mag-9*gap-1;a>=1;a--)
{
int b=a+gap*2;
cnt_right[b]+=cnt_right[b+1];
cnt[1][b]+=cnt_right[b]*cnt_mag[a];
cnt[0][a]+=cnt_right[b]*cnt_mag[b];
}
}
复杂度O（n^2/9）
【Source code】
TLE45：
#include <bits/stdc++.h>
#define F(i,j,k) for(int i=j;i<=k;i++)
#define D(i,j,k) for(int i=j;i>=k;i--)
#define sc(i) scanf("%d",&i)
#define R return
using namespace std;
int n,m,x[40001],w[15001],vit[15001],cnt[4][15001],xx[40001];
void read()
{
sc(n);
sc(m);
F(i,1,m)
sc(x[i]);
R;
}
void work()
{
F(a,1,m)
F(b,1,m)
F(c,1,m)
F(d,1,m)
if(x[a]<x[b]&&x[b]<x[c]&&x[c]<x[d]&&x[b]-x[a]==2*x[d]-2*x[c]&&3*x[b]-3*x[a]<x[c]-x[b])
{
cnt[0][a]++;
cnt[1][b]++;
cnt[2][c]++;
cnt[3][d]++;
}
F(i,1,m)
{
F(j,0,3)
cout<<cnt[j][i]<<" ";
cout<<endl;
}
R;
}
int main()
{
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
read();
work();
R 0;
}
TLE 85：
#include <bits/stdc++.h>
#define F(i,j,k) for(int i=j;i<=k;i++)
#define D(i,j,k) for(int i=j;i>=k;i--)
#define sc(i) scanf("%d",&i)
#define R return
using namespace std;
int n,m,x[40001],w[15001],vit[15001],cnt[4][15001],xx[40001],next[15001];
void read()
{
sc(n);
sc(m);
F(i,1,m)
{
sc(x[i]);
vit[x[i]]++;
xx[i]=x[i];
}
sort(x+1,x+m+1);
F(i,1,m)if(x[i]>x[i-1])
w[++w[0]]=x[i];
int sub=1;
F(i,0,x[m])
{
if(w[sub]<i)sub++;
next[i]=sub;
}
R;
}
void work()
{
for(int c=3;c<w[0];c++)
for(int d=c+1;d<=w[0]&&9*w[d]-9*w[c]<n&&9*w[c]>8*w[d];d++)
{
int dis=w[d]-w[c];
for(int b=next[w[1]+2*dis];b<next[w[c]-6*dis];b++)
{
int a=w[b]-2*dis;
if(vit[a])
{
int sum=vit[a]*vit[w[b]]*vit[w[c]]*vit[w[d]];
cnt[0][a]+=sum/vit[a];
cnt[1][w[b]]+=sum/vit[w[b]];
cnt[2][w[c]]+=sum/vit[w[c]];
cnt[3][w[d]]+=sum/vit[w[d]];
}
}
}
F(i,1,m)
{
F(j,0,3)
cout<<cnt[j][xx[i]]<<" ";
cout<<endl;
}
R;
}
int main()
{
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
read();
work();
R 0;
}
AC（优化前）：
#include <bits/stdc++.h>
#define bound_cnt 40010
#define bound_magic 15010
using namespace std;
int max_magic,cnt_obj,cnt_num,cnt[4][bound_cnt],magic[bound_cnt],unsort_magic[bound_cnt],waitsort_magic[bound_cnt];
int exist_magic[bound_magic],exist_left[bound_magic],exist_right[bound_magic],cnt_left[bound_magic],cnt_right[bound_magic];;
void in()
{
cin>>max_magic>>cnt_obj;
for(int i=1;i<=cnt_obj;i++)
{
scanf("%d",&unsort_magic[i]);
waitsort_magic[i]=unsort_magic[i];
exist_magic[unsort_magic[i]]++;
}
sort(waitsort_magic+1,waitsort_magic+cnt_obj+1);
for(int i=1;i<=cnt_obj;i++)
if(waitsort_magic[i]>waitsort_magic[i-1])magic[++cnt_num]=waitsort_magic[i];
return;
}
void work()
{
for(int gap=1;gap*9<magic[cnt_num]-magic[1];gap++)
{
memset(exist_left,0,sizeof(exist_left));
memset(exist_right,0,sizeof(exist_right));
memset(cnt_left,0,sizeof(cnt_left));
memset(cnt_right,0,sizeof(cnt_right));
for(int sub_a=1;magic[sub_a]+gap*9<magic[cnt_num];sub_a++)
exist_left[magic[sub_a]+gap*2]=exist_magic[magic[sub_a]]*exist_magic[magic[sub_a]+gap*2];
for(int sub_d=cnt_num;magic[sub_d]-gap*9>magic[1];sub_d--)
exist_right[magic[sub_d]-gap]=exist_magic[magic[sub_d]]*exist_magic[magic[sub_d]-gap];
for(int i=magic[1];i<=magic[cnt_num];i++)
cnt_left[i]=cnt_left[i-1]+exist_left[i];
for(int i=magic[cnt_num];i>=magic[1];i--)
cnt_right[i]=cnt_right[i+1]+exist_right[i];
for(int sub_a=1;magic[sub_a]+gap*9<magic[cnt_num];sub_a++)
{
cnt[0][magic[sub_a]]+=cnt_right[magic[sub_a]+8*gap+1]*exist_magic[magic[sub_a]+gap*2];
cnt[1][magic[sub_a]+gap*2]+=cnt_right[magic[sub_a]+8*gap+1]*exist_magic[magic[sub_a]];
}
for(int sub_d=cnt_num;magic[sub_d]-gap*9>magic[1];sub_d--)
{
cnt[2][magic[sub_d]-gap]+=cnt_left[magic[sub_d]-7*gap-1]*exist_magic[magic[sub_d]];
cnt[3][magic[sub_d]]+=cnt_left[magic[sub_d]-7*gap-1]*exist_magic[magic[sub_d]-gap];
}
}
return;
}
void out()
{
for(int i=1;i<=cnt_obj;i++)
{
for(int j=0;j<=3;j++)
cout<<cnt[j][unsort_magic[i]]<<" ";
cout<<endl;
}
return;
}
int main()
{
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
in();
work();
out();
return 0;
}
AC（优化后）：
#include <bits/stdc++.h>
#define bnd_cnt 40010
#define bnd_mag 15010
using namespace std;
int max_mag,cnt_obj,cnt_num,cnt[4][bnd_mag],mag[bnd_cnt],ust_mag[bnd_cnt],cnt_mag[bnd_mag];
void in()
{
cin>>max_mag>>cnt_obj;
int wst_mag[bnd_cnt];
memset(wst_mag,0,sizeof(wst_mag));
for(int i=1;i<=cnt_obj;i++)
{
scanf("%d",&ust_mag[i]);
wst_mag[i]=ust_mag[i];
cnt_mag[ust_mag[i]]++;
}
sort(wst_mag+1,wst_mag+cnt_obj+1);
for(int i=1;i<=cnt_obj;i++)
if(wst_mag[i]>wst_mag[i-1])mag[++cnt_num]=wst_mag[i];
return;
}
void work()
{
for(int gap=1;gap*9<max_mag;gap++)
{
int cnt_left[bnd_mag];
int cnt_right[bnd_mag];
memset(cnt_left,0,sizeof(cnt_left));
memset(cnt_right,0,sizeof(cnt_right));
for(int a=1;a+gap*9<max_mag;a++)
{
int b=a+gap*2;
int least_c=b+gap*6+1;
cnt_left[least_c]+=cnt_mag[a]*cnt_mag[b];
}
for(int c=gap*8+2;c+gap<=max_mag;c++)
{
int d=c+gap;
int least_b=c-gap*6-1;
cnt_right[least_b]+=cnt_mag[c]*cnt_mag[d];
cnt_left[c]+=cnt_left[c-1];
cnt[2][c]+=cnt_left[c]*cnt_mag[d];
cnt[3][d]+=cnt_left[c]*cnt_mag[c];
}
for(int a=max_mag-9*gap-1;a>=1;a--)
{
int b=a+gap*2;
cnt_right[b]+=cnt_right[b+1];
cnt[1][b]+=cnt_right[b]*cnt_mag[a];
cnt[0][a]+=cnt_right[b]*cnt_mag[b];
}
}
return;
}
void out()
{
for(int i=1;i<=cnt_obj;i++)
{
for(int j=0;j<=3;j++)
cout<<cnt[j][ust_mag[i]]<<" ";
cout<<endl;
}
return;
}
int main()
{
freopen("magic.in","r",stdin);
freopen("magic.out","w",stdout);
in();
work();
out();
return 0;
}
原文：https://www.cnblogs.com/qswx/p/9155685.html