【从算法小白到 csp-j 一等 第一节】枚举 + 模拟

embedded/2024/12/27 11:25:53/

【从算法小白到 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 1n104 0 ≤ x , y ≤ 1 0 9 0 \leq x, y \leq 10^9 0x,y109

解法

这个问题相对于上个问题更加简单。

枚举每两个点即可,注意不能枚举自己和自己,这样距离会为零。枚举的时候第二个点的下标可以只大于第一个点的下标,因为两个点不管谁是第一个,谁是第二个都无所谓,谁在前都枚举会重复计算。但因为这题要求的是最小值,所以不会影响结果,只是第一次下标小于第二次下标更省时间。

设两点坐标为 ( 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=(x0x1)2+(y0y1)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)

  1. ( K − 1 ) (K-1) (K1) 在第一行但不在最后一列,则将 K K K 填在最后一行, ( K − 1 ) (K-1) (K1) 所在列的右一列;
  2. ( K − 1 ) (K-1) (K1) 在最后一列但不在第一行,则将 K K K 填在第一列, ( K − 1 ) (K-1) (K1) 所在行的上一行;
  3. ( K − 1 ) (K-1) (K1) 在第一行最后一列,则将 K K K 填在 ( K − 1 ) (K-1) (K1) 的正下方;
  4. ( K − 1 ) (K-1) (K1) 既不在第一行,也不在最后一列,如果 ( K − 1 ) (K-1) (K1) 的右上方还未填数,则将 K K K 填在 ( K − 1 ) (K-1) (K1) 的右上方,否则将 K K K 填在 ( K − 1 ) (K-1) (K1) 的正下方。

现给定 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 1N39 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)

  1. ( K − 1 ) (K-1) (K1) 在第一行但不在最后一列,则将 K K K 填在最后一行, ( K − 1 ) (K-1) (K1) 所在列的右一列;
  2. ( K − 1 ) (K-1) (K1) 在最后一列但不在第一行,则将 K K K 填在第一列, ( K − 1 ) (K-1) (K1) 所在行的上一行;
  3. ( K − 1 ) (K-1) (K1) 在第一行最后一列,则将 K K K 填在 ( K − 1 ) (K-1) (K1) 的正下方;
  4. ( K − 1 ) (K-1) (K1) 既不在第一行,也不在最后一列,如果 ( K − 1 ) (K-1) (K1) 的右上方还未填数,则将 K K K 填在 ( K − 1 ) (K-1) (K1) 的右上方,否则将 K K K 填在 ( K − 1 ) (K-1) (K1) 的正下方。

由于所有操作都是直接 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 1M20 0 ≤ N ≤ M 0\le N\le M 0NM 1 ≤ P ≤ 100 1\le P\le 100 1P100

解法

这是一道枚举模拟相结合的题目。

先进行枚举枚举凶手和星期。再根据题目进行模拟,判断出每句话是真话还是假话,然后从前往后扫,如果有矛盾或人数不符就跳过这种情况,否则把当前凶手记录下来。最后进行判断,如果人数为 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 号码
绘制二叉树

其中第一题较简单,二、三题难度中等,第四题较为困难。

结语

枚举模拟虽基础,但他们是其他更难算法的铺垫,只有打好基础,才能在日后的学习中更加轻松。


http://www.ppmy.cn/embedded/149160.html

相关文章

主从复制架构介绍和主从复制配置案例

每一个数据库的业务都对应着一个前端的业务, 主从复制架构的必要性? 第一点是两个服务器如果有一台服务器出现故障,那么另一台服务器可以正常工作,以保障前端业务可以被正常访问,第二点是两个服务器可以共同去处理数据&#xff…

智能眼镜_AI眼镜基于紫光展锐W517方案定制开发

AI眼镜的国产方案搭载紫光展锐的W517穿戴芯片,该芯片采用12纳米制程技术,采用了1A752.0GHz和3A551.8GHz的大小核架构,配合无级变速系统调度与先进的3D SiP高集成技术,使得整体电路板尺寸较前一代产品缩小了40%。其高阶EPOP封装设计…

【java面向对象编程】第九弹----抽象类、接口、内部类

笔上得来终觉浅,绝知此事要躬行 🔥 个人主页:星云爱编程 🔥 所属专栏:javase 🌷追光的人,终会万丈光芒 🎉欢迎大家点赞👍评论📝收藏⭐文章 一、抽象类 1.1基本介绍 &…

flink-1.16 table sql 消费 kafka 数据,指定时间戳位置消费数据报错:Invalid negative offset 问题解决

1 背景 1.使用 flink-1.16 的 table sql 消费 kafka数据,并使用 sql 计算指标,然后写入 doris; 2.指标计算时,需要统计当日数据条数,考虑到作业异常退出被重新拉起时,需要从零点开始消费,所以…

虚幻引擎结构之UWorld

Uworld -> Ulevel ->Actors -> AActor 在虚幻引擎中,UWorld 类扮演着至关重要的角色,它就像是游戏世界的总指挥。作为游戏世界的核心容器,UWorld 包含了构成游戏体验的众多元素,从游戏实体到关卡设计,再到物…

ffmpeg源码分析(九)解协议

本文将聚焦于FFmpeg协议处理模块,以avformat_open_input函数为核心,详细剖析其在最新FFmpeg源码中的实现。 音视频处理流程简介 avformat_open_input概述 avformat_open_input是FFmpeg用于打开输入多媒体数据的关键函数。它通过统一的接口处理多种协议…

详细介绍Sd-WebUI提示词的语法规则

AI绘画中最大的门槛就是提示词,对英语水平、文学水平、想象力、灵感等要求较高。不能每次一输入正向提示词(positive prompt),就只会写a girl, big eyes, red hair。虽然sd-webui软件可以直接翻译,输入一个子母后会立刻…

重发布技术

重发布 在路由协议的边界设备上,将某一种路由协议的路由信息引入到另一种路由协议中,这个操作被称为路由引入或者路由重分发。----技术本质为重发布。 条件 必须存在ASBR设备(路由边界设备)---同时连接两种协议或两个进程&#…