【从算法小白到 csp-j 一等 第一节】枚举 + 模拟
- 内容提要
- 1.枚举
- 1.1枚举的定义
- 1.2 [NOIP1998 普及组] 三连击(1.00s,64.00MB)
- 题目背景
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 解法
- 1.3 平面上的最接近点对(1.00s,125.00MB)
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 提示
- 数据规模与约定
- 解法
- 1.4 习题
- 2 模拟
- 2.1 模拟的定义
- 2.2 [NOIP2015 提高组] 神奇的幻方
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 提示
- 解法
- 2.3 [NOIP2003 提高组] 侦探推理
- 题目描述
- 输入格式
- 输出格式
- 样例 #1
- 样例输入 #1
- 样例输出 #1
- 提示
- 解法
- 习题
- 结语
这里为整个【从算法小白到 csp-j 一等 】系列博客,欢迎阅读。
内容提要
本节讲解枚举和模拟算法,以及其在算法竞赛中的基础应用,并选择了几道习题进行举例讲解,让读者有对枚举和模拟算法的初步认识。
1.枚举
1.1枚举的定义
看个简单的例子。
1.2 [NOIP1998 普及组] 三连击(1.00s,64.00MB)
题目背景
本题为提交答案题,您可以写程序或手算在本机上算出答案后,直接提交答案文本,也可提交答案生成程序。
题目描述
将 1 , 2 , … , 9 1, 2, \ldots , 9 1,2,…,9 共 9 9 9 个数分成 3 3 3 组,分别组成 3 3 3 个三位数,且使这 3 3 3 个三位数构成 1 : 2 : 3 1 : 2 : 3 1:2:3 的比例,试求出所有满足条件的 3 3 3 个三位数。
输入格式
无
输出格式
若干行,每行 3 3 3 个数字。按照每行第 1 1 1 个数字升序排列。
样例 #1
样例输入 #1
无
样例输出 #1
192 384 576
* * *
...* * *
(剩余部分不予展示)
解法
这道题是一个经典的枚举问题。
考虑枚举三个数都是什么,最后判断一下是不是 1 1 1 ~ 9 9 9 都各一个并且满足 1 : 2 : 3 1 : 2 : 3 1:2:3 即可。时间复杂度 O ( 100 0 3 ) O(1000^3) O(10003), T L E TLE TLE。
考虑优化,我们发现,后两层枚举都是无意义的,因为如果第一个数确定,二三个数也就都确定为第一个数的两倍和三倍了,无需再进行枚举并判断。
于是直接枚举第一个数,然后计算出二三个数。判断一下是否 1 1 1 ~ 9 9 9 都各一个即可。时间复杂度 O ( 1000 ) O(1000) O(1000),可以通过本题。
再举个添加链接描述。
1.3 平面上的最接近点对(1.00s,125.00MB)
题目描述
给定平面上 n n n 个点,找出其中的一对点的距离,使得在这 n n n 个点的所有点对中,该距离为所有点对中最小的。
输入格式
第一行一个整数 n n n,表示点的个数。
接下来 n n n 行,每行两个整数 x , y x,y x,y ,表示一个点的行坐标和列坐标。
输出格式
仅一行,一个实数,表示最短距离,四舍五入保留 4 4 4 位小数。
样例 #1
样例输入 #1
3
1 1
1 2
2 2
样例输出 #1
1.0000
提示
数据规模与约定
对于 100 % 100\% 100% 的数据,保证 1 ≤ n ≤ 1 0 4 1 \leq n \leq 10^4 1≤n≤104, 0 ≤ x , y ≤ 1 0 9 0 \leq x, y \leq 10^9 0≤x,y≤109。
解法
这个问题相对于上个问题更加简单。
枚举每两个点即可,注意不能枚举自己和自己,这样距离会为零。枚举的时候第二个点的下标可以只大于第一个点的下标,因为两个点不管谁是第一个,谁是第二个都无所谓,谁在前都枚举会重复计算。但因为这题要求的是最小值,所以不会影响结果,只是第一次下标小于第二次下标更省时间。
设两点坐标为 ( x 0 , y 0 ) , ( x 1 , y 1 ) (x_0, y_0), (x_1, y_1) (x0,y0),(x1,y1),则两点间距离 d = ( x 0 − x 1 ) 2 + ( y 0 − y 1 ) 2 d = \sqrt{(x_0 - x_1) ^ 2 + (y_0 - y_1) ^ 2} d=(x0−x1)2+(y0−y1)2。
时间复杂度 O ( n 2 ) O(n ^ 2) O(n2),可以通过本题。
1.4 习题
[NOIP2004 普及组] 不高兴的津津
[NOIP2001 普及组] 最大公约数和最小公倍数问题
P1618 三连击(升级版)
第一题较简单,二、三题难度中等。
2 模拟
2.1 模拟的定义
模拟就是按照题目的要求直接做。
先来看一个例子。
2.2 [NOIP2015 提高组] 神奇的幻方
题目描述
幻方是一种很神奇的 N × N N\times N N×N 矩阵:它由数字 1 , 2 , 3 , ⋯ ⋯ , N × N 1,2,3,\cdots \cdots ,N \times N 1,2,3,⋯⋯,N×N 构成,且每行、每列及两条对角线上的数字之和都相同。
当 N N N 为奇数时,我们可以通过下方法构建一个幻方:
首先将 1 1 1 写在第一行的中间。
之后,按如下方式从小到大依次填写每个数 K ( K = 2 , 3 , ⋯ , N × N ) K \ (K=2,3,\cdots,N \times N) K (K=2,3,⋯,N×N) :
- 若 ( K − 1 ) (K-1) (K−1) 在第一行但不在最后一列,则将 K K K 填在最后一行, ( K − 1 ) (K-1) (K−1) 所在列的右一列;
- 若 ( K − 1 ) (K-1) (K−1) 在最后一列但不在第一行,则将 K K K 填在第一列, ( K − 1 ) (K-1) (K−1) 所在行的上一行;
- 若 ( K − 1 ) (K-1) (K−1) 在第一行最后一列,则将 K K K 填在 ( K − 1 ) (K-1) (K−1) 的正下方;
- 若 ( K − 1 ) (K-1) (K−1) 既不在第一行,也不在最后一列,如果 ( K − 1 ) (K-1) (K−1) 的右上方还未填数,则将 K K K 填在 ( K − 1 ) (K-1) (K−1) 的右上方,否则将 K K K 填在 ( K − 1 ) (K-1) (K−1) 的正下方。
现给定 N N N ,请按上述方法构造 N × N N \times N N×N 的幻方。
输入格式
一个正整数 N N N,即幻方的大小。
输出格式
共 N N N 行,每行 N N N 个整数,即按上述方法构造出的 N × N N \times N N×N 的幻方,相邻两个整数之间用单空格隔开。
样例 #1
样例输入 #1
3
样例输出 #1
8 1 6
3 5 7
4 9 2
提示
对于 100 % 100\% 100% 的数据,对于全部数据, 1 ≤ N ≤ 39 1 \leq N \leq 39 1≤N≤39 且 N N N 为奇数。
解法
本题直接按照提议模拟即可,具体来说按照如下规则(摘自题面):
首先将 1 1 1 写在第一行的中间。
之后,按如下方式从小到大依次填写每个数 K ( K = 2 , 3 , ⋯ , N × N ) K \ (K=2,3,\cdots,N \times N) K (K=2,3,⋯,N×N) :
- 若 ( K − 1 ) (K-1) (K−1) 在第一行但不在最后一列,则将 K K K 填在最后一行, ( K − 1 ) (K-1) (K−1) 所在列的右一列;
- 若 ( K − 1 ) (K-1) (K−1) 在最后一列但不在第一行,则将 K K K 填在第一列, ( K − 1 ) (K-1) (K−1) 所在行的上一行;
- 若 ( K − 1 ) (K-1) (K−1) 在第一行最后一列,则将 K K K 填在 ( K − 1 ) (K-1) (K−1) 的正下方;
- 若 ( K − 1 ) (K-1) (K−1) 既不在第一行,也不在最后一列,如果 ( K − 1 ) (K-1) (K−1) 的右上方还未填数,则将 K K K 填在 ( K − 1 ) (K-1) (K−1) 的右上方,否则将 K K K 填在 ( K − 1 ) (K-1) (K−1) 的正下方。
由于所有操作都是直接 O ( 1 ) O(1) O(1) 一步到位,共要动 n 2 n ^ 2 n2 次,所以时间复杂度为 O ( n 2 ) O(n ^ 2) O(n2),可以通过本题。
再来一个很困难的。
2.3 [NOIP2003 提高组] 侦探推理
题目描述
明明同学最近迷上了侦探漫画《柯南》并沉醉于推理游戏之中,于是他召集了一群同学玩推理游戏。游戏的内容是这样的,明明的同学们先商量好由其中的一个人充当罪犯(在明明不知情的情况下),明明的任务就是找出这个罪犯。接着,明明逐个询问每一个同学,被询问者可能会说:
证词内容 证词含义 I am guilty. 我是罪犯。 I am not guilty. 我不是罪犯。 XXX is guilty. XXX 是罪犯。其中 XXX 表示某个同学的名字。 XXX is not guilty. XXX 不是罪犯。 Today is XXX . 今天是 XXX 。其中 XXX 表示某个星期的单词。 星期只有可能是以下之一: Monday , Tuesday , Wednesday , Thursday , Friday , Saturday , Sunday 。 \def\arraystretch{1.5} \begin{array}{|l|l|}\hline \textbf{\textsf{证词内容}} & \textbf{\textsf{证词含义}}\\\hline \text{I am guilty.} & \text{我是罪犯。} \\\hline \text{I am not guilty.} & \text{我不是罪犯。} \\\hline \text{{\tt XXX} is guilty.} & \text{{\tt XXX} 是罪犯。其中 {\tt XXX} 表示某个同学的名字。} \\\hline \text{{\tt XXX} is not guilty.} & \text{{\tt XXX} 不是罪犯。} \\\hline \text{Today is {\tt XXX}.} & \begin{aligned} &\text{今天是 {\tt XXX}。其中 {\tt XXX} 表示某个星期的单词。}\\ &\text{星期只有可能是以下之一:}\\ &\texttt{Monday}, \texttt{Tuesday}, \texttt{Wednesday}, \texttt{Thursday}, \\ &\texttt{Friday}, \texttt{Saturday}, \texttt{Sunday}。 \end{aligned} \\\hline \end{array} 证词内容I am guilty.I am not guilty.XXX is guilty.XXX is not guilty.Today is XXX.证词含义我是罪犯。我不是罪犯。XXX 是罪犯。其中 XXX 表示某个同学的名字。XXX 不是罪犯。今天是 XXX。其中 XXX 表示某个星期的单词。星期只有可能是以下之一:Monday,Tuesday,Wednesday,Thursday,Friday,Saturday,Sunday。
证词中出现的其他话,都不列入逻辑推理的内容。
明明所知道的是,他的同学中有 N N N 个人始终说假话,其余的人始终说真。
现在,明明需要你帮助他从他同学的话中推断出谁是真正的凶手,请记住,凶手只有一个!
输入格式
输入由若干行组成。
第一行有三个整数, M , N M,N M,N 和 P P P。 M M M 是参加游戏的明明的同学数, N N N 是其中始终说谎的人数, P P P 是证言的总数。
接下来 M M M 行,每行是明明的一个同学的名字(英文字母组成,没有空格,全部大写)。
往后有 P P P 行,每行开始是某个同学的名宇,紧跟着一个冒号和一个空格,后面是一句证词,符合前表中所列格式。证词每行不会超过 250 250 250 个字符。
输入中不会出现连续的两个空格,而且每行开头和结尾也没有空格。
输出格式
如果你的程序能确定谁是罪犯,则输出他的名字;如果程序判断出不止一个人可能是罪犯,则输出 Cannot Determine
;如果程序判断出没有人可能成为罪犯,则输出 Impossible
。
样例 #1
样例输入 #1
3 1 5
MIKE
CHARLES
KATE
MIKE: I am guilty.
MIKE: Today is Sunday.
CHARLES: MIKE is guilty.
KATE: I am guilty.
KATE: How are you??
样例输出 #1
MIKE
提示
对于 100 % 100\% 100% 数据,满足 1 ≤ M ≤ 20 1\le M\le 20 1≤M≤20, 0 ≤ N ≤ M 0\le N\le M 0≤N≤M, 1 ≤ P ≤ 100 1\le P\le 100 1≤P≤100。
解法
先进行枚举,枚举凶手和星期。再根据题目进行模拟,判断出每句话是真话还是假话,然后从前往后扫,如果有矛盾或人数不符就跳过这种情况,否则把当前凶手记录下来。最后进行判断,如果人数为 0 0 0 则输出 Impossible
,如果人数为 1 1 1 则输出凶手编号,如果人数 > 1 > 1 >1 输出 Cannot Determine
即可。
本题需要用到字符串处理,需要读者对 s u b s t r substr substr 等字符串函数有一定的了解(或者直接手动实现这些函数)。
习题
[NOIP2005 普及组] 校门外的树
[NOIP1999 普及组] Cantor 表
[NOIP2008 普及组] ISBN 号码
绘制二叉树
其中第一题较简单,二、三题难度中等,第四题较为困难。