题目的主要信息： 查找两个字符串a,b中的最长公共子串。若有多个，输出在较短串中最先出现的那个。 方法一： 枚举法。用sub_str暂存最长公共子串，首先找到a、b中较长的那个子串，使得a总为较短的那个子串，枚举所有a中可能出现的子串，用find函数判断该子串是否在b中出现，如果在b中出现的话，比较该子串与已知的最长公共子串的长度，如果更长，则更新sub_str。枚举所有的子串用双重for循环，首先遍历一遍子串的起始位置，然后遍历一遍所有可能的长度。需要注意的是，当某个子串temp不在b中时，说明从这个位置开始，大于temp长度的子串都不可能在b中找到，因此可以结束当前循环，从下一个位置开始判...

题目的主要信息： MP3每页只能显示4首歌曲，光标初始的位置为第1首歌，通过上下键控制光标移动来浏览歌曲列表。有以下几种情况： 特殊翻页：屏幕显示的是第一页且光标在第一首歌曲上，用户按Up键后，屏幕要显示最后一页，同时光标放到最后一首歌上； 一般翻页：屏幕显示的不是第一页时，光标在当前屏幕显示的第一首歌曲时，用户按Up键后，屏幕从当前歌曲的上一首开始显示，光标也挪到上一首歌曲。光标当前屏幕的最后一首歌时的Down键处理也类似。 其他情况无需翻页，只需移动光标。 需要注意的是，当歌曲数小于等于4时，无需翻页。 方法一： 模拟整个过程处理。情况分为歌曲数小于等于4和大于4两种情况，每种情况都要...

题目的主要信息： 给定一个很长的 DNA 序列，以及限定的子串长度 N ，请帮助研究人员在给出的 DNA 序列中从左往右找出 GC-Ratio 最高且长度为 N 的第一个子串。 方法一： 暴力方法。遍历一遍str的所有长度为len的子串，用max保存其中最大的G、C个数，index用来索引G、C个数最多的子串。遍历每一个子串，统计其中的G、C的个数count，count和max比较，如果count>max，则更新max和index的值。 最后用substr函数、index输出对应的子串。 具体做法： #include<iostream> using namespace st...

题目的主要信息： 输入一个正整数，计算它在二进制下的1的个数。 方法一： 移位统计。每次判断n的二进制的最低位是否为1，更新统计变量count。然后将n向右移动一位，直至判断完所有位。 具体做法： #include<iostream> using namespace std; int main(){ int n; while(cin >> n){ int count = 0; while(n > 0){ if(n & 1){//看最低位是否为1 +...

题目的主要信息： 把m个同样的苹果放在n个同样的盘子里，允许有的盘子空着不放，问共有多少种不同的分法？ 方法一： 采用递归。用apples函数实现，放苹果分为两种情况： 有盘子为空：假设有一个盘子为空，则m个苹果放在n个盘子上的问题转化为将m个苹果放在n-1个盘子上。 每个盘子上都有苹果：假设所有盘子都装有苹果，则每个盘子上至少有一个苹果，即最多剩下m-n个苹果，问题转化为将m-n个苹果放到n个盘子上。 因此(m,n)=(m-n,n)+(m,n-1)。 当m<0时表示已经没有苹果了，不能再分了，结束递归。当m==1||m=0||n==1表示只有0个苹果或者1个苹果或者1个盘子，只有一...

题目的主要信息： 任意一个偶数（大于2）都可以由2个素数组成，组成偶数的2个素数有很多种情况，本题目要求输出组成指定偶数的两个素数差值最小的素数对。 方法一： 穷举。首先知道判断素数的方法，素数是指在大于1的自然数中，除了1和它自身外，不能被其他自然数整除的数。判断一个数是否为素数用试除法，用各个数从小到大依次去除a，如果到某一个数正好整除，这个a就可以断定不是质数。 从2开始遍历所有小于n的数字i，如果i和n-i均为素数，判断他们之间的差值是否比min小，如果比min小的话，min更新为i和n-i的差值，即为abs(n-i-i)，p更新为i；如果差值比min大，则不发生变化，继续往下遍历。当...

题目的主要信息： 此题要求将数字转换成英文，具体规则如下: 从最右边往左数，三位数字作为一个单位，例如12,345等。 每三位数后记得带上计数单位，分别是thousand, million, billion。 公式：百万以下千以上的数 X thousand X, 10亿以下百万以上的数：X million X thousand X, 10 亿以上的数：X billion X million X thousand X. 每个X分别代表三位数或两位数或一位数。 百位数和十位数之间要加and。 方法一： 采用递归。用itoe函数实现递归。ones中储存了个位数的英文，tens储存了10-19对应...

题目的主要信息： 输入一个迷宫，其中的1表示墙壁，0表示可以走的路。 迷宫中只能横着走或竖着走，不能斜着走。 要求从坐标[0,0]出发,找到一条到右下角的路径走出迷宫。 方法一： 采用递归。用ans保存最终路径，temp用于暂存递归中的路径，row和col为迷宫的行数和列数，flag用于递归结束判断。dfs函数用于递归，从坐标(0,0)出发，每经过一个坐标就把它存到temp中，并且将当前位置的值从0变为1，表示当前位置已经访问过，不可重复访问。接着尝试从上下左右四个方向走，如果flag为true说明已经找到了一条路径，结束递归。如果四个方向都走不通，那么将temp回溯，并且恢复当前位置状态...

题目的主要信息： 已知9X9盘面上的已知数字，推算出所有剩余空格的数字，并且满足每一行、每一列、每一个3X3粗线宫内的数字均含1-9，并且不重复。 方法一： 采用递归。九宫格里一共有81个数字，给这些数字编号为0、1、2……80，从第0个数开始递归，当最后一个数字递归完后结束递归。用dfs进行递归，check函数判断当前填充的值是否满足每行每列不重复、且九宫格内不重复的条件。 dfs进行递归时，首先判断当前的值是否为0，如果是0，则需要推算当前值是1-9中的哪一个，用枚举方法依次尝试往下递归，如果flag为true，结束整个递归，否则恢复当前值为0，需要回溯；如果当前值不是0，直接往下一个位置...

题目的主要信息： 字符串的“漂亮度”是其所有字母“漂亮度”的总和。 每个字母都有一个“漂亮度”，范围在1到26之间。没有任何两个不同字母拥有相同的“漂亮度”。字母忽略大小写。 给出多个名字，计算每个名字最大可能的“漂亮度”。 方法一： 首先统计字符串中，每个字符出现的次数，用num储存。要想最大化字符串的漂亮度，只需要让出现次数最多的字母的漂亮度最大即可，因此对num从大到小排序，然后计算字符串的漂亮度，出现次数最多的字符的漂亮度为26，然后递减为25、24……。最后得到的漂亮度即为最大的漂亮度。 具体做法： #include<iostream> #include<ve...

题目的主要信息： 现有一组砝码，重量互不相等，分别为 m1m_1m1​,m2m_2m2​,m3m_3m3​…mnm_nmn​； 每种砝码对应的数量为x1x_1x1​,x2x_2x2​,x3x_3x3​...xnx_nxn​ 。 求解这些砝码能组合出多少种不同的重量。需要注意的是，称重重量包括 0 。 方法一： 采用动态规划。用weights储存不同的砝码重量，nums储存不同重量砝码的数量。maxw表示所有砝码加起来的重量，dp为动态数组，dp[i]=1表示重量i可以用砝码组合出来，dp[i]=0表示重量i不能用砝码组合出来。 用三层for循环对dp数组进行更新，第一层对所有不同重量的砝码...

题目的主要信息： 输入一个字符串和一个整数 k ，截取字符串的前k个字符并输出。 方法一： 输入字符串str和整数k，利用函数substr输出前k个字符。 具体做法： #include <iostream> #include <string> using namespace std; int main() { string str; int k; while(cin>>str>>k){//输入字符串和k string sub_str = str.substr(0,k); cout&lt...

题目的主要信息： 计算一个浮点数的立方根，不使用库函数。 方法一： 牛顿迭代法。设f(x)=x3−yf(x)=x^3-yf(x)=x3−y, 求f(x)=0f(x)=0f(x)=0时的解x，即为y的立方根。根据牛顿迭代思想，xn+1=xn−f(xn)/f′(xn)x_{n+1}=x_n-f(x_n)/f'(x_n)xn+1​=xn​−f(xn​)/f′(xn​)即x=x−(x3−y)/(3∗x2)x=x-(x^3-y)/(3*x^2)x=x−(x3−y)/(3∗x2)。不断更新x的值，直到误差小于0.000001。 具体做法： #include<iostream> #include...

题目的主要信息： 正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小公倍数。 方法一： 从第一个数字开始，逐渐递增，直到找到一个能同时整除a和b的数字，即为a和b的最小公倍数。 具体做法： #include<iostream> using namespace std; int main(){ int a, b; while(cin >> a >> b){ int res = a; while((res%a)||(res%b)){//能同时整除a和b时就找到了...