题解

78 条题解

  • 1
    @ 2013-12-08 08:23:09

    注意事件

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

    算法

    最小表示法

  • 0
    @ 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
    @ 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
    @ 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
    @ 2015-12-13 22:32:22

    最小表示法

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

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

  • 0
    @ 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
    @ 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
    @ 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
    @ 2012-09-27 10:47:37

    模版题

  • 0
    @ 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
    @ 2009-10-22 15:14:57

    用最小表示法,详见

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

  • 0
    @ 2009-10-22 08:38:13

    这输入。。。。。

    郁闷。。。。

  • 0
    @ 2009-09-21 21:22:22

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

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

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

  • 0
    @ 2009-09-19 21:32:35

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

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

    传说中最难的水题吗?!!!!

  • 0
    @ 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
    @ 2009-08-12 20:08:29

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

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

  • 0
    @ 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
    @ 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
    @ 2009-08-05 10:55:37

    编译通过...

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

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

    ├ 测试数据 03:答案正确... 25ms

    ├ 测试数据 04:运行超时|无输出...

    ├ 测试数据 05:运行超时|无输出...

    ├ 测试数据 06:运行超时|无输出...

    ├ 测试数据 07:运行超时|无输出...

    ├ 测试数据 08:运行时错误...| 错误号: 216 | 存取非法

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

    ├ 测试数据 10:运行超时|无输出...

  • 0
    @ 2009-08-03 16:10:32

    时限不对啊

信息

ID
1437
难度
7
分类
字符串 | 最小表示法 点击显示
标签
(无)
递交数
858
已通过
170
通过率
20%
上传者