首页 > 代码库 > 【NOI题库】9269:Big String超级字符串
【NOI题库】9269:Big String超级字符串
传送门：http://noi.openjudge.cn/ch0207/9269/
//------------------------------------题目内容--------------------------------------
9269:Big String超级字符串
总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制: 131072kB
描述
fish在无数次oi竞赛的狱炼之后，悟出一个真理，往往越容易的题目，陷阱越深。由此，fish创作了这道题目。
fish首先给出两个短串A=’4567’ (4个字符)， B=’123’(3个字符)。反复进行如下的操作得到一个长串C。
（１）C=B+A (例如：A=’4567’ ,B=’123’ C=B+A=’1234567’)
（２）A=B B=C (上述例子 A=’123’ B=’1234567’)
请你编程找出这个长串的第n个字符。
---------
输入
第一行包含一个整数 n (1<=n<=10^9)
---------
输出
仅一行，包含一个字符，表示这个长串的第n个字符。
---------
样例输入
9
样例输出
2
//----------------------------------------解题-----------------------------------------
先来观察一下a,b,c的长度变化：
可以发现嘛，这个字符串的构成只有1，2，3，4，5，6，7这几个字符，
而且4，5，6，7只会属于‘4567’，而1，2，3只会属于‘123’，
然后呢，但操作次数为单数时，字符串【c】末段一定是‘4567’【长度为4】
但操作次数为偶数时，字符串【c】末段一定是‘123’【长度为3】
--------------------------------------------
思路：
可以用递归查找那个要找的那个字符在123或4567中的第几位，找到后输出就可以啦
代码：
1 program chaojizifuchuan; 2 var 3 n,tochange,tcd:longint; 4 //----------------------------------------------------------------------------- 5 function need(t1:longint):longint;//需要进行几步操作 6 var 7 sum,xh,sum2,su:longint; 8 begin 9 xh:=2; //默认需要两步10 sum:=7; //xh-1步的字符串长度11 sum2:=10; //xh步的字符串长度12 while sum2<t1 do //当xh步的字符串长度小于t1时13 begin14 inc(xh); //在增加一步 15 su:=sum2; //备份sum216 sum2:=sum+sum2; //增加sum217 sum:=su; //sum=上一步时的sum2 18 end;19 if t1<=7 then xh:=1; //如果t1小于等于7只需要一步即可20 tochange:=sum2; //tochange用于记录此时xh步的字符串长度【全局变量】21 tcd:=sum; //tcd用于记录此时xh-1步的字符串长度【全局变量】22 exit(xh); //返回xh步23 end;24 //-----------------------------------------------------------------------------25 procedure printf(t2:char);26 begin27 writeln(t2); //输出28 halt; //终止主程序29 end;30 //-----------------------------------------------------------------------------31 procedure try(len:longint);32 var33 bu,total,last:longint;34 c:string;35 begin36 if len<=7 then begin //小于等于7时37 c:=‘1234567‘;38 printf(c[len]);39 end40 else begin //大于7时41 bu:=need(len); //求所需步数42 total:=tochange; //记录bu步时字符串长度43 tochange:=0; //还原tochange44 if odd(bu) then last:=4 45 else last:=3; //如果所需步数为单数就是’4567‘结尾，若是双数就是‘123’结尾46 if len>=total-last then begin //如果在字符串末段47 if last=4 then c:=‘4567‘48 else c:=‘123‘; //last记录的是末段的长度嘛49 printf(c[len-total+last]); //输出50 end51 else begin52 dec(bu); //这个似乎可以删掉QAQ53 total:=tcd; //上一步长度54 tcd:=0; //还原tcd55 try(len-total);//继续try那个lastend到len段【其长度就是len减去上一步的长度】56 end;57 end;58 59 end;60 //-----------------------------------------------------------------------------61 begin62 readln(n); //读入63 try(n); //try64 end.
//中秋快乐QAQ ----于2016.9.15
【NOI题库】9269:Big String超级字符串