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

fishhh

发布于 2022-10-04 19:27:03

4390

发布于 2022-10-04 19:27:03

文章被收录于专栏：OI算法学习笔记

[NOIP2016 普及组] 魔法阵

题目背景

NOIP2016 普及组 T4

题目描述

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

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

大魔法师认为，当且仅当四个编号为 a,b,c,da,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)Xa<Xb<Xc<Xd,Xb−Xa=2(Xd−Xc)，并且 Xb−Xa<(Xc−Xb)/3X_b-X_a<(X_c-X_b)/3Xb−Xa<(Xc−Xb)/3 时，这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这个魔法阵的 AAA 物品，BBB 物品，CCC 物品，DDD 物品。

现在，大魔法师想要知道，对于每个魔法物品，作为某个魔法阵的 AAA 物品出现的次数，作为 BBB 物品的次数，作为 CCC 物品的次数，和作为 DDD 物品的次数。

输入格式

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

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

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

输出格式

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

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

样例 #1

样例输入 #1

样例输出 #1

样例 #2

样例输入 #2

样例输出 #2

提示

【样例解释 111】

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

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

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

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

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

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

以物品 555 为例，它作为 AAA 物品出现了 111 次，作为 BBB 物品出现了 333 次，没有作为 CCC 物品或者 DDD 物品出现，所以这一行输出的四个数依次为 1,3,0,01,3,0,01,3,0,0。

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

【数据规模】

编号	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物品分别出现的次数。

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

Xa<Xb<Xc<XdX_a<X_b<X_c<X_dXa<Xb<Xc<Xd
Xb−Xa=2(Xd−Xc)X_b-X_a=2(X_d-X_c)Xb−Xa=2(Xd−Xc)
Xb−Xa<(Xc−Xb)/3X_b-X_a<(X_c-X_b)/3Xb−Xa<(Xc−Xb)/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)Θ(n4),只能获得一部分的分数。

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

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

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个测试点。

优化

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

Xa<Xb<Xc<XdX_a<X_b<X_c<X_dXa<Xb<Xc<Xd
Xb−Xa=2(Xd−Xc)X_b-X_a=2(X_d-X_c)Xb−Xa=2(Xd−Xc)
Xb−Xa<(Xc−Xb)/3X_b-X_a<(X_c-X_b)/3Xb−Xa<(Xc−Xb)/3

我们设t=Xd−Xct=X_d - X_ct=Xd−Xc 。

Xa<Xb<Xc<XdX_a<X_b<X_c<X_dXa<Xb<Xc<Xd
Xb−Xa=2tX_b-X_a=2tXb−Xa=2t
2t<(Xc−Xb)/32t<(X_c-X_b)/32t<(Xc−Xb)/3

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

Xa<Xb<Xc<XdX_a<X_b<X_c<X_dXa<Xb<Xc<Xd
Xb=Xa+2tX_b=X_a+2tXb=Xa+2t
Xd=Xc+tX_d=X_c+tXd=Xc+t
Xc−Xb>6tX_c-X_b > 6tXc−Xb>6t

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

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

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

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

此时

c=d−tc=d-tc=d−t 。

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

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

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

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

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

ansc=cnta×cntb×cntdans_c=cnt_a\times cnt_b\times cnt_dansc=cnta×cntb×cntd

ansd=cnta×cntb×cntcans_d=cnt_a\times cnt_b\times cnt_cansd=cnta×cntb×cntc

若存在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=cnta1×cntb1×cntd+⋯+cntam×cntbm×cntd

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

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=cnta1×cntb1×cntc+⋯+cntam×cntbm×cntc

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

那么所有的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})Θ(9n2) ，可以满足该题目的时间限制。

代码实现

#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;
}

Q.E.D.

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自作者个人站点/博客前往查看

如有侵权，请联系 cloudcommunity@tencent.com 删除。

本文参与腾讯云自媒体同步曝光计划，欢迎热爱写作的你一起参与！

登录后参与评论

0 条评论

热度