https://www.luogu.com.cn/problem/P2119
题意:输入n和m,有m个魔法物品,每个魔法物品的魔法值为[1,n],取4个魔法物品a,b,c,d,如果魔法值满足a<b<c<d,b-a=2(d-c)并且b-a<(c-b)/3时,可以形成魔法阵,称这四个魔法物品分别为这个魔法阵的A物品,B物品,C物品,D物品。求对于每个魔法物品,作为某个魔法阵的A物品出现的次数,作为B物品的次数,作为C物品的次数,和作为D物品的次数。
解题思路:桶排序其实就是离散化计数操作
1.4个魔法阵的关系:a<b<c<d,单调递增序列
2.各种关系
b-a=2*(d-c)
3*(b-a)<(c-b)
显然d-c最小并且有倍数关系
假设d-c=t
b-a=2t
c-b>6t
最小的魔法阵为a,范围[1,n]
b可以表示为[a+2t,n]
c可以表示为[b+6t+1,n][a+8t+1,n]
d可以表示为[c+t,n][a+9t+1,n]
任意一个t,a和b的差是固定的,c和d的差也是固定的,但是b和c的差可以跨得很大,这种组合对后面的贡献需要用前缀和来累计,同理计算后面的组合对前面的贡献需要后缀和。很像逆序对中离散化的树状数组。
import java.util.*; public class Main{//桶排序 static int[] val=new int[40005]; static int[] num=new int[15005]; static int[] a=new int[15005]; static int[] b=new int[15005]; static int[] c=new int[15005]; static int[] d=new int[15005]; public static void main(String []args){ Scanner scan=new Scanner(System.in); int n=scan.nextInt(); int m=scan.nextInt(); for(int i=1;i<=m;i++) { int x=scan.nextInt(); val[i]=x; num[x]++;//间距为1的桶 } for(int t=1;9*t+1<=n;t++) { int sum=0; int va,vb,vc,vd; for(vd=t*9+2;vd<=n;vd++) { va=vd-9*t-1; vb=va+2*t; vc=va+8*t+1; sum+=num[vb]*num[va]; //a和b的距离是固定的,但b和c的距离可大可小,任何前面的ab组合都可以和c组成魔法阵 c[vc]+=sum*num[vd];//但c和d的距离也是固定的,用任何一个c都必须要固定d d[vd]+=sum*num[vc];//同理,可用的d与c相关 } sum=0; for(va=n-9*t-1;va>=1;va--) {//c和d已经计算出来了,任何后面的cd都可以对a铺垫,a越小越多,后缀和 vb=va+2*t; vc=va+8*t+1; vd=va+9*t+1; sum+=num[vc]*num[vd]; a[va]+=sum*num[vb]; b[vb]+=sum*num[va];//同理,a和b一一对应 } } for(int i=1;i<=m;i++) { int x=val[i]; System.out.println(a[x]+" "+b[x]+" "+c[x]+" "+d[x]); } } }