题解 - Vijos

1

yuyilahanbao LV 10 @ 2013-12-08 08:23:09

注意事件

题目所说字符串只有一行，实际上字符串有多行。但是这多行字符串是一个字符串。例如字符串aaaaddddaaacccceeeeee可能输入文件的字符串分了3行表示（如下）。所以输入时要小心一点。 aaaa dddda aacccceeeeee
这道题说什么什么排序的，什么什么之类的，不要信它，否则肯定tle。
题目说所在位置要减1，对于c来说，直接输出就可以了，不解释

算法

最小表示法

0

PowderHan LV 10 @ 2018-09-29 00:19:17

这题有毒
说好的一行
结果输入的字符串可能是多行
如果是10分只有第九个点过了估计就是栽在这里了

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <stack>
#include <cmath>
#include <set>
#include <map>
using namespace std;

char rd;    int pn;
template<typename Type>
inline void read(Type& v)
{
    pn=1;
    while((rd=getchar())<'0'||rd>'9')
        if(rd=='-')
            pn=-1;
    v=rd-'0';
    while((rd=getchar())>='0'&&rd<='9')
        v=v*10+rd-'0';
    v*=pn;
}
template<typename Type>
inline void out(Type v,bool c=1)
{
    if(v==0)
        putchar(48);
    else  
    {
        if(v<0)
        {
            putchar('-');
            v=-v;
        }
        int len=0,dg[20];  
        while(v>0)
        {
            dg[++len]=v%10;
            v/=10;
        }  
        for(int i=len;i>=1;i--)
            putchar(dg[i]+48);  
    }
    if(c)
        putchar('\n');
    else
        putchar(' ');
}

const int MAXN=100005;
char a[MAXN<<1];
int n;

void init()
{
    read(n);
    char ch;
    for(int i=1;i<=n;i++)
    {
        ch=getchar();
        if(ch!='\n')
            a[i]=ch;
        else
            i--;
    }
    for(int i=1;i<=n;i++)
        a[i+n]=a[i];
    a[(n<<1)+1]='\0';
}

void work()
{
    int i=1,j=2;
    while(i<=n&&j<=n)
    {
        int k=0;
        while(k<=n&&a[i+k]==a[j+k])
            k++;
        if(k==n)
        {
            cout<<0<<endl;
            return;
        }
        if(a[i+k]>a[j+k])
        {
            i=i+k+1;
            if(i==j)
                j++;
        }
        else
        {
            j=j+k+1;
            if(i==j)
                i++;
        }
    }
    int ans=min(i,j);
    out(ans-1);
}

int main()
{
    init();
    work();
    return 0;
}

0

starli LV 10 @ 2016-04-23 20:04:42

#include <cstdio>
#include <algorithm>
using namespace std;
struct node{
int fail,l,to[30];
}sam[300010];
int last=1,n,s[100010],tot=1,tmp,p;
char ss[100010];
int newnode(int l){
sam[++tot].l=l;
return tot;
}
void add(int c){
int p=last,np=newnode(sam[p].l+1);
while(p && !sam[p].to[c]) {
sam[p].to[c]=np;
p=sam[p].fail;
}
if(!p) sam[np].fail=1;
else{
int q=sam[p].to[c];
if(sam[q].l== sam[p].l+1) sam[np].fail=q;
else {
int nq=newnode(sam[p].l+1);
for(int i=0;i<26;i++) sam[nq].to[i]=sam[q].to[i];
sam[nq].fail=sam[q].fail;
sam[q].fail=sam[np].fail=nq;
while(p && sam[p].to[c]==q) sam[p].to[c]=nq,p=sam[p].fail;
}
}
last=np;
}
int main(){
freopen("1437.in","r",stdin);freopen("1437.out","w",stdout);
scanf("%d",&n);
for(int i=1;i<=n;i++) {while((s[i]=getchar())<'a'||s[i]>'z');s[i]-='a';}
for(int i=1;i<=n;i++) add(s[i]);for(int i=1;i<=n;i++) add(s[i]);
for(tmp=0,p=1;tmp<=n;tmp++){
for(int i=0;i<=26;i++) if(sam[p].to[i]){p=sam[p].to[i];break;}
}
printf("%d",sam[p].l-n-1);
return 0;
}
后缀自动机上走n次后输出当前位置-n-1

0

xmyjd LV 8 @ 2016-01-17 17:00:54

#include <cstdio>
#include <algorithm>
#include <climits>
using namespace std;
int n, i, j, k, t;
char D[200001];

int main() {
scanf("%d\n", &n);
for (i = 0; i < n; i++)
scanf("%c\n", &D[i]);
i = 0, j = 1;
while (i < n && j < n && k < n) {
t = D[(i + k) % n] - D[(j + k) % n];
if (t == 0)
k++;
else {
if (t < 0)
j += k + 1;
else
i += k + 1;
k = 0;
if (i == j)
j++;
}
}
printf("%d", min(i, j));
return 0;
}

0

308454 LV 10 @ 2015-12-13 22:32:22

最小表示法

注意下楼下yuyilahanbao大牛提醒的，输入的字符串有多行，需要特殊处理下

处理前10分->处理后100分

0

xxxxxxxxyu LV 8 @ 2015-10-04 21:45:24

#include<cstdio>
#include<iostream>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<set>
using namespace std;
map<string,int>yu;
set<string>q;
int main()
{
int n;
cin>>n;string ooo,m;
while(getline(cin,ooo))
{
m=m+ooo;
}

for(int i=0;i<m.length();i++)
{
string ok=m.substr(i,m.length()-i);
string op=m.substr(0,i);
string ll=ok+op;
yu[ll]=i;
q.insert(ll);
}
for(set<string>::iterator it=q.begin();it!=q.end();it++){
cout<<yu[*it];break;
}
return 0;

}

0

juan1973 LV 10 @ 2013-11-08 09:54:11

var
s,s1,p,min:ansistring;
n,i,ans:longint;
begin
readln(n);
while not(eof) do
begin
readln(s1);
s:=s+s1;
end;
s:=s+s;min:='{';
for i:=1 to n do
begin
p:=copy(s,i,n);
if p<min then
begin
min:=p;
ans:=i;
end;
end;
writeln(ans-1);
end.
本来想用数组记录，开0-n-1，这样用mod循环。
但是觉得这会超时，就开了个字符串。
但开始WA了一次。
大家注意！！
数据可能有多行。

0

IGNORE LV 8 @ 2012-10-11 16:23:10

重开之后vijos可能更新了数据，n的上限是十万，朴素的n^2算法在第七个点会超时，此刻膜拜各位神牛及他们提供的最小表示法。这题算是最小表示法的直接应用了吧。

最小表示法网址见下，所给原程序为C++

直接百度最小表示法也可以。

http://wenku.baidu.com/view/185b95d726fff705cc170a7a.html

翻译为pascal见下：

p1:=0;p2:=1;k:=0;

while (p1

0

搞笑了 LV 7 @ 2012-09-27 10:47:37

模版题

0

9362554551 LV 8 @ 2012-08-13 18:35:27

├ 测试数据 01：答案正确... (9ms, 688KB)

├ 测试数据 02：答案正确... (0ms, 876KB)

├ 测试数据 03：答案正确... (21ms, 876KB)

├ 测试数据 04：答案正确... (2056ms, 1920KB)

├ 测试数据 05：答案正确... (2056ms, 1920KB)

├ 测试数据 06：答案正确... (2071ms, 1920KB)

├ 测试数据 07：运行超时... (?, 1920KB)

├ 测试数据 08：答案正确... (181ms, 876KB)

├ 测试数据 09：答案正确... (5ms, 688KB)

├ 测试数据 10：答案正确... (446ms, 876KB)

我kao

这题.....

我交了n次......

真他妈恶心

通过率呀

~~~~(>_

0

0803enjoy LV 8 @ 2009-10-22 15:14:57

用最小表示法，详见

http://epic.32o.cn/article.asp?id=39

0

laz LV 10 @ 2009-10-22 08:38:13

这输入。。。。。

郁闷。。。。

0

start_pop LV 9 @ 2009-09-21 21:22:22

什么破评测机啊，一模一样的程序交了两遍才A。

我还以为我哪里错了，检查的要死，一模一样的程序交上去居然A了。

这评测机也太不负责任了啊！

0

K-Boy LV 10 @ 2009-09-19 21:32:35

好吧.....输入文件不止一行....

要用到eof....然后readln(s1) s:=s+s1.....

传说中最难的水题吗？！！！！

0

Eudaemonia LV 7 @ 2009-08-24 09:07:38

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 9ms

├ 测试数据 05：答案正确... 384ms

├ 测试数据 06：答案正确... 650ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 338ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：1381ms

输入害死人的道理大家都知道...

0

zhh1993 LV 10 @ 2009-08-12 20:08:29

为什么输入会换行啊.....

这题目不是阴人吗.....

0

玛维-影之歌 LV 10 @ 2009-08-11 14:23:58

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 0ms

├ 测试数据 05：答案正确... 0ms

├ 测试数据 06：答案正确... 0ms

├ 测试数据 07：答案正确... 0ms

├ 测试数据 08：答案正确... 0ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 0ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：0ms

最小表示法...瞬秒...

读入要这样读

while not eof do

begin

readln(b);

a:=a+b;

end;

0

junfpc LV 8 @ 2009-08-10 16:57:11

可恶的读入格式......

编译通过...

├ 测试数据 01：答案正确... 0ms

├ 测试数据 02：答案正确... 0ms

├ 测试数据 03：答案正确... 0ms

├ 测试数据 04：答案正确... 1431ms

├ 测试数据 05：答案正确... 1509ms

├ 测试数据 06：答案正确... 1447ms

├ 测试数据 07：答案正确... 4431ms

├ 测试数据 08：答案正确... 134ms

├ 测试数据 09：答案正确... 0ms

├ 测试数据 10：答案正确... 291ms

---|---|---|---|---|---|---|---|-

Accepted 有效得分：100 有效耗时：9243ms

var l,a:longint;

s,min,tmp:ansistring;

begin

readln(l);

s:='';

if l mod 72=0 then

for a:=1 to l div 72 do

begin

readln(tmp);

s:=s+tmp;

end

else

for a:=1 to (l div 72)+1 do

begin

readln(tmp);

s:=s+tmp;

end;

min:=s;

s:=s+s;

for a:=1 to l do

begin

tmp:=copy(s,a,l);

if min>tmp then min:=tmp;

end;

write(pos(min,s)-1);

end.

0

搁浅 LV 9 @ 2009-08-05 10:55:37

0

宇智波带屌 LV 9 @ 2009-08-03 16:10:32

时限不对啊

题解

78 条题解

注意事件

算法

简单的口令

信息

状态

开发

支持

题解

78 条题解

注意事件

算法

简单的口令

信息

状态

开发

支持

还没有账户？

登录