欢迎来到Marginalin的博客
X星球日报和我们地球的城市早报是一样的，都是一些单独的纸张叠在一起而已。每张纸印有4版。
比如，某张报纸包含的4页是：5,6,11,12，可以确定它应该是最上边的第2张报纸。
我们在太空中捡到了一张X星球的报纸，4个页码分别是：1125,1126,1727,1728
请你计算这份报纸一共多少页（也就是最大页码,并不是用了几张纸哦）？
请填写表示总页数的数字。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：首先要知道报纸的页码是怎么编号的。如下图。
方案一：已知最小页码的5减去1是4，而最大页码16减去已知最大页面12也是4，这就很巧妙了，设最大页码是x，则有：x-已知最大页码==已知最小页码-1。
方案二：可以发现每一张的每一面的两个数字相加都是一样的，如下图：16+1 == 15+2 == 14+3 == ... == 9+8，且都比最大页码大1，设最大页码为x，则有：x+1 == 已知最大+已知最小 == 已知较大+已知较小。
答案：2852
有一堆煤球，堆成三角棱锥形。具体：第一层放1个，第二层3个（排列成三角形），第三层6个（排列成三角形），第四层10个（排列成三角形），....如果一共有100层，共有多少个煤球？
请填表示煤球总数目的数字。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：枚举
答案：171700
如果把一个正整数的每一位都平方后再求和，得到一个新的正整数。对新产生的正整数再做同样的处理。
如此一来，你会发现，不管开始取的是什么数字，最终如果不是落入1，就是落入同一个循环圈。
请写出这个循环圈中最大的那个数字。
请填写该最大数字。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：枚举若干个数字，然后按照要求做个几十遍，期间把最大值保存，然后输出。这若干个数一比对就出来了。
答案：145
小明想在控制台上输出 m x n 个方格。比如 10x4的，输出的样子是：+---+---+---+---+---+---+---+---+---+---+| | | | | | | | | | |+---+---+---+---+---+---+---+---+---+---+| | | | | | | | | | |+---+---+---+---+---+---+---+---+---+---+| | | | | | | | | | |+---+---+---+---+---+---+---+---+---+---+| | | | | | | | | | |+---+---+---+---+---+---+---+---+---+---+
以下是小明写的程序，请你分析其流程，填写划线部分缺少的代码。
注意：仅仅填写划线部分缺少的内容，不要添加任何已有内容或说明性文字。
思路：填空的地方注释掉输出一看就知道填写啥了。
答案：
排序在各种场合经常被用到。快速排序是十分常用的高效率的算法。
其思想是：先选一个“标尺”，用它把整个队列过一遍筛子，以保证：其左边的元素都不大于它，其右边的元素都不小于它。
这样，排序问题就被分割为两个子区间。再分别对子区间排序就可以了。
下面的代码是一种实现，请分析并填写划线部分缺少的代码。
注意：只填写缺少的内容，不要书写任何题面已有代码或说明性文字。
思路：我们发现在partition函数中，是以a[p]为标尺，在[p, r]中比a[p]大的和比a[p]小的做交换，那么完成之后就是：a[p]，小，小，大，大，大。a[p]显然是要与一个数交换的，那么是i，还是j呢(可以输入i，j输出看一下)。因为我们这个partition函数是要求吧所有小于a[p]的数字放到左边，大于的放到右边，而下标i所指的数是大于a[p]的，与其交换就无法满足要求，所以是与j交换。
答案：
这个算式中A~I代表1~9的数字，不同的字母代表不同的数字。
比如：6+8/3+952/714 就是一种解法，5+3/1+972/486 是另一种解法。
这个算式一共有多少种解法？
注意：你提交应该是个整数，不要填写任何多余的内容或说明性文字。
思路：拉成一维数组全排练+判断，值得注意的是B/C和DEF/GHI都是整除。
答案：29
现在小学的数学题目也不是那么好玩的。看看这个寒假作业：
每个方块代表1~13中的某一个数字，但不能重复。比如：6 + 7 = 139 - 8 = 13 * 4 = 1210 / 2 = 5
以及： 7 + 6 = 139 - 8 = 13 * 4 = 1210 / 2 = 5
就算两种解法。（加法，乘法交换律后算不同的方案）你一共找到了多少种方案？
请填写表示方案数目的整数。注意：你提交的应该是一个整数，不要填写任何多余的内容或说明性文字。
思路：其实也是全排列问题，把12个格子看成一维数组，然后填充，最后判断。值得注意的是13!很大，直接跑大约需要一分钟左右，这是填空题所以没什么事。但是我们可以添加几个优化。第22行加的语言可以排除很多无用的排列，大大的提高了效率。
答案：64
任意给定一个正整数N，如果是偶数，执行： N / 2如果是奇数，执行： N * 3 + 1
生成的新的数字再执行同样的动作，循环往复。
通过观察发现，这个数字会一会儿上升到很高，一会儿又降落下来。就这样起起落落的，但最终必会落到“1”这有点像小冰雹粒子在冰雹云中翻滚增长的样子。
比如N=99,28,14,7,22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1可以看到，N=9的时候，这个“小冰雹”最高冲到了52这个高度。
输入格式：一个正整数N（N<1000000）输出格式：一个正整数，表示不大于N的数字，经过冰雹数变换过程中，最高冲到了多少。
例如，输入：10程序应该输出：52
再例如，输入：100程序应该输出：9232
资源约定：峰值内存消耗 < 256MCPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
思路：这题很坑，这个N和上面的N不一样，答案是要求1-N这N个数在执行过程中的最大数，不单单只是一个N。记得开long long，不然会溢出。
你玩过华容道的游戏吗？这是个类似的，但更简单的游戏。看下面 3 x 2 的格子
+---+---+---+| A | * | * |+---+---+---+| B | | * |+---+---+---+
在其中放5张牌，其中A代表关羽，B代表张飞，* 代表士兵。还有一个格子是空着的。
你可以把一张牌移动到相邻的空格中去(对角不算相邻)。游戏的目标是：关羽和张飞交换位置，其它的牌随便在哪里都可以。
输入格式：输入两行6个字符表示当前的局面
输出格式：一个整数，表示最少多少步，才能把AB换位（其它牌位置随意）
例如，输入：* A**B
程序应该输出：17
再例如，输入：A B***
程序应该输出：12
资源约定：峰值内存消耗 < 256MCPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
思路：宽搜题，注释写的很详细。
X星球的考古学家发现了一批古代留下来的密码。这些密码是由A、B、C、D 四种植物的种子串成的序列。仔细分析发现，这些密码串当初应该是前后对称的（也就是我们说的镜像串）。由于年代久远，其中许多种子脱落了，因而可能会失去镜像的特征。
你的任务是：给定一个现在看到的密码串，计算一下从当初的状态，它要至少脱落多少个种子，才可能会变成现在的样子。
输入一行，表示现在看到的密码串（长度不大于1000）要求输出一个正整数，表示至少脱落了多少个种子。
例如，输入：ABCBA则程序应该输出：0
再例如，输入：ABDCDCBABC则程序应该输出：3
资源约定：峰值内存消耗 < 256MCPU消耗 < 1000ms
请严格按要求输出，不要画蛇添足地打印类似：“请您输入...” 的多余内容。
所有代码放在同一个源文件中，调试通过后，拷贝提交该源码。
注意: main函数需要返回0注意: 只使用ANSI C/ANSI C++ 标准，不要调用依赖于编译环境或操作系统的特殊函数。注意: 所有依赖的函数必须明确地在源文件中 #include <xxx>， 不能通过工程设置而省略常用头文件。
提交时，注意选择所期望的编译器类型。
方法二：要求是对称，那我我们把原串翻转一下，在进行对比可以发现两串有3个不同的字母，那么我们添加这三个字母不就好了。所以答案就是长度-LCS(最长公共子序列)。