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

Codechef April Challenge 2012. Substrings on a Tree

Brief description:

给定一个 tire,求其中互不相同的子串的个数。之后每次询问,求将 a-z 的优先级重拍后字典序第 kth 大的子串。

Analysis:

广义后缀自动机。注意这个是 12 年的题。。。

修改 Ext() 过程,tail 指针现在需要作为参数传入。。。

    int Ext(int c, int tail){
        int u = tail, uu = new_node(); len[uu] = len[u] + 1;
        while (u && !v) v = uu, u = p;
        if (!u && !v) v = uu, pp = 0;
        else{
            if (len[v] == len[u] + 1) pp = v;
            else{
                int _v = v, vv = new_node(_v); len[vv] = len[u] + 1;
                par[_v] = pp = vv; while (v == _v) v = vv, u = p;
            }
        }
        return uu;
    }

之后。。

    void Init(){

        RD(n, q); RS(s+1); n = strlen(s+1); REP_1(i, n) s[i] -= 'a';

        //RST(hd);
        FOR_C(i, 2, n<<1){
            RD(aa, bb);
            suc[i] = hd[aa], hd[aa] = i++;
            suc[i] = hd[aa], hd[aa] = i;
        }

        tot = 0; queue<int> Q; Q.push(1);
        GtoM[1] = Ext(s[1], new_node());

        while(SZ(Q)){
            int u = Q.front(); Q.pop();
            REP_G(i, u) if (!GtoM[v]){
                GtoM[v] = Ext(s[v], GtoM[u]);
                Q.push(v);
            }
        }
    }

Select 的过程参照 SPOJ SUBLEX 即可。

http://www.codechef.com/viewsolution/4511141

TCO 2B

900.

Brief description:

f(x) = x%m==0 未定义
= x/(x%m), otherwise
求在区间 [l, r] 范围内,对任意的 k>=1, f^k(x) 都有定义的 x 的数目
...

Analysis:

我们设 。。使得答案为 ...
。。考虑递归解决。

这样只需要考虑一次函数的作用。。
。。设 r 为模 m 的余数。。
我们尝试对 r 进行分组。。

不妨考虑 m = 6,

1 7 13 ..
2 8 14 ...
3 9 ..
4 10 ..
5 11 ..

1

Case 1:

若 r = 1 显然都合法。。可以直接计算出来。。。
。。。。更进一步。我们发现.。。对于所有 r ⊥m 互质的情况,做法都是类似的。。。
例如。。观察上面 r = 5:5 11 17 23 29 35 。。。
。。 /m 后变成:1 x x x x 7 x x x x 13 。。。和 r = 1 的情况是一致的。。
。。。。也就是。。对答案的贡献为。。ceil(nn, r)。。(这里的 nn 相当于把 n 压缩下。.。)

(Tips:注意 nn 这里是 #define nn ((n-r)/m+1)
。。。。但是实际。。我们大可以留个标记。。
。。然后继续往下思考。。不必再次就深究 nn 的具体值。。
。。。因为随着程序结构的清晰。。。这些值可能用不到或者代替或被被约去。。。)

Case 2:
。。若 r \not ⊥ m。。。
。。我们以上面的 r = 4 为例吧。。。。

4 10 14 20 26 30 36 ...
->
1 x x 5 x x 9 ....

实际上就是把 n 压缩一下。。然后修改一下步长。。。
因为我们的 f() 还需要添加一个步长 d。。初始为 1。。而上面互质的情况相当于一个边界条件。。d = m。

。。这样就可以了。。。。

。。。这个算法跑的很快。。。但是我不会对其进行分析。。。。
。。。这个题我的做法和当时 SRM 622 900 的思维回路是一样的。。可是这一次我却未能作出。。
。。。。主要是对中间 gcd() 一带的抗性太低了。。。对 pattern 的洞察力不够。。。。
。。。自始至终都没有把 【步长】 这则关键信息归纳出来。。而是在子问题中不停的尝试去修改模数 m。。。
。。甚至都一度想到模线性方程和莫比乌斯反演上面去了。。。。

template<class T> inline T ceil(T x, T y){return (x - 1) / y + 1;}

#define nn ((n-r)/r+1)
#define g __gcd(m,r)

int m; LL f(LL n, int d = 1){
    if (n <= 0) return 0; if (d == m) return ceil(n,(LL)m);
    LL res = 0; int mm = min((LL)m, n+1);
    for (int r=1;r<mm;r+=d) res += f(nn,m/g);
    return res;
}

class AlwaysDefined {
public:
	long long countIntegers(long long L, long long R, int W) {
        m = W; return f(R) - f(L-1);
	}
};