彩色项链解题报告

1、彩色项链解题报告上海市复旦附中 张宁题目描述程序文件：necklace.cpp/necklace.c/necklace.pas输入/输出文件：necklace.in/necklace.out【问题描述】一条项链由N个珠子连接而成，编号依次为0, 1, 2, , N-1。每个珠子的颜色用09之间的一位数字来表示（因此，可用的颜色一共有10种）。一条长度为4的项链如下图所示：（圆圈中的数字表示颜色，圆圈旁边的数字为珠子的编号）图1 一条长度为4的项链需要注意的是，如图1所示，编号为0, 1, 2, , N-1的珠子大小是依次递增的，设编号为i的珠子的颜色值为ai，则数字序列a0a1an-1可以唯一

2、的表示一种项链。例如，图1所示的项链表示为“1337”。现在有一台自动生产项链的机器，它的结构和工作方式如下所述：机器的核心控制部件主要包括：一个CPU、一个整数寄存器START、和存储器S。机器内部固化有一段程序，由CPU解释执行。该程序的输入是长度为N的十进制数字序列A，输出是另一个长度为N的十进制数字序列B。每次执行程序前将S初始化为输入序列A；程序结束后把S作为输出串B。START初始化为0。程序包含M条指令，顺序编号为1M。指令共有5种，以下是指令的格式和功能：（尖括号表示指令参数，都是整数）编号功能格式说明1设置寄存器SETSTART 设置START的值：从S的第a位开始取连续b位

3、得到的十进制整数（可能大于N-1）。0=a=N-1，1=b=min(8, N)2循环移位SHIFT 把S从第START位开始的连续L 位，循环移位|x|位。x0时右移，x0时左移。2=L=min(10, N)，1=|x|=L-13乘法MUL 把S从第START位开始的连续L位当做原始串（L位十进制整数），将其乘以x以后保留结果的最低L位，替换原始串。1=x=9，1=L=min(10, N)4条件ONDIGIT 如果S的第x位等于y，则跳转到第z条指令。0=x=N-1，0=y=9，1=z=M。z大于当前指令序号, 即不会往回跳转。5终止END仅作为最后一条语句出现，程序终止。由于项链是环型的，因

4、此第i位和第i+kN位（k为整数）代表数字序列的同一位置。例如当N=4时，第6位和第2位是等价的。下面是一个程序的例子：MUL 3 2SETSTART 2 1ONDIGIT 0 4 1SHIFT 3 2END机器启动的时候，输入一个数字串S0，执行程序得到一个新的数字序列S1并生产出S1代表的项链来，以后机器每生产出一条新项链Sn，就把Sn对应的数字序列作为输入重新执行一遍程序，得到一个新的数字序列Sn+1并生产出新的项链。由于长度为N的项链种类数目是有限的（至多10N种不同的项链），因此如果让机器一直工作下去，某些种类的项链会被生产出无限多条。编程计算出这些将被无限生产出的项链有多少种。在本

5、题中，可以被生产出来的项链种类总数保证不超过106。【输入文件】输入文件necklace.in的第1行包含两个整数N和M (1=N=100,000，2=M=30)，第2行包含一个有N个数字的串S0。第3行到第M+2行为一段程序，每行一条指令，程序保证无错，行末和行首均没有空格。【输出文件】输出文件necklace.out仅有一行，包含一个整数，是将被无限生产出来的项链种类数目。【输入输出样例】necklace.innecklace.out4 51234MUL 3 2SETSTART 2 1ONDIGIT 0 4 1SHIFT 3 2END8【样例说明】该样例对应于题目描述中给出的示例程序。前2

6、9次生产出来的项链是：4426 4886 6796 8356 0676 4136 6286 6526 4306 0866 6712 2432 4882 2796 8556 0716 6412 2822 4562 2192 2786 6556 0316 6602 0322 4062 2182 4382 2786可以看出，从2786开始机器陷入了循环，因此从2786开始的8条项链将被无限制的生产出来。解题报告初看到题目名称“彩色项链”时，不要误以为是一道考Plya原理或是考图论算法的题目，经过快速地阅读题目，可以初步断定这是一道大数据量的统计问题，需要统计出总共有多少项链将被无限制的生产出来。当仔

7、细阅读题目的细节后，来分析一下样例中的前几条项链的生产过程：步骤指令编号程序指令项链原形START项链新形第一条项链11MUL 3 212340246422SETSTART 2 124646(2)246433ONDIGIT 0 4 124646(2)246444SHIFT 3 -224646(2)4426第二条项链11MUL 3 244260884622SETSTART 2 188464(0)884633ONDIGIT 0 4 188464(0)884644SHIFT 3 288464(0)4886第三条项链11MUL 3 248860976622SETSTART 2 197666(2)976

8、633ONDIGIT 0 4 197666(2)976644SHIFT 3 297666(2)6796进一步分析题意，可以得知我们的工作是模拟一台机器的生产，而机器的生产是与前一次的产品相关的，而且对项链片断的改造涉及到局部位移以及局部乘法两种操作。观察题目中所给出的限制条件，对于SHIFT操作2=L=min(10, N)，1=|x|=L-1，而对于MUL操作1=x=9，1=L460920，这样的空间复杂度是不能承受。因此对于大一些的数据就不能通过。而且随着项链的总数增多，判断项链是否相同的时间复杂度也越来越高，比较项链是否相同的总时间复杂度为O(N*T2)，同样也是不能承受的。因此算法需要改

9、进。算法2首先为了改善空间问题，我们不能将所有项链都一一纪录，那么我们是否有方法能够不纪录之前生产的项链直接判断是否生产出相同的项链呢？这时，我们可以考虑采用Floyd判圈算法，用在本题上，就可以这样考虑：我们有两条生产项链的流水线，一条流水线生产的速度是另一条的两倍，那么如果有某一时刻两条流水线生产出了相同的项链，则我们就可以知道两条流水线已进入或正进入循环的生产。那是否对任何情况都有上述结果呢？证明是非常容易的。假设第一条流水线速度慢，第二条流水线速度快。假设在陷入循环之前总共生产了X条项链，而将有Y条项链将被无限制的生产出来。则我们显然可以找到正整数Z，使得Y|X+Z，这里1=Z=Y，显

10、然当第一条流水线生产第X+Z条项链时，第二条流水线生产第2X+2Z条项链，比第一条流水线多生产X+Z条，由于Y|X+Z，因此两条流水线生产的项链相同。这样我们已经能够确定有一条项链将被无限制的生产出来，则我们只需要以这条项链为标准，经过Y次生产将又生产出了相同的项链，则我们就可以确定将被无限制生产出来的项链数为Y。算法2的空间复杂度为O(2N)，显然已经不存在空间上的问题了。虽然我们在模拟生产上多付出了一定的代价，算法1只需模拟生产X+Y+1条项链，而现在需要模拟3(X+Z)+Y=3X+4Y条项链，最坏情况下模拟量为算法1的四倍，但是算法2中比较项链是否相同的次数却大大减少，我们降低了时间复杂

11、度的阶，算法2中比较项链是否相同的时间复杂度为O(N*(X+Z+Y)=O(N*(T+Z)1 then/若乘1则不需要做改动 begin u:=0;/进位标志 for i:=l-1 downto 0 do/分别计算每一位 begin j:=(i+start) mod n;/计算当前珠子的编号 u:=u+productid.beadj*x;/计算每一位的乘积 inc(productid.hash,(u mod 10-productid.beadj)*(j+1);/修改hash函数值 productid.beadj:=u mod 10;/改造第j颗珠子的颜色 u:=u div 10;/进位 end;

12、 end; inc(cmd_count);/设置为下一条语句 end; procedure ondigit(x,y,z:longint); /执行ONDIGIT操作 begin if productid.beadx=y then/符合条件则转向第z条语句 cmd_count:=z else/否则执行下一条语句 inc(cmd_count); end; begin/模拟的过程 cmd_count:=1;/设置为第一条语句 start:=0;/START清零 while cmd_countm do/若程序为结束 with progcmd_count do/开域语句 case cmdtype of/

13、分情况执行操作 1:setstart(data1,data2); 2:shift(data1,data2); 3:mul(data1,data2); 4:ondigit(data1,data2,data3); end; end; function compare(id1,id2:integer):boolean;/比较两条项链是否相同 var i:longint; begin if productid1.hashproductid2.hash then/先比较两者的hash函数 begin compare:=false;/两项链不同 exit; end; for i:=0 to n-1 do/

14、逐一比较每颗珠子的颜色 if productid1.beadiproductid2.beadi then begin compare:=false;/两项链不同 exit; end; compare:=true;/两项链相同 end; begin/算法主过程 s:=0; repeat/两条进度不同的流水线 inc(s);/生产次数加1 produce(1);/第一条流水线生产一次 produce(2);/第二条流水线 produce(2);/生产两次 until compare(1,2);/若某次两流水线生产出的项链相同 ans:=0;/循环节长度清零 repeat produce(1);/第一条流水线生产一次 inc(ans);/循环节长度加1 if s mod ans0 then continue;/若不可能是循环节则无需比较 until compare(1,2);/以第二条流水线生产的最后一条项链为标志/比较是否已陷入循环 end;procedur