一、简答题
1、1.最近的斐波那契数
斐波那契数列 Fn 的定义为：对 n ≥ 0 有 Fn+2 = Fn+1 + Fn，初始值为 F0 = 0 和 F1 = 1。所谓与给定的整数 N 最近的斐波那契数是指与 N 的差之绝对值最小的斐波那契数。
本题就请你为任意给定的整数 N 找出与之最近的斐波那契数。
时间限制：1000
内存限制：65536
输入
输入在一行中给出一个正整数 N（≤ 108）。
输出
在一行输出与 N 最近的斐波那契数。如果解不唯一，输出最小的那个数。
样例输入
305
样例输出
233
提示
样例解释 部分斐波那契数列为 { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, ... }。可见 233 和 377 到 305 的距离都是最小值 72，则应输出较小的那个解。
解析：
这个问题需要找到与给定整数N最近的斐波那契数。可以通过生成斐波那契数列并比较每个数与N的差的绝对值来解决这个问题。在生成斐波那契数列的过程中，需要记录最小的差值和对应的斐波那契数。如果存在多个斐波那契数与N的差的绝对值相同，选择较小的那个数作为答案。这种算法的时间复杂度是O(n)，其中n是斐波那契数列中需要计算的数的个数，因此可以在给定的时间限制内解决问题。
2、2.构造性证明
关于数学定理证明，也有高下之分。最暴力的证明方法是“构造性证明”，即当需要证明某种解存在时，直接把解构造出来，而不是仅通过推理证明解之存在。
下面有一个定理：
设 ai（i=1, … , 5）均为正实数。则一定存在 4 个互不相同的下标 i、j、k、l，使得 |ai / aj - ak / al| < 1/2。
作为程序员，就请你编写程序构造出正确的下标，验证这个结论。
时间限制：1000
内存限制：65536
输入
输入在一行中顺序给出 5 个正实数。为保证计算中不产生浮点溢出，我们令输入的数字在 [10-10, 1010] 区间内，且小数点后不超过 10 位小数。
输出
在一行中首先输出使得定理结论成立的下标有多少套，随后输出最小的一套下标。数字间以 1 个空格分隔，行首尾不得有多余空格。 注：所谓下标集 {i1, …, i4} 小于下标集 {j1, …, j4}，是指存在 1 ≤ k ≤ 4 使得 il=jl 对所有 l < k 成立，且 ik < jk。
样例输入
3.12 5.27 0.0007 9825.4413 10
样例输出
18 1 4 3 2
提示
样例解释： 易验证 |a1/a4-a3/a2|=|3.12/9825.4413 - 0.0007/5.27| < 1/2。满足条件的解有 18 个，例如 5、4、3、2 就是另一套解。
解析：
本题要求验证一个数学定理，并通过编程来构造出满足定理的下标。定理的内容是：设a1，a2，a3，a4，a5均为正实数，则一定存在4个互不相同的下标i、j、k、l，使得|ai/aj - ak/al| < 1/2。
为了解决这个问题，我们可以采用穷举法，遍历所有可能的下标组合，计算|ai/aj - ak/al|的值，当找到满足条件的下标组合时，就输出该组合。由于输入的数字在[10^-10, 10^10]区间内，且小数点后不超过10位小数，所以我们可以使用浮点数进行计算。
具体实现时，可以先将输入的5个正实数读入，然后利用嵌套循环遍历所有可能的下标组合。对于每一组下标，计算对应的|ai/aj - ak/al|的值，如果小于1/2，则输出该组下标。最后输出的结果包括使得定理结论成立的下标组合的数量，以及最小的一套下标组合。
需要注意的是，由于本题有内存限制，因此在实现时需要注意节约内存使用，避免使用过多的空间。此外，由于本题的时间限制为1000，因此需要在规定的时间内完成计算并输出结果。
3、3.12 5.27 0.0007 9825.4413 10
样例输出
18 1 4 3 2
提示
样例解释： 易验证 |a1/a4-a3/a2|=|3.12/9825.4413 - 0.0007/5.27| < 1/2。满足条件的解有 18 个，例如 5、4、3、2 就是另一套解。
解析：
{根据题目提示，需要验证的是表达式 |a1/a4 - a3/a2| 是否小于 1/2。其中 a1=3.12，a2=5.27，a3=0.0007，a4=9825.4413。通过计算可以得出验证结果，并据此找出满足条件的解。由于此题无法直接计算得出答案，需要通过编程或手工计算验证。}
4、4.子串和子列
子串是一个字符串中连续的一部分，而子列是字符串中保持字符顺序的一个子集，可以连续也可以不连续。例如给定字符串 atpaaabpabtt，pabt 是一个子串，而 pat 就是一个子列。
现给定一个字符串 S 和一个子列 P，本题就请你找到 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。
时间限制：1000
内存限制：65536
输入
输入在第一行中给出字符串 S，第二行给出 P。S 非空，由不超过 104 个小写英文字母组成；P 保证是 S 的一个非空子列。
输出
在一行中输出 S 中包含 P 的最短子串。若解不唯一，则输出起点最靠左边的解。
样例输入
atpaaabpabttpcat
pat
样例输出
pabt
解析：
本题要求找到字符串中包含特定子列的最短子串，且如果存在多个解，需要输出起点最靠左边的解。可以使用滑动窗口算法来解决这个问题。首先遍历字符串S，找到子列P在S中第一次出现的位置，然后以这个位置为中心，向两边扩展窗口，直到找到包含P的最短子串。在这个过程中，需要记录最小窗口的起始位置和结束位置。最后输出对应的最短子串即可。需要注意的是，如果存在多个解，需要继续向左移动窗口的起始位置，直到找到最靠左的解为止。
5、5.拼大数
如何随机生成一个有 n 位数的大数呢？一种方法是，找到 n 个小朋友，每人发一张卡片，卡片一面写着编号（这里假设小朋友们从 1 到 n 编号），另一面让他们随便写下一个 1 位数字。然后让小朋友们把自己的卡片在墙上钉成一排，要求一张挨着一张，按他们的编号升序排列，显示他们自己写的数字。
但是，让十万个孩子都按指令行动，可太难了。结果是卡片乱七八糟满墙都是，有些甚至显示的不是正确的面。例如第 23 号小朋友在卡片上写了 8，我们应该在墙上看到 8，但是却看到了 23…… 你的任务就是把这些卡片整理好，得到我们真想要拼成的大数。
时间限制：6000
内存限制：65536
输入
输入第一行给出一个正个整数 n (≤ 105)，随后 n 行，每行按 n1 n2的格式给出一张卡片两面的数字。
输出
在一行中输出我们真想要拼成的 n 位大数。 如果卡片两面都是 1 位数，那么就很难说哪个数字是编号，哪个数字是小朋友自己写的，所以解可能是不唯一的。这时候需要输出能得到的最小的数字。
样例输入
12
7 11
8 9
3 1
2 12
4 6
10 0
5 1
2 5
6 8
1 4
7 2
9 3
样例输出
359114268072
解析：
题目描述了一个场景，需要我们从混乱的卡片中整理出一个有序的n位大数。首先，我们需要理解题目的要求，即按照小朋友的编号顺序将卡片上的数字连接起来。在这个过程中，如果一张卡片两面都是一位数，我们需要选择较小的数字作为该位置的数字，以确保得到最小的数字。另外，如果某张卡片有一面是数字零，我们应该选择零作为该位置的数字。根据上述规则，我们可以编写程序来模拟这个过程，从而得到最终的结果。
喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！
