2016 CSP-J/NOIP万字长文复赛真题题解——秒杀T1 买铅笔,T2 回文日期,T3 海港，T4 魔法阵

标签：24 10 NOIP int 题解 样例 魔法阵 29 leq

[NOIP2016 普及组] 买铅笔

题干

[NOIP2016 普及组] 买铅笔

题目背景

NOIP2016 普及组 T1

题目描述

P 老师需要去商店买 n n n 支铅笔作为小朋友们参加 NOIP 的礼物。她发现商店一共有 3 3 3 种包装的铅笔，不同包装内的铅笔数量有可能不同，价格也有可能不同。为了公平起 见，P 老师决定只买同一种包装的铅笔。

商店不允许将铅笔的包装拆开，因此 P 老师可能需要购买超过 n n n 支铅笔才够给小朋友们发礼物。

现在 P 老师想知道，在商店每种包装的数量都足够的情况下，要买够至少 n n n 支铅笔最少需要花费多少钱。

输入格式

第一行包含一个正整数 n n n，表示需要的铅笔数量。

接下来三行，每行用 2 2 2 个正整数描述一种包装的铅笔：其中第 1 1 1 个整数表示这种包装内铅笔的数量，第 2 2 2 个整数表示这种包装的价格。

保证所有的 7 7 7 个数都是不超过 10000 10000 10000 的正整数。

输出格式

1 1 1 个整数，表示 P 老师最少需要花费的钱。

样例 #1

样例输入 #1

57
2 2
50 30
30 27

样例输出 #1

54

样例 #2

样例输入 #2

9998
128 233
128 2333
128 666

样例输出 #2

18407

样例 #3

样例输入 #3

9999
101 1111
1 9999
1111 9999

样例输出 #3

89991

提示

铅笔的三种包装分别是：

• 2 2 2 支装，价格为 2 2 2;
• 50 50 50 支装，价格为 30 30 30;
• 30 30 30 支装，价格为 27 27 27。

P 老师需要购买至少 57 57 57 支铅笔。

如果她选择购买第一种包装，那么她需要购买 29 29 29 份，共计 2 × 29 = 58 2 \times 29 = 58 2×29=58 支，需要花费的钱为 2 × 29 = 58 2 \times 29 = 58 2×29=58。

实际上，P 老师会选择购买第三种包装，这样需要买 2 2 2 份。虽然最后买到的铅笔数量更多了，为 30 × 2 = 60 30 \times 2 = 60 30×2=60 支，但花费却减少为 27 × 2 = 54 27 \times 2 = 54 27×2=54，比第一种少。

对于第二种包装，虽然每支铅笔的价格是最低的，但要够发必须买 2 2 2 份，实际的花费达到了 30 × 2 = 60 30 \times 2 = 60 30×2=60，因此 P 老师也不会选择。

所以最后输出的答案是 54 54 54。

数据范围

保证所有的 7 7 7 个数都是不超过 10000 10000 10000 的正整数。

子任务

子任务会给出部分测试数据的特点。如果你在解决题目中遇到了困难，可以尝试只解决一部分测试数据。

每个测试点的数据规模及特点如下表：

上表中“整倍数”的意义为：若为 K K K，表示对应数据所需要的铅笔数量 n n n —定是每种包装铅笔数量的整倍数（这意味着一定可以不用多买铅笔）。

思路

一共有三种铅笔，并且只能有一种铅笔。这个运算量非常小，所以我们可以直接暴力枚举，枚举每一种包装铅笔需要多少钱，取最小值即可。
怎么计算需要多少包铅笔呢？只要用总共需要的铅笔数除以一包这种包装的铅笔数，如果有余数就再加1，就可以保证能够满足要求，再用需要的包数乘以一包的单价即可求出买这一种铅笔的总价

时间复杂度

O ( 1 ) O(1) O(1)

空间复杂度

O ( 1 ) O(1) O(1)

代码

#include <bits/stdc++.h>
using namespace std ;
int n,a,b,ans = INT_MAX ;
int main(){
    scanf("%d",&n) ;
    for(int i = 0;i < 3;++ i){
        scanf("%d%d",&a,&b) ;
        ans = min(ans,((n / a) + int((n % a) != 0)) * b) ;
    }
    printf("%d",ans) ;
    return 0 ;
}

[NOIP2016 普及组] 回文日期

题干

题目背景

NOIP2016 普及组 T2

题目描述

在日常生活中，通过年、月、日这三个要素可以表示出一个唯一确定的日期。

牛牛习惯用 8 8 8 位数字表示一个日期，其中，前 4 4 4 位代表年份，接下来 2 2 2 位代表月份，最后 2 2 2 位代表日期。显然：一个日期只有一种表示方法，而两个不同的日期的表 示方法不会相同。

牛牛认为，一个日期是回文的，当且仅当表示这个日期的 8 8 8 位数字是回文的。现在，牛牛想知道：在他指定的两个日期之间包含这两个日期本身），有多少个真实存在的日期是回文的。

一个 8 8 8 位数字是回文的，当且仅当对于所有的 i i i（ 1 ≤ i ≤ 8 1 \le i \le 8 1≤i≤8）从左向右数的第 i i i 个数字和第 9 − i 9-i 9−i 个数字（即从右向左数的第 i i i 个数字）是相同的。

例如：

• 对于 2016 年 11 月 19 日，用 8 8 8 位数字 20161119 20161119 20161119 表示，它不是回文的。
• 对于 2010 年 1 月 2 日，用 8 8 8 位数字 20100102 20100102 20100102 表示，它是回文的。
• 对于 2010 年 10 月 2 日，用 8 8 8 位数字 20101002 20101002 20101002 表示，它不是回文的。

每一年中都有 12 12 12 个月份：

其中， 1 , 3 , 5 , 7 , 8 , 10 , 12 1, 3, 5, 7, 8, 10, 12 1,3,5,7,8,10,12 月每个月有 31 31 31 天； 4 , 6 , 9 , 11 4, 6, 9, 11 4,6,9,11 月每个月有 30 30 30 天；而对于 2 2 2 月，闰年时有 29 29 29 天，平年时有 28 28 28 天。

一个年份是闰年当且仅当它满足下列两种情况其中的一种：

1. 这个年份是 4 4 4 的整数倍，但不是 100 100 100 的整数倍；
2. 这个年份是 400 400 400 的整数倍。

例如：

• 以下几个年份都是闰年： 2000 , 2012 , 2016 2000, 2012, 2016 2000,2012,2016。
• 以下几个年份是平年： 1900 , 2011 , 2014 1900, 2011, 2014 1900,2011,2014。

输入格式

两行，每行包括一个 8 8 8 位数字。

第一行表示牛牛指定的起始日期。

第二行表示牛牛指定的终止日期。

保证 d a t e 1 \mathit{date}_1 date1​ 和 d a t e 2 \mathit{date}_2 date2​ 都是真实存在的日期，且年份部分一定为 4 4 4 位数字，且首位数字不为 0 0 0。

保证 d a t e 1 \mathit{date}_1 date1​ 一定不晚于 d a t e 2 \mathit{date}_2 date2​。

输出格式

一个整数，表示在 d a t e 1 \mathit{date}_1 date1​ 和 d a t e 2 \mathit{date}_2 date2​ 之间，有多少个日期是回文的。

样例 #1

样例输入 #1

20110101
20111231

样例输出 #1

1

样例 #2

样例输入 #2

20000101
20101231

样例输出 #2

2

提示

【样例说明】

对于样例 1，符合条件的日期是 20111102 20111102 20111102。

对于样例 2，符合条件的日期是 20011002 20011002 20011002 和 20100102 20100102 20100102。

【子任务】

对于 60 % 60 \% 60% 的数据，满足 d a t e 1 = d a t e 2 \mathit{date}_1 = \mathit{date}_2 date1​=date2​。

思路

普通思路

枚举两个日期之间的每一天，然后判断有多少个回文数。
用一个数组记录下每个月份的天数，如果是闰年的话，就把2月改成29天，否则改成28天。
如果天数超过了这个月的最大天数，天数归一，月份数加一。
如果月份数超过了12，月份数归一，年数加一。
具体解析看代码

时间复杂度

n = 两个日期相差的天数 n = 两个日期相差的天数 n=两个日期相差的天数
O ( n ) O(n) O(n)

空间复杂度

O ( 1 ) O(1) O(1)

代码

#include <bits/stdc++.h>
using namespace std ;
int start,e,s ;
int a[] = {0,31,28,31,30,31,30,31,31,30,31,30,31} ;
//不能用end，因为end在一些编译器上会编译错误 
bool run(int date){
	//判断是否是闰年 
    int year = date / 10000 ; 
    if((year % 100) == 0)return (year % 400) == 0 ;
    return (year % 4) == 0 ; 
}
void new_day(int& date){
    if(run(date))a[2] = 29 ;
    //如果是闰年，把二月天数改成29 
    else a[2] = 28 ;
    //否则，把二月天数改成28 
    int year = date / 10000,day = date % 100,month = date / 100 % 100 ;
    //去除年、月、日 
    day ++ ;
    //天数加一 
    if(day > a[month])month ++ , day = 1 ;
    //如果超过了这个月的最大天数，月数加一 
    if(month > 12)month = 1 , year ++ ;
    //如果超过了12个月，年数加一 
    date = year * 10000 + month * 100 + day ;
    //重新拼接成原来的格式 
    return ;
}
bool hw(int num){
	//判断是否是回文数 
    int t = 0,k = num ;
    while(num)t = t * 10 + num % 10 , num /= 10 ;
    return t == k ;
}
int main(){
    scanf("%d%d",&start,&e) ;
    while(start <= e){
        s += hw(start) ;
        //判断当前日期是否为答案 
        new_day(start) ;
        //下一天 
    }
    printf("%d",s) ;
    return 0 ;
}

更快的思路

直接枚举月份和日期，然后通过月份和日期反转获得年份，在拼接成题目那样子的格式。
如当前枚举到的月份和日期为：一月一日，即 0101 0101 0101
翻转过来即： 1010 1010 1010
拼接在一起即： 10100101 10100101 10100101，即 1010 1010 1010年 01 01 01月 01 01 01日，
在判断一下这个日期是否在题目给的起始日期和结束日期之间即可。
如果是的话，答案加 1 1 1。

2 2 2月份不需要特殊判断，设为 29 29 29天即可，如：
0229 0229 0229：二月二十九日
反转得： 9220 9220 9220，
而 9220 9220 9220是闰年，二月就的确是有 29 29 29天

时间复杂度

n = 366 表示一个闰年的总天数 n = 366 表示一个闰年的总天数 n=366表示一个闰年的总天数
O ( n ) O(n) O(n)

空间复杂度

O ( 1 ) O(1) O(1)

代码

#include <stdio.h>
int s,e,ans ;
int a[13] = {0,31,29,31,30,31,30,31,31,30,31,30,31} ;
//一到十二月每个月份的天数 
int main(){
    scanf("%d%d",&s,&e) ;
    for(int i = 1;i <= 12;++ i)
    	//枚举月份 
    	for(int o = 1;o <= a[i];++ o){
    		//枚举天数 
    		const int date = (o % 10 * 10000000) +
    					(o / 10 * 1000000) +
    					(i % 10 * 100000) +
    					(i / 10 * 10000) +
    					(i * 100) +
    					(o) ;
    		//拼接得到枚举出来的日期 
    		if(date > e || date < s)continue ;
    		//如果日期不合法，跳过 
    		++ ans ;
    		//否则，答案加一 
		}
	printf("%d",ans) ;
	//输出答案 
    return 0 ;
}

[NOIP2016 普及组] 海港

题干

题目背景

NOIP2016 普及组 T3

题目描述

小 K 是一个海港的海关工作人员，每天都有许多船只到达海港，船上通常有很多来自不同国家的乘客。

小 K 对这些到达海港的船只非常感兴趣，他按照时间记录下了到达海港的每一艘船只情况；对于第 i i i 艘到达的船，他记录了这艘船到达的时间 t i t_i ti​ (单位：秒)，船上的乘客数 k i k_i ki​，以及每名乘客的国籍 x i , 1 , x i , 2 , … , x i , k x_{i,1}, x_{i,2},\dots,x_{i,k} xi,1​,xi,2​,…,xi,k​。

小K统计了 n n n 艘船的信息，希望你帮忙计算出以每一艘船到达时间为止的 24 24 24 小时（ 24 24 24 小时 = 86400 =86400 =86400 秒）内所有乘船到达的乘客来自多少个不同的国家。

形式化地讲，你需要计算 n n n 条信息。对于输出的第 i i i 条信息，你需要统计满足 t i − 86400 < t p ≤ t i t_i-86400<t_p \le t_i ti​−86400<tp​≤ti​ 的船只 p p p，在所有的 x p , j x_{p,j} xp,j​ 中，总共有多少个不同的数。

输入格式

第一行输入一个正整数 n n n，表示小 K 统计了 n n n 艘船的信息。

接下来 n n n 行，每行描述一艘船的信息：前两个整数 t i t_i ti​ 和 k i k_i ki​ 分别表示这艘船到达海港的时间和船上的乘客数量，接下来 k i k_i ki​ 个整数 x i , j x_{i,j} xi,j​ 表示船上乘客的国籍。

保证输入的 t i t_i ti​ 是递增的，单位是秒；表示从小K第一次上班开始计时，这艘船在第 t i t_i ti​ 秒到达海港。

保证 1 ≤ n ≤ 1 0 5 1 \le n \le 10^5 1≤n≤105，$\sum{k_i} \le 3\times 10^5 $ ， 1 ≤ x i , j ≤ 1 0 5 1\le x_{i,j} \le 10^5 1≤xi,j​≤105， 1 ≤ t i − 1 ≤ t i ≤ 1 0 9 1 \le t_{i-1}\le t_i \le 10^9 1≤ti−1​≤ti​≤109。

其中 ∑ k i \sum{k_i} ∑ki​ 表示所有的 k i k_i ki​ 的和。

输出格式

输出 n n n 行，第 i i i 行输出一个整数表示第 i i i 艘船到达后的统计信息。

样例 #1

样例输入 #1

3
1 4 4 1 2 2
2 2 2 3
10 1 3

样例输出 #1

3
4
4

样例 #2

样例输入 #2

4
1 4 1 2 2 3
3 2 2 3
86401 2 3 4
86402 1 5

样例输出 #2

3
3
3
4

提示

【样例解释 1】

第一艘船在第 1 1 1 秒到达海港，最近 24 24 24 小时到达的船是第一艘船，共有 4 4 4 个乘客，分别是来自国家 4 , 1 , 2 , 2 4,1,2,2 4,1,2,2，共来自 3 3 3 个不同的国家；

第二艘船在第 2 2 2 秒到达海港，最近 24 24 24 小时到达的船是第一艘船和第二艘船，共有 4 + 2 = 6 4 + 2 = 6 4+2=6 个乘客，分别是来自国家 4 , 1 , 2 , 2 , 2 , 3 4,1,2,2,2,3 4,1,2,2,2,3，共来自 4 4 4 个不同的国家；

第三艘船在第 10 10 10 秒到达海港，最近 24 24 24 小时到达的船是第一艘船、第二艘船和第三艘船，共有 4 + 2 + 1 = 7 4+2+1=7 4+2+1=7 个乘客，分别是来自国家 4 , 1 , 2 , 2 , 2 , 3 , 3 4,1,2,2,2,3,3 4,1,2,2,2,3,3，共来自 4 4 4 个不同的国家。

【样例解释 2】

第一艘船在第 1 1 1 秒到达海港，最近 24 24 24 小时到达的船是第一艘船，共有 4 4 4 个乘客，分别是来自国家 1 , 2 , 2 , 3 1,2,2,3 1,2,2,3，共来自 3 3 3 个不同的国家。

第二艘船在第 3 3 3 秒到达海港，最近 24 24 24 小时到达的船是第一艘船和第二艘船，共有 4 + 2 = 6 4+2=6 4+2=6 个乘客，分别是来自国家 1 , 2 , 2 , 3 , 2 , 3 1,2,2,3,2,3 1,2,2,3,2,3，共来自 3 3 3 个不同的国家。

第三艘船在第 86401 86401 86401 秒到达海港，最近 24 24 24 小时到达的船是第二艘船和第三艘船，共有 2 + 2 = 4 2+2=4 2+2=4 个乘客，分别是来自国家 2 , 3 , 3 , 4 2,3,3,4 2,3,3,4，共来自 3 3 3 个不同的国家。

第四艘船在第 86402 86402 86402 秒到达海港，最近 24 24 24 小时到达的船是第二艘船、第三艘船和第四艘船，共有 2 + 2 + 1 = 5 2+2+1=5 2+2+1=5 个乘客，分别是来自国家 2 , 3 , 3 , 4 , 5 2,3,3,4,5 2,3,3,4,5，共来自 4 4 4个 不同的国家。

【数据范围】

• 对于 10 % 10\% 10% 的测试点， n = 1 , ∑ k i ≤ 10 , 1 ≤ x i , j ≤ 10 , 1 ≤ t i ≤ 10 n=1,\sum k_i \leq 10,1 \leq x_{i,j} \leq 10, 1 \leq t_i \leq 10 n=1,∑ki​≤10,1≤xi,j​≤10,1≤ti​≤10。
• 对于 20 % 20\% 20% 的测试点， 1 ≤ n ≤ 10 , ∑ k i ≤ 100 , 1 ≤ x i , j ≤ 100 , 1 ≤ t i ≤ 32767 1 \leq n \leq 10, \sum k_i \leq 100,1 \leq x_{i,j} \leq 100,1 \leq t_i \leq 32767 1≤n≤10,∑ki​≤100,1≤xi,j​≤100,1≤ti​≤32767。
• 对于 40 % 40\% 40% 的测试点， 1 ≤ n ≤ 100 , ∑ k i ≤ 100 , 1 ≤ x i , j ≤ 100 , 1 ≤ t i ≤ 86400 1 \leq n \leq 100, \sum k_i \leq 100,1 \leq x_{i,j} \leq 100,1 \leq t_i \leq 86400 1≤n≤100,∑ki​≤100,1≤xi,j​≤100,1≤ti​≤86400。
• 对于 70 % 70\% 70% 的测试点， 1 ≤ n ≤ 1000 , ∑ k i ≤ 3000 , 1 ≤ x i , j ≤ 1000 , 1 ≤ t i ≤ 1 0 9 1 \leq n \leq 1000, \sum k_i \leq 3000,1 \leq x_{i,j} \leq 1000,1 \leq t_i \leq 10^9 1≤n≤1000,∑ki​≤3000,1≤xi,j​≤1000,1≤ti​≤109。
• 对于 100 % 100\% 100% 的测试点， 1 ≤ n ≤ 1 0 5 , ∑ k i ≤ 3 × 1 0 5 , 1 ≤ x i , j ≤ 1 0 5 , 1 ≤ t i ≤ 1 0 9 1 \leq n \leq 10^5,\sum k_i \leq 3\times 10^5, 1 \leq x_{i,j} \leq 10^5,1\leq t_i \leq 10^9 1≤n≤105,∑ki​≤3×105,1≤xi,j​≤105,1≤ti​≤109。

思路

这一题，我们看到题目，可以发现 ∑ k i ≤ 3 × 1 0 5 \sum k_i \leq 3\times 10^5 ∑ki​≤3×105 。
即所有 k i k_i ki​ 的和加在一起都只有 3 × 1 0 5 3\times 10^5 3×105，所以我们哪怕把所有旅客的身份信息都遍历一遍也不会超时。所以我们可以模拟一个队列，每次有新船只来的时候，我们就记录下这艘船上乘客的身份信息，并且用数组计数记录下某个国家的乘客有多少个。而用一个变量cnt记录下乘客国家种类数，即在每次给某个国家的乘客数加 1 1 1时，判断一下这个国家是否只有这一个乘客，如果是的话，那么国家种类数加一。
如果当前船只的到达时间与以前的某艘船的时间差距超过了一天的时间（86400秒），则减去这艘船上乘客。由于时间是递增的，所以如果第 l l l艘船已经不符合一天之内的要求了，则前面的船只也一定不会符合要求，所以只要用一个变量记录下左边界，然后每次从左边界开始判断，并且一直左边界右移即可。在减去乘客的过程中，如果某个乘客是这个国家唯一的乘客，那么这个国家就没有其他乘客了，国家种类数就要减 1 1 1。

时间复杂度

O ( k ) O(k) O(k)

空间复杂度

O ( n ) O(n) O(n)

代码

#include <bits/stdc++.h>
using namespace std ;
#define N (100005)
vector<int> a[N] ;
int n,t[N],k,x,c[N],num,li,cnt ; 
int main(){
    scanf("%d",&n) ;
    //输入船的数量 
    for(int i = 0;i < n;++ i){
        scanf("%d%d",&t[i],&k) ;
        //输入时间和人数 
        for(int o = 0;o < k;++ o){
            scanf("%d",&x) ;
            a[i].push_back(x) ;
            //记录下第i艘船的人都是从哪里来的 
            if((++ c[x]) == 1)++ cnt ;
            //如果这个国家以前没来过人，
			//而现在来了一个人，
			//则乘客的总国家种类数加一 
        }
        while(t[li] < (t[i] - 86399)){
        	//循环直到第li艘船在当前这艘船的一天之内
			//（86400秒） 
            for(int o = 0;o < a[li].size();++ o)
                if((-- c[a[li][o]]) == 0) -- cnt ;
            //减去这些人，如果减去的人刚好是这个国家
			//来的唯一一个人，则乘客的总国家种类数减一 
            ++ li ;
            //判断下一艘船 
        }
        printf("%d\n",cnt) ;
        //输出答案 
    }
    return 0 ;
}

[NOIP2016 普及组] 魔法阵

题干

题目背景

NOIP2016 普及组 T4

题目描述

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

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

大魔法师认为，当且仅当四个编号为 a , b , c , d a,b,c,d a,b,c,d 的魔法物品满足 X a < X b < X c < X d , X b − X a = 2 ( X d − X c ) 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​)，并且 X b − X a < ( X c − X b ) / 3 X_b-X_a<(X_c-X_b)/3 Xb​−Xa​<(Xc​−Xb​)/3 时，这四个魔法物品形成了一个魔法阵，他称这四个魔法物品分别为这个魔法阵的 A A A 物品， B B B 物品， C C C 物品， D D D 物品。

现在，大魔法师想要知道，对于每个魔法物品，作为某个魔法阵的 A A A 物品出现的次数，作为 B B B 物品的次数，作为 C C C 物品的次数，和作为 D D D 物品的次数。

输入格式

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

接下来 m m m 行，每行一个正整数，第 i + 1 i+1 i+1 行的正整数表示 X i X_i Xi​，即编号为 i i i 的物品的魔法值。

保证 1 ≤ n ≤ 15000 1 \le n \le 15000 1≤n≤15000， 1 ≤ m ≤ 40000 1 \le m \le 40000 1≤m≤40000， 1 ≤ X i ≤ n 1 \le X_i \le n 1≤Xi​≤n。每个 X i X_i Xi​ 是分别在合法范围内等概率随机生成的。

输出格式

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

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

样例 #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

提示

【样例解释 1 1 1】

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

• 物品 1 , 3 , 7 , 6 1,3,7,6 1,3,7,6，其魔法值分别为 1 , 7 , 26 , 29 1,7,26,29 1,7,26,29；
• 物品 1 , 5 , 2 , 7 1,5,2,7 1,5,2,7，其魔法值分别为 1 , 5 , 24 , 26 1,5,24,26 1,5,24,26；
• 物品 1 , 5 , 7 , 4 1,5,7,4 1,5,7,4，其魔法值分别为 1 , 5 , 26 , 28 1,5,26,28 1,5,26,28；
• 物品 1 , 5 , 8 , 7 1,5,8,7 1,5,8,7，其魔法值分别为 1 , 5 , 24 , 26 1,5,24,26 1,5,24,26；
• 物品 5 , 3 , 4 , 6 5,3,4,6 5,3,4,6，其魔法值分别为 5 , 7 , 28 , 29 5,7,28,29 5,7,28,29。

以物品 5 5 5 为例，它作为 A A A 物品出现了 1 1 1 次，作为 B B B 物品出现了 3 3 3 次，没有作为 C C C 物品或者 D D D 物品出现，所以这一行输出的四个数依次为 1 , 3 , 0 , 0 1,3,0,0 1,3,0,0。

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

【数据规模】

思路

由题可得：
X a < X b < X c < X d X_a<X_b<X_c<X_d Xa​<Xb​<Xc​<Xd​
X b − X a = 2 ( X d − X c ) X_b-X_a=2(X_d-X_c) Xb​−Xa​=2(Xd​−Xc​)
X b − X a < ( X c − X b ) / 3 X_b-X_a<(X_c-X_b)/3 Xb​−Xa​<(Xc​−Xb​)/3
发现，不是很好下手，所以我们就可以转化一下它们。
不难发现这里出现的最小的数就是 ( X D − X C ) (X_D - X_C) (XD​−XC​)了，
所以让我们尝试用 t t t 来表示 ( X D − X C ) (X_D - X_C) (XD​−XC​) ，并且把其他项也化成以 t t t 表示的格式。
整理一下可得：
( X d − X c ) = t (X_d - X_c) = t (Xd​−Xc​)=t
( X b − X a ) = 2 t (X_b - X_a) = 2t (Xb​−Xa​)=2t
( X c − X b ) > 6 t (X_c - X_b) > 6t (Xc​−Xb​)>6t
这样就好下手了：
由于题目中的数字的范围比数字的数量要大得多，所以直接用桶排序，一个数如果出现了多次直接乘上即可。下面为了简洁 ：
用 a a a 表示 X a X_a Xa​
用 b b b 表示 X b X_b Xb​
用 c c c 表示 X c X_c Xc​
用 d d d 表示 X d X_d Xd​
我们可以先枚举 t t t 。
很容易发现，a、b确定其中一个可以推出另一个，c、d确定其中一个可以推出另一个，而(a,b)和(c,d)之间并没有直接确定的关系，即只要符合 ( X c − X b ) > 6 t (X_c - X_b) > 6t (Xc​−Xb​)>6t 就可以。
所以先枚举了 a a a ，确定了一对 ( a , b ) (a,b) (a,b) 以后，一对符合条件的 ( c , d ) (c,d) (c,d) 以及所有更小的 ( c , d ) (c,d) (c,d) 都可以与这对(a,b)组成魔法阵。
以及枚举了 c c c ，确定了一对 ( c , d ) (c,d) (c,d) 以后，一对符合条件的 ( a , b ) (a,b) (a,b) 以及所有更大的 ( a , b ) (a,b) (a,b) 都可以与这对 ( c , d ) (c,d) (c,d) 组成魔法阵。
由上面就可以得出有一部分的计算是重复的，所以用一个变量计算前缀和，就能再省下一点时间。
而 t t t 只需要枚举 1 1 1 到 n / 9 n / 9 n/9 即可，因为 d d d 的取值范围是 9 ∗ t + 2 9 * t + 2 9∗t+2 到 n n n ，而 a a a 的取值范围是 n − 9 ∗ t − 1 n - 9 * t - 1 n−9∗t−1 到 1 1 1 。要不然就会有某一个变量取到负数或超过 n n n ，可以自己试一下。

时间复杂度

O ( n 2 / 9 ) O(n^2/9) O(n2/9)

空间复杂度

O ( n ) O(n) O(n)

代码

#include <bits/stdc++.h>
using namespace std ;
int n,m,x[40005],q[15005],p[15005][4] ;
int main(){
	scanf("%d%d",&n,&m) ;
	for(int i = 1;i <= m;++ i)scanf("%d",&x[i]),++ q[x[i]] ;
	//输入数据，数组计数 
	for(int t = 1;(t * 9) < n;++ t){
		int te = 0,a,b,c,d ;
		for(d = 9 * t + 2;d <= n;++ d){
			//枚举d 
			a = d - 9 * t - 1 ;
			//计算a 
			b = a + 2 * t ;
			//计算b 
			c = d - t ;
			//计算c 
			te += q[b] * q[a] ;
			//计算与c，d这两个位置相符的 
			//所有a，b的数量，累加在一起的和 
			p[d][3] += te * q[c] ;
			//计算位置c上的答案 
			p[c][2] += te * q[d] ;
			//计算位置d上的答案 
		}
		te = 0 ;
		//前缀和归零 
		for(a = n - 9 * t - 1;a >= 1;-- a){
			//枚举a 
			b = a + 2 * t ;
			//计算b 
			c = b + 6 * t + 1 ;
			//计算c 
			d = a + 9 * t + 1 ;
			//计算d 
			te += q[c] * q[d] ;
			//计算与a，b这两个位置相符的 
			//所有c，d的数量，累加在一起的和 
			p[a][0] += te * q[b] ;
			//计算位置a上的答案 
			p[b][1] += te * q[a] ;
			//计算位置c上的答案 
		}
	}
	for(int i = 1;i <= m;++ i){
		for(int o = 0;o < 4;++ o)
			printf("%d ",p[x[i]][o]) ;
		printf("\n") ;
		//输出答案 
	}
	return 0 ;
}

尾声

又成功地“秒杀”了一年的CSP/NOIP，祝读者水平高升，参加竞赛都能“秒杀”取得好成绩！

标签：24,10,NOIP,int,题解,样例,魔法阵,29,leq
From： https://blog.csdn.net/lixuean0408/article/details/140215412