信息学-许智磊necklace解题报告_第1页
信息学-许智磊necklace解题报告_第2页
全文预览已结束

下载本文档

版权说明：本文档由用户提供并上传，收益归属内容提供方，若内容存在侵权，请进行举报或认领

文档简介

WinterCamp2003《Necklace》解题报题 这些珠子依次为0~N-1。而且是在模N的意义下的。也就是说，第kN+i号珠子也就是第i号珠子。0~9之间的任意一种颜色，不妨认为就是将珠子链。注意，尽管珠子的是“循环”的，但是项链却不是，也就0位开始依次比较它们的相同位，而不能转动其中的一条之后再比较。——这实际上就是告诉：不需要考虑循环同构的情况。二次执行程序来产生下一条项链，依此类推，不断地产生下去。可0的值。特别是MUL，由于是做乘法，所以能够非常随机地“打这两条指令都会用到寄存器的值作为起点，所以它们配合规律可循。另外，这样也彻底决定了根本就没有办法知道怎样的项链会被生产无限多次呢？“样例说明”里已经提示（也就是先后生产出两条相同的项链前后两条相同项链之间的所有项链都会被产生无限多次，也就是说，循环节的长度就是需要求得的答案。另外，题目中还告诉最多只会生产出106种不同的项链模拟的操作不是非常繁（当然，这是和很多的模拟题例如Mice相比较比较操作就需要一定的技巧了：因为项链最长可以达到105，所以不可比较判重的方法。判重要非常高效才可以，所以拿Hash表来所有产生过的项链，采用Hash判重。问题就出在这里了：由于在情况下需要产K是搞不定的，因此空间的需求这种方法之处在于：仅仅考虑了时间，而忽视了空间上的等等！无论题目还是的分析中，都并没有要求找到第一个被重复产正是思维定势，诱导走上了一条不归路。这条项链开始不断地产生下去，直到再次产生出项链A，也就求出了答案。问题是怎样确定项链A，一个简单的想法是：由于最多只有106种不同的项链，所以第106条产生的项链必然是处于循环节中的。S=10642生和比较。如果平均地把每步模拟操作的复杂度看作Time1，比较的复杂度看作Time2，则此算法的时间复杂度为O(Time1*(106+R)+(Time1+Time2)*R)，其中R是循环节的长度，也就是答案。显然，在情况下达到，AA开始把环“走”一遍。第二步应该是必不可少的，而且复杂度(Time1+Time2)*R应该也达到了最优，那么之后才找到了项链A，可不可以一些呢？直接改变项链Y。链，并且在环内Y要追上X，因此总共的执行步数规模是O(T-R+U)，其中T是需要产生、比较R次。因此整个算法的复杂度是O((Time1*3+Time2)*(T-R+U)+(Time1+Time2)*R)。显然在情况下达到O((4*Time1+2*Time2)*106)，反而不如解法二，但是注意到：T在很多情况下难以达到106，更重要的是，Y在环内追上X花的步数U在大多数情况下小于RR106。所以这个算法还是非常高效的，对于本题的测试总——要充分挖掘利用——要有——基本如果想要更好地解决此题，需要用到一个竞赛中不常考到的算法—Floyd判圈算

人人文库> 全部分类> 教育资料 > 课件下载

温馨提示

  • 1. 本站所有资源如无特殊说明，都需要本地电脑安装OFFICE2007和PDF阅读器。图纸软件为CAD,CAXA,PROE,UG,SolidWorks等.压缩文件请下载最新的WinRAR软件解压。
  • 2. 本站的文档不包含任何第三方提供的附件图纸等，如果需要附件，请联系上传者。文件的所有权益归上传用户所有。
  • 3. 本站RAR压缩包中若带图纸，网页内容里面会有图纸预览，若没有图纸预览就没有图纸。
  • 4. 未经权益所有人同意不得将文件中的内容挪作商业或盈利用途。
  • 5. 人人文库网仅提供信息存储空间，仅对用户上传内容的表现方式做保护处理，对用户上传分享的文档内容本身不做任何修改或编辑，并不能对任何下载内容负责。
  • 6. 下载文件中如有侵权或不适当内容，请与我们联系，我们立即纠正。
  • 7. 本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。

最新文档

评论

0/150

提交评论