ZOJ 3505：Yet Another Set of Numbers
地址：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3505
题意：有一个数字集合，集合中的数遵循以下规则：
( 1 ). 每个数字的最高位不是 0 ;
( 2 ). 每个数字包含最多 N 位，且只有 0，1，2，3 这四个数字可能出现（0 < N < 20）;
( 3 ). 每个数字的相邻位不同（例如：301是有效的，300不是）;
( 4 ). 数字比较大小和他们的字符串比较方法相同（例如：1 < 123 < 20 < 21 < 3）.
问题是，给出这个集合中的一个数字 B，从数字 B 开始，在这个集合中向前数数到第 K 个数字时输出这个数字（K > 0）;
原文叙述：求满足以下条件的数字A：在集合中恰好有 ( K - 1 ) 个数字大于 A 小于 B （题目保证存在解）;
时空限制：Time Limit: 2 Seconds; Memory Limit: 65,536 KB;
例如：当 N = 2 时，这个集合中一共有 12 个数字，依次是：
1 < 10 < 12 < [ 13 ] < 2 < 20 < 21 < 23 < [ 3 ] < 30 < 31 < 32; ----（序列中A和B用方括号标示）
当 B = 3 时，K = 5 时，从集合中的 3 向前数到第 5 个数字时是 13，因此应该输出 13。
（1）第一个解法，模拟法（Result：TLE）
我想到的第一个解法是，观察这个序列的规律，然后用模拟数数的方法，依次向前数，数到第 K 个为止即可。
考虑集合中最大的一个数字的字符串表示，显然是以下形式 "3232..."（长度为 N）。
因此可以给出下面的模拟数数的第一个解，模拟法代码如下： ( X. 以下代码算法时间超出题目限制 )
zoj3505_analog(TLE)
#include <stdio.h>
#include <string.h>
int length; /*当前数字的字符串长度*/
char Num[24];
/*检测当前数字是否合法*/
int IsNumValid()
{
int i;
// 第一位不能为0
if(Num[0] == '0')
return 0;
//相邻位不能相同
for(i = 0; i < (length - 1); i++)
{
if(Num[i] == Num[i+1])
return 0;
}
return 1;
}
void GetNextNum(int N)
{
char _MaxChars[4] = "32";
int i;
do
{
/* 如果最后一个字符是0，则去掉结尾的0 */
if(Num[length - 1] == '0')
{
Num[length - 1] = 0;
length--;
continue;
}
//ELSE: 当前字符递减后，立即扩展到 N 的长度
Num[length - 1] = Num[length - 1] - 1;
for(i = length; i < N; i++)
{
Num[i] = _MaxChars[ (i - length) & 1 ];
}
length = N;
}
while( !IsNumValid() );
}
int main(int argc, char* argv[])
{
int N = 0; /*字符串最大长度, 0 < N < 20 */
int K = 0; /*往下数第K个数字*/
int index; /*往下数多少个*/
while(scanf("%d %d", &N, &K) != EOF)
{
scanf("%s", Num);
length = strlen(Num);
for(index = 0; index < K; index++)
{
GetNextNum(N);
}
printf("%s\n", Num);
}
return 0;
}
但第一个方法提交后超时。显然，如果 N 比较大，这个集合中的数字数量是非常大的，因此这时 K 也可以取得很大。而这个方法是一个笨方法，是一个一个数字向前找，且还要进行数字合法校验，时间效率很低。当 N 和 K 都比较大时，这个方法在速度上显然不能满足要求。因此不能使用笨方法，必须找出这个序列中蕴藏的内在规律。
（2）速度更快的解法：使用三叉树模型（Result：MLE）
观察这个序列的规律，考虑数字用字符串进行比较的特点，比较时，越高（靠左）的位越重要，越低的位则不重要。因此考虑把每一位看作一个节点，则低位属于高位的子节点，父子节点彼此属于相邻的位，显然有每个节点含有三个子节点（由于每一位上只能在 0，1，2，3 中选择，且不能与父节点数字相同），因此形成一个满的三叉树。
每个节点代表了序列中的一个数字，把从根节点到该节点的路径所经过的节点依次输出，就是这个数字的字符串表示。当 N = 2 时，该树如下图所示：
题意中的规则（2）规定了树的高度，规则（1）和（3）使该树从完全四叉树变成完全三叉树，规则（1）去掉了“0” 子树，规则（3）缩减了子节点个数。
考虑两个树节点 N1 和 N2 之间的排序关系（比较时，深度小的节点比深度大的节点重要），注意和字符串比较算法进行对比：
（a）如果 N1 节点位于 N2 的路径上，则路径短的节点小；( eg. 123 < 1230 )
（b）如果 N1 和 N2 在节点 N' 处开始分离（从根节点到 N’ 处路径重合），则进入 N' 左侧子树的小于进入 N' 右侧子树的。( eg. 121230 < 123 )
（c）从前两点可知，此树前序遍历（先遍历当前节点的所有子节点，然后访问当前节点），即为数集合的有序排列。（对比：二叉查找树的中序遍历为有序序列）
图中节点圆圈中的黑色数字就是用于组成输出数字的位（num）。为了统计树中每个子树所代表的子序列中的数字个数，我们在每个节点上加一个属性 sum，表示以该节点为根的子树所表征的数字组成的子序列的数字个数，在图中用节点旁边的红色数字表示。显然，节点的 sum，就是以该节点为根的子树所包含的所有节点的数目，因为每个节点都一对一的代表集合中一个数字，用节点路径表示（类似贪心算法中的霍夫曼编码和霍夫曼树的关系）。由于输出节点路径时，根节点无需输出 ( dummy node )，因此根节点用阴影填充，和子节点的连线用虚线表示。
显然，最底层的所有叶子节点（深度为 N + 1）仅代表一个数字，其 sum = 1，对非叶子节点，其三个子节点的 sum 值相同，再加上自身节点代表的数字，因此有：
Node.sum = Node.Child[0].sum * 3 + 1 ;
因此对于本题目来说，可以创建这样一个三叉树，对于给定的数字 B，设它对应的是树中的节点 B，从 B 节点开始，向前回退寻找目标节点 A。
为了清楚的描述算法，我用节点游标的形式来阐述该算法（在代码中可以是一个节点的指针，表示当前所处的位置），并做如下定义：
(a). K 的逻辑含义是，代表当前节点和目标节点 A 的“距离”。寻找过程中 K 的值将不断减小，直到为 K = 0 ，表示到达目标节点A。
(b). 游标指向的改变称为 “移动到” 某个节点。
(c). 如果节点需要处理（即调整 K 值），称为“访问” ( visit ) 该节点。
(d). 如果节点不需要处理（即不需要调整 K 值），称为“经过” ( pass ) 该节点。
则算法（2）的基本步骤（GetNodeBySteps ）如下：
(2.1). 令游标指向起始节点 B; （这是准备工作，接下来将“向前”寻找节点 A）
(2.2). 如果所在节点已经是兄弟节点中的老大（位于最左侧），则（向上）“访问”其父节点，令 K = K - 1; 跳到（2.6）; （请思考为什么此处 K 的递减值是 1 而不是 Node.sum？）
(2.3). 如果所在节点有哥哥节点，则（向左）移动到它的哥哥节点; （接下来在 （2.4）和（2.5）中一定能找到一个可访问节点，请思考这是为什么？）
(2.4). 如果 Node.sum <= K ，则“访问”该节点，令 K = K - Node.sum，跳到（2.6）; （备注：Node.sum < K 时说明 A 不位于该节点为根的子树中）
(2.5). 如果 Node.sum > K，（备注：说明 A 位于 Node 为根的子树中） 则连续的（向下）移动到当前节点的（最右侧）最幼子节点，直到找到符合（2.4）中的条件（Node.Sum <= k）的节点为止，然后用和（2.3）的相同方法“访问”它：令 K = K - Node.sum; （这是一个嵌在内部的 while 循环）
(2.6). 如果 K != 0，则重复（2.2）~ （2.5）。直到 K = 0 为止，此时我们到达的节点就是目标节点 A，输出节点 A 的路径就是问题的解;（这是最外层的 while 循环）
总结上面的探查方法：如果一个节点是被访问节点，则绝不会再进入它的任何子树；当寻找下一个可访问节点时，如果左侧有哥哥节点，则一定先探查哥哥节点（如果哥哥节点没有超越目标，则访问它；否则进入它的幼子子树继续探查），否则访问父节点（此时父节点必是可访问节点）。
上面的语言接近伪码，括号内的描述属于导航时的逻辑方向或备注性说明。显然（2.2）~（2.6）整体是一个 while 循环，其中（2.5）是嵌在其内的又一个 while 循环。上诉步骤即对应的是代码中的 GetNodeBySteps 方法，参数 step 即 K。
【思考】：为何（2.2）向父节点回退时的访问和（2.4）和（2.5）中的访问方法不同，前者令 K 递减 1，后者令 K 递减 Node.sum。
（提示：前者，当子节点向父节点“回退”时，子节点为根的子树位于其父节点所代表的子树中。后者则进入到了另一个独立的子树。）
第二个解法的代码（三叉树方法），如下所示： ( X. 以下代码内存使用超出题目限制 )
zoj3505_trian_tree(MLE)
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct _NODE
{
char index; /* 在兄弟节点中的排行索引 */
char num; /* 节点数字, 只能取下列值 0,1,2,3，为 'R' 时表示 root */
int sum; /* 1 + 3 + 9 + ... + 3^k */
_NODE* parent; /* 父节点 */
_NODE* child[3]; /* 子节点 */
} NODE, *PNODE;
/* 递归函数： N - 树的深度（不含根节点的深度） */
void AddChildren(PNODE pNode)
{
int i, _num = 0;;
PNODE pChild = NULL;
pNode->sum = pNode->sum * 3 + 1;
if(pNode->child[0] == NULL)
{
for(i = 0; i < 3; i++)
{
pChild = (PNODE)malloc(sizeof(NODE));
memset(pChild, 0, sizeof(NODE));
pChild->parent = pNode;
pChild->index = i;
pChild->sum = 1;
/* 回避父节点数字 */
if(pNode->num == _num) _num++;
pChild->num = _num++;
pNode->child[i] = pChild;
}
}
else
{
for(i = 0; i < 3; i++)
AddChildren(pNode->child[i]);
}
}
PNODE CreateTree(int depth)
{
int i;
PNODE pRoot = (PNODE)malloc(sizeof(NODE));
memset(pRoot, 0, sizeof(NODE));
pRoot->num = 0; /*根节点数字为0，可以让第一层子节点为1，2，3 */
pRoot->sum = 1;
for(i = 0; i < depth; i++)
{
AddChildren(pRoot);
}
pRoot->num = 'R';
return pRoot;
}
/* 释放树占用的内存（递归函数） */
void FreeTree(PNODE pNode)
{
int i;
for(i = 0; i < 3; i++)
{
if(pNode->child[i] != NULL)
{
FreeTree(pNode->child[i]);
}
}
free(pNode);
}
/* 从节点 pStart 向前追溯到某个节点 */
PNODE GetNodeBySteps(PNODE pRoot, PNODE pStart, int step)
{
int remainStep = step;
int index;
PNODE pCurNode = pStart, pNextNode = NULL;
while(remainStep > 0)
{
/*找到下一个不大于 remainStep 距离的节点*/
index = pCurNode->index;
if(index == 0)
{
/* 向上返回一层时，只-1 */
pCurNode = pCurNode->parent;
remainStep--;
continue;
}
pNextNode = pCurNode->parent->child[ index - 1];
while(pNextNode->sum > remainStep)
{
/* 向下进入最右侧的最小子节点分支 */
pNextNode = pNextNode->child[2];
}
pCurNode = pNextNode;
remainStep -= pCurNode->sum;
}
return pCurNode;
}
/* path: 字符串形式例如“12301” */
PNODE GetNodeByPath(PNODE pRoot, char* path)
{
int i;
char *p = path;
PNODE pCur = pRoot;
while(*p)
{
for(i = 0; i < 3; i++)
{
if(pCur->child[i]->num == (*p - '0'))
{
pCur = pCur->child[i];
break;
}
}
++p;
}
return pCur;
}
/* 借助辅助栈，输出找到的节点的路径（从根节点到该节点）*/
void OutputNodePath(PNODE pNode)
{
char stack[24];
int top = 0;
PNODE pCur = pNode;
while(pCur->parent != NULL)
{
stack[top++] = pCur->num;
pCur = pCur->parent;
}
while(top > 0)
{
printf("%d", stack[ top - 1 ]);
--top;
}
printf("\n");
}
int main(int argc, char* argv[])
{
int depth, step;
char path[24];
PNODE pRoot, pStart, pDest;
while(scanf("%d %d\n", &depth, &step) != EOF)
{
gets(path);
pRoot = CreateTree(depth);
pStart = GetNodeByPath(pRoot, path);
pDest = GetNodeBySteps(pRoot, pStart, step);
OutputNodePath(pDest);
FreeTree(pRoot);
}
return 0;
}
【分析】为什么算法（2）比算法（1）快？
算法（1）永远是一个一个数字向前数，步进值（step）永远为 1 ; 当初我想改进算法（1）时发现，如果不借助数据结构，很难在原基础上进行改进。集合中的数也很难用数学公式计算或总结（这也是采用模拟法的原因）。
算法（2）是在树中导航，注意树节点越往上（深度越小），节点的 sum 值越大（而且是随着深度减小，以极快的指数速度增长），所以算法（2）的数数方式是跳跃式的，而且能用很快速度探索到一个理想的 Step 值（该 Step 足够大，又满足 Step <= K ，即向目标迈进的步子足够大，而又不会超越目标节点），该 Step 由树节点的 sum 值表示，然后直接越过该子树所代表的子集合，无需遍历该子集合（所有数字或树节点）。因此访问的节点在树中的深度越浅（越靠近树根），则以该节点为根的子树的规模就越大，代表着跨越的数字个数就越多。由于每个节点最多只有两个哥哥节点，在同一深度向前移动时所消耗的时间不多，因此算法能以很快的速度上升到跨度尽可能大的可访问节点。因此算法（2）在时间上比算法（1）高效的多。
算法（2）的另一种形象理解是：
B > A，则水平方向 B 位于 A 子树的下方或 A 的右侧子树。则存在一个深度最大（设深度为 d ）的公共子树 T ，满足 A, B ∈ T 。
现在从节点 B 出发，寻找节点 A。由于 A 比 B 小，因此 B 不可能是 T 的根。
(a). 如果 A 不是 T 的根，则必然 A 和 B 分别位于 T 的左右两个子树。因此从 B 所在的右侧子树上浮到 （d+1） 深度后，继续向前移动到 A 所在的左侧子树，然后靠右侧下沉到 A 。（搜寻路线类似梯形）
(b). 如果 A 是 T 的根，则靠左上浮到 A 。
上诉两种情况，在水平方向上在各个深度上都可能呈现一些向左的水平步进。因此在 向前向上 探寻时，探寻路径呈“锯齿形”。向下探寻时则是“直线”式下降。对平均情况，探索路径的长度（时间）和树的高度 N 为线性关系。
Figure 1. 节点 B 到节点 A 的探寻路径；
如 Figure 1 所示。图中红色虚线箭头相连得到的路径，即为从 B 到 A 的探寻路径。图中 A 和 B 的最深公共子树 T 是数字“10”所在节点，同时 T 被用粗线表示。灰色节点为可访问节点，斜线表示的节点为位于搜索路线上，但是被经过（Pass）的节点。图中 N = K = 4；从 A 到 B 的序列是：{ 1021, 1023, 103, 1030, 1031 } ;
【缺陷】但算法（2）的结果是内存超出限制（MLE）。理由实际上同（1），当 N 很大时，树非常庞大。由于它是一个满三叉树，所以节点数量是一个等比数列的和：
Sum = ∑ ( 3 ^ i ) = 1 + 3 + 9 + 27 + ... + 3^N = ( 3 ^ ( N + 1) - 1 ) / 2 ;
----( 高度为 N + 1 的三叉树的所有节点数量 ) ;
从上式粗略估算可知内存需求极大，产生 MLE 也就不足为奇了，考虑极限情况：
假设 N = 19，则此树共含有 1,743,392,200 个节点。设每个节点占用 24 Bytes 则：在内存中建立该树需要：38.97 GB ！！！ @_@ ...
（1）和（2）的解法一个超时一个超内存限制，都是因为该集合的元素数量非常大导致的。既要利用（2）中的三叉树模型的时间效率，但又不能采用在内存中完整建立树的方法，因此导出下面的第三个解法。
（3）正确解：虚拟树 / 树枝法（Result：AC）
为了时间效率，依然采用三叉树的模型，但是不能在内存中完整建树，因此启发我们，可以在内存中仅仅保留一条树枝，该树枝最长的长度（叶子在树中所处的深度）为 N。考察解法（2）中的方法，无非是在树之间进行导航，即从某个节点到其父节点，左侧的哥哥节点，右下方的幼子节点。同时，由于此树满足，相同深度的所有节点的 sum 值相同。因此我们可以仅用一条树枝即完成（2）中的算法。
方法是：在内存中不建立整个树，而是仅仅存储一个当前树枝。树枝长度可伸缩，最大为N。树枝采用一个线性表结构保存，可以使用数组或链表（为了代码简便我们使用数组）。每个节点依然含有两个属性： num 和 sum。如果说算法（2）中的树是内存中的实际树（物理树），则算法（3）中的树是仅存在于思维模型中的“虚拟树”。
一个树枝在树中的位置，以及它在数组中的存储状态如下图所示，图中树枝部分用实体粗线条表示，整个树由于不在内存中，因此用虚线表示：
为了实现算法，我们必须很容易的确定该树枝在完整的树模型中的位置和形态。即容易实现以下问题：
（3.1）求出某个节点在同辈兄弟中的排行索引（ Index_In_Siblings ） ，∈ { 0，1，2 } ;
（3.2）求出某个节点的哥哥节点（左侧）的 num （ Num_Of_Elder_Brother ），∈ { 0，1，2，3 } ;
（3.3）求出某个节点的幼子节点（右下）的 num （ Num_Of_Right_Child ），∈ { 0，1，2，3 } ;
其中（3.1）和（3.2）可以通过本节点的 num 和其父节点的 num 推断得出。（3.3）可以从本节点的 num 求出。
算法执行过程中，随着游标在树中的节点之间移动，树枝在树中的伸展形态（在树中的位置和树枝的长度）也同时发生变化，当寻找到目标节点 A 以后，树枝静止在最终状态，根据方法返回的树枝长度即可确定最终的树枝。目标节点 A 即为最终树枝的末端叶子节点。
因此解法（3）三叉树树枝法算法与（2）相同，但解决了空间复杂度的问题，代码如下： ( √. 以下代码是可接受的 )
zoj3505_branch(AC)
#include <stdlib.h>
#include <stdio.h>
#include <string.h>
typedef struct _NODE
{
int num; /* 节点数字, 取值 0,1,2,3 */
int sum; /* 1 + 3 + 9 + ... + 3^k */
} NODE, *PNODE;
NODE nodes[20]; //树枝
//初始化树枝各个节点的 sum 值
void InitSums(int N)
{
int i;
//叶子节点
nodes[N-1].sum = 1;
for(i = N - 2; i >=0 ; --i)
{
nodes[i].sum = nodes[i + 1].sum * 3 + 1;
}
}
//初始化树枝各个节点的 num 值
//path: "1231"
int InitNodesByPath(char *path)
{
int depth = 0;
char *p = path;
while(*p)
{
nodes[depth].num = (*p - '0');
++depth;
++p;
}
return depth - 1;
}
//输出指定深度节点的路径（从根节点到该节点）
void OutputNodePath(int depth)
{
int i;
for(i = 0; i <= depth; i++)
{
printf("%d", nodes[i].num);
}
printf("\n");
}
//获取节点在兄弟节点中的排行索引
int GetIndexInSibling(int depth)
{
if(depth == 0)
return (nodes[depth].num - 1);
else if(nodes[depth-1].num > nodes[depth].num)
{
return nodes[depth].num;
}
else
{
return nodes[depth].num - 1;
}
}
//返回哥哥节点的数字
int GetBrother(int depth)
{
int result = nodes[depth].num - 1;
if(depth > 0 && nodes[depth-1].num == result)
{
--result;
}
return result;
}
//返回幼子的数字
int GetRightChild(int depth)
{
int result = 3;
if(nodes[depth].num == 3)
result = 2;
return result;
}
//从节点A开始向前追溯到节点B，返回对应深度
//nStart: 节点A的深度
//step：节点A和B之间的距离
int GetNodeBySteps(int nStart, int nStep)
{
int remainStep = nStep;
int depth = nStart;
while(remainStep > 0)
{
//回退到父节点
if(GetIndexInSibling(depth) == 0)
{
//向上返回一层时，只-1
depth--;
remainStep--;
continue;
}
//进入哥哥节点
nodes[depth].num = GetBrother(depth);
while(nodes[depth].sum > remainStep)
{
//向下进入最右侧的最小子节点分支
nodes[depth + 1].num = GetRightChild(depth);
depth++;
}
remainStep -= nodes[depth].sum;
}
return depth;
}
int main(int argc, char* argv[])
{
int N, K;
char path[24];
int nStart, nDest;
while(scanf("%d %d\n", &N, &K) != EOF)
{
gets(path);
InitSums(N);
nStart = InitNodesByPath(path);
nDest = GetNodeBySteps(nStart, K);
OutputNodePath(nDest);
}
return 0;
}
以上代码提交后的结果是 AC。运行消耗是时间 120 ms，空间 180 KB。空间需求微不足道可以说是O（1），但用时是解排行榜单上的其他 C++ 优秀解法用时（40ms ~ 60ms）的两三倍。一可能是我用了很多很小的函数，没有inline，多少带来一些函数调用的开销，二是可能别人的算法要比我更快更好。
【分析】为什么可以使用树枝的方法？
此题目中，树的规模非常大，所以逼迫我们使用了树枝法，那么为什么可以不在内存中建立树呢，这是因为树自身具有的内在规律，即节点不是完全随机和独立的，而是存在下面的关系，假设树根深度为 1，树的高度（叶子节点的深度）为（N + 1），则深度为 d 的节点：Node.sum = ( 3 ^ (N + 2 - d ) - 1 ) / 2; 对于非叶子节点，有三个子节点，按升序排列并与父节点不重复。因为有了这些已知条件，使我们能推断出我们需要的节点的信息，因此不需要一个完整的树来存储它。
【说明】本文所有插图，使用 Microsoft Office Visio 绘制。
