SOJ题目报告(100多题,请搜索)

SOJ题目报告

四川大学ACM集训队 姜边

Every problem has simple, fast and wrong solution.

-- http://acm.timus.ru

没加★的表示只有一两句话

加一个★的表示有一小段

加两个★的表示有详细的叙述 SOJ1001 A + B Problem

几乎每个Online Judge的第一道题目都是这个（好像UVA除外^_^）。用于试验服务端环境的题目，主要考查scanf的用法。

　　主要考查高精度运算的知识，并没有太多的技术含量。

首先要判断点数总和能否被堆数整除，如果不能，就没有必要进行下面的操作了。

由于队列两端的卡片只能移到相邻的一个方向，这样我们在进行卡片移动操作的时候不得不考虑端点的情况，于是，程序变得不够统一，不统一的程序往往是没有通用性和不稳定的。

为了构造统一的程序，我只考虑每个卡片堆右边的情况。

基于以上考虑，我将队列分为两个部分：一堆卡片与这堆卡片右边的部分。显然，这里的“一堆卡片”不包括最右边的那堆。表示如下

P R

分别表示Pile Right

我定义Average为达到平衡的时候每堆卡片的张数，于是出现三种情况：

一、Pile = Average，此时不需要动这堆卡片。

二、Pile > Average，此时需要将这堆卡片中比Average多的部分移走，由于我只考虑向右的情况，所以Pile将(Pile – Average)张卡片移给Right（只能移给Right而不是Right + 1或是其他是由规则决定的）。

三、Pile < Average, 此时需要从别的卡片中移一些卡片给Pile，让Pile = Average，显示，需要(Average – Pile)张卡片。这种情况与[情况二]不一样，情况二只是把Pile多余的卡片分给右边，但[情况三]也许需要将多堆卡片中多余的部分一起分为Pile。
于是，当出现这种情况时，需要从Pile的右边开始搜索。显然，对于张数小于或等于Average的堆是不能够分卡片给Pile的，所以，需要从所有张数大于Average的堆中分卡片给Pile，直到Pile张数等于Average，也就是说，搜索的最后一堆也许不会将所有的多余卡片分给Pile。
由于我的操作是从左至右进行的，所以，当出现这种情况的时候，一定可以从Pile的右边找到多余的卡片，使Pile = Average。

重复考虑这三种情况，直到达到平衡为止。

很简单的一道题，原理就是查密码表。

注意读入的时候不要用scanf(“%s”, …)读入，用gets。

另外就是注意输入数据的格式。

题目很简单，但程序很麻烦，主要操作在于写出魔方在各种操作下的变换，没有什么算法。

给定一颗树，然后再给出两个结点，要求得到这两个结点的关系。这个问题主要是基于树结构的操作，基本操作是先找出两个结点的最近的公共祖先，再根据两个结点与它们的公共祖先的关系来判断两个结点的关系。

这道题的关键在于找出两个结点的公共祖先，我用的方法是：

假设两个结点是A和B，先找出从根到A的路径，再找到从根到B的路径，再找到两条路径中离根最远的公共点即可。两个结点一定会有公共祖先（至少是根）。

“生成类”动态规划的题目。从0元开始，不断地生成，直到生成到5.00元。在实际操作的时候，先将浮点数乘以100，转换为整数，这样再进行后面的运算便不会出现精度问题。

这道题在刚开始的时候会遇到精度问题，即在将读入的钱数乘以100得到整数的时候会出现得到的结果N % 5 = 1或N % 5 = 4的问题。在这道题里，我通过以下的方法避免此问题：判断N是否能被5整除，如果不能，则考虑N + 1和N – 1哪个能被5整除，则取哪个（N + 1和N – 1中只可能有一个被5整除）。

模拟题。关键在于理解题意：机器人在一个位置fall off之前，会在该位置留下标记，后面的机器人在走到该位置，如果下一条指令会导致它fall off，它会忽略掉该指令。注意，这里的fall off并不包含对方向的限制，也就是说，机器人留下的标记只是说明该位置有机器人fall off过，并没有记录是在哪个方向fall off的。 SOJ1011 The Skyline Problem

又是一道模拟题。先按矩形的左坐标排序会简化程序的操作。排序后，从最小的坐标开始扫描，发现高度变化，就记录下来，最后将这些“变化点”打印出来就行了。 SOJ1013 The Cat in the Hat★

数学题。为了叙述方面，我定义Cat帽子里的Cat为ChildCat。

根据题意，每只Cat有N只ChildCat，ChildCat的高度为Cat的1/(N+1)。

题目的输入告诉了initial Cat的高度和worker cat的数目，也就是说，告诉了最大的那只猫的高度和最小的猫的数目。基于Cat和ChildCat的高度、数量关系，假设所有的猫堆起来有n层，则有：

(N + 1) ^ n = initial Cat的高度

N ^ n = worker cat的数目

搜索到第一个满足条件的n后，再进行以后的计算。

题目要求得出non-worker cat的数目和猫叠起来的高度。得到n值以后，这两个值就很容易算了。

Non-worker cat的数目就是cat的总数目 – worker cat的数目（已经在输入中告诉了）

算猫叠起来的高度利用等比数列的求和公式就行了。 SOJ1014 Maximum Sum

最大子矩阵和的问题，动态规划的的经典题目。 SOJ1015 History Grading★

模拟＋最长公共子序列。关键还是在于理解题意，也就是得分的两种情况：一种是数字相同，位置也相同；另一种是学生给出的答案序列与标准答案序列的最长公共子序列的长度，注意，这个长度的最小值为1，也就是说，对于每个答案，最低得分都有1分。 SOJ1016 Tree Summing★★

题目的意思是给定一棵树，求是否存在一条路径，其上的结点的权值和为指定值。解决这个很简单。

这道题的难点在于输入中的树型结构的表示部分。

这道题用了数据结构中的“二叉树的括号表示法”，定义是这样的：

empty tree = ()

tree = empty tree | (integer tree tree)

于是一棵非空的二叉树可表示为

(根结点的权值左子树右子树)

而“左子树”和“右子树”又可用上面的形式来表示，所以，这种表示法是递归的。而递归的终点，就是空树。所以，

叶结点的表示就是：

(叶结点的权值 () ())

无左子树的结点的表示就是：

(结点的权值 () 右子树)

无右子树的结点的表示就是：

(结点的权值左子树 ())

在读入的时候，遇到“（”，就寻找与其相对应的“）”，它们之间的部分就是一棵完整的树（子树），一直这样解析下去，直到解析到空树为止。

寻找与“（”相对应的“）”的方法是：

定义一个变量iCC，赋初值1

从“（”开始扫描字符串，遇到“（”时iCC++；遇到“）”时，iCC--后判断iCC是否为0，如果为0则表示当前的“）”就是要找的“）”。 SOJ1017 Power of Cryptography

直接用pow函数，用double读入就行了。 SOJ1018 Simulation Wizardry★★

模拟题，主要是理解题意。

首先看看题目中的几个元素：

surface 一个m×n的棋盘，坐标原点在左下角

wall 墙壁，墙壁的定义是棋盘的边界，正确理解wall的定义是很重要的

bumper 缓冲器，小球撞到缓冲器会得到一定分数，不过不是只要撞到缓冲器就能得到分，规则在后面会说明

lifetime 生存期，相当于小球的生命，lifetime <= 0将导致小球消失（disappear）

cost 消耗，小球撞到墙壁或bumper时lifetime的减少值

*小球的方向，有上、下、左、右四种选择

然后是题目的规则：

小球撞到墙壁或bumper时，前进方向会向右旋转90度，但是，小球所处位置不改变。

小球撞到墙壁或bumper时，lifetime将减小cost点（墙壁和bumper的cost在题目中会分别告诉）。

小球撞到bumper时，得分的条件是：当时小球的lifetime为正。

小球每走一步，lifetime减1。

这些规则是此题的关键。 SOJ1019 Unidirectional TSP★★

动规的题，注意在行走的时候是可以上下“wrap around”的，也就是说，0行的上面是n - 1行，n - 1行的下面是0行。正是由于这种特征，在找到多条长度相同的路径时输出标号最小的路径（题目要求）的时候就要多一层考虑。

一般来说，我们在扩展[i][j]的时候，总是从[i - 1][j + 1]开始尝试，然后是[i][j + 1]，最后是[i + 1][j + 1]，所以，我们找到的第一条最短路径，一定就是标号最小的那条。但是，由于允许“wrap around”，情况变得有所不同，因为逻辑上的[i + 1]并不一定大于[i - 1]和[i]。

看看以下的情况

如果红、蓝两色的路径的长度是一样的，显然应该输出红色路径。但是在扩展[2][3]时，我们的顺序是[2 - 1][3 + 1]、[2][3 + 1]、[2 + 1][3 + 1]，而[2 + 1][3 + 1]实际上是[0][3 + 1]，所以出现了逻辑上的[i + 1]小于[i - 1]和[i]的情况。

由于这种情况的出现，我们找到的第一条最短路径并不一定是标号最小的路径。

克服这种问题的方法有两种：

一是将找到的所有路径存起来，再排序，得到标题最小的路径，当然，这是不推荐使用的。

第二种方法只需要找一次就行了，其实就一句话：从右往左找，将找到的第一条最短路径反着输出就行了^_^ SOJ1022 Uniform Generator

题目很玄，不过，实际上就是：如果两数互质，就是“Good choice”否则就是“Bad choice”，另外注意输出格式就行了。 SOJ1023 Prime Cuts

很简单的题目，很生成指定的素数序列，再在这个序列中按要求取出素数输出就行了。 SOJ1024 Word Index

我用的是土方法，先把83681个word序列生成出来，再查找就行了。

大数运算的题目。 SOJ1026 Eeny Meeny Moo

“丢手绢”的题目。 SOJ1027 Lotto

基本的回溯题目，按从小到大的顺序输出C(N, 6)的所有情况。 SOJ1028 Matrix Chain Multiplication

表达式解析的题目，注意矩阵乘法的规则。 SOJ1029 Humble Numbers★

由于我们无法保证后生成的数一定大于先生成的，所以，我先生成6000个数，再按升序排序即可。

这道题还有一个要注意的地方，那就是序数词的英语表达法。 SOJ1030 Sum It Up

又是基本的回溯题目。

“生成类”的动规题目。 SOJ1034 Ananagrams★

模拟题。题意是在一组单词中，找到这样的单词：任意交换单词的字母，得到的单词都不在这组单词中。

我判断两个单词是否能通过交换各自的字母互换转换的方法是：先将单词都转成小写形式，再统计各字母出现的次数。如果两个单词的统计结果是完全相同的，则这两个单词可以通过交换各自的字母互换转换。 SOJ1035 Power Crisis

又是“丢手绢”的题目。 SOJ1036 The Dole Queue

升级版“丢手绢”的题目，这次是两个人一起丢^_^ SOJ1037 ``Accordian'' Patience

模拟题。注意游戏规则，在移动一次以后，要再从头开始判断是否还可以移动。 SOJ1038 Trees on the level★

给出树的所有路径，判断这棵树是否完整。

我方法是先将所有路径按升序排序，然后对非空的路径进行判断，对每个非空的路径，判断它的前缀（即除最后一个字符的字符串）是否存在，如果不存在，则树不完整。

实际操作的时候，注意256个结点的树完全有可能是一条线。

很简单的模拟题。 SOJ1040 Maya Calendar

模拟题，按题目要求计算就行了。注意不要把月份的单词打错了。 SOJ1043 Joseph

还是“丢手绢”的题目。为了不超时，可以先把所有的结果算出来（只有14个），然后再查表即可。 SOJ1044 Cipher★

直接模拟也可以，但是很慢。最好先求出每个数的偏移量的最小公倍数，这就是整个单词变换的周期，再计算需要变换的周期中除整周期以外的部分就行了。

另外，输入的时候注意单词里的空格也要读入，输出的时候行末该有的空格不能去掉。 SOJ1046 Tin Cutter★★

这个题目很讲究技巧，看起来好像是一道几何题，其实不是。实际上，用几何的方法也可以解决此题，但十分复杂。这道题用模拟的思想更容易解决一些。

考虑下面的图：

如果按左图切割后，留下的阴影应该如右图所示，这使我们联想到floodfill的方法。所谓“floodfill”，就是在一个区域里倒足够的水，由于液体的流动性，水将向所有可能的地方流去，直到水不能再流动为止。Floodfill的结果将是一个“人工湖”（就像上图中右图的情况）。

于是，解决这道题的方法就是：将所有没有画线的地方进行floodfill，最后得到的“人工湖”的个数就是答案。

不过，即使采用这种方法，还是会遇到两个问题：

一、              题目中线的端点的坐标范围是很宽的，这就导致floodfill所用地图很大，在进行floodfill时，速度会很慢。

二、              对于上图中第一排左图，如果采用标准的floodfill，将产生3个“人工湖”，而显然答案应该是1。

现在我们来解决这两个问题：

对于第一个问题：分析题目我们可以知道，在这道题中，答案只与线的结构的关，而与线形成的矩形面积无关。于是，我们可以考虑“压缩”这些线。

以下图为例子：

左图经过压缩，就变成了右图，地图的大小减小了很多，这样floodfill的速度就大大提高了。

压缩的方法很像数字通信中讲的“量化”法。具体地说，就是这样：

对横纵坐标分别处理，比如对于横坐标，先将题目中所有点的横坐标排序，再按顺序给这些点设置新的横坐标。设置的方法是：

对于排序位置为i（以0开始）的点，横坐标为(i * 2)，要乘以2的原因是要在点与点之间留出一个空格以进行floodfill。

对纵坐标的处理方法也是一样的。

然后是第二个问题，考虑下图：

最左边是第一次floodfill后的图，第一次floodfill将地图的空白部分填充，这是一次标准的floodfill。由于地图已经被压缩过，所以floodfill是很快的。

左边第二个图是第二次floodfill的第一步。这一次floodfill就要考虑一些特殊情况了，注意红色的部分。在填到边界的时候，要考虑此边界是否可以“越过”。图中红色的那段边界就是可以越过的。对于可以越过的边界，在floodfill的时候要当作空白来处理，也就是说，要继续填充。

考虑边界是否可以被越过，实际上就是考虑边界上的点是否可以被越过。一个点可以被越过的条件就是与该点上、下、左、右四个方向相邻的四个点中，至少有一个点是空白点。

解决了上述两个问题，得到答案就很简单了。 SOJ1049 Packets

用贪心算法来解决。步骤就是先尽量放6×6，再尽量放5×5，然后是3×3、2×2，最后是1×1，直到将所有的方块放完，这时用去的盒子数目就是答案。 SOJ1050 Crosswords (II)

模拟题，没有什么算法，主要考验编程的基本功。

理解题意是关键，特别是写数字的条件和规则。

另外，去除多余的black square可以用floodfill的方法。 SOJ1051 palindromes

还是模拟题，理解题意就很简单了。 SOJ1052 MASH

继续“丢手绢”…… SOJ1053 Postscript

模拟题，考察基本功和身体素质，没有什么特别的地方。 SOJ1054 Radar Scopes

还是模拟题，关键是理解题目中“百分之几”的含义，是谁比谁多或少百分之几。

还有就是注意输出格式。 SOJ1055 Message Routing

又是模拟题，关键还是理解题意。

其实模拟题的关键都是理解题意，没有什么特别的算法^_^ SOJ1057 Excuses, Excuses!

模拟题……

我是用STL中的map来实现对key word的查找的。 SOJ1058 Centipede Collisions★

好多好多模拟题呀……

这道题要注意的地方是：

一、蜈蚣是按ID顺序轮流前进的

二、蜈蚣在相遇后，会在相遇的地方形成“相遇点”。蜈蚣走到“相遇点”时会掉到相遇点中。

三、如果一只蜈蚣被其他的蜈蚣“拦腰截断”，沿被截断的蜈蚣的前进方向考虑，在相遇点之前的那段蜈蚣将继续前进，在相遇点之后的那段蜈蚣将一步一步掉进相遇点中。 SOJ1059 Pi

一道模拟题，按题目要求算就行了。 SOJ1060 Up and Down Sequences

已经没有写的必要了，同上…… SOJ1061 Machined Surfaces

同上…… SOJ1062 LED Test

还是模拟题。

要注意地方是，已经假设灭的管以后再也不允许亮，已经假设亮的管以后可亮可灭。 SOJ1063 Molecules

模拟＋搜索，只有四层搜索，没有分支，用任何方法都可以做。 SOJ1067 Word-Search Wonder

同上…… SOJ1068 MPI Maelstrom

求图的最短路径，就这么简单。 SOJ1070 Arbitrage (II)

同上…… SOJ1071 The Tower of Babylon★

这是一道“生成类”的动规题，先按石头的底面生成所有的石头，理论上说，一块石头将生成另外两块石头。再将所有的石头按底面面积从大到小排序，然后就按“导弹防御”来做啦^_^ SOJ1072 The Circumference of the Circle

读过高中的人就会做^_^ SOJ1073 Knight Moves

“生成类”的动规题，先将地图上的点的权值全部赋为最大值，点M[i][j]的权值就是：

M[i][j] = min {与M相邻的点的权值 + 1} SOJ1074 Blue Eyes and Apples (I)

大数运算 SOJ1075 Blue Eyes and Apples (II)

模拟题。

同上……

同上……

“生成类”的动规题，很像“Dollars”

模拟题，注意在一关里只有消灭了所有的敌人才能拿到东西。

还是模拟题，关键在于处理“无限网络”。我用的是“wrap around”的方法。

搜索题目，八皇后问题的翻版。

把每个单词看作一个结点，单词与单词的关系看作边，于是可以构成一个图，求图中给定点对的最短路径就行了。

类似于Knight Move的问题。

计算几何的题目。注意，不能被检测到的情况除了“在那个平面上”之外，还有就是如果老鼠根本不在那两个球之内（或之上），也不能被猫检测到。

用贪心算法来解决。

从树的叶子结点开始扫描，如果一个结点还没有放士兵，则将它的父结点放上士兵，直到扫描到根结点为止。

模拟题。

有一个小技巧，求得2^E以后，取前N位判断的方法是：

设number为2^E

char strNum[100];

sprintf(strNum, “%d”, number);

strNum[N] = ‘\0’;

sscanf(strNum, “%d”, &testNumber);

再用testNumber和题目中给出的数比较就行了。

三重循环。

搜索题，提高速度的技巧在于判重，我用的是memcmp函数，比直接比较要快一些。

多层回溯。

生成类的动规题，不过有点不同的是在扩展的时候要保持波的“起伏”，也就是说，波峰后面应该接波谷，反之亦然。

求图的最短路径，注意精度问题。

很像“Dollars”，但要注意一下，在生成一定面额的时候，可以先加得超出去，再减回来。

模拟题。

关键在于精确地实现操作过程。

考虑下图：

左边是原图，在扫描的时候，在每处矩形相接的地方尝试水平或竖直地“切一刀”，如果这一刀没有切到其他的矩形，则将切出的两个矩形分别再切，直到不能再切为止。

动规题。

由于买N个指定类型的珍珠要另外付出与10个这种珍珠等价的购买费，所以把几种要买的珍珠合并到一起买，会节约一些费用。

考虑以下的情况：

要买两种珍珠，第一种单价为50元，要买100个，第二种单价为51元，要买80个。如果分别购买，则费用为 (100 + 10) * 50 + (80 + 10) * 51 = 10090(元)，但如果合到一起买，则费用为 (180 + 10) * 51 = 9690(元)。于是我们可以通过合并某些类型的珍珠来节约费用。题目要求只能将低价的珍珠合并到高价珍珠中而不允许相反的操作。可以证明，一种珍珠如果要与其他珍珠合并，和价格与它相邻的高价珍珠合并可以得到最小的费用。

由以上的分析可以得出，最后的最优解应该是下图中所示的形状：

如图所示，珍珠被分段合并了，当然，也可能有些珍珠并不参与合并。

这种形状很容易让人联想到“矩阵连乘”的问题。我正是用这种方法来解决这个问题的。

我定义了一个数组a[ ][ ]，a[ i ][ j ]表示从第i个珍珠买到第j个珍珠所需要的最小花费。显然，答案就是a[ 0 ][ N - 1 ]。珍珠是先按价格进行了升序排序的。

a[ i ][ j ]的初值是sum{ (n[k] + 10) * p[k] } ( i <= k <= j )，n[k]是第k种珍珠的需要量，p[k]是第k种珍珠的单价。

然后是a[ i ][ j ]的最优值：

a[ i ][ j ] = min {a[ i ][ k] + a[ k + 1 ][ j ]} ( i <= k < j )。

模拟题。

判断NONCOVERING的小技巧是在排队了NONDISJOINT和NONCONTAINED之后，判断所有矩形的面积之和是否等于floor的面积就行了。

我出的题。用任何方法都可以做出来。不过用sscanf最简单。

先把数读进来再进行大数运算是不现实的，因为测试数据有4M多（我写的^_^）。

这道题的关键在于理解加法的性质。

两个数相加，在个位对齐后，如果我们从最高位开始计算（如果从最低位开始计算，就是标准的大数运算，但题目中先读入的是高位），会遇到的问题就是，我们无法判断低位有无进位，因为低位的加法还未计算。不过，由于加法的性质，我们可以用另一种方法解决这个问题。

看看下面的例子：

987654321

009876543

876543210 (位号)

我们从第8位开始计算，9 + 0 = 9，不产生进位，但是，我们并不知道第7位是否会向第8位进位，所以，第8位的结果9并不能立即输出，要先保存下来。接着是第7位，8 + 0 = 8，也不产生进位，这时，我们就可以将第8位的9输出了，对于第7位的结果8，也不能马上输出，要先保存。

然后是第6位，7 + 9 = 16，产生了进位，这时，应该将第7位的结果8加1输出，输出为9，再把第6位结果16的个位6保存下来，再考虑第5位……这样一直进行下去，直到计算到第0位为止。

不过，下面还有一种特殊情况：

099999

000001

543210 (位号)

第4位的9在第三位计算出9以后，并不能马上输出，因为在加法里，9的进位是可以传递的。具体地说，当第0位计算出10后，将导致第1位产生进位，第1位的进位又导致第2位产生进位……一直影响到第4位。所以，在第i位的计算结果为9，而它的下一位第i - 1位的计算结果也为9时，第i位的9并不能马上输出，而是要得到第i - 2位的结果后才能输出，如果第i - 2位的计算结果也是9，则还要继续进行下去，直到计算到结果不是9的位为止。于是产生下面几种情况：

一、              第0位的计算结果还是9，这时先输出前面计算结果中最后的非9位，再输出前面计算得到的9，最后输出第0位的9就行了。

二、              计算到某位，结果小于9，这时先输出前面计算结果中最后的非9位，再输出前面计算得到的9，最后将这一位的计算结果保存，待后面位计算后再决定如何输出此位。

三、              计算到某位，结果大于9，产生了进位，这时先将前面计算结果中最后的非9位加1输出，再按前面计算得到的9个数输出0，最后将这一位的计算结果的个位保存，待后面位计算后再决定如何输出此位。

所以，在计算中遇到9时，并不需要保存此位，只需要保存积累到的9的个数就行了。

下面给一个综合的例子吧：

SOJ12345678

07658513

76543210 (位号)

计算过程：

可以说是模拟题。提高速度主要在于判断重复的分数。

首先我建立了一个二维数组a，a[ i ][ j ]表示的就是i / j，a[ i ][ j ]为1表示i / j可用，为0表示i / j不可用。显然，a[][0]都为0，因为分母不能为0。

然后我就按题目中的要求模拟行走路线行走，当找到一个可用的a[ i ][ j ]时，我就在二维数组中以(i, j)为直线的一点，以j / i为斜率画一条直线，直线经过的点就是与i / j的值相同的分数所在的点。将直线经过的点设为不可用，以后走到那些点的时候跳过就行了。 SOJ1106 DWeep

我是用类似“Knight Move”的方法解决这个问题的。不过，激光要特殊处理。

从激光经过的格子只能走到空白的格子，而且经过的激光数目要加1。

这道题的关键在于判重。题目中蛇的长度限定在8以内并不是没有道理的。

由于在运动过程中只有蛇在动，棋盘的状态并不会变化，所以，我们判断某种状态是否被搜索过，只需要判断当前蛇的状态是否已经存在就行了。

考虑蛇及棋盘的性质：蛇在运动的过程中实际上只是蛇头在动，而蛇的其他部分只是被蛇头牵引而运动，所以，蛇的位置可以用蛇头的位置来表示。棋盘的大小是20×20，所以蛇头的坐标范围也是在0到19之间。

现在的问题是蛇身如何表示。

前面已经说到，蛇的运动实际上是蛇头的运动，蛇身只是被牵引而运动，这样说来，我们只需要保存蛇身的每一段与前一段的相对位置就行了。

而蛇的每一段之间的相对位置只有四种：上、下、左、右，用2位二进制就可以表示。由于蛇的长度最长为8，除去蛇头为7，这样，蛇身最多只需要用2 * 7 = 14位二进制就可以表示。

于是，表示整条蛇所需要的二进制位数就是：5 + 5 + 14 = 24位，两个5位表示蛇头的横纵坐标，14位表示蛇身。实际操作的时候，这样建立数组：

aMap[20][20][1024 * 16]，1024 * 16就是2^14。aMap[ i ][ j ][ k ]表示蛇头在(i, j)，且表示蛇身的数为k这种状态是否已经存在。

另外，用二进制来表示蛇身还有一个好处，那就是在蛇运动的时候只需要将蛇身右移2位就行了。

带点数学味道的模拟题。

将序列分段可得：

SOJ1　12　123　1234　12345　123456　1234567　12345678　123456789　12345678910　1234567891011　12345678910

我们要知道第i位(i是从1开始的)的数字，首先要知道第i位是在哪一段，然后再得到第i位在此段的序号就行了。

要知道第i位在哪一段，首先要知道每段的长度。

前九段的长度就是段号i（i是从一开始的）。

对于第10段，由于比第9增加了一个两位数10，所以长度为第9段的长度加2。

第11段比第9段增加了两个两位数，所以长度为第9段的长度加2 * 2。

与第10段和第11段性质相同的段是

SOJ12345678910 ~ 123456789101112……99

它们的长度是第9段的长度加 (段号 - 9) * 2，其中(段号 - 9)为这些段相对于第9段的偏移量，乘以2是因为这些段增加的全是两位数。

同理，1123456789101112……99100 ~ 1123456789101112……99100……999的长度是

第99段的长度加 (段号 - 99) * 3

后面的段以此类推。

我们定义一个段的位数为这段中位数最长的数的位数。

比如：

SOJ123的位数为1

SOJ12345678910的位数为2，因为有10的存在

SOJ1123456789101112……99100为3，因为有100的存在

于是，根据上面的结论可以得出：

位数为N的段的个数为10 ^ N - 10 ^ (N - 1)

这些段的长度为：

L[ i ] = L[ N - 1 ] + (i - 10 ^ (N - 1) + 1) * N，10 ^ (N - 1) <= i < 10 ^ N

一般地，设一个数M的十进制位数D(M)，则对于最后的数为M的序列123456……(M - 1)M，它的长度为

Len = L[ D(M) - 1 ] + (M - 10 ^ (D(M) - 1) + 1) * D(M)

有了以上的结论，我们便可先方便地得到第i位所在的段了，只需要把段的最后一个数作为循环变量进行循环就行了。

得到第i位所在的段之后，再在该段内从1开始循环，就可找到第i位所在的数，然后得到第i位数字在该数中的序号就可以得到第i位的数字了。

搜索题，注意，给出的方块是不能旋转的。

提高速度的方法是将相同的方块合并，只记录个数。

多次“导弹防御”问题。

题目很简单，但不要用搜索来做，用递推。

我是按模拟的方法来做的。

保存阶乘的所有结果是不现实的，我只保存阶乘结果的后面19位（用long long，并且去掉末尾的0），最后读出结果中从右往左第M位就行了。

模拟题，按题目要求做就行了。

实际上是将给出的几个数按降序排序再输出的问题，不过排序的规则不一样。

这道题的排序规则是：

对于两个数A和B，

如果AB大于BA，则A大于B，否则B大于A

可以当作模拟题来做，以第2站上车的人数来循环，以第一个满足题目条件的值算出的x就是答案。

按题目要求做就行了。

很像“Knight Move”问题。

由于是从左上角走到右下角，所以在扩展路径的时候只需考虑右边和下边的点就行了。

要注意的是下图所示的路径是合法的：

很像1044 Cipher。只不过刚开始有一个很复杂的模拟过程。

同“回文数I”，只不过是大数运算。

很简单的模拟题，用几重循环就行了。

博弈题。

几何题。很容易让人联想起高三的生活^_^

横边长a，纵边长b。

由于球是从台的中心发射，而最后又回到台的中心，故：

球与横边撞n次，说明球在纵向经过的路程是n * b（注意，是b而不是a）；相应地，球与纵边撞m次，说明球在横向经过的路程是m * a。

于是，球的运动可以简化为下图：

有了这个图，又知道球运动的时间，要算的东西就很好算了。

基本上就是归纳公式，归纳出的公式是：

result(i, j) = 0     (i = 0)

result(i, j) = 1     (i = 1)

result(i, j) = result(i - 1, j) + result(i - 1, j - 1) + 1

先建立一张素数表，再查表分解，速度会提高很多。

求凸包的问题。

由于棋盘是4×4大小的，而每个格子只有黑白两色，于是我们可以用一个16位的数（比如short）来表示一张棋盘。那么判重就和1108 Holed ox Moving差不多了。

另外，这道题的操作是“翻转”，所以我们可以用二进制异或来做。

模拟题加一点点动规。很分解出所有连续的段（即不含“*”的段），再求每一个段的最小L连续和就行了。

还是模拟题，模拟二分查找，记录下符合条件的值。

这道题的输出也是需要注意的，注意要把连续的值合并。

把多叉树化成二叉树来做。见下图：

左图是多叉树，右图是化成的二叉树，右图中的红色箭头表示从父结点到子结点。

此二叉树中，一个结点的左子结点是它在多叉树中从左到右第一个子结点；右结点是它在多叉树中的右兄弟。

注意，Equipment Box可以这样放：

判断欧拉路径是否存在的题。

模拟题，注意“-”的长度。

这是一道很好的动规题，所以我就写详细一些了^_^

首先，我们来分析一下解的结构。

第一点要注意的是，给定的字母序列是不能更改的。第二点就是，如果多个字母放到一个按键上，越靠后的字母的“代价”越大。同一个字母上放太多的字母，会使排在后面的字母的“代价”变得很大。最理想的情况就是每个按键上只放一个字母，但是，这往往是不现实的，因为按键的个数通常小于字母的个数。于是，最优解就在把较多的字母分配到较少的按键上的过程中产生了。

所以，最优解的结构就应该是这样的形式：

然后，我们来分析一下最优解的产生过程：

由以上分析得出的最优解的结构，我们可以看出，求最优解的过程就是移动分段符的过程，这些分段符将给定的字母序列分成N段（Ｎ就是按键的数目）。于是，我们很容易联想到“矩阵连乘”的模型。但这个问题与矩阵连乘不同之处在于，矩阵连乘是不限制分段的数目的，而此问题将分段的数目精确地限制成了按键的数目。所以，我们在利用矩阵连乘的模型来解决这个问题的时候，要考虑到分段数目的问题。

先考虑两种最基本的情况：

一、只有一个按键。此时只能将所有的字母分配到这个按键上。

二、按键数目等于字母数目。此时只能按顺序给每个按键分配一个字母。

以上两种最基本的情况是几乎不会在测试数据中出现的，但它们是我们在进行动规的边界。

好了，下面考虑一种简单的情况：

只有两个按键，且字母的数目多于按键的数目。在这种情况下，分段符只有一个，我们只需要把分段符从第一、二个字母之间移到最后两个字母之间，取每种分段方法的最小值就行了。

由上面的情况，我们将分段分出的第一段用“代入法”变换成多段，就变成了我们求解的过程。

比如：有Ｍ个字母，要分配到Ｎ个按键上，过程如下：

首先要说明的是，N > 1，如果N = 1，则变成了基本情况一了。

先考虑最后一个按键的第一个字母的位置（即确定最后一段的分段符）。最后一段的分段符将字母序列分成前M - 1段和第M - 1段（段号是从0开始的）。由于每个按键上都要安排字母，所以最后一个按键的第一个字母的位置区间是[N - 1, M - 1]，由于N <= M，所以这个区间总是存在的。最后一个按键的第一个字母的位置便由以下表达式来确定：

P = Min {aTotalP[i - 1][N - 1] + aPrice[ i ][M - 1]} (N - 1 <= i <= M - 1)

最后一个按键的第一个字母的最佳位置就是P取得最小值的i值。

aPrice表示将序列[i, M - 1]安排到一个按键上的代价，这个值是可以预先算好保存起来的。

aTotalP [L][N]表示将序列[0, L]分成N段时得到的最小代价值，显然，整个问题的答案就是aTotalP [M][N]。

根据P的表达式就可以逐级算出每一个分段符的最佳位置，进而得出aP[M][N]了。

算最优解的过程就告一段落，接下来要解决的问题就是输出这个最优解的组成。

要输出最优解的组成，很容易想到的就是保存各个分段符的位置这种方法。我就是这样做的。我用了一个二维数组aPos来保存分段符的位置，aPos[L][N]表示将序列[0, L]分成N段时最后一个分段符的位置。

我写了一个函数叫PrintResult(L, N)，功能是输出将序列[0, L]分成N段时的最优情况。

PrintResult函数的执行过程如下：

如果N = 1，则直接输出序列[0, L]；

否则，先PrintResult(aPos[L][N] - 1, N - 1)，即输出从序列开始到当前最后一个分段符之间的部分（这部分应该被分成N - 1段），再输出序列[ aPos[L][N], L ]。

最后，注意一下输出的格式应该按题目要求来做。

跟Dollars差不多，加一些flag会提高速度。

概率论的题目，还带一点递归的味道。主要用到的数学理论是概率论中的全概率公式。全概率公式我就不写了，翻翻书就可以知道。

在这个问题中，首先要搞清楚的是比赛的规则，特别是发球权更替的规则。

首先，比赛采用的是“发球得分”制，除了整个比赛的第一个球是用“丢硬币”的方式决定发球权，每局的第一个球由后面要介绍的规则决定发球权以外，其余的球都是由上一个球的胜者发。

以上是一局以内的情况，局间的情况是“轮流发球”制，除了整个比赛的第一个球是用“丢硬币”的方式决定发球权以外，其余的各局的第一个球都是由上一局没有先发球的那一方发。

为了不被规则所迷惑，我们先考虑一种比较简单的情况，比赛只有一局，谁赢了这一局，谁就赢得了比赛。这样，我们不必考虑“轮流发球”的情况。

在这种情况下，我们再简化一下，一局只有一个球，即一个回合，谁在此回合中取胜，谁就赢得此局。

已经简化到这一步，计算方法变得十分明显：

我们要求的是A赢得比赛的概率：

如果A发球，P = Pa；如果A不发球，P = (1 - Pb)，Pa和Pb的意义和题目中的描述相同。

由于A发球与A不发球是一对互补的事件，所以根据全概率公式可得：

P = (A发球的概率) * Pa + (A不发球的概率) * (1 - Pb)

而根据比赛规则，整个比赛的第一个球的发球权是由“丢硬币”的方式决定的，所以，A发球的概率为0.5，不发球的概率也是一样，所以：

P = 0.5 * Pa + 0.5 * (1 - Pb)

现在我们考虑稍微复杂一些的情况，比赛还是打一局，但一局有L个球（L > 1），那么：

P = (A发球的概率) * Pa’ + (A不发球的概率) * (1 - Pb’)

这里的Pa’和Pb’的意义是A赢得有L个球的一局的概率和B赢得有L个球的一局的概率了。

由于一局以内是采用“发球得分”制，所以，Pa和Pb就是A和B在得到下一个球的发球权的概率了。

于是，我们考虑aPGame[La][Lb][0]和aPGame[La][Lb][1]。

aPGame[La][Lb][]表示在A还需要赢La个球才能赢得此局，B还需要赢Lb个球才能赢得此局的情况下，A赢得此局的概率。

aPGame[La][Lb][0]表示此时该A发球，aPGame[La][Lb][1]表示此时该B发球。

基于我上面得出的结论，可得：

aPGame[La][Lb][0] = Pa * aPGame[La - 1][Lb][0] + (1 - Pa) * aPGame[La][Lb - 1][1]

aPGame[La][Lb][1] = (1 - Pb) * aPGame[La - 1][Lb][0] + Pb * aPGame[La][Lb - 1][1]

显然，aPGame[0][][] = 1，aPGame[][0][] = 0

上面是考虑一局以内的情况，每局之间的情况很类似，只需要把一局看作一个整体来做即可，我就不再赘述了^_^

简单的模拟题，用STL里的deque来做会很方便。

需要注意的是，the removal list里的数字M不是进程的cost，而是表示要输出第M个被删除的进程，M是从１开始的。

一句话：图的最小生成树。

表达式求导，注意，不要去掉所谓“多余的括号”。

超简单的模拟题。

也是简单的模拟题，把序列颠倒顺序用STL里面的reverse会很方便^_^

矩阵连乘的另外一种表达方式，解决方法完全一样。