hiho一下第186周《罚抄一百遍》题目分析

9
0

《罚抄一百遍》题目分析

经过分析可以发现每行的开头或者是一个单词,或者是一个空格。设文本中的单词数是T,则在2T行以内必然出现循环。 例如样例在第8行开始循环:

123456789
Good good
 study   
day day   
up Good  
good     
study day
 day up  
Good good (开始循环)

值得一提的是循环不一定从第1行开始,例如对于M=6是2-7行循环。

123456
Good  
good  
study 
day 
day up
 Good
good  
study 
day 
day up

根据循环节计算最后一个字符的位置,复杂度是O(T)的。不过这题细节很多,不容易写对。

3 answer(s)

1

一直90分,有什么注意的地方吗

  • 行号可能会整形溢出

  • https://github.com/LightningBilly/ACMAlgorithms/tree/master/hihocoder/1355-%E7%BD%9A%E6%8A%84%E4%B8%80%E7%99%BE%E9%81%8D 详解,

  • 这几组测试一下 test cases 1000000001 9 Good good study day day up 1000000000 1000000000 Good good study day day up 2 1000000000 Good good study day day up 1 9 a b c dd ee f g hhhhh 2 9 a b c dd ee f g hhhhh 3 9 a b c dd ee f g hhhhh 1000 1 a 1 5 a b c dd ee f g hhhhh iiiii

  • 错误找到了。没考虑空格占一行的情况。老哥样例不错,谢谢了

  • 所有数据都对了,但还是wa。。。

  • 添加评论
  • reply
0

为什么在2T内一定有解?

0

为什么2T内一定有循环?

write answer 切换为英文 切换为中文


转发分享