《罚抄一百遍》题目分析

经过分析可以发现每行的开头或者是一个单词，或者是一个空格。设文本中的单词数是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)的。不过这题细节很多，不容易写对。

asked 2018-01-20

0

updae77 · Answer 1

0

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

2018-03-13

0

updae77 · Answer 2

0

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

2018-03-11

0

hnyzdxyz · Answer 3

1

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

2018-01-24

0

- xiaoniaomeimao
- 2018-01-24
行号可能会整形溢出
- chenbb
- 2018-01-24
https://github.com/LightningBilly/ACMAlgorithms/tree/master/hihocoder/1355-%E7%BD%9A%E6%8A%84%E4%B8%80%E7%99%BE%E9%81%8D 详解，
- chenbb
- 2018-01-24
这几组测试一下 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
- hnyzdxyz
- 2018-01-27
错误找到了。没考虑空格占一行的情况。老哥样例不错，谢谢了
- updae77
- 2018-03-16
所有数据都对了，但还是wa。。。
添加评论
✖reply