首页 > 代码库 > bzoj1692

bzoj1692

2024-09-20 12:37:24   215人阅读

http://www.lydsy.com/JudgeOnline/problem.php?id=1692

这道题还是双倍经验。。。

这道题只用到了sa。首先有一个弱化版的题目：1640，n<=2000。我们有个贪心的策略：每次从两端取，取字典序较小的，但是当两端的字符相等，那么我们需要一些其他的依据。如果我们把这两个相同的字符去掉，看下一个字符，取比较小的是最优的，那么也就是说当两个字符相等的时候，我们比较下一个，那么这不就是字典序的比较吗？也就是比较两端字符到各自结尾的字典序的大小。那么我们可以暴力比较，也可以用后缀数组。但是我们要比较两端的字典序，那么我们把这个串加一个无关的字符，然后倒过来复制一遍，然后用两个指针指向1

和n+2，每次比较字典序，取较小的并向后移。但是这里有一个问题：中间那个字符会不会影响比较？当然不会，因为如果两个串受到这个字符的影响，说明他们之前是完全相同的，那么也就是说从两边取是一样的，自然就没关系了。

#include<bits/stdc++.h>
using namespace std;
const int N = 60010;
int n, len, k;
char s[N];
int sa[N], temp[N], rank[N];
bool cp(int i, int j) 
{
    if(rank[i] != rank[j]) return rank[i] < rank[j];
    int ri = i + k <= len ? rank[i + k] : -1;
    int rj = j + k <= len ? rank[j + k] : -1;
    return ri < rj;
}
void Sa()
{
    for(int i = 1; i <= len; ++i) sa[i] = i, rank[i] = s[i];
    for(k = 1; k <= len; k <<= 1)
    {
        sort(sa + 1, sa + len + 1, cp);
        temp[sa[1]] = 1;
        for(int i = 2; i <= len; ++i) temp[sa[i]] = temp[sa[i - 1]] + (cp(sa[i - 1], sa[i]));        
        for(int i = 1; i <= len; ++i) rank[i] = temp[i];
    }
}
int main()
{
    scanf("%d", &n); len = n;
    for(int i = 1; i <= n; ++i) 
    {
        char c[1]; scanf("%s", c);
        s[i] = c[0];
    }
    s[++len] = ‘Z‘ + 1;
    for(int i = n; i; --i) s[++len] = s[i];
    Sa();
    int l = 1, r = n + 2;
    for(int i = 1; i <= n; ++i)
    {
        if(rank[l] <= rank[r]) { printf("%c", s[l]); ++l; }
        else { printf("%c", s[r]); ++r; }
        if(i % 80 == 0) puts("");
    }
    return 0;
}

 

bzoj1692


联系
我们