注释说明
1≤单词长度≤10。 1≤文章长度≤1,000,000。
六、简单动态规划类试题
动态规划是解决多阶段决策最优化问题的一种思想方 法。一般我们从初始阶段出发，枚举每个阶段的所有 状态，在状态转移的过程中，我们需要决策。根据每 一步所选决策的不同，将随即引起状态的转移，最终 在变化的状态中产生一个决策序列。动态规划就是为 了使产生的决策序列在符合某种条件下达到最优。
样例输出：6
扫雷游戏 (noip2015普及组第二题)
扫雷游戏是一款十分经典的单机小游戏。 在 n 行 m 列的雷区中有一些格子含有地雷 （称之为地雷格） ，其他格子不含地雷（称之 为非地雷格） 。玩家翻开一个非地雷格时，该 格将会出现一个数字——提示周围格子中有多 少个是地雷格。 游戏的目标是在不翻出任何地 雷格的条件下，找出所有的非地雷格。
输入样例：
70 3 71 100
69 1 12
输出样例：
3
（1 <= T <= 1000） （1 <= M <= 100）
采药 （noip2005普及组第三题）
题目大意：共m株草药，每株草药有一个价值 和采摘的时间，问t时间能采摘到的草药的最大 价值。
统计单词个数 (noip2011普及组第二题) 样例输入1： To to be or not to be is a question
样例输出1： 20
样例输入2： to Did the Ottoman Empire lose its power at that time
样例输出2： -1 【输入输出样例2说明】 表示给定的单词to在文章中没有出现，输出整数-1。
输入样例 2 23 ?*? *??
输出样例 2 mine.out 2*1 *21
对于 100%的数据，1≤n≤100，1≤m≤100
比例简化 (noip2014普及组第二题)
在社交媒体上，经常会看到针对某一个观点同意与 否的民意调查以及结果。例如，对某 一观点表示 支持的有 1498 人，反对的有 902 人，那么赞同与 反对的比例可以简单的记为1498:902。
输入格式
输入共一行，包含三个整数 n，i，j，每两个整数 之间用一个空格隔开，分别表示矩阵大小、待求的 数所在的行号和列号。
输出格式
输出共一行，包含一个整数，表示相应矩阵中第 i 行第 j 列的数。
样例输入：4 2 3
样例输出：14
对于 50%的数据，1 ≤ n ≤ 100; 对于 100%的数据，1 ≤ n ≤ 30,000，1 ≤ i ≤ n，1 ≤ j ≤ n。
贪心
NOIP普及组题型分布
题型
简单 动态规划
题目 子矩阵(2014p4)、小朋友的数字(2013p3)
数学/数论
数据结构 图论（提高组）
表达式求值(2013p2)、 车站分级(2013p4 拓扑排序)
一、枚举类试题
枚举法的基本思想是根据提出的问题枚举所 有可能的解，并用问题给定的条件检验哪些 解是需要的，哪些解是不需要的。能使条件 成立，即为其解。
NOIP普及组历届试题分析
NOIP普及组题型分布
题型 枚举 模拟 字符串
题目 扫雷游戏(2015p2)、珠心算测验(2014p1)
数字统计(2010p1)、比例简化(2014p2) 金币(2015p1)、
螺旋方阵(2014p3)、计数问题(2013p1)、
数字反转(2011p1)、统计单词个数(2011p2)
不过，如果把调查结果就以这种方式呈现出来，大 多数人肯定不会满意。因为这个比例的数值太大， 难以一眼看出它们的关系。对于上面这个例子，如 果把比例记为 5:3，虽然与 真实结果有一定的误差， 但依然能够较为准确地反映调查结果，同时也显得 比较直观。
现给出支持人数 A，反对人数 B，以及一个上限 L， 请你将 A 比 B 化简为 A’比 B’，要求在 A’和 B’均 不大于 L 且 A’和 B’互质（两个整数的最大公约数 是 1）的前提下，A’/B’ ≥ A/B 且 A’/B’ - A/B 的值 尽可能小。
螺旋方阵试题分析
目标位置(i,j)到底在当前这一圈的第几个位置？ 如目标数26所在的位置(4,5)，在第2圈的什么位
置？ 分两种情况： 1）目标数(i,j)在上行或右行； i+j-2q+1 2）目标数(i,j)在下行或左行； 距离第一个数的距离
i+j-2q+1
计数问题 (noip2013普及组第一题)
比如在给定范围[2, 22]，数字2在数2中出现了1次，在 数12中出现了1次，在数20中出现了1次，在数21中出 现了1次，在数22中出现了2次，所以数字2在该范围内 一共出现了6次。
输入格式
输入共一行，为两个正整数L和R，之间用一个空格隔 开。
输出格式
输出共1行，表示数字2出现的次数。
样例输入：2 22
采药 （noip2005普及组第三题）
输入格式：
第一行有两个整数T和M，T代表总共能够用来采药的时间，M 代表山洞里的草药的数目。接下来的M行每行包括两个在1到 100之间（包括1和100）的整数，分别表示采摘某株草药的时 间和这株草药的价值。
输出格式：
一行只包含一个整数，表示在规定的时间内，可以采到的草药 的最大总价值。
试计算在区间1到n的所有整数中，数字x（0≤x≤9） 共出现了多少次？ 例如，在1到11中，即在1、2、3、4、5、6、7、8、 9、10、11中，数字1出现了4次。
输入：
输入共1行，包含2个整数n、x，之间用一个空格隔 开。 输出：
输出共1行，包含一个整数，表示x出现的次数。 输入示例： 11 1 输出示例： 4 其他说明：
输入 输入共1行，一个整数N。
输出 输出共1行，一个整数，表示反转后的新数。
样例输入
123 样例输出
321
统计单词个数 (noip2011普及组第二题)
一般的文本编辑器都有查找单词的功能，该功 能可以快速定位特定单词在文章中的位置，有 的还能统计出特定单词在文章中出现的次数。 现在，请你编程实现这一功能，具体要求 是：给定一个单词，请你输出它在给定的文章 中出现的次数和第一次出现的位置。注意：匹 配单词时，不区分大小写，但要求完全匹配， 即给定单词必须与文章中的某一独立单词在不 区分大小写的情况下完全相同（参见样例1）， 如果给定单词仅是文章中某一单词的一部分则 不算匹配（参见样例2）。
枚举法其实是最简单的搜索算法。
珠心算测验 (noip2014普及组第一题)
珠心算是一种通过在脑中模拟算盘变化来完成快 速运算的一种计算技术。珠心算训练，既能够开 发智力，又能够为日常生活带来很多便利，因而 在很多学校得到普及。
某学校的珠心算老师采用一种快速考察珠心算加 法能力的测验方法。他随机生成一个正整数集合， 集合中的数各不相同，然后要求学生回答：其中 有多少个数，恰好等于集合中另外两个（不同的） 数之和？ 最近老师出了一些测验题，请你帮忙求 出答案。
普及组一般考查的动态规划：01背包，最长上升子序 列，一些简单的线性动规。
采药 （noip2005普及组第三题）
辰辰是个天资聪颖的孩子，他的梦想是成为世 界上最伟大的医师。为此，他想拜附近最有威 望的医师为师。医师为了判断他的资质，给他 出了一个难题。医师把他带到一个到处都是草 药的山洞里对他说：“孩子，这个山洞里有一 些不同的草药，采每一株都需要一些时间，每 一株也有它自身的价值。我会给你一段时间， 在这段时间里，你可以采到一些草药。如果你 是一个聪明的孩子，你应该可以让采到的草药 的总价值最大。”
输入格式： 输入文件只有1行，包含一个正整数K，表示发放金币的天数。
输出格式： 输出文件只有1行，包含一个正整数，即骑士收到的金币数。
输入输出样例
输入样例：
1000 输出样例：
29820
螺旋方阵 (noip2014普及组第三题)
一个n行n列的螺旋矩阵可由如下方法生成： 从矩阵的左上角(第1行第1列)出发，初始时向右
对于100%的数据，1≤n≤1,000,000，0≤x≤9。
三、字符串类试题
对于字符串、表达式的求解、 大整数的处理 等等，我们经常采用字符串来处理。
字符串处理常见函数：
数字反转 (noip2011普及组第一题)
给定一个整数，请将该数各个位上数字反转得到一个新 数。新数也应满足整数的常见形式，即除非给定的原数 为零，否则反转后得到的新数的最高位数字不应为零 （如：输入-380，输出-83）。
统计单词个数 (noip2011普及组第二题)
输入格式
第1行为一个字符串，其中只含字母，表示给定单词； 第2行为一个字符串，其中只可能包含字母和空格， 表示给定的文章。
输出格式
只有一行，如果在文章中找到给定单词则输出两个整 数，两个整数之间用一个空格隔开，分别是单词在文 章中出现的次数和第一次出现的位置（即在文章中第 一次出现时，单词首字母在文章中的位置，位置从0 开始）；如果单词在文章中没有出现，则直接输出一 个整数-1。
比例简化 (noip2014普及组第二题)
输入格式 输入共一行，包含三个整数 A，B，L，每两个整
数之间用一个空格隔开，分别表示支持人数、反对 人数以及上限。 输出格式 输出共一行，包含两个整数 A’，B’，中间用一个 空格隔开，表示化简后的比例。 样例输入
1498 902 10 样例输出
螺旋方阵试题分析
本题首先让我们想到传统的模拟，从[1,1]开 始往数组中填充数字，但对于[30000,30000] 的数组，直接爆零。
对于读入的n, x, y，先判断(x,y)在第几圈， 再模拟圈内的数字。
螺旋方阵试题分析
如：n=4, (2,2)在第2圈，(3,1)在第1圈。 n=6，(4,5)在第2圈
现在给出n行m列的雷区中的地雷分布， 要 求计算出每个非地雷格周围的地雷格数。