【题解】[NOIP2016 普及组] 魔法阵

【题解】[NOIP2016 普及组] 魔法阵

小鱼干 462 2022-09-29

[NOIP2016 普及组] 魔法阵

题目背景

NOIP2016 普及组 T4

题目描述

六十年一次的魔法战争就要开始了，大魔法师准备从附近的魔法场中汲取魔法能量。

大魔法师有 mm 个魔法物品，编号分别为 1,2,…,m1,2,\ldots,m。每个物品具有一个魔法值，我们用 XiX_i 表示编号为 ii 的物品的魔法值。每个魔法值 XiX_i 是不超过 nn 的正整数，可能有多个物品的魔法值相同。

大魔法师认为，当且仅当四个编号为 a,b,c,da,b,c,d 的魔法物品满足 Xa<Xb<Xc<Xd,Xb−Xa=2(Xd−Xc)X_a<X_b<X_c<X_d,X_b-X_a=2(X_d-X_c)，并且 Xb−Xa<(Xc−Xb)/3X_b-X_a<(X_c-X_b)/3 时，这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这个魔法阵的 AA 物品，BB 物品，CC 物品，DD 物品。

现在，大魔法师想要知道，对于每个魔法物品，作为某个魔法阵的 AA 物品出现的次数，作为 BB 物品的次数，作为 CC 物品的次数，和作为 DD 物品的次数。

输入格式

第一行包含两个空格隔开的正整数 n,mn,m。

接下来 mm 行，每行一个正整数，第 i+1i+1 行的正整数表示 XiX_i，即编号为 ii 的物品的魔法值。

保证 1≤n≤150001 \le n \le 15000,1≤m≤400001 \le m \le 40000,1≤Xi≤n1 \le Xi \le n。每个 XiX_i 是分别在合法范围内等概率随机生成的。

输出格式

共 mm 行，每行 44 个整数。第 ii 行的 44 个整数依次表示编号为 ii 的物品作 为 A,B,C,DA,B,C,D 物品分别出现的次数。

保证标准输出中的每个数都不会超过 10910^9。每行相邻的两个数之间用恰好一个空格隔开。

样例 #1

样例输入 #1

30 8
1
24
7
28
5
29
26
24

样例输出 #1

4 0 0 0
0 0 1 0
0 2 0 0
0 0 1 1
1 3 0 0
0 0 0 2
0 0 2 2
0 0 1 0

样例 #2

样例输入 #2

15 15
1 
2 
3 
4 
5
6 
7 
8 
9
10
11
12
13
14
15

样例输出 #2

5 0 0 0
4 0 0 0
3 5 0 0
2 4 0 0
1 3 0 0
0 2 0 0
0 1 0 0
0 0 0 0
0 0 0 0
0 0 1 0
0 0 2 1
0 0 3 2
0 0 4 3
0 0 5 4
0 0 0 5

提示

【样例解释 11】

共有 55 个魔法阵，分别为：

物品 1,3,7,61,3,7,6，其魔法值分别为 1,7,26,291,7,26,29;

物品 1,5,2,71,5,2,7，其魔法值分别为 1,5,24,261,5,24,26;

物品 1,5,7,41,5,7,4，其魔法值分别为 1,5,26,281,5,26,28;

物品 1,5,8,71,5,8,7，其魔法值分别为 1,5,24,261,5,24,26;

物品 5,3,4,65,3,4,6，其魔法值分别为 5,7,28,295,7,28,29。

以物品 55 为例，它作为 AA 物品出现了 11 次，作为 BB 物品出现了 33 次，没有作为 CC 物品或者 DD 物品出现，所以这一行输出的四个数依次为 1,3,0,01,3,0,0。

此外，如果我们将输出看作一个 mm 行 44 列的矩阵，那么每一列上的 mm 个数之和都应等于魔法阵的总数。所以，如果你的输出不满足这个性质，那么这个输出一定不正确。你可以通过这个性质在一定程度上检查你的输出的正确性。

【数据规模】

编号 n m 编号 n m
1 =10 =12 11 =150 =250
2 =15 =18 12 =200 =350
3 =20 =25 13 =250 =500
4 =30 =35 14 =350 =700
5 =40 =50 15 =500 =1000
6 =50 =70 16 =700 =2000
7 =65 =100 17 =1000 =5000
8 =80 =125 18 =2000 =10000
9 =100 =150 19 =5000 =20000
10 =125 =200 20 =15000 =40000

题目分析

阅读题目，可知题目要求的是，每件物品作为A,B,C,D物品分别出现的次数。

四个元素需要满足的条件为：

  1. Xa<Xb<Xc<XdX_a<X_b<X_c<X_d

  2. Xb−Xa=2(Xd−Xc)X_b-X_a=2(X_d-X_c)

  3. Xb−Xa<(Xc−Xb)/3X_b-X_a<(X_c-X_b)/3

条件1表明元素严格单调递增。我们可将元素先进行排序和去重。之后枚举出所有的四元组合，统计各组合中元素出现的个数。

但是统计过程中需要注意的问题是会出现重复的元素。对应位置数值的次数为该数值出现在对应位置的组合数的数量，利用乘法原理可得到组合数量为其他三个元素的出现次数的成绩。

for(int ai=1;ai<=mm;ai++){
    for(int bi=ai+1;bi<=mm;bi++){
        for(int ci=bi+1;ci<=mm;ci++){
            for(int di=ci+1;di<=m;di++){
                if(满足 条件2 和 条件3)｛
                	cnta[x[ai]]+=cnt[x[bi]]*cnt[x[ci]]*cnt[x[di]];
               		cntb[x[bi]]+=cnt[x[ai]]*cnt[x[ci]]*cnt[x[di]];
                	cntc[x[ci]]+=cnt[x[ai]]*cnt[x[bi]]*cnt[x[di]];
                	cntd[x[di]]+=cnt[x[ai]]*cnt[x[bi]]*cnt[x[ci]];
                ｝
            }
        }
    }
}

此时时间复杂为Θ(n4)\Theta(n^4),只能获得一部分的分数。

此时尝试对暴力枚举的方式进行优化。首先可以减少枚举的对象，根据条件2，可发现xd=xb−xa2+xcx_d=\frac{x_b-x_a}{2}+x_c 。

那么只需要三重循环即可实现，时间复杂度降为Θ(n3)\Theta(n^3) 。

for(int i=1;i<=m;i++){
    for(int j=i+1;j<=m;j++){
        if((x[j]-x[i])%2!=0) continue;//不满足条件2
        for(int k=j+1;k<=m;k++){
            int d=x[k]+(x[j]-x[i])/2;//求出元素d
            if(d<=x[k] || cnt[d]==0 ) continue;//四个数非递增或求出的d不存在则不符合
            if(3*(x[j]-x[i])>=x[k]-x[j]) continue;//不符合条件3

            int num=cnt[x[i]]*cnt[x[j]]*cnt[x[k]]*cnt[d];
            cnta[x[i]]+=num/cnt[x[i]];
            cntb[x[j]]+=num/cnt[x[j]];
            cntc[x[k]]+=num/cnt[x[k]];
            cntd[d]+=num/cnt[d];
        }
    }
}

可过17个测试点。

优化

再次尝试进行优化。仔细观察对应的三个条件。

  1. Xa<Xb<Xc<XdX_a<X_b<X_c<X_d

  2. Xb−Xa=2(Xd−Xc)X_b-X_a=2(X_d-X_c)

  3. Xb−Xa<(Xc−Xb)/3X_b-X_a<(X_c-X_b)/3

我们设t=Xd−Xct=X_d - X_c 。

  1. Xa<Xb<Xc<XdX_a<X_b<X_c<X_d

  2. Xb−Xa=2tX_b-X_a=2t

  3. 2t<(Xc−Xb)/32t<(X_c-X_b)/3

整理一下，可得到这些关系描述。

  1. Xa<Xb<Xc<XdX_a<X_b<X_c<X_d
  2. Xb=Xa+2tX_b=X_a+2t
  3. Xd=Xc+tX_d=X_c+t
  4. Xc−Xb>6tX_c-X_b > 6t

此时，我们可以枚举t可能出现的值。在确定t的基础上，探讨、确定d的值，从而确定可能的c、d组合的元素值和数量。 再确定a的值，从而确定a、b组合的元素值和数量。

数值的范围为n，所以得到如下的大小关系。

可发现，因为严格递增，所以t最小为1。d=a+9t+k,k>=1d=a+9t+k,k>=1 。所以d≤nd\le n即9t≤n−29t\le n-2 。

a最小为1，所以9t+2≤d≤n9t+2\le d \le n 。

此时

  • c=d−tc=d-t 。

确定d、t后，c的值就能固定下来。但a、b的值由于k的不固定，会存在多组。

  • a=d−9t−ka=d-9t-k
  • b=a+2tb=a+2t

k≥1k\ge 1 ，所以a、b最大的一组为

  • a=d−9t−1a=d-9t-1
  • b=a+2tb=a+2t

对于任意一组四元组,a,b,c,d。根据乘法原理，c,d的次数可以表示为：

ansc=cnta×cntb×cntdans_c=cnt_a\times cnt_b\times cnt_d

ansd=cnta×cntb×cntcans_d=cnt_a\times cnt_b\times cnt_c

若存在m组可行的a、b。对于已固定值的c、d，它们的次数可表示为：

ansc=cnta1×cntb1×cntd+⋯+cntam×cntbm×cntdans_c=cnt_{a_1}\times cnt_{b_1}\times cnt_d+\cdots +cnt_{a_m}\times cnt_{b_m}\times cnt_d

ansc=∑i=1mcntai×cntbi×cntdans_c= \sum_{i=1}^{m}cnt_{a_i}\times cnt_{b_i}\times cnt_d

ansd=cnta1×cntb1×cntc+⋯+cntam×cntbm×cntcans_d =cnt_{a_1}\times cnt_{b_1}\times cnt_c+\cdots +cnt_{a_m}\times cnt_{b_m}\times cnt_c

ansd=∑i=1mcntai×cntbi×cntcans_d= \sum_{i=1}^{m}cnt_{a_i}\times cnt_{b_i}\times cnt_c

那么所有的a、b组进行前缀和处理即可。

同理，若固定t、a,即可确定a、b的数值，c、d会存在多组。需要注意的是，c、d在a、b的右侧，进行求和需要从右向左，后缀和思想。

for(int t=1;t*9<=(n-1);t++){//遍历 t
    int sum=0;//a与b 组合的个数
    for(int d=t*9+2;d<=n;d++){//遍历 d 的数值
        int a=d-9*t-1;
        int b=a+2*t;
        int c=d-t;
        sum+=cnt[a]*cnt[b];// 统计a,b组合的个数
        cntc[c]+=sum*cnt[d];
        cntd[d]+=sum*cnt[c];
    }

    sum=0;//c,d组合的个数
    for(int a=n-9*t-1;a>=1;a--){//注意顺序
        int b=a+t*2;
        int d=a+9*t+1;
        int c=d-t;
        sum+=cnt[c]*cnt[d];
        cnta[a]+=sum*cnt[b];
        cntb[b]+=sum*cnt[a];
    }
}

此时，整体时间复杂度为Θ(n29)\Theta(\frac{n^2}{9}) ，可以满足该题目的时间限制。

代码实现

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
const int N=4e4+5;
int n,m;
struct node{
	int id,val;	
};
int x[N],rks[5],cnt[N],a[N];
int cnta[N],cntb[N],cntc[N],cntd[N];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d",&x[i]);
		cnt[x[i]]++;//统计x[i]出现的次数
	}
	//t=d-c
	//a (2*t) b (6*t+k) c (t) d
	for(int t=1;t*9<=(n-1);t++){//遍历 t
		int sum=0;//a与b 组合的个数
		for(int d=t*9+2;d<=n;d++){//遍历 d 的数值
			int a=d-9*t-1;
			int b=a+2*t;
			int c=d-t;
			sum+=cnt[a]*cnt[b];// 统计a,b组合的个数
			cntc[c]+=sum*cnt[d];
			cntd[d]+=sum*cnt[c];
		}
		
		sum=0;//c,d组合的个数
		for(int a=n-9*t-1;a>=1;a--){//注意顺序
			int b=a+t*2;
			int d=a+9*t+1;
			int c=d-t;
			sum+=cnt[c]*cnt[d];
			cnta[a]+=sum*cnt[b];
			cntb[b]+=sum*cnt[a];
		}
	}
	for(int i=1;i<=m;i++){
		printf("%d %d %d %d\n",cnta[x[i]],cntb[x[i]],cntc[x[i]],cntd[x[i]]);
	}
	return 0;
}
数论 前缀和 题解 2016