| 比赛场次 | 333 |
|---|---|
| 比赛名称 | NOIP模拟赛by mzx Day2 |
| 比赛状态 | 已结束比赛成绩 |
| 开始时间 | 2016-10-20 18:30:00 |
| 结束时间 | 2016-10-20 22:00:00 |
| 开放分组 | 全部用户 |
| 注释介绍 | 辣鸡mzx模拟赛的Day2 题解：http://pan.baidu.com/s/1mhN6xW8 |
| 题目名称 | 拯救紫萱学姐 |
|---|---|
| 输入输出 | savemzx.in/out |
| 时间限制 | 1000 ms (1 s) |
| 内存限制 | 256 MiB |
| 测试点数 | 10 简单对比 |
| 用户 | 结果 | 时间 | 内存 | 得分 |
|---|---|---|---|---|
 KZNS |
AAAAAAAAAA | 0.122 s | 12.69 MiB | 100 |
 前鬼后鬼的守护 |
AAAAAAAAAA | 0.884 s | 47.04 MiB | 100 |
 Cydiater |
AAAAAAAAAA | 0.950 s | 47.04 MiB | 100 |
 chad |
AAAAAAAAAA | 1.231 s | 60.35 MiB | 100 |
 再见 |
AAAAAAAAAA | 1.345 s | 59.42 MiB | 100 |
 liu_runda |
AAAAAAAAAA | 1.516 s | 49.19 MiB | 100 |
 scpointer |
AAAAAAAAAA | 1.573 s | 107.13 MiB | 100 |
 Marvolo |
AAAAAAAAAA | 1.902 s | 32.74 MiB | 100 |
 FoolMike |
AAAAAAAAAA | 2.005 s | 127.14 MiB | 100 |
 宋逸群 |
AAAWAAAAAA | 0.232 s | 14.87 MiB | 90 |
 派特三石 |
AAWWAAAAAA | 1.462 s | 46.14 MiB | 80 |
 _Itachi |
AAAAAAAWWW | 1.035 s | 11.82 MiB | 70 |
 可以的. |
AAAAAAAWWW | 1.048 s | 32.74 MiB | 70 |
 AntiLeaf |
AAAAAAAWWW | 1.167 s | 116.64 MiB | 70 |
 Respawn |
AAAAAAAWWW | 1.571 s | 39.45 MiB | 70 |
 Sky_miner |
WWAAAAWAAA | 1.779 s | 78.52 MiB | 70 |
 农场主 |
AAAAAWWAWA | 2.060 s | 20.08 MiB | 70 |
 jmisnal |
AAAWAAAWWW | 0.279 s | 16.53 MiB | 60 |
 Rapiz |
AAWWAAAWWW | 1.569 s | 52.62 MiB | 50 |
 Hzoi_Yniverse |
WWAAAAWWWW | 1.042 s | 32.74 MiB | 40 |
 iortheir |
WAWWAWWWWW | 0.351 s | 5.08 MiB | 20 |
 1azyReaper |
WAWWAWWWWW | 0.697 s | 8.90 MiB | 20 |
 cdcq |
WAWWAWWWWW | 0.753 s | 8.78 MiB | 20 |
 旺仔小馒头 |
WAWWWWAEEE | 1.564 s | 1.93 MiB | 20 |
 PorterCass·D·Ace |
WAWWWAWEEE | 2.930 s | 0.37 MiB | 20 |
 assassin |
WAWWWAWEEE | 3.014 s | 0.37 MiB | 20 |
 Theodore |
WAWWWWWWWW | 0.264 s | 0.31 MiB | 10 |
 燕哥到此一游 |
WATTTTTTTT | 8.191 s | 0.15 MiB | 10 |
 やんないち |
C | 0.000 s | 0.00 MiB | 0 |
 Hzoi_chairman |
MMMMMMMMMM | 0.010 s | 0.00 MiB | 0 |
 kito |
WWWWWWWWWW | 0.015 s | 0.29 MiB | 0 |
 mybing |
WWWWWWWWWW | 0.022 s | 0.25 MiB | 0 |
 Zars19 |
WWWWWWWWWW | 0.257 s | 1.14 MiB | 0 |
 Lare |
WWWWEEEEEE | 0.699 s | 0.28 MiB | 0 |
 Ostmbh |
WWWWTTTEEE | 3.435 s | 21.95 MiB | 0 |
 sxysxy |
WWWWWWWTTT | 5.131 s | 230.15 MiB | 0 |
【题目描述】
其实在开考前半个小时题面并不是这样的。
由于明天要考试，同学们要把抽屉里的书都搬空，书很多而且办了走读不能回寝室的学长一眼就看到了回班撩他的学姐，于是就把学姐当学长用♂了：“帮我把这摞书搬走OvO”。
学姐筋疲力尽地抱着沉重的一摞书回到了机房，出于无聊她翻开了学长的字典。
学长的字典由一个字符串组成。对于两个字符串a和b，如果a既是b的前缀也是b的后缀，那么称a和b“相似”，空字符串和任何字符串相似。一个字符串可以通过编辑变换成一个比它短而且与它相似的字符串，付出的代价为这两个字符串的长度之差的平方。两个字符串通过编辑而变为同一个字符串所花费的最小代价被称为最短编辑距离。
给定学长的字典，现在学姐想知道这个字符串的每一对前缀的最短编辑距离中的最大值是多少。请你帮助劳累的紫萱学姐解决这个问题。
【输入格式】
一个字符串，仅包含小写英文字母。
【输出格式】
这个字符串每一对前缀中最长的最短编辑距离。
【样例输入】
abcab
【样例输出】
23
【提示】
最短编辑距离最长的一对前缀是abca和abcab，最短变换过程如下（箭头中的数字为过程的代价）
“abca”-9->“a”-1->“”（空字符串）
“abcab”-9->“ab”-4->“”
对于40%的数据，n≤500。
对于70%的数据，n≤5000。
对于100%的数据，n≤1000000，n为字符串长度。
【来源】
mzx