HDU 5442 Favorite Donut
Favorite Donut
Time Limit: 1500/1000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 79 Accepted Submission(s): 17
Lulu has a sweet tooth. Her favorite food is ring donut. Everyday she buys a ring donut from the same bakery. A ring donut is consists of n parts. Every part has its own sugariness that can be expressed by a letter from a to z (from low to high), and a ring donut can be expressed by a string whose i-th character represents the sugariness of the i−th part in clockwise order. Note that z is the sweetest, and two parts are equally sweet if they have the same sugariness.
Once Lulu eats a part of the donut, she must continue to eat its uneaten adjacent part until all parts are eaten. Therefore, she has to eat either clockwise or counter-clockwise after her first bite, and there are 2n ways to eat the ring donut of n parts. For example, Lulu has 6 ways to eat a ring donut abc: abc,bca,cab,acb,bac,cba. Lulu likes eating the sweetest part first, so she actually prefer the way of the greatest lexicographic order. If there are two or more lexicographic maxima, then she will prefer the way whose starting part has the minimum index in clockwise order. If two ways start at the same part, then she will prefer eating the donut in clockwise order. Please compute the way to eat the donut she likes most.
Input
First line contain one integer T,T≤20, which means the number of test case.
For each test case, the first line contains one integer n,n≤20000, which represents how many parts the ring donut has. The next line contains a string consisted of n lowercase alphabets representing the ring donut.
Output
You should print one line for each test case, consisted of two integers, which represents the starting point (from 1 to n) and the direction (0 for clockwise and 1 for counterclockwise).
解题:后缀自动机
#include <bits/stdc++.h>
using namespace std;
const int maxn = ;
struct SAM {
struct node {
int son[],f,len;
void init() {
f = -;
len = ;
memset(son,-,sizeof son);
}
} sn[maxn<<];
int tot,last;
void init() {
tot = last = ;
sn[tot++].init();
}
int newnode() {
sn[tot].init();
return tot++;
}
void extend(int c) {
int np = newnode(),p = last;
sn[np].len = sn[last].len + ;
while(p != - && sn[p].son[c] == -) {
sn[p].son[c] = np;
p = sn[p].f;
}
if(p == -) sn[np].f = ;
else {
int q = sn[p].son[c];
if(sn[p].len + == sn[q].len) sn[np].f = q;
else {
int nq = newnode();
sn[nq] = sn[q];
sn[nq].len = sn[p].len + ;
sn[np].f = sn[q].f = nq;
while(p != - && sn[p].son[c] == q) {
sn[p].son[c] = nq;
p = sn[p].f;
}
}
}
last = np;
}
} sam;
char str[maxn];
int fail[maxn];
void getFail(const char *word) {
fail[] = -;
fail[] = ;
for(int i = ,j = -; word[i]; ++i) {
while(j != - && word[i] != word[j]) j = fail[j];
fail[i+] = ++j;
}
}
char text[maxn];
int mymin(int x,int y) {
return x > y?y:x;
}
int mymax(int x,int y) {
return x > y?x:y;
}
int FindIndex(const char *word,int (*f)(int,int),int idx,int len) {
for(int i = , j = ; text[i] ; ++i) {
while(j > - && word[j] != text[i]) j = fail[j];
if(!word[++j]) {
if(i - len + <= len)idx = f(idx,i - len + );
j = fail[j];
}
}
return idx;
}
int main() {
int kase,len;
scanf("%d",&kase);
while(kase--) {
sam.init();
scanf("%d",&len);
scanf("%s",str);
int p = ;
for(int i = ; i < (len<<); ++i)
sam.extend(str[i%len]-'a');
string ss = "",sb = "";
for(int i = ; i < len; ++i) {
for(int j = ; j >= ; --j) {
if(sam.sn[p].son[j] != -) {
p = sam.sn[p].son[j];
ss += char('a' + j);
break;
}
}
}
int clockwise = sam.sn[p].len - len + ;
getFail(ss.c_str());
strcpy(text,str);
strcpy(text + len,str);
clockwise = FindIndex(ss.c_str(),mymin,len*,len);
reverse(str,str + len);
sam.init();
for(int i = p = ; i < (len<<); ++i) {
sam.extend(str[i%len]-'a');
}
for(int i = ; i < len; ++i) {
for(int j = ; j >= ; --j) {
if(sam.sn[p].son[j] != -) {
p = sam.sn[p].son[j];
sb += char('a' + j);
break;
}
}
}
getFail(sb.c_str());
strcpy(text,str);
strcpy(text + len,str);
int anticlockwise = len - FindIndex(sb.c_str(),mymax,,len) + ;
if(ss == sb) {
if(clockwise == anticlockwise) {
printf("%d %d\n",clockwise,);
} else if(clockwise < anticlockwise) {
printf("%d %d\n",clockwise,);
} else printf("%d %d\n",anticlockwise,);
} else if(ss < sb) printf("%d %d\n",anticlockwise,);
else printf("%d %d\n",clockwise,);
}
return ;
}
最新文章
- php中通过DOM操作XML
- Android基础学习第三篇—Intent的用法
- HDU5887 Herbs Gathering(2016青岛网络赛 搜索 剪枝)
- 百度统计接口demo中错误
- html基本的内容
- SQL2005 : 如何在SQL Server Profiler (事件查看器)中 跟踪查看死锁恢复
- 如何为自己的项目在pycharm中设置debug?
- 如何正确读取war包中配置文件的路径
- java 遍历文件夹里的文件
- Careercup - Google面试题 - 5377673471721472
- HDU 2516 (Fabonacci Nim) 取石子游戏
- .NET基础:C#静态构造函数、静态方法、静态属性
- linux shell编程学习笔记(二) --- grep命令
- pd的django To do list 教程------(1)说明与展示
- Android不编译某个模块
- 使用静态基类方案让 ASP.NET Core 实现遵循 HATEOAS Restful Web API
- C# 委托 事件
- Java线程和线程池
- 微信小程序——部署云函数【三】
- python六十课——高阶函数之map