题目分析The Hendrie Sequence\texttt{The Hendrie Sequence}The Hendrie Sequence是一个自描述序列其定义如下H(1)0H(1) 0H(1)0如果将序列HHH中的每个数xxx展开为包含xxx个000后跟数字x1x 1x1的子序列那么得到的结果序列仍然是HHH去掉第一个元素后序列的前几项为0,1,0,2,1,0,0,3,0,2,1,1,0,0,0,4,1,0,0,3,0,…0, 1, 0, 2, 1, 0, 0, 3, 0, 2, 1, 1, 0, 0, 0, 4, 1, 0, 0, 3, 0, \dots0,1,0,2,1,0,0,3,0,2,1,1,0,0,0,4,1,0,0,3,0,…我们需要编写程序对于给定的nnn0n2630 n 2^{63}0n263计算H(n)H(n)H(n)的值。解题思路序列规律分析通过观察序列的生成过程我们可以发现一些重要的规律块结构序列可以划分为多个块每个块的大小呈指数增长递归性质每个块的内容由前面块的内容递归构成自相似性序列具有分形结构大块包含小块的多个副本关键发现经过深入分析我们发现第kkk块具有以下结构块大小2k−12^{k-1}2k−1块内容[[[第(k−2)(k-2)(k−2)块的内容][] [][第(k−3)(k-3)(k−3)块的内容重复222次]...[] ... []...[第111块的内容重复(k−2)(k-2)(k−2)次][(k−1)] [(k-1)][(k−1)个000] [kkk]例如第333块[1,0,0,3][1, 0, 0, 3][1,0,0,3] 第111块内容[1]2[1] 2[1]2个0 [0,0][3]0 \ [0,0] [3]0[0,0][3]第444块[0,2,1,1,0,0,0,4][0, 2, 1, 1, 0, 0, 0, 4] [0,2,1,1,0,0,0,4]第222块内容[0,2] [0,2] \ [0,2]第111块内容重复222次[1,1]3[1,1] 3[1,1]3个0 [0,0,0][4]0 \ [0,0,0] [4]0[0,0,0][4]算法设计基于上述规律我们设计递归算法预处理计算各块的大小和前綴和块定位对于给定的nnn找到它所在的块kkk块内定位在块内递归定位根据块结构判断如果在子块内容区域递归到对应的子块如果在额外的000区域返回000如果是最后一个元素返回kkk技术细节使用__int128_t处理大数避免溢出实现__int128_t的输入输出功能递归深度最多646464层效率可接受复杂度分析时间复杂度O(logn)O(\log n)O(logn)每次递归都将问题规模减半空间复杂度O(logn)O(\log n)O(logn)递归调用栈的深度代码实现// The Hendrie Sequence// UVa ID: 10479// Verdict: Accepted// Submission Date: 2025-11-08// UVa Run Time: 0.000s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 使用128位整数处理大数避免溢出typedef__int128_t BigInt;/** * 打印BigInt类型的数字 * param n 要打印的大整数 */voidprintBigInt(BigInt n){if(n0){cout0;return;}if(n0){cout-;n-n;}string s;while(n){s0(n%10);n/10;}reverse(s.begin(),s.end());couts;}/** * 求解Hendrie序列的第n个元素 * param n 位置索引从1开始 * return 序列的第n个元素值 */BigIntsolveHendrie(BigInt n){// 基础情况第一个元素是0if(n1)return0;// 去掉第一个元素0在剩余序列中定位n--;// 找到n所在的块BigInt blockStart1;// 当前块的起始位置BigInt blockIndex1;// 当前块的索引BigInt blockSize1;// 当前块的大小// 定位n所在的块while(blockStartblockSizen){blockStartblockSize;blockIndex;blockSize*2;}// n在当前块中的位置从1开始BigInt posInBlockn-blockStart1;// 在块内递归定位while(blockIndex1){BigInt currentPos0;// 当前在块内的位置// 处理子块内容第i块的内容出现(blockIndex-1-i)次for(BigInt iblockIndex-2;i1;i--){BigInt copiesblockIndex-1-i;// 重复次数BigInt subBlockSizeBigInt(1)(i-1);// 子块大小 2^(i-1)BigInt segmentSizesubBlockSize*copies;// 该段的总大小// 如果n在当前段内if(posInBlockcurrentPossegmentSize){BigInt offsetposInBlock-currentPos;// 在段内的偏移量// 计算在子块内的位置posInBlock(offset-1)%subBlockSize1;blockIndexi;// 递归到子块currentPos0;// 重置当前位置continue;// 重新开始循环}currentPossegmentSize;}// 处理额外的0有(blockIndex-1)个0if(posInBlockcurrentPos(blockIndex-1)){return0;}// 最后一个是blockIndexreturnblockIndex;}// 第一块只有一个元素1return1;}intmain(){string input;// 处理多个测试用例直到输入0为止while(cininputinput!0){// 将字符串转换为BigIntBigInt n0;for(charc:input){nn*10(c-0);}// 计算并输出结果printBigInt(solveHendrie(n));cout\n;}return0;}总结本题的关键在于发现序列的自相似性和递归结构。通过将序列划分为指数增长的块并分析块内的组成规律我们能够设计出高效的递归算法。使用__int128_t确保了大数情况下的正确性而递归的深度保证了算法的高效性。这种分而治之的思路在解决具有自相似性的序列问题时非常有效类似的思路也可以应用于其他分形序列或递归定义序列的问题中。
UVa 10479 The Hendrie Sequence
题目分析The Hendrie Sequence\texttt{The Hendrie Sequence}The Hendrie Sequence是一个自描述序列其定义如下H(1)0H(1) 0H(1)0如果将序列HHH中的每个数xxx展开为包含xxx个000后跟数字x1x 1x1的子序列那么得到的结果序列仍然是HHH去掉第一个元素后序列的前几项为0,1,0,2,1,0,0,3,0,2,1,1,0,0,0,4,1,0,0,3,0,…0, 1, 0, 2, 1, 0, 0, 3, 0, 2, 1, 1, 0, 0, 0, 4, 1, 0, 0, 3, 0, \dots0,1,0,2,1,0,0,3,0,2,1,1,0,0,0,4,1,0,0,3,0,…我们需要编写程序对于给定的nnn0n2630 n 2^{63}0n263计算H(n)H(n)H(n)的值。解题思路序列规律分析通过观察序列的生成过程我们可以发现一些重要的规律块结构序列可以划分为多个块每个块的大小呈指数增长递归性质每个块的内容由前面块的内容递归构成自相似性序列具有分形结构大块包含小块的多个副本关键发现经过深入分析我们发现第kkk块具有以下结构块大小2k−12^{k-1}2k−1块内容[[[第(k−2)(k-2)(k−2)块的内容][] [][第(k−3)(k-3)(k−3)块的内容重复222次]...[] ... []...[第111块的内容重复(k−2)(k-2)(k−2)次][(k−1)] [(k-1)][(k−1)个000] [kkk]例如第333块[1,0,0,3][1, 0, 0, 3][1,0,0,3] 第111块内容[1]2[1] 2[1]2个0 [0,0][3]0 \ [0,0] [3]0[0,0][3]第444块[0,2,1,1,0,0,0,4][0, 2, 1, 1, 0, 0, 0, 4] [0,2,1,1,0,0,0,4]第222块内容[0,2] [0,2] \ [0,2]第111块内容重复222次[1,1]3[1,1] 3[1,1]3个0 [0,0,0][4]0 \ [0,0,0] [4]0[0,0,0][4]算法设计基于上述规律我们设计递归算法预处理计算各块的大小和前綴和块定位对于给定的nnn找到它所在的块kkk块内定位在块内递归定位根据块结构判断如果在子块内容区域递归到对应的子块如果在额外的000区域返回000如果是最后一个元素返回kkk技术细节使用__int128_t处理大数避免溢出实现__int128_t的输入输出功能递归深度最多646464层效率可接受复杂度分析时间复杂度O(logn)O(\log n)O(logn)每次递归都将问题规模减半空间复杂度O(logn)O(\log n)O(logn)递归调用栈的深度代码实现// The Hendrie Sequence// UVa ID: 10479// Verdict: Accepted// Submission Date: 2025-11-08// UVa Run Time: 0.000s//// 版权所有C2025邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;// 使用128位整数处理大数避免溢出typedef__int128_t BigInt;/** * 打印BigInt类型的数字 * param n 要打印的大整数 */voidprintBigInt(BigInt n){if(n0){cout0;return;}if(n0){cout-;n-n;}string s;while(n){s0(n%10);n/10;}reverse(s.begin(),s.end());couts;}/** * 求解Hendrie序列的第n个元素 * param n 位置索引从1开始 * return 序列的第n个元素值 */BigIntsolveHendrie(BigInt n){// 基础情况第一个元素是0if(n1)return0;// 去掉第一个元素0在剩余序列中定位n--;// 找到n所在的块BigInt blockStart1;// 当前块的起始位置BigInt blockIndex1;// 当前块的索引BigInt blockSize1;// 当前块的大小// 定位n所在的块while(blockStartblockSizen){blockStartblockSize;blockIndex;blockSize*2;}// n在当前块中的位置从1开始BigInt posInBlockn-blockStart1;// 在块内递归定位while(blockIndex1){BigInt currentPos0;// 当前在块内的位置// 处理子块内容第i块的内容出现(blockIndex-1-i)次for(BigInt iblockIndex-2;i1;i--){BigInt copiesblockIndex-1-i;// 重复次数BigInt subBlockSizeBigInt(1)(i-1);// 子块大小 2^(i-1)BigInt segmentSizesubBlockSize*copies;// 该段的总大小// 如果n在当前段内if(posInBlockcurrentPossegmentSize){BigInt offsetposInBlock-currentPos;// 在段内的偏移量// 计算在子块内的位置posInBlock(offset-1)%subBlockSize1;blockIndexi;// 递归到子块currentPos0;// 重置当前位置continue;// 重新开始循环}currentPossegmentSize;}// 处理额外的0有(blockIndex-1)个0if(posInBlockcurrentPos(blockIndex-1)){return0;}// 最后一个是blockIndexreturnblockIndex;}// 第一块只有一个元素1return1;}intmain(){string input;// 处理多个测试用例直到输入0为止while(cininputinput!0){// 将字符串转换为BigIntBigInt n0;for(charc:input){nn*10(c-0);}// 计算并输出结果printBigInt(solveHendrie(n));cout\n;}return0;}总结本题的关键在于发现序列的自相似性和递归结构。通过将序列划分为指数增长的块并分析块内的组成规律我们能够设计出高效的递归算法。使用__int128_t确保了大数情况下的正确性而递归的深度保证了算法的高效性。这种分而治之的思路在解决具有自相似性的序列问题时非常有效类似的思路也可以应用于其他分形序列或递归定义序列的问题中。
