编程杂谈

关于使用伪随机数rand的一些思考

Posted on

本文基于V站上一个大佬的博文,在此之上的一些启发与思考。
在此先对原作者致敬。

前置

基本上的编程语言的rand函数的实现原理是,通过一个算法,得出一个序列,影响序列生成的因素压缩成若干个变量。
换句话说,若作为影响因素的参数不变,rand所得的随机数是固定的。
为了达到我们 “ 随机 ” 的目的,我们将当前时间作为参数,使得序列有一定的随机性。
关于rand函数的实现,wiki上有详细介绍,传送门

错误的使用

假设我们现在的rand函数是完全意义上的随机。我现在要求一个 [ 0,N ) 的随机数。
一般人包括我自己都是这样使用的

srand(time(NULL));
int r = rand()%N;

但实际上存在一个疏忽的地方,因为存在取模,所以 [ 0, RAND_MAX %N ) 被随机到的概率会比 [ RAND_MAX%N , N )多一次。
而我们严格意义上的随机数是均匀分布的,也就是说这是不被我们所允许的。

尝试解决

其实解决方法很简单,问题就只是出在 [ RAND_MAX - RAND_MAX %N , RAND_MAX ] 这一段影响区间,所以我们只要把它去掉就好了。
而将之去掉的可以尝试

  1. 更改RAND_MAX,使得其为 N 的整数倍
  2. 多随机几次,当随机结果不在这个区间的就输出我们的结果。

第一种方法我尝试了一下,貌似不行……,应该是我不会,因为RAND_MAX 被定义在 stdlib.h 头文件中,头文件不允许修改,在当前文件中宏定义显然不能将之覆盖,说加 extern 的麻烦去把 C 学好再说实际上我也试了一下 ,gcc编译选项? 貌似只能添加不能指定吧……
总之第一种方法显示了我对语言了解的短板,我个人解决不了。

对于第二种方法,显然是很好实现的。

srand(time(NULL));
unsigned long long r , limit = RAND_MAX - RAND_MAX %N ;
do {
   r = rand();
} while(r>=limit);
return r / (RAND_MAX / N);

结尾

虽然说这么多,然而实际上并没多大意义,因为rand本身的误差就挺大的……
另一方面,RAND_MAX 本身在我们平时的使用就挺大的,而RAND_MAX越大,区间长度越小,误差就越小。稍微想一下就是对的所以在我们平时的应用上就没有什么感觉。
如果你有一个悠闲的下午去实现了一个rand,可以试试另 RAND_MAX = 3 , 而 N = 2 ,统计一下 0,1的数量,就更显然了。

后缀数组

POJ 3415 Common Substrings

Posted on

后缀数组 + 单调栈好题
网络赛时的后缀数组可以用这个思路解,但是我并不是很会,今天补上。

题意:
给你两个串,问你长度不小于 k 的重复子串的数量。

思路:
若只是对于一个字符串,问它长度不小于 k 的重复子串数量,那么考虑对height根据 k 分组,然后记录一下就可以了,将 height 去重后,每个 height 的贡献为 \( max ( 0, height - k +1 ) \) 个人猜测,后果不计

但这题是两个字符串,我们可以将两个字符串用一个特殊字符连接,并将后缀通过第一个字符串长度区分开来,对于同一个 height 组中,当前的 height 只能跟另一个 height 组相比求 lcp 。
一个可行的方法是,将组内不同的height都记录下来,再对于每一个当前height,我把它跟另一个height组一一求贡献。但是这个复杂度为 \( O ( n^2 ) \),显然是不行的。

最后学到的优化就是单调栈优化了,用 st[i][0]表示栈中第 i 号元素记录时候的height值,st[i][1]表示在这个height值上覆盖了st[i][1]个子串,在栈内维护height递增,实现\( O( 1 ) \) 求贡献。

#include <algorithm>
#include <cstdio>
#include <cstring>

#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;
typedef long long ll;
const int inf = 0x3f3f3f3f;
const double eps = 1e-5;
const int maxn = 2e5 + 5;

struct SuffixArray {
private:
    int len;
    int t1[maxn], t2[maxn], buc[maxn];
    int s[maxn];

    void DA(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 n)
    {
        int j, k = 0;
        each(i, n + 1) rank[sa[i]] = i;
        each(i, n)
        {
            k ? k-- : 0;
            j = sa[rank[i] - 1];
            while (s[i + k] == s[j + k])
                k++;
            height[rank[i]] = k;
        }
    }

public:
    int sa[maxn];
    int rank[maxn], height[maxn];

    void input(char* str)
    {
        len = strlen(str);
        range(i, 0, len) s[i] = str[i];
        DA(len + 1, 130);
        getHeight(len);
    }

    int st[maxn][2];
    void solve(int key, int limit)
    {
        ll tot = 0, top = 0, sum = 0;
        range(i, 1, len) if (height[i] < limit) top = tot = 0;
        else
        {
            int cnt = 0;
            if (sa[i - 1] < key)
                cnt++, tot += height[i] - limit + 1;
            while (top > 0 && height[i] <= st[top - 1][0]) {
                top--;
                tot -= st[top][1] * (st[top][0] - height[i]);
                cnt += st[top][1];
            }
            st[top][0] = height[i];
            st[top++][1] = cnt;
            if (sa[i] > key)
                sum += tot;
        }
        range(i, 1, len) if (height[i] < limit) top = tot = 0;
        else
        {
            int cnt = 0;
            if (sa[i - 1] > key)
                cnt++, tot += height[i] - limit + 1;
            while (top > 0 && height[i] <= st[top - 1][0]) {
                top--;
                tot -= st[top][1] * (st[top][0] - height[i]);
                cnt += st[top][1];
            }
            st[top][0] = height[i];
            st[top++][1] = cnt;
            if (sa[i] < key)
                sum += tot;
        }
        printf("%lld\n", sum);
    }

} suffix_array;

char buf[maxn];

int main()
{
    int k;
    while (scanf("%d", &k) != EOF && k > 0) {
        scanf("%s", buf);
        int len = strlen(buf);
        buf[len] = '$';
        scanf("%s", buf + len + 1);
        suffix_array.input(buf);
        suffix_array.solve(len, k);
    }
    return 0;
}