Rabbit的字符串题解

题目大意：
给你一个串，问你这个串现在的顺序是不是不是最小表示法的串

做法：
一开始打算暴力，但是仔细想想，发现，暴力很可能卡成 $O(n^2)$ ,导致凉凉。【比如给一个长度为n的串里面的每个字母都一样】

一般来说，这道题应该属于字符串类型，需要使用字符串算法。

但是！

作为一个菜鸡，怎么会打字符串算法呢？/x
所以，这里就用上了我之前yy出来的一个算法：分块求字符串区间

how？
我们知道，c++提供了一个变量:string，它支持对string，char的'+'操作，而且复杂度是O(1)的，所以，我们可以按分块的思想，开 $\sqrt{n}$ 个string数组，每个数组存的是第i个块中的所有字符形成的字符串。
这样，如果我们要搞出区间为[l,r]的字符串，我们就可以先判断下，假设两个点所属的块相同或相邻，我们暴力合并出串，否则，我们先对左边块暴力合并，中间块直接调用数组合并，再暴力合并右边块，就用 $O(\sqrt{n})$ 的时间合并出了我们想要的块，而且，不难证明，该方法空间复杂度也是优秀的 $O(n)$

代码

#include<bits/stdc++.h>
using namespace std;
const int N=318,M=1e5+1;
string s[N];int b[M];
string x;int n,block;
inline string get_string(int l,int r){
    string res="";
    if(b[r]-b[l]<=1){
        for(int i=l;i<=r;++i){
            res+=x[i-1];
        }
        return res;
    }
    for(int i=l;i<=(b[l]*block);++i){
        res+=x[i-1];
    }
    for(int i=b[l]+1;i<b[r];++i){
        res+=s[i];
    }
    for(int i=(b[r]-1)*block+1;i<=r;++i){
        res+=x[i-1];
    }
    return res;

}
int main(){
    //最小表示法?NO！分块拼表?先试试卡时优化~哈哈
    scanf("%d",&n);
    block=sqrt(n);
    cin>>x;
    for(int i=1;i<=n;++i){
        b[i]=(i-1)/block+1;
        s[b[i]]+=x[i-1];
    }
    for(int i=2;i<=n;++i){//以i为开头
        if(x[i-1]<x[0]){
            puts("YES");
            return 0;
        }
        if(x[i-1]>x[0]){
            continue;
        }
        string y=get_string(i,n)+get_string(1,i-1);
        if(y<x){
            puts("YES");
            return 0;
        }
    }
    puts("NO");
    return 0;
}

Rabbit的字符串 题解

Rabbit的字符串题解