《noip模拟总结》PPT课件.ppt

1、模拟,by windfinder,模拟综述,试题描述中是怎么做的，程序就模拟怎么做，该进时进，该退时退，须记录时就记录（变量赋值）。选择合适的数据结构如标记变量（或者数组）、栈、队列、树等，这样才能方便程序的实现，数据清晰，不该有的交叉绝对不能有，正如数学上函数的对应关系一样，f(x)对于某一个x有一个唯一确定的值与它对应。,Noip中的模拟,前几年的NOIP复赛第一题基本上都可以通过模拟或者再结合其它的一些基本算法就可以完成。如NOIP2010第一道题. 某道题如果你不能确定套用什么典型算法来实现，那么你就模拟吧！,模拟分类,模拟： 分为三类： 普通模拟（完全模拟的较少，大多为结合贪心 。排

2、序的，贪心 。 排序的不单独讨论） 历届试题：NOIP多项式输出数列 NOIP 多项式输出.： 多项式输出:这道题想要拿分很容易，但要注意一下模拟过程，此题实际上需有4个判段过程，其中有一个是极易遗漏的。 数列:这道题竟是第4题,很简单的模拟题,还可用转成2进制的方式直接算. 字符模拟 历届试题：NOIP ISBN号码 Jam记数法 立体图 ISBN号码: 总体难度不大，这道题如果是使用C语言的话，可以用 每个字符都减去字符0 的方式，直接把它们从字符转为数字,再进行处理。 Jam记数法:很绝对的模拟,一开始我还认为是数学知识模拟题,就是从后往前推. 立体图:很难的很考细心的一道模拟题,没说的

3、,就是上机不断的调程序. 数学知识模拟 历届试题：NOIP 细胞分裂 初中组目前唯一一道数学知识模拟题，掌握了相关的知识就应该不难，这道题要满分还是比较难的，需要高精度运算（用LONG LONG 型不知道可不可以）,还有一定要注意时间问题,这道题极易超时.,小试牛刀,学校里有一个水房，水房里一共装有m 个龙头可供同学们打开水，每个龙头每秒钟的供水量相等，均为1。现在有n 名同学准备接水，他们的初始接水顺序已经确定。将这些同学按接水顺序从1到n 编号，i 号同学的接水量为wi。接水开始时，1 到m 号同学各占一个水龙头，并同时打开水龙头接水。当其中某名同学j 完成其接水量要求wj 后，下一名排队

4、等候接水的同学k马上接替j 同学的位置开始接水。这个换人的过程是瞬间完成的，且没有任何水的浪费。即j 同学第x 秒结束时完成接水，则k 同学第x+1 秒立刻开始接水。若当前接水人数n不足m，则只有n个龙头供水，其它m；n个龙头关闭。现在给出n 名同学的接水量，按照上述接水规则，问所有同学都接完水需要多少秒。 输入格式 第1 行2 个整数n 和m，用一个空格隔开，分别表示接水人数和龙头个数。第2 行n 个整数w1、w2、wn，每两个整数之间用一个空格隔开，wi 表示i 号同学的接水量。 输出格式 输出只有一行，1 个整数，表示接水所需的总时间 样例输入 【输入输出样例1】 5 3 4 4 1 2

5、 1 【输入输出样例1】 4,此题巨水无比把所有人 按顺序塞入当前时间最短的那个水龙头 最后找时间最长的水龙头就行了优化 前M个人直接塞入M个水龙头中预计得分 AC实际得分 AC程序复杂度 0程序长度 低 另： 此题不是贪心，切忌贪心,普通模拟,一元 n 次多项式可用如下的表达式表示： 其中，a_ixi 称为i次项，a_i称为i 次项的系数。给出一个一元多项式各项的次数和系数，请按照如下规定的格式要求输出该多项式：1. 多项式中自变量为x，从左到右按照次数递减顺序给出多项式。2. 多项式中只包含系数不为0 的项。3. 如果多项式n 次项系数为正，则多项式开头不出现“+”号，如果多项式n 次项系

6、数为负，则多项式以“-”号开头。4. 对于不是最高次的项，以“+”号或者“-”号连接此项与前一项，分别表示此项系数为正或者系数为负。紧跟一个正整数，表示此项系数的绝对值（如果一个高于0 次的项，其系数的绝对值为1，则无需输出1）。如果x 的指数大于1，则接下来紧跟的指数部分的形式为“xb”，其中b 为x 的指数；如果x 的指数为1，则接下来紧跟的指数部分形式为“x”；如果x 的指数为0，则仅需输出系数即可。5. 多项式中，多项式的开头、结尾不含多余的空格。【数据范围】1 n 100，多项式各次项系数的绝对值均不超过100。 输入格式 共有2 行。第一行 1 个整数，n，表示一元多项式的次数。第

7、二行有 n+1 个整数，其中第i 个整数表示第n-i+1 次项的系数，每两个整数之间用空 输出格式 共1 行，按题目所述格式输出多项式。 输入格式 共有2 行。第一行 1 个整数，n，表示一元多项式的次数。第二行有 n+1 个整数，其中第i 个整数表示第n-i+1 次项的系数，每两个整数之间用空 输出格式 共1 行，按题目所述格式输出多项式。 【输入样例1】 5 100 -1 1 -3 0 10 【输出样例1】 100 x5-x4+x3-3x2+10,字符模拟：,ISBN号码【问题描述】每一本正式出版的图书都有一个ISBN号码与之对应，ISBN码包括9位数字、1位识别码和3位分隔符，其规定格式

8、如“x-xxx-xxxxx-x”，其中符号“-”是分隔符（键盘上的减号），最后一位是识别码，例如0-670-82162-4就是一个标准的ISBN码。ISBN码的首位数字表示书籍的出版语言，例如0代表英语；第一个分隔符“-”之后的三位数字代表出版社，例如670代表维京出版社；第二个分隔之后的五位数字代表该书在出版社的编号；最后一位为识别码。识别码的计算方法如下：首位数字乘以1加上次位数字乘以2以此类推，用所得的结果mod 11，所得的余数即为识别码，如果余数为10，则识别码为大写字母X。例如ISBN号码0-670-82162-4中的识别码4是这样得到的：对067082162这9个数字，从左至右，

9、分别乘以1，2，9，再求和，即01+62+29=158，然后取158 mod 11的结果4作为识别码。你的任务是编写程序判断输入的ISBN号码中识别码是否正确，如果正确，则仅输出“Right”；如果错误，则输出你认为是正确的ISBN号码。【输入】输入文件isbn.in只有一行，是一个字符序列，表示一本书的ISBN号码（保证输入符合ISBN号码的格式要求）。【输出】输出文件isbn.out共一行，假如输入的ISBN号码的识别码正确，那么输出“Right”，否则，按照规定的格式，输出正确的ISBN号码（包括分隔符“-”）。【特别说明】输出文件最后会多一个空行。【输入输出样例1】isbn.in0-6

10、70-82162-4isbn.outRight【输入输出样例2】isbn.in：0-670-82162-0isbn.out：0-670-82162-4,ISBN号码 解题思路：本题主要考查基本编程能力。数组 char isbn20 用来保存输入的ISBN号码，可将输入数据以字符串的方式读入数组isbn中。ISBN号码共有13位，存放在数组下标为012的元素中，其中isbn12是识别码，本题需验证这一位是否正确。根据ASCII码将isbn数组中的规定位上字符转换成数字，然后根据识别码公式计算出正确的识别码，并与isbn12中字符进行比较。识别码计算公式如下：（ (isbn0-0)+(isbn2-

11、0)*2+(isbn3-0)*3+(isbn4-0)*4+(isbn6-0)*5+(isbn7-0)*6+(isbn8-0)*7+(isbn9-0)*8+(isbn10-0)*9 ）%11,核心代码如下：char isbn20; int idCode=0; cin isbn;/以字符串的形式读入isbn码到数组isbn中idCode = (isbn0-0)+(isbn2-0)*2+(isbn3-0)*3+(isbn4-0)*4+(isbn6-0)*5+(isbn7-0)*6+(isbn8-0)*7+(isbn9-0)*8+(isbn10-0)*9; idCode = idCode%11;/计算

12、识别码if (idCode10)if ( isbn12 = idCode+0 )/识别码正确cout Right endl;else/识别码不正确isbn12 = idCode+0;cout isbn endl;else if (isbn12 = X)/识别码正确cout Right endl;else/识别码不正确isbn12 = X;cout isbn endl;,数学模拟：,描述Hanks 博士是BT (Bio-Tech，生物技术) 领域的知名专家。现在，他正在为一个细胞实验做准备工作：培养细胞样本。Hanks 博士手里现在有N 种细胞，编号从1N，一个第i 种细胞经过1 秒钟可以分裂为

13、Si 个同种细胞（Si 为正整数）。现在他需要选取某种细胞的一个放进培养皿，让其自由分裂，进行培养。一段时间以后，再把培养皿中的所有细胞平均分入M 个试管，形成M 份样本，用于实验。Hanks 博士的试管数M 很大，普通的计算机的基本数据类型无法存储这样大的M 值，但万幸的是，M 总可以表示为m1 的m2 次方，即M = m1m2 ，其中m1，m2 均为基本数据类型可以存储的正整数。注意，整个实验过程中不允许分割单个细胞，比如某个时刻若培养皿中有4 个细胞，Hanks 博士可以把它们分入2 个试管，每试管内2 个，然后开始实验。但如果培养皿中有5个细胞，博士就无法将它们均分入2 个试管。此时，

14、博士就只能等待一段时间，让细胞们继续分裂，使得其个数可以均分，或是干脆改换另一种细胞培养。为了能让实验尽早开始，Hanks 博士在选定一种细胞开始培养后，总是在得到的细胞“刚好可以平均分入M 个试管”时停止细胞培养并开始实验。现在博士希望知道，选择哪种细胞培养，可以使得实验的开始时间最早。 输入格式输入文件名为 cell.in，共有三行。第一行有一个正整数 N，代表细胞种数。第二行有两个正整数 m1，m2，以一个空格隔开，m1m2即表示试管的总数M。第三行有 N 个正整数，第i 个数Si 表示第i 种细胞经过1 秒钟可以分裂成同种细胞的个数。输出格式输出文件 cell.out 共一行，为一个整

15、数，表示从开始培养细胞到实验能够开始所经过的最少时间（单位为秒）。 如果无论 Hanks 博士选择哪种细胞都不能满足要求，则输出整数-1。 样例输入112 13 样例输出1-1 输入输出样例1 说明：经过 1 秒钟，细胞分裂成3 个，经过2 秒钟，细胞分裂成9 个，可以看出无论怎么分裂，细胞的个数都是奇数，因此永远不能分入2 个试管。 样例输入 2224 130 12 样例输出 22 输入输出样例2 说明：第 1 种细胞最早在3 秒后才能均分入24 个试管，而第2 种最早在2 秒后就可以均分（每试管144/(241)=6 个）。故实验最早可以在2 秒后开始。 数据范围 对于 50%的数据，有m

16、1m2 30000。 对于所有的数据，有1 N 10000，1 m1 30000，1 m2 10000，1 Si 2,000,000,000。,总的来说就算是 分解质因数 由于m1=30000,m2=10000，根本无法直接计算，所以需要 通过数学分析得出答案。如果一个数能够整除另一个数，那么这个数因数分解后一定有另一个数所有的元素，且每个元素个数均大于等于另一个数相同元素的个数。因此我们可以先对m1进行因数分解，并将对应元素的个数乘以m2。之后读入每个数，判断该数因数分解后是否有m1中所有的元素。如果有的话，则计算该细胞最大的分裂次数，即对应m1种元素个数/si中元素个数后向上取整。最后更新

17、答案即可。 注意因数分解中1比较特殊，所以要单独判断一下。,1机器翻译(translate.pas/c/cpp)【问题描述】小晨的电脑上安装了一个机器翻译软件，他经常用这个软件来翻译英语文章。这个翻译软件的原理很简单，它只是从头到尾，依次将每个英文单词用对应的中文含义来替换。对于每个英文单词，软件会先在内存中查找这个单词的中文含义，如果内存中有，软件就会用它进行翻译；如果内存中没有，软件就会在外存中的词典内查找，查出单词的中文含义然后翻译，并将这个单词和译义放入内存，以备后续的查找和翻译。假设内存中有M 个单元，每单元能存放一个单词和译义。每当软件将一个新单词存入内存前，如果当前内存中已存入的

18、单词数不超过M1，软件会将新单词存入一个未使用的内存单元；若内存中已存入M 个单词，软件会清空最早进入内存的那个单词，腾出单元来，存放新单词。假设一篇英语文章的长度为N 个单词。给定这篇待译文章，翻译软件需要去外存查找多少次词典？假设在翻译开始前，内存中没有任何单词。【输入】输入文件名为translate.in，输入文件共2 行。每行中两个数之间用一个空格隔开。第一行为两个正整数M 和N，代表内存容量和文章的长度。第二行为N 个非负整数，按照文章的顺序，每个数（大小不超过1000）代表一个英文单词。文章中两个单词是同一个单词，当且仅当它们对应的非负整数相同。【输出】输出文件translate.out 共1 行，包含一个整数，为软件需要查词典的次数。【输入输出样例1】3 71 2 1 5 4 4 15【输入输出样例 1 说