后缀数组

POJ 1743 Musical Theme

Posted on

后缀数组求最长不重叠重复子串的入门题。
论文题。
也是男人八题之一。 想我活了十多年终于成了 \( \dfrac {2} {8}\) 个男人

虽然说是入门题,但也没有那么简单。
说到底,这道题是我第一次将后缀数组应用起来。我意外的发现,后缀数组之所以强大,在于它拆分了所有后缀,然后又构造了 height 数组描述前缀。这就掌握了所有连续子串。
神了!

这里还是说一下我对最长不重叠重复子串求法的理解。
直接求最长不重叠重复子串是困难的,但对于一个确定的长度 len ,我们却可以\( O\left( n \right) \) 地判断其可行性。而这长度又具有单调性,这就使得我们可以用二分的思维去解决它。可行性判断方法如下:

前面说了,sa + height 可以用来描述子串 不是所有。不考虑其它,height 可以单纯的描述为存在的一个公共子串长度。而这个长度大于 len 是我们的必要条件。接下来要判断的就是是否会产生重叠。
sa数组记录的是这个公共子串所对应的后缀起始位置,如果两个后缀它们的起始位置大于等于 len ,毫无疑问,不会重叠。
因此我们只需要在连续的满足 \( height \geq len \) 的 sa 数组中的\( \max(sa) - \min(sa) \geq len \),那么存在长度为 len 的不重叠重复子串。
为什么必须是连续的呢,我们大可以在纸上操作一下,只有连续的 height ,它们两两之间都会存在长度相同的子串。

题意:
给你一串数字,要你找出满足要求的两个字段。要求如下 :

  1. 长度大于等于 \( 5 \)
  2. 两个字段相似。其中相似的定义在于两个字段的每个字符,它与前一字符的差值相同

思路:
首先将输入处理一下,单方向让每一个相邻的字符相减,这样问题才近似转变成一个最长不重复子串的问题。

说近似的原因在于,同一个元素可能会被两个字段所共用。比如原字段 1 2 3 ----> 1 1 ,这时候你判定在转化后的序列中存在长度为 \( 1\)的 不重叠重复子串的话,显然是错的。
不过处理起来也挺简单的

之后就是关于最长不重叠重复子串的算法了。上面已经有陈述了。

AC Code

#include <algorithm>
#include <cstdio>
#include <iostream>

#define each(i, n) for (int(i) = 0; (i) < (n); (i)++)
#define reach(i, n) for (int(i) = n - 1; (i) >= 0; (i)--)
#define range(i, st, en) for (int(i) = (st); (i) <= (en); (i)++)
#define rrange(i, st, en) for (int(i) = (en); (i) >= (st); (i)--)
#define fill(ary, num) memset((ary), (num), sizeof(ary))

using namespace std;

const int inf = 0x3f3f3f3f;
const int maxn = 2e4 + 5;

int sa[maxn];
int t1[maxn], t2[maxn], buc[maxn];
int rnk[maxn], height[maxn];

void buildSA(int s[], int n, int m)
{
    int p, *x = t1, *y = t2;
    each(i, m) buc[i] = 0;
    each(i, n) buc[x[i] = s[i]]++;
    range(i, 1, m - 1) buc[i] += buc[i - 1];
    reach(i, n) sa[--buc[x[i]]] = i;
    for (int k = 1; k <= n; k <<= 1) {
        p = 0;
        range(i, n - k, n - 1) y[p++] = i;
        each(i, n) if (sa[i] >= k) y[p++] = sa[i] - k;
        each(i, m) buc[i] = 0;
        each(i, n) buc[x[i]]++;
        range(i, 1, m - 1) buc[i] += buc[i - 1];
        reach(i, n) sa[--buc[x[y[i]]]] = y[i];
        swap(x, y);
        p = 1, x[sa[0]] = 0;
        range(i, 1, n - 1) x[sa[i]] = y[sa[i - 1]] == y[sa[i]] && y[sa[i - 1] + k] == y[sa[i] + k] ? p - 1 : p++;
        if (p >= n)
            break;
        m = p;
    }
}

void getHeight(int s[], int n)
{
    int j, k = 0;
    each(i, n + 1) rnk[sa[i]] = i;
    each(i, n)
    {
        k ? k-- : 0;
        j = sa[rnk[i] - 1];
        while (s[i + k] == s[j + k])
            k++;
        height[rnk[i]] = k;
    }
}

bool judge(int len, int n)
{
    int mx = -inf, mm = inf;
    for (int i = 2; i <= n; ++i) {
        if (height[i] >= len) {
            mm = min(mm, min(sa[i], sa[i - 1]));
            mx = max(mx, max(sa[i], sa[i - 1]));
            if (mx - mm > len)
                return true;
        } else
            mx = -inf, mm = inf;
    }
    return false;
}

int s[maxn];

int main()
{
    int n;
    while (scanf("%d", &n) != EOF && n) {
        each(i, n) scanf("%d", s + i);
        each(i, n - 1) s[i] = s[i + 1] - s[i] + 88;
        s[--n] = 0;
        buildSA(s, n + 1, 88 * 2);
        getHeight(s, n);
        int l = 0, r = n >> 1, mid;
        while (l <= r) {
            mid = (l + r) >> 1;
            if (judge(mid, n))
                l = mid + 1;
            else
                r = mid - 1;
        }
        printf("%d\n", l > 4 ? l : 0);
    }
    return 0;
}
二分

你真的会二分么

Posted on

这次我敢打包票我是真的 ~~完全~~ 进了一大步了解了二分。

这个内容对在座的各位大佬来说肯定还是很简单的,菜鸡现在才搞懂,个人还是觉得是有里程碑的意义的。

1.元素完全确定的二分查找

这是二分查找的最简单形式,就是你要查找的值确定,且不重复。
这种形式下,只要找到这个值直接返回即可。

int binarySearch(int le, int ri, int val)
{
    int mid;
    while (le <= ri) {
        mid = (le + ri) >> 1;
        if (ary[mid] == val)
            return mid;
        else if (ary[mid] > val)
            ri = mid - 1;
        else
            le = mid + 1;
    }
    return -1;
}

2.给定条件的二分查找

举个栗子,求出某个有序序列中最小的比val大的数,第一个等于val的下标等等……

这种二分查找当我们找到一个满足约束条件的值时,我们就尝试着去扩大这个约束极限,使得它更满足我们的条件。我这里可能表述不清楚,比如 ary[idx] > val ,假设序列递增 , 那么可以尝试让idx向右移动。

而对于初学者来说,可能会有两个很困惑的地方。

2.1 最后的二分的结果究竟 取 l ? r ?

当然如果是浮点数二分的话,直接返回 mid 即可

曾经我拿这个问题去问学长,学长说看情况,所以我拖到了现在。
其实我用一句话概括的话,==就是你最后一个满足条件的 mid ==。

我这里举个栗子,查找某个递增序列中最小的比val大的数。

int binarySearch(int le, int ri, int val)
{
    int mid, rlen = ri + 1;
    while (le <= ri) {
        mid = (le + ri) >> 1;
        if (ary[mid] > val) //此时的ary[mid] 满足约束条件
            ri = mid - 1;
        else
            le = mid + 1;
    }
    return ri == rlen ? -1 : ary[ri + 1]; //若val比ary[0]还小,那么ary[0]是满足要求的。
                                          //但如果数组中不存在比val大的数,就要特判一下。
                                          // mid = ri+1 就是在二分过程中最后一个满足约束条件的 idx
}
2.2 在while循环的时候,\( le \le ri \) 还是 \(le \lt ri\)

首先我们可以确定的是,在浮点数二分的时候,这个等于并不会给我们带来太大影响。
而不管是浮点数还是整型数,加了一个等于都能是我们进一步扩大极限的机会。

哦,说白了,其实这个我也不是很清楚,你只要把 = 加上去肯定是没错的……

这个坑以后回来再填。

二分

我也不是B(倍增二分

Posted on

玲珑杯 Round #13 B题

DESCRIPTION

小 L 有一串 Q 个数排成一排,从左往右是 A1 开始一直到 AQ,它一直很喜欢这串数。

有一天,小 L 去高考报名了,小 J 和小 N 过来用这串数玩游戏。

一开始,小 N 手上有一个空序列,定义变量C:=0
。小 J 从左往右依次把序列中的数取出,放到小 N 手上序列的最右边,如果放完之后,整个序列的混乱度超过了 M,小 N 就会把手上的所有数全部扔掉,然后令 C:=C+1。

定义一个长度为 K,序列的混乱度 S=K∑i=1Bi×Vi,其中 Bi 表示序列中第 i 小的数,V
为一个给定的序列。

小 J 和小 N 想知道,加入每个数之后,C是多少。

题意
很好理解就不说了

思路
说实话这道题拿到手,我只是傻傻的遍历+优先队列做。毫无疑问就 T 了。最后T了4发就滚去睡午觉了。

看了题解竟然是二分!以当前位置对后续位置二分,满足这个区间的混乱度都小于等于 K。

完全没想到二分的辣鸡已经开始颤抖,然而这道题用的却是倍增二分,单纯的二分复杂度还是太高了。

对当前位置 idx ,我枚举 2^n 使得 [idx,idx+2^n]这个区间混乱度大于 K ,再对 [idx+2^(n-1),idx+2^n)
进行二分即可。

说实话,倍增二分我以前真的从未听闻,今天见到也是长了见识。

/* ***********************************************************************
  > File Name: lonlife.cpp
  > Author: Key
  > Mail: keyld777@gmail.com
  > Created Time: Mon 03 Apr 2017 02:34:09 PM CST
 ********************************************************************** */

#include <algorithm>
#include <cmath>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <vector>

using namespace std;
const int inf = 0x3f3f3f3f;
const double eps = 1e-6;
const int maxn = 1000010; //不知道为什么  数组大小调成 3e5+10 会RE 索性增大到 1e6+10

long long a[maxn], v[maxn], ans[maxn], tmp[maxn], n, k;

bool Traversal(int st, int en)
{
    int len = 0;
    for (int i = st; i <= en; i++)
        tmp[++len] = a[i];
    sort(tmp + 1, tmp + len + 1);
    long long tmp_ans = 0;
    for (int i = 1; i <= len; i++) {
        tmp_ans += (tmp[i] * v[i]);
        if (tmp_ans > k)
            return true;
    }
    return false;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int p;

    while (cin >> n >> k) {
        for (int i = 1; i <= n; i++)
            cin >> a[i];
        for (int i = 1; i <= n; i++)
            cin >> v[i];
        int idx = 1, key = 0;
        while (idx <= n) {
            for (p = 1; idx + p <= n; p <<= 1)
                if (Traversal(idx, idx + p))
                    break;
            int l = idx + p / 2, r = idx + p, mid;
            while (l < r) {
                mid = (l + r) >> 1;
                if (Traversal(idx, mid))
                    r = mid;         //因为要维护的是一个  左闭右开区间
                else
                    l = mid + 1;
            }
            for (; idx <= l; idx++) {
                if (idx == l) {
                    ans[idx++] = ++key;
                    break;
                }
                ans[idx] = key;
            }
        }
        for (int i = 1; i < n; i++)
            cout << ans[i] << " ";
        cout << ans[n] << endl;
    }
    return 0;
}

顺便说一点个人对二分的看法:

在一直二分下去不跳出的情况下,并且也是正常标准写法的时候,left,mid与right都是会无限接近的。
当循环条件为left < right 时 最终 left必然与right相等,如果是 left<=right 则最终结果则必然为left+1 = right。

==而mid的最终结果不好判断==

举个例子 如果我在 left < right 的某个最终状态前 left=50 right=51 则 mid=50。 而在之后的条件判断下,有可能会使left=mid+1 则最终结果为 left=right=51 mid=50……

这样说的话,也许我们应该在循环结束后再加个 (left+right)>>1 才能确保mid必定与left与right中的一个相等……

总而言之,(个人觉得),在运用二分算法不中途跳出的情况下,最终结果不必顾及mid,如果顾及并使用,可能会有麻烦。

二分

HDU 4355 Party All the Time

Posted on

暑假集训选拔马上就要开始了

挺虚的,就临时抱一下佛脚

把以前没有写的周练补一下,从最开始补起,也就是二分三分

没想到一下子就A了,说明还是有点长进的,哈哈,可喜可贺,可喜可贺

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define eps 1e-6

using namespace std;

inline double cal(double a,double b)
{
    if(a<0) a=-a;
    return a*a*a*b;
}

int main()
{
    int t;
    scanf("%d",&t);
    for(int k=1;k<=t;k++)
    {
        int n;
        double x[50100],w[50100],l=1000000,r=-1000000,mid,midmid,ans=0;
        scanf("%d",&n);
        for(int i=0;i<n;i++)
        {
            scanf("%lf%lf",&x[i],&w[i]);
            l=min(l,x[i]);
            r=max(r,x[i]);
        }
        while(eps+l<=r)
        {
            mid=(l+r)/2;
            midmid=(l+mid)/2;
            double msum=0,mmsum=0;
            for(int i=0;i<n;i++)
            {
                msum+=cal(mid-x[i],w[i]);
                mmsum+=cal(midmid-x[i],w[i]);
            }
            if(msum+eps<mmsum) l=midmid;
            else r=mid;
            ans=min(msum,mmsum);
        }
        printf("Case #%d: %.0f\n",k,ans);
    }
    return 0;
}