Page 1 of 6123456

SPOJ 744. Longest Permutation

http://www.spoj.com/problems/LPERMUT/

Brief description:

给出一个序列,求最大的 mx,使得存在一个长度为 mx 的连续子序列,使其恰好为 1..mx 的一个排列。

Analysis:

好题。。。Vijos1381 数据太弱,正解应是 O(n) 。

尽量避免使用数据结构。。。我们需要充分利用排列的性质。。。
区间 [l, r] 恰好是 1..len (len = r-l+1)的排列的充分必要条件是:

  • [l, r] 区间的数两两不同。
  • s[r]-s[l+1] = 1+2+...+len。。。

为了确保区间中的数字两两不同。。。我们设 l[i] 为 i 向左最长可以延伸的距离。。(边界设 l[0] = 0, l[n+1] = n+1。。)
。。那么有 l[i] = max(l[i], p[a[i]]+1)。。。(p[a[i]] 是上一个 a[i] 的位置。。。(也可以用 two point 得到这个东西。。。。

void upd(int l, int r, int len){
    if (len < ans) return;
    if (::l[r] <= l && (s[r]-s[l-1])*2 == (1+len)*len) ans = len;
}

。序列被 1 分割成了一些小的区间。。(不能包含两个相同的 1。。。)。。

____ 1 ____ 1 _________ 1 _____

我们枚举每个 1.。。讨论区间中最大的数字 mx 出现在 1 的左边还是右边。。对称处理。。
。。考虑左边。。

        for (int j=i-1,mx=1;l[i]<=j;--j){
            checkMax(mx, a[j]);
            upd(j,j+mx-1,mx);
        }

由于 upd() 过程是 O(1) 的。。所以整个算法是 O(n) 的。。。

//}/* .................................................................................................................................. */

const int N = int(1e5) + 9;

int a[N], s[N], l[N], p[N], n, ans;

void upd(int l, int r, int len){
    if (len < ans) return;
    if (::l[r] <= l && (s[r]-s[l-1])*2 == (1+len)*len) ans = len;
}

int main(){

#ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);
#endif

    REP_1_C(i, RD(n)) s[i] = s[i-1] + RD(a[i]);

    RST(p); l[0] = 0; REP_1(i, n){
        l[i] = max(l[i-1], p[a[i]]+1); p[a[i]] = i;
        //cout << l[i] << " ";
    }
    l[n+1] = n+1;

    //puts("");

    REP_1(i, n) if (a[i] == 1){

        upd(i, i, 1);

        for (int j=i-1,mx=1;l[i]<=j;--j){
            checkMax(mx, a[j]);
            upd(j,j+mx-1,mx);
        }

        for (int j=i+1,mx=1;l[j]<=i;++j){
            checkMax(mx, a[j]);
            upd(j-mx+1,j,mx);
        }
    }

    OT(ans);
}

SPOJ 7258. Lexicographical Substring Search

http://vjudge.net/problem/viewProblem.action?id=28015

Brief description:

求给定字符串,字典序第 kth 大的子串(重复的算一个)。

Analysis:

算法一:后缀数组
预处理前 i 个后缀能形成多少个不同的子串,之后二分,复杂度 $O(logn)$。
http://vjudge.net/problem/viewSource.action?id=1577464

算法二:后缀自动机
DP 出每个状态出发可以识别多少子串。之后在 SAM 上,逐个字符尝试。
。。。这种方法时间复杂度较差(依赖于子串长度)、想要通过此题需要常数优化和一定运气。。。
http://vjudge.net/problem/viewSource.action?id=2604504

Page 1 of 6123456