20200917 算法培训

一、KMP

实现KMP算法，并求next[]与nextval[]

输入描述：输入一行字符串，其中只含字母
输出描述：见示例

示例1：
输入：
ababaaababaa
输出：

二、统计单词数

来源：牛客网

一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。
现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章
中的某一独立单词在不区分大小写的情况下完全相同（参见样例1 ），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2 ）

输入描述：
共 2 行。
第 1 行为一个字符串，其中只含字母，表示给定单词；
第 2 行为一个字符串，其中只可能包含字母和空格，表示给定的文章
输出描述：
一行，如果在文章中找到给定单词则输出两个整数，两个整数之间用一个空格隔开，分别是单词在文章中出现的次数和第一次出现的位置（即在文章中第一次出现时，单词首字母在文章中的位置，位置从 0 开始）；如果单词在文章中没有出现，则直接输出一个整数 -1。

示例1：
输入：
To
to be or not to be is a question
输出：
2 0
说明：
输出结果表示给定的单词 To 在文章中出现两次，第一次出现的位置为0。

示例2：
输入：
to
Did the Ottoman Empire lose its power at that time
输出：
-1

三、回文数

来源：牛客网

若一个数（首位不为零）从左向右读与从右向左读都一样，我们就将其称之为回文数。
例如：给定一个10进制数56，将56加65（即把56从右向左读），得到121是一个回文数。
又如：对于10进制数87：
STEP1：87+78 = 165
STEP2：165+561 = 726
STEP3：726+627 = 1353
STEP4：1353+3531 = 4884
在这里的一步是指进行了一次N进制的加法，上例最少用了4步得到回文数4884。
写一个程序，给定一个N（2<=N<=10，N=16）进制数M，求最少经过几步可以得到回文数。如果在30步以内（包含30步）不可能得到回文数，则输出“Impossible！”

输入描述：
两行，分别为N,M
输出描述：
STEP=ans

示例1：
输入：
9
87
输出：
STEP=6

四、出现次数最多的数

http://118.190.20.162/view.page?gpid=T5
给定n个正整数，找出它们中出现次数最多的数。如果这样的数有多个，请输出其中最小的一个。

输入描述：
输入的第一行只有一个正整数n(1 ≤ n ≤ 1000)，表示数字的个数。
输入的第二行有n个整数s1, s2, …, sn (1 ≤ si ≤ 10000, 1 ≤ i ≤ n)。相邻的数用空格分隔。
输出描述：
输出这n个次数中出现次数最多的数。如果这样的数有多个，输出其中最小的一个。

示例1：
输入：
6
10 1 10 20 30 20
输出：
10

五、有趣的数

http://118.190.20.162/view.page?gpid=T2
我们把一个数称为有趣的，当且仅当：

1. 它的数字只包含0, 1, 2, 3，且这四个数字都出现过至少一次。
2. 所有的0都出现在所有的1之前，而所有的2都出现在所有的3之前。
3. 最高位数字不为0。
   因此，符合我们定义的最小的有趣的数是2013。除此以外，4位的有趣的数还有两个：2031和2301。
   请计算恰好有n位的有趣的数的个数。由于答案可能非常大，只需要输出答案除以1000000007的余数。

输入描述：
输入只有一行，包括恰好一个正整数n (4 ≤ n ≤ 1000)。
输出描述：
输出只有一行，包括恰好n 位的整数中有趣的数的个数除以1000000007的余数。

示例1：
输入：
4
输出：
3

六、质数因子

输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）

输入描述：
输入一个long型整数
输出描述：
按照从小到大的顺序输出它的所有质数的因子，以空格隔开。最后一个数后面也要有空格。

示例1：
输入：
180
输出：
2 2 3 3 5

七、递归实现组合型枚举

来源：牛客网

从 1~n 这 n 个整数中随机选出 m 个，输出所有可能的选择方案。

输入描述：
两个整数n，m。
输出描述：
按照从小到大的顺序输出所有方案，每行1个。
首先，同一行内的数升序排列，相邻两个数用一个空格隔开。其次，对于两个不同的行，对应下标的数一一比较，字典序较小的排在前面（例如1 3 9 12排在1 3 10 11前面）。

示例1：
输入：
5 3
输出：
1 2 3
1 2 4
1 2 5
1 3 4
1 3 5
1 4 5
2 3 4
2 3 5
2 4 5
3 4 5