POJ1509 Glass Beads
Time Limit: 3000MS | Memory Limit: 10000K | |
Total Submissions: 4314 | Accepted: 2448 |
Description
The necklace should be made of glass beads of different sizes connected to each other but without any thread running through the beads, so that means the beads can be disconnected at any point. The actress chose the succession of beads she wants to have and the IBM promised to make the necklace. But then he realized a problem. The joint between two neighbouring beads is not very robust so it is possible that the necklace will get torn by its own weight. The situation becomes even worse when the necklace is disjoined. Moreover, the point of disconnection is very important. If there are small beads at the beginning, the possibility of tearing is much higher than if there were large beads. IBM wants to test the robustness of a necklace so he needs a program that will be able to determine the worst possible point of disjoining the beads.
The description of the necklace is a string A = a1a2 ... am specifying sizes of the particular beads, where the last character am is considered to precede character a1 in circular fashion.
The disjoint point i is said to be worse than the disjoint point j if and only if the string aiai+1 ... ana1 ... ai-1 is lexicografically smaller than the string ajaj+1 ... ana1 ... aj-1. String a1a2 ... an is lexicografically smaller than the string b1b2 ... bn if and only if there exists an integer i, i <= n, so that aj=bj, for each j, 1 <= j < i and ai < bi
Input
Output
Sample Input
4
helloworld
amandamanda
dontcallmebfu
aaabaaa
Sample Output
10
11
6
5
题解:
显然现在再刷后缀数组 所以就这么去想吧,然后发现贼水 只要复制一边求一遍sa即可?
然后自信满满交了 WA...
看讨论 发现了aaaaaa这一组....显然答案要的是min i
然后后缀排序显然是从后往前的 所以乱搞了个High数组直接扫到一个<=串长一半的就往后扫 直到high[i]!=L(sa[i+1]) 为止
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=;
char S[N];int tmp[N],s[N],n,sa[N],rk[N],k;
bool comp(int i,int j){
if(rk[i]!=rk[j])return rk[i]<rk[j];
int ri=i+k<=n?rk[i+k]:-;
int rj=j+k<=n?rk[j+k]:-;
return ri<rj;
}
void Getsa(){
for(int i=;i<=n;i++){
sa[i]=i;rk[i]=s[i];
}
for(k=;k<=n;k<<=){
sort(sa+,sa+n+,comp);
for(int i=;i<=n;i++)
tmp[sa[i]]=tmp[sa[i-]]+comp(sa[i-],sa[i]);
for(int i=;i<=n;i++)rk[i]=tmp[i];
}
}
int high[N];
void Gethight(){
int h=,j;
for(int i=;i<=n;i++){
j=sa[rk[i]-];
if(h)h--;
for(;i+h<=n && j+h<=n;h++)if(s[i+h]!=s[j+h])break;
high[rk[i]-]=h;
}
}
void work(){
n=;
scanf("%s",S+);
int l=strlen(S+);
for(int i=;i<=l;i++){
s[++n]=S[i]-'a'+;
s[n+l]=S[i]-'a'+;
}
n<<=;
Getsa();
Gethight();
int p;
for(int i=;i<=n;i++){
if(sa[i]<=l){
p=i;
while(sa[p+]<=l && high[p]==n-sa[p]+)p++;
printf("%d\n",sa[p]);
return ;
}
}
}
int main()
{
int T;
scanf("%d",&T);
while(T--)
work();
return ;
}
最新文章
- 用SQL Server(T-SQL)获取连接字符串
- java培训第一天--画板
- windows2003 DHCP中批处理绑定IP与MAC
- 将yyyyMMdd,dd/MM/yyyy 类型字符串转换为datetime 类型 yyyy-MM-dd C#
- Nop源码分析一
- form 表单
- 【springmvc】之常用的注解
- BZOJ 2763: [JLOI2011]飞行路线 spfa dp
- [位运算] [搜索] [递推优化] [计算几何] TEST 2016.7.15
- jquery live()只支持css选择器
- Scala的一些语言特点
- mysql 触发器和存储过程组合使用,实现定时触发操作
- mediawiki在windows下的安装
- Javaweb 第5天 mysql 数据库课程
- 安卓餐厅点餐系统---针对浩然android工作室的一个小白的分析
- mybatis的Mapper文件配置
- Use Multiple log4net Outputs from One Application
- mysql报错1105 -without an explicit primary key with pxc_strict_mode = ENFORCING or MASTER
- Jsp中如何通过Jsp调用Java类中的方法
- linux查询系统负载