含章信竞周赛J01题解

含章信竞周赛HanZJ01题解本周竞赛题目难度为CSP_J组复赛T1/T2难度。算法为模拟算法。三道题，用时120分钟。题目名称：谢弗涅的猜想题号：HanZJ01T1算法分类：模拟算法聪明的谢弗涅在学习数列的时候发现一个有趣的现象：从正整数n开始，如果n是偶数，就将它除以2；如果n是奇数，就将它乘以3再加1。用得到的新值不断重复上述步骤，最终都会得到1。例如，n=22时，会得到如下序列：22,11,34,17,52,26,13,40,20,10,5,16,8,4,2,1。谢弗涅猜想，对于任意正整数n，该算法总能终止于n=1。到目前位置该算法在1e6的数值内都是正确的。对于给定的n，该序列中的元素的个数，包括1，被称为该数字的循环节长度。如上例中的22，其循环节长度为16。输入两个正整数i,j（0<i<j<=1e6）。计算区间[i,j]内整数的循环节长度最大值。输入由多组样例组成，第一行为正整数T（1<=T<=100）。第二行为两个正整数i,j，定义如题。对于每个输入，在不同的行输出一个正整数。输入样例：21101030输出样例：20112解题思路：此题为角谷猜想得板子题。唯一变化是角谷猜想常态下会要求输出路径，此题仅要求输出路径长度，即循环节。此题解题时须注意多样例初始化问题。解题代码如下：题目名称：谢弗涅的扫雷游戏题号：HanZJ01T2算法分类：模拟算法最近谢弗涅迷恋上了扫雷游戏。游戏的目标是找到一个n*m矩阵中的所有地雷。在游戏中，每个单元格有8个相邻的各自，谢弗涅需要计算出每个单元格周围地雷的个数。如下例是一个4*4的单元格，用*表示地雷，左侧为游戏初始的样子，右侧为计算出的结果。输入将包含若干个矩阵。对于每一个矩阵，第一行将包含两个正整数n,m(0<n,m<=100)，表示矩阵的行列数。接下来n行，表示矩阵。其中*表示地雷，#表示安全区。当n=m=0时，输入结束。程序不应处理这一行。对于每个输入的矩阵，同样输出一个矩阵。输出矩阵中，以数字代替#，数字要求如题意。*单元还以*表示。两个矩阵之间应以一个空行隔开。*注：本编译器不支持while(1)写法。输入样例：44*########*######35**#########*###00输出样例：*10022101*101110**100332001*100解题思路：此题为模拟算法，解法就是将题目文字描述的扫雷过程代码复原即可。需要注意的是，8个方向的坐标调整系不要写错。同时需要注意，多样例中图形矩阵的初始化问题。解题代码如下：题目名称：谢弗涅的猜想（J01T3）题号：HanZJ01T3算法分类：模拟算法谢弗涅学校每年的组织同学去不同的地方旅游。学生们要均摊所有的旅费。同学们在旅行中会垫付一些费用，并在旅行结束后计算。计费原则是多退少补，每个同学的支出差距在1分钱以内。同学们互相转钱是件很麻烦的事，所以你的任务是在一份清单的基础上，计算出为了平摊费用所必须进行的最小总“交易”额。输入由若干组组成。每组第一行一个正整数n(1<=n<=1000)，表示这次旅行由n名同学组成。一下n行，包含了每一个同学垫付的费用pi(0<pi<=1e5)，精确到分。最后一行由一个0结束。对于每组数据只输出一行，为最小交易额度，精确到分。输入样例：310.00