| 题目名称 | 3150. [CH 1807]项链 |
|---|---|
| 输入输出 | necklacee.in/out |
| 难度等级 | ★★★ |
| 时间限制 | 500 ms (0.5 s) |
| 内存限制 | 128 MiB |
| 测试数据 | 10 |
| 题目来源 |
 LGLJ
于2019-05-26加入 |
| 开放分组 | 全部用户 |
| 提交状态 | |
| 分类标签 | |
| 分享题解 |
| 通过：12， 提交：23， 通过率：52.17% | ||||
 darkMoon |
100 | 0.025 s | 4.39 MiB | C++ |
 瑆の時間~無盡輪迴·林蔭 |
100 | 0.072 s | 10.17 MiB | C++ |
|
锝镆氪锂铽 |
100 | 0.096 s | 8.74 MiB | C++ |
|
梦那边的美好ET |
100 | 0.136 s | 4.18 MiB | C++ |
|
小金 |
100 | 0.178 s | 4.39 MiB | C++ |
|
yrtiop |
100 | 0.180 s | 4.62 MiB | C++ |
 Oasiz |
100 | 0.185 s | 7.78 MiB | C++ |
 Hale |
100 | 0.237 s | 15.57 MiB | C++ |
 reØreOré |
100 | 0.259 s | 9.16 MiB | C++ |
 LGLJ |
100 | 0.281 s | 8.52 MiB | C++ |
| 关于 项链 的近10条评论(全部评论) | ||||
|---|---|---|---|---|
|
回复 @乐孤廉居 :
好吧，那我只能写O（n）的后缀自动机啦 梦那边的美好ET
2019-05-27 21:24
9楼
| ||||
|
这又不是单一算法题，卡什么？你这是比我卡常开02呀！
梦那边的美好ET
2019-05-27 21:23
8楼
| ||||
|
回复 @梦那边的美好ET :
所以要让大家练习一下模板啊 LGLJ
2019-05-27 21:23
7楼
| ||||
|
回复 @梦那边的美好ET :
介意，已将时限改为500ms LGLJ
2019-05-27 21:21
6楼
| ||||
|
@乐孤廉居 不介意我该一下时限吧，我想这道题不应该卡O(nlogn)算法！
梦那边的美好ET
2019-05-27 21:19
5楼
| ||||
|
回复 @梦那边的美好ET :
黄巨佬好  雷电法王杨永信
2019-05-27 20:42
4楼
| ||||
|
感谢大佬让我学会最小表示法，STO
| ||||
|
学弟们都好强呀，我只能打打50分暴力
梦那边的美好ET
2019-05-27 13:26
2楼
| ||||
|
我不知道什么是最小表示法，去掉输出最小表示这不是KMP裸题吗？
梦那边的美好ET
2019-05-27 13:08
1楼
| ||||
【题目描述】
有一天，FZH大佬绵了一条价值连城宝石项链，但是，一个严重的问题是，他竟然忘记了项链的主人是谁！在得知此事后，很多人向FZH大佬发来了很多邮件，都说项链是自己的，要求他归还（显然其中最多只有一个人说了真话）。 FZH大佬要求每个人都写了一段关于自己项链的描述： 项链上的宝石用数字0至9来标示。一个对于项链的表示就是从项链的某个宝石开始，顺指针绕一圈，沿途记下经过的宝石，比如如下项链： 1-2-3-4 它的可能的四种表示是0123、1230、2301、3012。
FZH大佬现在心急如焚，因为FZH大佬忙着准备AK IOI于是他找到了你，希望你能够编一个程序，判断两个给定的描述是否代表同一个项链（注意，项链是不会翻转的）。。
给定两个项链的表示，判断他们是否可能是一条项链。
【输入格式】
输入文件只有两行，每行一个由0至9组成的字符串，描述一个项链的表示（保证项链的长度是相等的）。
【输出格式】
如果两条项链不可能同构，那么输出’No’，否则的话，第一行输出一个’Yes’，第二行输出该项链的字典序最小的表示。
【样例输入】
2234342423 2423223434
【样例输出】
Yes 2234342423
【提示】
设L = 项链长度， 对于50%的数据L <= 100000； 对于100%的数据L <= 1000000。
【来源】
《算法竞赛进阶指南》