图片 39

省选前模板总计

写在前面

整个项目都托管在了 Github
上:
查找更为方便的版本见:
这一节内容可能会用到的库文件有 Quick,同样在 Github 上可以找到。
善用 Ctrl + F 查找题目。

DATA STRUCTURE

$ LaTeX{} $历史

$LaTeX{}$(/ˈlɑːtɛx/,常被读作/ˈlɑːtɛk/或/ˈleɪtɛk/),文字形式写作LaTeX,是一种基于TEX的排版系统,由美国计算机科学家莱斯利·兰伯特在20世纪80年代初期开发,利用这种格式,即使用户没有排版和程序设计的知识也可以充分发挥由TEX所提供的强大功能,能在几天,甚至几小时内生成很多具有书籍质量的印刷品。对于生成复杂表格和数学公式,这一点表现得尤为突出。因此它非常适用于生成高印刷质量的科技和数学类文档。这个系统同样适用于生成从简单的信件到完整书籍的所有其他种类的文档。

$ LaTeX{} $使用TEX作为它的格式化引擎。

习题&题解

1.数据结构

控制序列

所谓控制序列,是以反斜杠开头,以第一个空格或非字母
的字符结束的一串文字,他们并不被输出,但是他们会影响输出文档的效果。
TeX 对控制序列的大小写是敏感的

部分控制序列还有被方括号[]包括的可选参数。
所谓文档类,即是 TeX
系统预设的(或是用户自定的)一些格式的集合。不同的文档类在输出效果上会有差别。

2.3.1

1.1字符串哈希

为后缀计算一个哈希值,满足(H(i)=H(i+1)x+s[i])(其中(0 leq i < n, H(n) = 0)),例如
[H(4)=s[4]]
[H(3)=s[4]x+s[3]]
一般地,(H(i)=s[n-1]x^{n-1-i}+s[n-2]x^{n-2-i}+…+s[i+1]x+s[i])
对于一段长度为L的子串s[i]~s[i+L-1],定义他的哈希值(Hash(i, L) = H(i)-H(i+L)x^L)。
预处理H和(x^L)。注意到hash值很大,我们把他存在unsigned
long long中,这样就实现了自然溢出,可以大大减小常数。

Markdown中插入$ LaTeX{}$公式

题目

按照 Partition() 方法的轨迹的格式给出该方法是如何切分数组 E A S Y Q U E
S T I O N 的。

1.2树状数组

1.如何插入公式

的数学公式有两种:行中公式和独立公式。行中公式放在文中与其它文字混编,独立公式单独成行。

行中公式可以用如下方法表示:

$ 数学公式 $

独立公式可以用如下方法表示:

$$ 数学公式 $$

自动编号的公式可以用如下方法表示:

若需要手动编号,参见大括号和行标的使用。

begin{equation}
数学公式
end{equation}

例子:

J_alpha(x) = sum_{m=0}^infty frac{(-1)^m}{m! Gamma (m +
alpha + 1)} {left({ frac{x}{2} }right)}^{2m + alpha}

显示:
$$
Jalpha(x) = sum{m=0}^infty frac{(-1)^m}{m! Gamma (m + alpha

  • 1)} {left({ frac{x}{2} }right)}^{2m + alpha}
    $$
    例子:
  1. begin{equation}
  2. E=mc^2
  3. end{equation}

显示:

$$
begin{equation}E=mc^2end{equation}
$$

解答

图片 1

1.2.1普通树状数组

树状数组好写好调,能用树状数组的时候尽量要使用。
树状数组从1开始。

int lowbit(int x) { return x & -x; }
int sum(int x) {
  int ans = 0;
  while (x) {
    ans += bit[x];
    x -= lowbit(x);
  }
  return ans;
}
void add(int i, int x) {
  while (i <= n) {
    bit[i] += x;
    i += lowbit(i);
  }
}

2.如何输入上下标

^表示上标,
_表示下标。如果上下标的内容多于一个字符,要用{}把这些内容括起来当成一个整体。上下标是可以嵌套的,也可以同时使用。

例子:x{yz}=(1+{rm e}x){-2xy^w}

显示: $ x{yz}=(1+{rm e}x){-2xy^w} $

另外,如果要在左右两边都有上下标,可以用sideset命令。

例子:sideset{1_2}{3_4}bigotimes

显示: $ sideset{1_2}{3_4}bigotimes $

2.3.2

1.2.2支援区间修改的树状数组

假设对于区间([a,
b])增加k,令g[i]为加了k以后的数组。
[g[i] = s[i] (i < a)]
[g[i] = s[i] + i*k – k(a-1) (i >=
a 且 i <= b)]
[g[i] = s[i] + b*k – k(a-1) (i >
b)]
所以我们开设两个树状数组。

3.如何输入括号和分隔符

()、[]和|表示自己,{}表示{}。当要显示大号的括号或分隔符时,要用
leftright 命令。

例子:f(x,y,z) = 3y^2z left( 3+frac{7x+5}{1+y^2} right)

显示:$ f(x,y,z) = 3y^2z left( 3+frac{7x+5}{1+y^2} right) $

有时候要用left.或right.进行匹配而不显示本身。

例子:left. frac{{rm d}u}{{rm d}x} right| _{x=0}

显示: $ left. frac{{rm d}u}{{rm d}x} right| _{x=0} $

题目

按照本节中快速排序所示轨迹的格式给出快速排序是如何将数组 E A S Y Q U E S
T I O N 排序的(出于练习的目的,可以忽略开头打乱数组的部分)。

1.2.3二维树状数组

直接扩展就可以了。非常的直观和显然。

//bzoj3132
void change(int id, int x, int y, int val) {
  for (int i = x; i <= n; i += i & -i) {
    for (int j = y; j <= m; j += j & -j) {
      c[id][i][j] += val;
    }
  }
}
int qu(int id, int x, int y) {
  int ans = 0;
  for (int i = x; i > 0; i -= i & -i) {
    for (int j = y; j > 0; j -= j & -j) {
      ans += c[id][i][j];
    }
  }
  return ans;
}

4.如何输入分数

例子:frac{1}{3} 或 1 over 3

显示: $ frac{1}{3} $

解答

图片 2

1.3线段树

5.如何输入开方

例子:sqrt{2} 和 sqrt[n]{3}

显示: $ sqrt{2} $

2.3.3

1.3.1普通线段树

这个线段树版本来自bzoj1798,代表了一种最基础的线段树类型,支持区间修改,多重标记下传等等操作。

//bzoj1798
void build(int k, int l, int r) {
  t[k].l = l;
  t[k].r = r;
  if (r == l) {
    t[k].tag = 1;
    t[k].add = 0;
    scanf("%lld", &t[k].sum);
    t[k].sum %= p;
    return;
  }
  int mid = (l + r) >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
  t[k].sum = (t[k << 1].sum + t[k << 1 | 1].sum) % p;
  t[k].add = 0;
  t[k].tag = 1;
}
void pushdown(int k) {
  if (t[k].add == 0 && t[k].tag == 1)
    return;
  ll ad = t[k].add, tag = t[k].tag;
  ad %= p, tag %= p;
  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
  t[k << 1].tag = (t[k << 1].tag * tag) % p;
  t[k << 1].add = ((t[k << 1].add * tag) % p + ad) % p;
  t[k << 1].sum = (((t[k << 1].sum * tag) % p + (ad * (mid - l + 1) % p)%p)%p) % p;
  t[k << 1 | 1].tag = (t[k << 1 | 1].tag * tag) % p;
  t[k << 1 | 1].add = ((t[k << 1 | 1].add * tag) % p + ad) % p;
  t[k << 1 | 1].sum = (((t[k << 1|1].sum * tag) % p + (ad * (r-mid) % p)%p)%p) % p;
  t[k].add = 0;
  t[k].tag = 1;
  return;
}
void update(int k) { t[k].sum = (t[k << 1].sum%p + t[k << 1 | 1].sum%p) % p; }
void add(int k, int x, int y, ll val) {
  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
  if (x <= l && r <= y) {
    t[k].add = (t[k].add + val) % p;
    t[k].sum = (t[k].sum + (val * (r - l + 1) % p) % p) % p;
    return;
  }
  pushdown(k);
  if (x <= mid)
    add(k << 1, x, y, val);
  if (y > mid)
    add(k << 1 | 1, x, y, val);
  update(k);
}
void mul(int k, int x, int y, ll val) {
  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
  if (x <= l && r <= y) {
    t[k].add = (t[k].add * val) % p;
    t[k].tag = (t[k].tag * val) % p;
    t[k].sum = (t[k].sum * val) % p;
    return;
  }
  pushdown(k);
  if (x <= mid)
    mul(k << 1, x, y, val);
  if (y > mid)
    mul(k << 1 | 1, x, y, val);
  update(k);
}
ll query(int k, int x, int y) {
  int l = t[k].l, r = t[k].r, mid = (l + r) >> 1;
  if (x <= l && r <= y) {
    return t[k].sum%p;
  }
  pushdown(k);
  ll ans = 0;
  if (x <= mid)
    ans = (ans + query(k << 1, x, y)) % p;
  if (y > mid)
    ans = (ans + query(k << 1 | 1, x, y)) % p;
  update(k);
  return ans%p;
}

6.如何输入省略号

数学公式中常见的省略号有两种,ldots表示与文本底线对齐的省略号,cdots表示与文本中线对齐的省略号。

例子:f(x_1,x_2,ldots,x_n) = x_1^2 + x_2^2 + cdots + x_n^2

显示:

$$
f(x1,x2,ldots,x_n) = x1^2 + x2^2 + cdots + x_n^2
$$

题目

对于长度为 N 的数组,在 Quick.sort()
执行时,其最大元素最多会被交换多少次?

1.3.2可持久化线段树

一种可持久化数据结构。
继承一样的节点,只是把修改的重新链接,节省空间。
容易爆空间。
经常与权值线段树和二分答案结合。

int rt[maxn], lc[maxm], rc[maxm], sum[maxm];
void update(int l, int r, int x, int &y, int v) {
  y = ++sz;
  sum[y] = sum[x] + 1;
  if (l == r)
    return;
  lc[y] = lc[x];
  rc[y] = rc[x];
  int mid = (l + r) >> 1;
  if (v <= mid)
    update(l, mid, lc[x], lc[y], v);
  else
    update(mid + 1, r, rc[x], rc[y], v);
}

7.如何输入矢量

例子:vec{a} cdot vec{b}=0

显示:$ vec{a} cdot vec{b}=0 $

例子:overrightarrow{xy} overleftrightarrow{xy}

显示: $ overrightarrow{xy} overleftrightarrow{xy} $

解答

N / 2
在快速排序中,一个元素要被交换,有以下两种情况
1.该元素是枢轴,在切分的最后一步被交换
2.该元素位于枢轴错误的一侧,需要被交换到另一侧去
注意,以上两种情况在一次切分中只会出现一次

首先来看第一种情况,如果一个元素变成了枢轴
那么在之后的切分中该元素会被排除,不存在后续的交换。
因此我们的目标应该是:
最大的元素总是出现在错误的一侧,同时切分的次数尽可能多。

接下来我们来思考如何构造这样的数组
由于我们针对的是最大的元素,因此「错误的一侧」就是枢轴的左侧。
为了使切分的次数尽可能多,我们需要保持最大值移动的距离尽量短。
但如果每次只移动一位的话,下一次切分时最大值就会变成枢轴
例如 4 10 3 5 6,枢轴为 4,交换后数组变为:
4 3 10 5 6
随后 4 和 3 交换
3 4 10 5 6
下一次切分时 10 会变成枢轴,不再参与后续的切分。
因此我们需要让最大值每次移动两个元素。

考虑下面的数组:
2 10 4 1 6 3 8 5 7 9
第一次切分的时候,枢轴为 2,10 和 1 进行交换
数组变为:
2 1 4 10 6 3 8 5 7 9
随后枢轴交换,数组变为:
1 2 4 10 6 3 8 5 7 9
第二次切分,枢轴为 4,10 和 3 进行交换。
1 2 4 3 6 10 8 5 7 9
随后枢轴交换 数组变为:
1 2 3 4 6 10 8 5 7 9
第三次切分,枢轴为 6,10 和 5 交换
1 2 3 4 6 5 8 10 7 9
随后枢轴交换,数组变为:
1 2 3 4 5 6 8 10 7 9
第四次切分,枢轴为 8,10 和 7 交换
1 2 3 4 5 6 8 7 10 9
枢轴交换,数组变为
1 2 3 4 5 6 7 8 10 9
最后一次切分,枢轴为 10,直接交换
1 2 3 4 5 6 7 8 9 10

我们可以总结出要构造这样的数组的模板
a2 max a3 a1
其中 a1 < a2 < a3 < max
max 每轮切分移动两格,总共切分 N/ 2 次。

1.3.3标记永久化

一种奇怪的姿势,又称李超线段树。
给节点打下的标记不进行下传,而是仅仅在需要的时候进行下传,这就是所谓永久化标记。
图片 3

struct line {
  double k, b;
  int id;
  double getf(int x) { return k * x + b; };
};
bool cmp(line a, line b, int x) {
  if (!a.id)
    return 1;
  return a.getf(x) != b.getf(x) ? a.getf(x) < b.getf(x) : a.id < b.id;
}
const int maxn = 50010;
line t[maxn << 2];
line query(int k, int l, int r, int x) {
  if (l == r)
    return t[k];
  int mid = (l + r) >> 1;
  line tmp;
  if (x <= mid)
    tmp = query(k << 1, l, mid, x);
  else
    tmp = query(k << 1 | 1, mid + 1, r, x);
  return cmp(t[k], tmp, x) ? tmp : t[k];
}
void insert(int k, int l, int r, line x) {
  if (!t[k].id)
    t[k] = x;
  if (cmp(t[k], x, l))
    std::swap(t[k], x);
  if (l == r || t[k].k == x.k)
    return;
  int mid = (l + r) >> 1;
  double X = (t[k].b - x.b) / (x.k - t[k].k);
  if (X < l || X > r)
    return;
  if (X <= mid)
    insert(k << 1, l, mid, t[k]), t[k] = x;
  else
    insert(k << 1 | 1, mid + 1, r, x);
}
void Insert(int k, int l, int r, int x, int y, line v) {
  if (x <= l && r <= y) {
    insert(k, l, r, v);
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    Insert(k << 1, l, mid, x, y, v);
  if (y > mid)
    Insert(k << 1 | 1, mid + 1, r, x, y, v);
}

8.如何输入积分

例子:int_0^1 x^2 {rm d}x

显示: $ int_0^1 x^2 {rm d}x $

另请参阅

Number of largest element exchanges for quicksort-Stack
Overflow

1.4 平衡树

9.如何输入极限运算

例子:lim_{n rightarrow +infty} frac{1}{n(n+1)}

显示: $ lim_{n rightarrow +infty} frac{1}{n(n+1)} $

2.3.4

1.4.1 Splay伸展树

图片 4
一种最为常用的BBST。

int ch[maxn][2], fa[maxn];
int size[maxn], data[maxn], sum[maxn], la[maxn], ra[maxn], ma[maxn], cov[maxn],
    a[maxn];
bool rev[maxn];
int n, m, sz, rt;
std::stack<int> st;
void update(int x) {
  if (!x)
    return;
  la[x] = std::max(la[l(x)], sum[l(x)] + data[x] + std::max(0, la[r(x)]));
  ra[x] = std::max(ra[r(x)], sum[r(x)] + data[x] + std::max(0, ra[l(x)]));
  ma[x] = std::max(std::max(ma[l(x)], ma[r(x)]),
                   data[x] + std::max(0, ra[l(x)]) + std::max(0, la[r(x)]));
  sum[x] = sum[l(x)] + sum[r(x)] + data[x];
  size[x] = size[l(x)] + size[r(x)] + 1;
}
void reverse(int x) {
  if (!x)
    return;
  std::swap(ch[x][0], ch[x][1]);
  std::swap(la[x], ra[x]);
  rev[x] ^= 1;
}
void recover(int x, int v) {
  if (!x)
    return;
  data[x] = cov[x] = v;
  sum[x] = size[x] * v;
  la[x] = ra[x] = ma[x] = std::max(v, sum[x]);
}
void pushdown(int x) {
  if (!x)
    return;
  if (rev[x]) {
    reverse(ch[x][0]);
    reverse(ch[x][1]);
    rev[x] = 0;
  }
  if (cov[x] != -inf) {
    recover(ch[x][0], cov[x]);
    recover(ch[x][1], cov[x]);
    cov[x] = -inf;
  }
}
void zig(int x) {
  int y = fa[x], z = fa[y], l = (ch[y][1] == x), r = l ^ 1;
  fa[ch[y][l] = ch[x][r]] = y;
  fa[ch[x][r] = y] = x;
  fa[x] = z;
  if (z)
    ch[z][ch[z][1] == y] = x;
  update(y);
  update(x);
}
void splay(int x, int aim = 0) {
  for (int y; (y = fa[x]) != aim; zig(x))
    if (fa[y] != aim)
      zig((ch[fa[y]][0] == y) == (ch[y][0] == x) ? y : x);
  if (aim == 0)
    rt = x;
  update(x);
}
int pick() {
  if (!st.empty()) {
    int x = st.top();
    st.pop();
    return x;
  } else
    return ++sz;
}
int setup(int x) {
  int t = pick();
  data[t] = a[x];
  cov[t] = -inf;
  rev[t] = false;
  sum[t] = 0;
  la[t] = ra[t] = ma[t] = -inf;
  size[t] = 1;
  return t;
}
int build(int l, int r) {
  int mid = (l + r) >> 1, left = 0, right = 0;
  if (l < mid)
    left = build(l, mid - 1);
  int t = setup(mid);
  if (r > mid)
    right = build(mid + 1, r);
  if (left) {
    ch[t][0] = left, fa[left] = t;
  } else
    size[ch[t][0]] = 0;
  if (right) {
    ch[t][1] = right, fa[right] = t;
  } else
    size[ch[t][1]] = 0;
  update(t);
  return t;
}
int find(int k) {
  int x = rt, ans;
  while (x) {
    pushdown(x);
    if (k == size[ch[x][0]] + 1)
      return ans = x;
    else if (k > size[ch[x][0]] + 1) {
      k -= size[ch[x][0]] + 1;
      x = ch[x][1];
    } else
      x = ch[x][0];
  }
  return -1;
}
void del(int &x) {
  if (!x)
    return;
  st.push(x);
  fa[x] = 0;
  del(ch[x][0]);
  del(ch[x][1]);
  la[x] = ma[x] = ra[x] = -inf;
  x = 0;
}
void print(int x) {
  if (!x)
    return;
  if (ch[x][0])
    print(ch[x][0]);
  std::cout << data[x] << ' ';
  if (ch[x][1])
    print(ch[x][1]);
}

10.如何输入累加、累乘运算

例子:sum_{i=0}^n frac{1}{i^2} 和 prod_{i=0}^n frac{1}{i^2}

显示:

$$
sum{i=0}^n frac{1}{i^2}
$$

$$
prod{i=0}^n frac{1}{i^2}
$$

题目

假如跳过开头打乱数组的操作,
给出六个含有 10 个元素的数组,
使得 Quick.sort() 所需的比较次数达到最坏情况。

1.5树套树

11.如何输入希腊字母

例子:

alpha A beta B gamma Gamma delta Delta epsilon E

varepsilon zeta Z eta H theta Theta vartheta

iota I kappa K lambda Lambda mu M nu N

xi Xi o O pi Pi varpi rho P

varrho sigma Sigma varsigma tau T upsilon Upsilon

phi Phi varphi chi X psi Psi omega Omega

显示:

$$
alpha A beta B gamma Gamma delta Delta epsilon E

varepsilon zeta Z eta H theta Theta vartheta

iota I kappa K lambda Lambda mu M nu N

xi Xi o O pi Pi varpi rho P

varrho sigma Sigma varsigma tau T upsilon Upsilon

phi Phi varphi chi X psi Psi omega Omega
$$

解答

每次只让枢轴变为已排序,这就是最坏情况。
这种时候枢轴是当前子数组的最大值 / 最小值。
由于在我们的实现中总是取子数组的第一个元素作为枢轴。
因此一个已排序的数组可以达到最坏情况,比较次数达到 O(n^ 2)。
如果换作取最后一个元素,最坏情况会变成逆序数组。

我们的实现中如果碰到与枢轴相等的元素也会停止循环,
因此如果数组中有重复的元素会减少比较次数。

例如:

1 2 3 4 5 6 7 8 9 10
2 3 4 5 6 7 8 9 10 11
3 4 5 6 7 8 9 10 11 12
4 5 6 7 8 9 10 11 12 13
5 6 7 8 9 10 11 12 13 14
6 7 8 9 10 11 12 13 14 15

1.5.1 线段树套splay

您需要写一种数据结构(可参考题目标题),来维护一个有序数列,其中需要提供以下操作:

  1. 查询k在区间内的排名
  2. 查询区间内排名为k的值
  3. 修改某一位值上的数值
  4. 查询k在区间内的前驱(前驱定义为小于x,且最大的数)
  5. 查询k在区间内的后继(后继定义为大于x,且最小的数)

    #include
    #include
    #include
    using namespace std;
    const int maxn = 4e6 + 5;
    const int inf = 1e9;
    int ans, n, m, opt, l, r, k, pos, sz, Max;
    int a[maxn], fa[maxn], ch[maxn][2], size[maxn], cnt[maxn], data[maxn], rt[maxn];
    inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch)) {

    if (ch == '-')
      f = -1;
    ch = getchar();
    

    }
    while (isdigit(ch)) {

    x = x * 10 + ch - '0';
    ch = getchar();
    

    }
    return x * f;
    }
    struct Splay {
    void clear(int x) {

    fa[x] = ch[x][0] = ch[x][1] = size[x] = cnt[x] = data[x] = 0;
    

    }
    void update(int x) {

    if (x) {
      size[x] = cnt[x];
      if (ch[x][0])
        size[x] += size[ch[x][0]];
      if (ch[x][1])
        size[x] += size[ch[x][1]];
    }
    

    }
    void zig(int x) {

    int y = fa[x], z = fa[y], l = (ch[y][1] == x), r = l ^ 1;
    fa[ch[y][l] = ch[x][r]] = y;
    fa[ch[x][r] = y] = x;
    fa[x] = z;
    if (z)
      ch[z][ch[z][1] == y] = x;
    update(y);
    update(x);
    

    }
    void splay(int i, int x, int aim = 0) {

    for (int y; (y = fa[x]) != aim; zig(x))
      if (fa[y] != aim)
        zig((ch[fa[y]][0] == y) == (ch[y][0] == x) ? y : x);
    if (aim == 0)
      rt[i] = x;
    

    }
    void insert(int i, int v) {

    int x = rt[i], y = 0;
    if (x == 0) {
      rt[i] = x = ++sz;
      fa[x] = ch[x][0] = ch[x][1] = 0;
      size[x] = cnt[x] = 1;
      data[x] = v;
      return;
    }
    while (1) {
      if (data[x] == v) {
        cnt[x]++;
        update(y);
        splay(i, x);
        return;
      }
      y = x;
      x = ch[x][v > data[x]];
      if (x == 0) {
        ++sz;
        fa[sz] = y;
        ch[sz][0] = ch[sz][1] = 0;
        size[sz] = cnt[sz] = 1;
        data[sz] = v;
        ch[y][v > data[y]] = sz;
        update(y);
        splay(i, sz);
        rt[i] = sz;
        return;
      }
    }
    

    }
    void find(int i, int v) {

    int x = rt[i];
    while (1) {
      if (data[x] == v) {
        splay(i, x);
        return;
      } else
        x = ch[x][v > data[x]];
    }
    

    }
    int pre(int i) {

    int x = ch[rt[i]][0];
    while (ch[x][1])
      x = ch[x][1];
    return x;
    

    }
    int succ(int i) {

    int x = ch[rt[i]][1];
    while (ch[x][0])
      x = ch[x][0];
    return x;
    

    }
    void del(int i) {

    int x = rt[i];
    if (cnt[x] > 1) {
      cnt[x]--;
      return;
    }
    if (!ch[x][0] && !ch[x][1]) {
      clear(rt[i]);
      rt[i] = 0;
      return;
    }
    if (!ch[x][0]) {
      int oldroot = x;
      rt[i] = ch[x][1];
      fa[rt[i]] = 0;
      clear(oldroot);
      return;
    }
    if (!ch[x][1]) {
      int oldroot = x;
      rt[i] = ch[x][0];
      fa[rt[i]] = 0;
      clear(oldroot);
      return;
    }
    int y = pre(i), oldroot = x;
    splay(i, y);
    rt[i] = y;
    ch[rt[i]][1] = ch[oldroot][1];
    fa[ch[oldroot][1]] = rt[i];
    clear(oldroot);
    update(rt[i]);
    return;
    

    }
    int rank(int i, int v) {

    int x = rt[i], ans = 0;
    while (1) {
      if (!x)
        return ans;
      if (data[x] == v)
        return ((ch[x][0]) ? size[ch[x][0]] : 0) + ans;
      else if (data[x] < v) {
        ans += ((ch[x][0]) ? size[ch[x][0]] : 0) + cnt[x];
        x = ch[x][1];
      } else if (data[x] > v) {
        x = ch[x][0];
      }
    }
    

    }
    int find_pre(int i, int v) {

    int x = rt[i];
    while (x) {
      if (data[x] < v) {
        if (ans < data[x])
          ans = data[x];
        x = ch[x][1];
      } else
        x = ch[x][0];
    }
    return ans;
    

    }
    int find_succ(int i, int v) {

    int x = rt[i];
    while (x) {
      if (v < data[x]) {
        if (ans > data[x])
          ans = data[x];
        x = ch[x][0];
      } else
        x = ch[x][1];
    }
    return ans;
    

    }
    } sp;
    void insert(int k, int l, int r, int x, int v) {
    int mid = (l + r) >> 1;
    sp.insert(k, v);
    if (l == r)

    return;
    

    if (x <= mid)

    insert(k << 1, l, mid, x, v);
    

    else

    insert(k << 1 | 1, mid + 1, r, x, v);
    

    }
    void askrank(int k, int l, int r, int x, int y, int val) {
    int mid = (l + r) >> 1;
    if (x <= l && r <= y) {

    ans += sp.rank(k, val);
    return;
    

    }
    if (x <= mid)

    askrank(k << 1, l, mid, x, y, val);
    

    if (mid + 1 <= y)

    askrank(k << 1 | 1, mid + 1, r, x, y, val);
    

    }
    void change(int k, int l, int r, int pos, int val) {
    int mid = (l + r) >> 1;
    sp.find(k, a[pos]);
    sp.del(k);
    sp.insert(k, val);
    if (l == r)

    return;
    

    if (pos <= mid)

    change(k << 1, l, mid, pos, val);
    

    else

    change(k << 1 | 1, mid + 1, r, pos, val);
    

    }
    void askpre(int k, int l, int r, int x, int y, int val) {
    int mid = (l + r) >> 1;
    if (x <= l && r <= y) {

    ans = max(ans, sp.find_pre(k, val));
    return;
    

    }
    if (x <= mid)

    askpre(k << 1, l, mid, x, y, val);
    

    if (mid + 1 <= y)

    askpre(k << 1 | 1, mid + 1, r, x, y, val);
    

    }
    void asksucc(int k, int l, int r, int x, int y, int val) {
    int mid = (l + r) >> 1;
    if (x <= l && r <= y) {

    ans = min(ans, sp.find_succ(k, val));
    return;
    

    }
    if (x <= mid)

    asksucc(k << 1, l, mid, x, y, val);
    

    if (mid + 1 <= y)

    asksucc(k << 1 | 1, mid + 1, r, x, y, val);
    

    }
    int main() {
    #ifdef D
    freopen(“input”, “r”, stdin);
    #endif
    n = read(), m = read();
    for (int i = 1; i <= n; i++)

    a[i] = read(), Max = max(Max, a[i]), insert(1, 1, n, i, a[i]);
    

    for (int i = 1; i <= m; i++) {

    opt = read();
    if (opt == 1) {
      l = read(), r = read(), k = read();
      ans = 0;
      askrank(1, 1, n, l, r, k);
      printf("%dn", ans + 1);
    } else if (opt == 2) {
      l = read(), r = read(), k = read();
      int head = 0, tail = Max + 1;
      while (head != tail) {
        int mid = (head + tail) >> 1;
        ans = 0;
        askrank(1, 1, n, l, r, mid);
        if (ans < k)
          head = mid + 1;
        else
          tail = mid;
      }
      printf("%dn", head - 1);
    } else if (opt == 3) {
      pos = read();
      k = read();
      change(1, 1, n, pos, k);
      a[pos] = k;
      Max = std::max(Max, k);
    } else if (opt == 4) {
      l = read();
      r = read();
      k = read();
      ans = 0;
      askpre(1, 1, n, l, r, k);
      printf("%dn", ans);
    } else if (opt == 5) {
      l = read();
      r = read();
      k = read();
      ans = inf;
      asksucc(1, 1, n, l, r, k);
      printf("%dn", ans);
    }
    

    }

12.如何输入其它特殊字符

若找不到需要的符号,使用来画出想要的符号。

图片 5

img

另请参阅

Analysis of
Quicksort-khanacademy
Worst case for QuickSort – When can it occur?-Stack
Overflow

1.6点分治

void getroot(int x, int fa) {
  size[x] = 1;
  f[x] = 0;
  for (int i = 0; i < G[x].size(); i++) {
    edge &e = G[x][i];
    if (!vis[e.to] && e.to != fa) {
      getroot(e.to, x);
      size[x] += size[e.to];
      f[x] = max(f[x], size[e.to]);
    }
  }
  f[x] = max(f[x], sum - size[x]);
  if (f[x] < f[rt])
    rt = x;
}
void getdeep(int x, int fa) {
  cnt[deep[x]]++;
  for (int i = 0; i < G[x].size(); i++) {
    edge &e = G[x][i];
    if (!vis[e.to] && e.to != fa) {
      deep[e.to] = (deep[x] + e.weigh) % 3;
      getdeep(e.to, x);
    }
  }
}
int cal(int x, int now) {
  cnt[0] = cnt[1] = cnt[2] = 0;
  deep[x] = now;
  getdeep(x, 0);
  return cnt[1] * cnt[2] * 2 + cnt[0] * cnt[0];
}
void work(int x) {
  ans += cal(x, 0); //统计不同子树通过重心的个数
  vis[x] = 1;
#ifndef ONLINE_JUDGE
  printf("In root %d: %dn", rt, ans);
#endif
  for (int i = 0; i < G[x].size(); i++) {
    edge &e = G[x][i];
    if (!vis[e.to]) {
      ans -= cal(e.to, e.weigh); //去除在同一个子树中被重复统计的
      rt = 0;
      sum = size[e.to];
      getroot(e.to, 0);
      work(rt); // Decrease and Conquer
    }
  }
}

(1).关系运算符

±:pm

×:times

÷:div

∣:mid

∤:nmid

⋅:cdot

∘:circ

∗:ast

⨀:bigodot

⨂:bigotimes

⨁:bigoplus

≤:leq

≥:geq

≠:neq

≈:approx

≡:equiv

∑:sum

∏:prod

∐:coprod

2.3.5

1.7树链剖分

void dfs1(int x) {
  vis[x] = size[x] = 1;
  for (int i = 1; i <= 17; i++) {
    if (deep[x] < (1 << i))
      break;
    fa[x][i] = fa[fa[x][i - 1]][i - 1];
  }
  for (int i = head[x]; i; i = e[i].next) {
    if (!vis[e[i].to]) {
      deep[e[i].to] = deep[x] + 1;
      fa[e[i].to][0] = x;
      dfs1(e[i].to);
      size[x] += size[e[i].to];
    }
  }
}
void dfs2(int x, int chain) {
  pl[x] = ++sz;
  que[sz] = x;
  belong[x] = chain;
  int k = 0;
  for (int i = head[x]; i; i = e[i].next)
    if (deep[e[i].to] > deep[x] && size[k] < size[e[i].to])
      k = e[i].to;
  if (!k)
    return;
  dfs2(k, chain);
  for (int i = head[x]; i; i = e[i].next)
    if (e[i].to != k && deep[e[i].to] > deep[x])
      dfs2(e[i].to, e[i].to);
}
void update(int k) {}
void build(int k, int l, int r) {
  t[k].l = l, t[k].r = r, t[k].s = 1, t[k].tag = -1;
  if (l == r) {
    t[k].lc = t[k].rc = value[que[l]];
    return;
  }
  int mid = (l + r) >> 1;
  build(k << 1, l, mid);
  build(k << 1 | 1, mid + 1, r);
  update(k);
}
int lca(int x, int y) {
  if (deep[x] < deep[y])
    std::swap(x, y);
  int t = deep[x] - deep[y];
  for (int i = 0; i <= 17; i++) {
    if (t & (1 << i))
      x = fa[x][i];
  }
  for (int i = 17; i >= 0; i--) {
    if (fa[x][i] != fa[y][i]) {
      x = fa[x][i];
      y = fa[y][i];
    }
  }
  if (x == y)
    return x;
  else
    return fa[x][0];
}
void pushdown(int k) {}
int query(int k, int x, int y) {}//线段树操作
int getcolor(int k, int pos) {}//线段树操作
int solvesum(int x, int f) {
  int sum = 0;
  while (belong[x] != belong[f]) {
    sum += query(1, pl[belong[x]], pl[x]);
    if (getcolor(1, pl[belong[x]]) == getcolor(1, pl[fa[belong[x]][0]]))
      sum--;
    x = fa[belong[x]][0];
  }
  sum += query(1, pl[f], pl[x]);
  return sum;
}
void change(int k, int x, int y, int c) {}//线段树操作
void solvechange(int x, int f, int c) {
  while (belong[x] != belong[f]) {
    change(1, pl[belong[x]], pl[x], c);
    x = fa[belong[x]][0];
  }
  change(1, pl[f], pl[x], c);
}
void solve() {
  dfs1(1);
  dfs2(1, 1);
  build(1, 1, n);
  for (int i = 1; i <= m; i++) {
    char ch[10];
    scanf("%s", ch);
    if (ch[0] == 'Q') {
      int a, b;
      scanf("%d %d", &a, &b);
      int t = lca(a, b);
      printf("%dn", solvesum(a, t) + solvesum(b, t) - 1);
    } else {
      int a, b, c;
      scanf("%d %d %d", &a, &b, &c);
      int t = lca(a, b);
      solvechange(a, t, c);
      solvechange(b, t, c);
    }
  }
}

(2).集合运算符

∅:emptyset

∈:in

∉:notin

⊂:subset

⊃:supset

⊆:subseteq

⊇:supseteq

⋂:bigcap

⋃:bigcup

⋁:bigvee

⋀:bigwedge

⨄:biguplus

⨆:bigsqcup

题目

给出一段代码将已知只有两种主键值的数组排序。

1.8 Link-Cut Tree

对于树上的操作,我们现在已经有了树链剖分可以处理这些问题。然而树链剖分不支持动态维护树上的拓扑结构。所以我们需要Link-Cut
Tree(lct)来解决这种动态树问题。顺带一提的是,动态树也是Tarjan发明的。

首先我们介绍一个概念:Preferred
path(实边),其他的边都是虚边。我们使用splay来实时地维护这条路径。

lct的核心操作是access。access操作可以把虚边变为实边,通过改变splay的拓扑结构来维护实边。

有了这个数据结构,我们依次来考虑两个操作。

对于链接两个节点,我们需要首先把x节点变为他所在树的根节点,然后直接令fa[x]
= y即可。

怎样换根呢?稍微思考一下可以发现,我们直接把从根到他的路径反转即可。

对于第二种操作,我们直接断开拓扑关系即可。

另外实现的时候要注意,splay的根节点的父亲是他的上一个节点。所以zig和splay的写法应该格外注意。

inline bool isroot(int x) { return ch[fa[x]][0] != x && ch[fa[x]][1] != x; }
void pushdown(int k) {
  if (rev[k]) {
    rev[k] = 0;
    rev[ch[k][0]] ^= 1;
    rev[ch[k][1]] ^= 1;
    std::swap(ch[k][0], ch[k][1]);
  }
}
void zig(int x) {
  int y = fa[x], z = fa[y], l = (ch[y][1] == x), r = l ^ 1;
  if (!isroot(y))
    ch[z][ch[z][1] == y] = x;
  fa[ch[y][l] = ch[x][r]] = y;
  fa[ch[x][r] = y] = x;
  fa[x] = z;
}
void splay(int x) {
  stack<int> st;
  st.push(x);
  for (int i = x; !isroot(i); i = fa[i])
    st.push(fa[i]);
  while (!st.empty()) {
    pushdown(st.top());
    st.pop();
  }
  for (int y = fa[x]; !isroot(x); zig(x), y = fa[x])
    if (!isroot(y))
      zig((ch[fa[y]][0] == y) == (ch[y][0] == x) ? y : x);
}
void access(int x) {
  int t = 0;
  while (x) {
    splay(x);
    ch[x][1] = t;
    t = x;
    x = fa[x];
  }
}
void rever(int x) {
  access(x);
  splay(x);
  rev[x] ^= 1;
}
void link(int x, int y) {
  rever(x);
  fa[x] = y;
  splay(x);
}
void cut(int x, int y) {
  rever(x);
  access(y);
  splay(y);
  ch[y][0] = fa[x] = 0;
}
int find(int x) {
  access(x);
  splay(x);
  int y = x;
  while (ch[y][0])
    y = ch[y][0];
  return y;
}

(3).对数运算符

log:log

lg:lg

ln:ln

解答

官方实现:

算法 gif 动图
图片 6

1.9 KMP

对于字符串S的前i个字符构成的子串,既是它的后缀又是它的前缀的字符串中(它本身除外),最长的长度记作next[i]

多用于DP

for (int i = 2; i <= m; i++) {
    while (j > 0 && ch[j + 1] != ch[i])
      j = p[j];
    if (ch[j + 1] == ch[i])
      j++;
    p[i] = j;
  }

(4).三角运算符

30∘:30^circ

30 ∘

sin:sin

sin x

cos:cos

tan:tan

cot:cot

sec:sec

csc:csc

⊥:bot

平 面 A ⊥ 平 面 B

∠:angle

∠ A = 30 ∘

代码
namespace Quick
{
    /// <summary>
    /// 用于将只有两种元素的数组排序。
    /// </summary>
    public class Sort2Distinct : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public Sort2Distinct() { }

        /// <summary>
        /// 对数组 a 进行排序。
        /// </summary>
        /// <typeparam name="T">数组 a 的元素类型。</typeparam>
        /// <param name="a"></param>
        public override void Sort<T>(T[] a)
        {
            int lt = 0, gt = a.Length - 1;
            int i = 0;
            while (i <= gt)
            {
                int cmp = a[i].CompareTo(a[lt]);
                if (cmp < 0)
                    Exch(a, lt++, i++);
                else if (cmp > 0)
                    Exch(a, i, gt--);
                else
                    i++;
            }
        }
    }
}

1.10 AC自动机

KMP在Trie上的扩展.

void insert(char s[101]) {
  int now = 1, c;
  for (int i = 0; i < strlen(s); i++) {
    c = s[i] - 'A' + 1;
    if (a[now][c])
      now = a[now][c];
    else
      now = a[now][c] = ++sz;
  }
  leaf[now] = 1;
}
void ac() {
  std::queue<int> q;
  q.push(1);
  point[1] = 0;
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 1; i <= 26; i++) {
      if (!a[u][i])
        continue;
      int k = point[u];
      while (!a[k][i])
        k = point[k];
      point[a[u][i]] = a[k][i];
      if (leaf[a[k][i]])
        leaf[a[u][i]] = 1;
      q.push(a[u][i]);
    }
  }
}

(5).微积分运算符

′:prime

∫:int∬:iint∭:iiint∬∬:iiiint∮:oint

lim:lim

lim

∞:infty

∇:nabla

另请参阅

Quick

1.11 后缀数组

void getsa(int sa[maxn], int rank[maxn], int Sa[maxn], int Rank[maxn]) {
  for (int i = 1; i <= n; i++)
    v[rank[sa[i]]] = i;
  for (int i = n; i >= 1; i--)
    if (sa[i] > k)
      Sa[v[rank[sa[i] - k]]--] = sa[i] - k;
  for (int i = n - k + 1; i <= n; i++)
    Sa[v[rank[i]]--] = i;
  for (int i = 1; i <= n; i++)
    Rank[Sa[i]] = Rank[Sa[i - 1]] + (rank[Sa[i - 1]] != rank[Sa[i]] ||
                                     rank[Sa[i - 1] + k] != rank[Sa[i] + k]);
}
void getheight(int sa[maxn], int rank[maxn]) {
  int i, k = 0;
  for (i = 1; i <= n; height[rank[i++]] = k) {
    if (k)
      k--;
    int j = sa[rank[i] - 1];
    while (a[i + k] == a[j + k])
      k++;
  }
}
void da() {
  p = 0, q = 1, k = 1;
  for (int i = 1; i <= n; i++)
    v[a[i]]++;
  for (int i = 1; i <= 2; i++)
    v[i] += v[i - 1];
  for (int i = 1; i <= n; i++)
    sa[p][v[a[i]]--] = i;
  for (int i = 1; i <= n; i++)
    rank[p][sa[p][i]] =
        rank[p][sa[p][i - 1]] + (a[sa[p][i - 1]] != a[sa[p][i]]);
  while (k < n) {
    getsa(sa[p], rank[p], sa[q], rank[q]);
    p ^= 1;
    q ^= 1;
    k <<= 1;
  }
  getheight(sa[p], rank[p]);
}

(6).逻辑运算符

∵:because

∴:therefore

∀:forall

∃:exists

≠:not=

≯:not>

⊄:notsubset

2.3.6

1.12 后缀自动机

图片 7

struct Suffix_Automaton {
  ll fa[maxn], trans[maxn][26], len[maxn], right[maxn];
  ll last, root, sz;
  bool flag[maxn];
  void init() {
    memset(flag, 0, sizeof(flag));
    sz = 0;
    last = root = ++sz;
  }
  void insert(ll x) {
    ll p = last, np = last = ++sz;
    len[np] = len[p] + 1;
    flag[np] = 1;
    right[np] = right[p] + 1;
    for (; !trans[p][x]; p = fa[p])
      trans[p][x] = np;
    if (p == 0)
      fa[np] = root;
    else {
      ll q = trans[p][x];
      if (len[q] == len[p] + 1) {
        fa[np] = q;
      } else {
        ll nq = ++sz;
        fa[nq] = fa[q];
        memcpy(trans[nq], trans[q], sizeof(trans[q]));
        len[nq] = len[p] + 1;
        fa[q] = fa[np] = nq;
        for (; trans[p][x] == q; p = fa[p])
          trans[p][x] = nq;
      }
    }
  }
} sam;

(7).戴帽符号

y^:hat{y}

^

xy^:widehat{xy}

x ˆ

yˇ:check{y}

ˇ

y˘:breve{y}

˘

题目

编写一段代码来计算 $ C_N $ 的准确值,
在 $ N=100、1000 $ 和 $10 000 $ 的情况下比较准确值和估计值 $ 2NlnN $
的差距。

1.13 Manacher

void manacher() {
  int mx = 1, id = 1;
  for (int i = n; i; i--)
    str[i * 2] = '#', str[i * 2 - 1] = str[i];
  n <<= 1;
  for (int i = 1; i <= n; i++) {
    p[i] = std::min(p[id * 2 - i], mx - i);
    while (i - p[i] > 0 && str[i - p[i]] == str[i + p[i]]) {
      int al = (i - p[i]) / 2 + 1;
      int ar = (i + p[i] + 1) / 2;
      // printf("%d %dn", al, ar);
      sam.query(al, ar);
      p[i]++;
    }
    if (i + p[i] > mx)
      mx = i + p[i], id = i;
  }
}

(8).连线符号

a+b+c+d:overline{a+b+c+d}

a + b + c +

a+b+c+d:underline{a+b+c+d}

a + b + c +

a+b+c1.0+d2.0:overbrace{a+underbrace{b+c}_{1.0}+d}^{2.0}

a + b + c 1.0 + 2.0

解答

运行结果如下:
图片 8

1.14 分块

随便给一个例题吧.

给定一个数列,您需要支持一下两种操作:1.给[l,r]同加一个数.
2.询问[l,r]中有多少数字大于或等于v.

把数据分为(sqrt
n)一份,那么对于每一个查询,我们都可以把这个查询分为(sqrt n)个区间,修改的时候也是(O(sqrt
n))的级别,所以总的复杂度就是(O(sqrt n log sqrt n))

具体地,对于每一块,我们都存储排序前和排序后的序列,这样我们就解决了这个题。

#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
int n, q, m, block;
const int maxn = 1000001;
int a[maxn], b[maxn], pos[maxn], add[maxn];
using std::sort;
using std::min;
inline int read() {}
inline void reset(int x) {
  int l = (x - 1) * block + 1, r = min(x * block, n);
  for (int i = l; i <= r; i++)
    b[i] = a[i];
  sort(b + l, b + r + 1);
}
inline int find(int x, int v) {
  int l = (x - 1) * block + 1, r = min(x * block, n);
  int last = r;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (b[mid] < v)
      l = mid + 1;
    else
      r = mid - 1;
  }
  return last - l + 1;
}
inline void update(int x, int y, int v) {
  if (pos[x] == pos[y]) {
    for (int i = x; i <= y; i++)
      a[i] = a[i] + v;
  } else {
    for (int i = x; i <= pos[x] * block; i++)
      a[i] = a[i] + v;
    for (int i = (pos[y] - 1) * block + 1; i <= y; i++)
      a[i] = a[i] + v;
  }
  reset(pos[x]);
  reset(pos[y]);
  for (int i = pos[x] + 1; i < pos[y]; i++)
    add[i] += v;
}
inline int query(int x, int y, int v) {
  int sum = 0;
  if (pos[x] == pos[y]) {
    for (int i = x; i <= y; i++)
      if (a[i] + add[pos[i]] >= v)
        sum++;
  } else {
    for (int i = x; i <= pos[x] * block; i++)
      if (a[i] + add[pos[i]] >= v)
        sum++;
    for (int i = (pos[y] - 1) * block + 1; i <= y; i++)
      if (a[i] + add[pos[i]] >= v)
        sum++;
    for (int i = pos[x] + 1; i < pos[y]; i++)
      sum += find(i, v - add[i]);
  }
  return sum;
}
int main() {
#ifndef ONLINE_JUDGE
  freopen("input", "r", stdin);
#endif
  n = read(), q = read();
  if (n >= 500000)
    block = 3676;
  else if (n >= 5000) {
    block = 209;
  } else
    block = int(sqrt(n));
  for (int i = 1; i <= n; i++) {
    a[i] = read();
    pos[i] = (i - 1) / block + 1;
    b[i] = a[i];
  }
  if (n % block)
    m = n / block + 1;
  else
    m = n / block;
  for (int i = 1; i <= m; i++)
    reset(i);
  for (int i = 1; i <= q; i++) {
    char ch[5];
    int x, y, v;
    scanf("%s", ch);
    x = read(), y = read(), v = read();
    if (ch[0] == 'M')
      update(x, y, v);
    else
      printf("%dn", query(x, y, v));
  }
}

(9).箭头符号

↑:uparrow

↓:downarrow

⇑:Uparrow

⇓:Downarrow

→:rightarrow

←:leftarrow

⇒:Rightarrow

⇐:Leftarrow

⟶:longrightarrow

⟵:longleftarrow

⟹:Longrightarrow

⟸:Longleftarrow

代码

新建一个 QuickSortAnalyze 类,在 QuickSort 的基础上添加一个 CompareCount
属性,用于记录比较次数。重写 Less 方法,每调用一次就让 CompareCount 增加
1 。

using System;
using System.Diagnostics;

namespace Quick
{
    /// <summary>
    /// 自动记录比较次数以及子数组数量的快速排序类。
    /// </summary>
    public class QuickSortAnalyze : BaseSort
    {
        /// <summary>
        /// 比较次数。
        /// </summary>
        public int CompareCount { get; set; }

        /// <summary>
        /// 是否启用打乱。
        /// </summary>
        public bool NeedShuffle { get; set; }

        /// <summary>
        /// 是否显示轨迹。
        /// </summary>
        public bool NeedPath { get; set; }

        /// <summary>
        /// 大小为 0 的子数组数量。
        /// </summary>
        public int Array0Num { get; set; }

        /// <summary>
        /// 大小为 1 的子数组数量。
        /// </summary>
        public int Array1Num { get; set; }

        /// <summary>
        /// 大小为 2 的子数组数量。
        /// </summary>
        public int Array2Num { get; set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortAnalyze()
        {
            this.CompareCount = 0;
            this.NeedShuffle = true;
            this.NeedPath = false;
            this.Array0Num = 0;
            this.Array1Num = 0;
            this.Array2Num = 0;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            this.Array0Num = 0;
            this.Array1Num = 0;
            this.Array2Num = 0;
            this.CompareCount = 0;
            if (this.NeedShuffle)
                Shuffle(a);
            if (this.NeedPath)
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write("  ");
                }
                Console.WriteLine("tlotjthi");
            }
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        private void Sort<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            if (hi - lo == 1)
                this.Array2Num++;
            else if (hi == lo)
                this.Array1Num++;
            else if (hi < lo)
                this.Array0Num++;

            if (hi <= lo)                   // 别越界
                return;
            int j = Partition(a, lo, hi);
            if (this.NeedPath)
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write(a[i] + " ");
                }
                Console.WriteLine("t" + lo + "t" + j + "t" + hi);
            }
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }

        /// <summary>
        /// 比较第一个元素是否小于第二个元素。
        /// </summary>
        /// <typeparam name="T">要比较的元素类型。</typeparam>
        /// <param name="a">第一个元素。</param>
        /// <param name="b">第二个元素。</param>
        /// <returns></returns>
        new protected bool Less<T>(T a, T b) where T : IComparable<T>
        {
            this.CompareCount++;
            return a.CompareTo(b) < 0;
        }
    }
}

主方法

using System;
using Quick;

namespace _2._3._6
{
    /*
     * 2.3.6
     * 
     * 编写一段代码来计算 C_N 的准确值,
     * 在 N=100、1000 和 10 000 的情况下比较准确值和估计值 2NlnN 的差距。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("Nt准确值t估计值t比值");
            QuickSortAnalyze sort = new QuickSortAnalyze();
            int N = 100;
            int trialTime = 500;
            for (int i = 0; i < 3; i++)
            {
                int sumOfCompare = 0;
                int[] a = new int[N];
                for (int j = 0; j < trialTime; j++)
                {
                    for (int k = 0; k < N; k++)
                    {
                        a[k] = k;
                    }
                    SortCompare.Shuffle(a);
                    sort.Sort(a);
                    sumOfCompare += sort.CompareCount;
                }
                int averageCompare = sumOfCompare / trialTime;
                double estimatedCompare = 2 * N * Math.Log(N);
                Console.WriteLine(N + "t" + averageCompare + "t" + (int)estimatedCompare + "t" + averageCompare / estimatedCompare);
                N *= 10;
            }
        }
    }
}

1.15 莫队算法

如果你知道了[L,R]的答案。你可以在O(1)的时间下得到[L,R-1]和[L,R+1]和[L-1,R]和[L+1,R]的答案的话。就可以使用莫队算法。
对于莫队算法我感觉就是暴力。只是预先知道了所有的询问。可以合理的组织计算每个询问的顺序以此来降低复杂度。要知道我们算完[L,R]的答案后现在要算[L’,R’]的答案。由于可以在O(1)的时间下得到[L,R-1]和[L,R+1]和[L-1,R]和[L+1,R]的答案.所以计算[L’,R’]的答案花的时间为|L-L’|+|R-R’|。如果把询问[L,R]看做平面上的点a(L,R).询问[L’,R’]看做点b(L’,R’)的话。那么时间开销就为两点的曼哈顿距离。所以对于每个询问看做一个点。我们要按一定顺序计算每个值。那开销就为曼哈顿距离的和。要计算到每个点。那么路径至少是一棵树。所以问题就变成了求二维平面的最小曼哈顿距离生成树。
关于二维平面最小曼哈顿距离生成树。感兴趣的可以参考胡泽聪大佬的这篇文章

这样只要顺着树边计算一次就ok了。可以证明时间复杂度为(O(n∗sqrt n)).

但是这种方法编程复杂度稍微高了一点。所以有一个比较优雅的替代品。那就是先对序列分块。然后对于所有询问按照L所在块的大小排序。如果一样再按照R排序。然后按照排序后的顺序计算。为什么这样计算就可以降低复杂度呢。

一、i与i+1在同一块内,r单调递增,所以r是O(n)的。由于有n^0.5块,所以这一部分时间复杂度是n^1.5。
二、i与i+1跨越一块,r最多变化n,由于有n^0.5块,所以这一部分时间复杂度是n^1.5
三、i与i+1在同一块内时变化不超过n^0.5,跨越一块也不会超过2*n^0.5,不妨看作是n^0.5。由于有n个数,所以时间复杂度是n^1.5
于是就变成了Θ(n1.5)

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
const int maxn = 50010;
#define ll long long
ll num[maxn], up[maxn], dw[maxn], ans, aa, bb, cc;
int col[maxn], pos[maxn];
struct qnode {
  int l, r, id;
} qu[maxn];
bool cmp(qnode a, qnode b) {
  if (pos[a.l] == pos[b.l])
    return a.r < b.r;
  else
    return pos[a.l] < pos[b.l];
}
ll gcd(ll x, ll y) {
  ll tp;
  while ((tp = x % y)) {
    x = y;
    y = tp;
  }
  return y;
}
void update(int x, int d) {
  ans -= num[col[x]] * num[col[x]];
  num[col[x]] += d;
  ans += num[col[x]] * num[col[x]];
}
int main() {
  int n, m, bk, pl, pr, id;
#ifndef ONLINE_JUDGE
  freopen("input", "r", stdin);
#endif
  scanf("%d %d", &n, &m);
  memset(num, 0, sizeof(num));
  bk = ceil(sqrt(1.0 * n));
  for (int i = 1; i <= n; i++) {
    scanf("%d", &col[i]);
    pos[i] = (i - 1) / bk;
  }
  for (int i = 0; i < m; i++) {
    scanf("%d %d", &qu[i].l, &qu[i].r);
    qu[i].id = i;
  }
  std::sort(qu, qu + m, cmp);
  pl = 1, pr = 0;
  ans = 0;
  for (int i = 0; i < m; i++) {
    id = qu[i].id;
    if (qu[i].l == qu[i].r) {
      up[id] = 0, dw[id] = 1;
      continue;
    }
    if (pr < qu[i].r) {
      for (int j = pr + 1; j <= qu[i].r; j++)
        update(j, 1);
    } else {
      for (int j = pr; j > qu[i].r; j--)
        update(j, -1);
    }
    pr = qu[i].r;
    if (pl < qu[i].l) {
      for (int j = pl; j < qu[i].l; j++)
        update(j, -1);
    } else {
      for (int j = pl - 1; j >= qu[i].l; j--)
        update(j, 1);
    }
    pl = qu[i].l;
    aa = ans - qu[i].r + qu[i].l - 1;
    bb = (ll)(qu[i].r - qu[i].l + 1) * (qu[i].r - qu[i].l);
    cc = gcd(aa, bb);
    aa /= cc, bb /= cc;
    up[id] = aa, dw[id] = bb;
  }
  for (int i = 0; i < m; i++)
    printf("%lld/%lldn", up[i], dw[i]);
}

### 1.16 整体二分&CDQ分治

13.如何进行字体转换

要对公式的某一部分字符进行字体转换,可以用{rm
需转换的部分字符}命令,其中rm可以参照下表选择合适的字体。一般情况下,公式默认为意大利体
a m p l e

项目 说明 示例 项目 说明 示例
rm 罗马体 it 意大利体
bf 粗体 cal 花体
Bbb 黑板粗体 sf 等线体
mit 数学斜体 tt 打字机体
scr 手写体 frak 旧德式字体
另请参阅

Quick

GRAPHIC

14.大括号和行标的使用

使用 leftright 来创建自动匹配高度的 (圆括号),[方括号] 和
{花括号} 。

在每个公式末尾前使用 tag{行标} 来实现行标。

例子:

  1. $$
  2. fleft(
  3. left[
  4. frac{
  5. 1+left{x,yright}
  6. }{
  7. left(
  8. frac{x}{y}+frac{y}{x}
  9. right)
  10. left(u+1right)
  11. }+a
  12. right]^{3/2}
  13. right)
  14. tag{行标}
  15. $$

显示:

1 + { x , } ( + ) ( u + 1 ) + a 3 / 2 ( 行 标 )

2.3.7

2.图论

15.其它命令

题目

在使用快速排序将 N 个不重复的元素排序时,
计算大小为 0、1 和 2 的子数组的数量。如果你喜欢数学,请推导;
如果你不喜欢,请做一些实验并提出猜想。

2.1图的连通性

(1).定义新的符号 operatorname

例子:

  1. $$ operatorname{Sample} A $$

显示:

Sample A

解答

我讨厌数学= =

证明:
我们设 $ C_0(n) $ 代表将 $ n $ 个不重复元素排序时大小为 0
的数组的数量。
同理有 $ C_1(n) $ 和 $ C_2(n) $ 代表大小为 1 的数组的数量以及大小为 2
的数组的数量。
设 k 代表切分位置,显然切分位置随机且概率相等,在 1~n 之间均匀分布。
根据条件,$ C_0(n), C_1(n),C_2(n) $ 都满足下式:
[ C(n)=
frac{sum_{k=1}^{n}(C(k-1)+C(n-k))}{n} ]
根据快速排序算法, $ sum_{k=1}^{n}C(k-1)=sum_{k=1}^{n}C(n-k) $
,因此
[
C(n)=frac{2sum_{k=1}^{n}C(k-1)}{n}\
nC(n)=2sum_{k-1}^{n}C(k-1) ]
同理代入 $ n-1 $ 有
[ (n-1)C(n-1)=2sum_{k-1}^{n-1}C(k-1)
]
相减
[ nC(n)-(n-1)C(n-1)=2C(n-1)\
C(n)=frac{n+1}{n}C(n-1) ]
利用累乘法求到通项公式
[ frac{C(n)}{C(n-1)}=frac{n+1}{n} \
frac{C(n)}{C(n-1)}timesfrac{C(n-1)}{C(n-2)}timesdotstimesfrac{C(m+1)}{C(m)}=
frac{n+1}{n}timesfrac{n}{n-1}timesdotstimesfrac{m+2}{m+1}\
frac{C(n)}{C(m)}=frac{n+1}{m+1}\
C(n)=C(m)frac{n+1}{m+1},n>m ]
对于 $ C_0(n) $ ,我们有初始条件 $ C_0(0)=1,
C_0(1)=0,C_0(2)=C_0(0)+C_0(1)=1 $
[ C_0(n)=frac{n+1}{3}, n>2
]
对于 $ C_1(n) $ ,我们有初始条件 $
C_1(0)=0,C_1(1)=1,C_1(2)=C_1(0)+C_1(1)=1 $
[ C_1(n)=frac{n+1}{3},n>2
]
对于 $ C_2(n) $ ,我们有初始条件 $
C_2(0)=C_2(1)=0,C_2(2)=1,C_2(3)=frac{2times(C_2(0)+C_2(1)+C_2(2))}{3}=frac{2}{3}
$
[ C_2(n)=frac{n+1}{6},n>3
]
结论
[ C_0(n)=C_1(n)=frac{n+1}{3},n>2
\ C_2(n)=frac{n+1}{6},n>3 ]
实验结果:
图片 9

2.1.1 双连通分量

  • 定理: 在无向连通图G的DFS树中,
    非根节点u是G的割顶当且仅当u存在一個子节点v,
    使得v及其后代都没有反向边连回u的祖先.
  • 设low(u)为u及其后代所能连回的最早的祖先的pre值, 则定理中的条件就是:
  • 节点u存在一个子节点v, 使得low(v) >= pre(u).
  • 对于一个连通图, 如果任意两点存在至少两条”点不重复”的路径,
    就说这个图是点-双连通的, 这个要求等价于任意两条边都在同一个简单环中,
    即内部无割顶. 类似的定义边-双连通. 对于一张无向图,
    点-双连通的极大子图称为双连通分量.
  • 不同双连通分量最多只有一个公共点, 且它一定是割顶.
    任意割顶都是两个不同双连通分量的公共点.

    stack S;
    int dfs(int u, int fa) {
    int lowu = pre[u] = ++dfs_clock;
    int child = 0;
    for(int i = 0; i < G[u].size(); i++) {

    int v = G[u][i];
    Edge e = (Edge){u, v};
    if(!pre[v]) {
      S.push(e);
      child++;
      int lowv = dfs(v, u);
      lowu = min(lowu, lowv);
      if(lowv >= pre[u]) {
        iscut[u] = true;
        bcc_cnt++;
        bcc[bcc_cnt].clear();
        for(;;) {
          Edge x = S.top(); S.pop();
          if(bccno[x.u] != bcc_cnt) {bcc[bcc_cnt].push_back(x.u); bccno[x.u] = bcc_cnt;}
          if(bccno[x.v] != bcc_cnt) {bcc[bcc_cnt].push_back(x.v); bccno[x.v] = bcc_cnt;}
          if(x.u == u && x.v == v) break;
        }
      }
    }
    else if(pre[v] < pre[u] && v != fa) {
      S.push(e);
      lowu = min(lowu, pre[v]);
    }
    

    }
    if(fa < 0 && child == 1) iscut[u] = 0; return lowu; }

  • 边-双连通分量可以使用更简单的方法求出, 分两个步骤,
    先做一次dfs标记出所有的桥, 然后再做一次dfs找出边-双连通分量.
    因为边-双连通分量是没有公共节点的,
    所以只要在第二次dfs的时候保证不经过桥即可.

(2).添加注释文字 text

例子:

  1. $$ f(n)= begin{cases} n/2, & text {if $n$ is even} \ 3n+1, & text{if $n$ is odd} end{cases} $$

显示:

( n ) = { n / 2 , 3 n + 1 , if n is even if n is odd

代码

QuickSortAnalyze 类,添加了三个属性用于计算数组数量。

using System;
using System.Diagnostics;

namespace Quick
{
    /// <summary>
    /// 自动记录比较次数以及子数组数量的快速排序类。
    /// </summary>
    public class QuickSortAnalyze : BaseSort
    {
        /// <summary>
        /// 比较次数。
        /// </summary>
        public int CompareCount { get; set; }

        /// <summary>
        /// 是否启用打乱。
        /// </summary>
        public bool NeedShuffle { get; set; }

        /// <summary>
        /// 是否显示轨迹。
        /// </summary>
        public bool NeedPath { get; set; }

        /// <summary>
        /// 大小为 0 的子数组数量。
        /// </summary>
        public int Array0Num { get; set; }

        /// <summary>
        /// 大小为 1 的子数组数量。
        /// </summary>
        public int Array1Num { get; set; }

        /// <summary>
        /// 大小为 2 的子数组数量。
        /// </summary>
        public int Array2Num { get; set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortAnalyze()
        {
            this.CompareCount = 0;
            this.NeedShuffle = true;
            this.NeedPath = false;
            this.Array0Num = 0;
            this.Array1Num = 0;
            this.Array2Num = 0;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            this.Array0Num = 0;
            this.Array1Num = 0;
            this.Array2Num = 0;
            this.CompareCount = 0;
            if (this.NeedShuffle)
                Shuffle(a);
            if (this.NeedPath)
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write("  ");
                }
                Console.WriteLine("tlotjthi");
            }
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        private void Sort<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            if (hi - lo == 1)
                this.Array2Num++;
            else if (hi == lo)
                this.Array1Num++;
            else if (hi < lo)
                this.Array0Num++;

            if (hi <= lo)                   // 别越界
                return;
            int j = Partition(a, lo, hi);
            if (this.NeedPath)
            {
                for (int i = 0; i < a.Length; i++)
                {
                    Console.Write(a[i] + " ");
                }
                Console.WriteLine("t" + lo + "t" + j + "t" + hi);
            }
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }

        /// <summary>
        /// 比较第一个元素是否小于第二个元素。
        /// </summary>
        /// <typeparam name="T">要比较的元素类型。</typeparam>
        /// <param name="a">第一个元素。</param>
        /// <param name="b">第二个元素。</param>
        /// <returns></returns>
        new protected bool Less<T>(T a, T b) where T : IComparable<T>
        {
            this.CompareCount++;
            return a.CompareTo(b) < 0;
        }
    }
}

主方法

using System;
using Quick;

namespace _2._3._7
{
    /*
     * 2.3.7
     * 
     * 在使用快速排序将 N 个不重复的元素排序时,
     * 计算大小为 0、1 和 2 的子数组的数量。
     * 如果你喜欢数学,请推导;
     * 如果你不喜欢,请做一些实验并提出猜想。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            // 证明
            // 我们设 C0(n) 代表将 n 个不重复元素排序时大小为 0 的数组的数量。
            // 同理有 C1(n) 和 C2(n) 代表大小为 1 的数组的数量和大小为 2 的数组的数量。
            // 设 k 代表切分位置,显然切分位置随机且概率相等,在 1~n 之间均匀分布。
            // 根据条件,三者都满足下式。
            // C(n) = 1/n sum(C(k - 1) + C(n - k)), k=1,2,...,n
            // 显然 sum(C(k - 1)) = sum(C(n - k)), k=1,2,...,n
            // 于是可以化简为
            // C(n) = 2/n sum(C(k - 1)), k=1,2,...,n
            // nC(n) = 2 * sum(C(k-1)), k=1,2,...,n
            // 同理有
            // (n-1)C(n-1) = 2 * sum(C(k-1)), k = 1,2,...,n-1
            // 相减得到递推式
            // nC(n) - (n-1)C(n-1) = 2*C(n-1)
            // C(n) = (n+1)/n * C(n-1)
            // 利用累乘法可以求得通项公式
            // C(n)=C(k)*(n+1)/(k+1), n>k
            // 对于 C0 有 C0(0)=1, C0(1)=0
            // C0(2)=C(0)+C(1)=1
            // C0(n)=(n+1)/3, n>2
            // 对于 C1 有 C1(0)=0, C1(1)=1
            // C1(2)=C1(0)+C1(1)=1
            // C1(n)=(n+1)/3, n>2
            // 对于 C2 有 C2(0)=C2(1)=0, C2(2)=1
            // C2(3)=1/3*2*(C2(0)+C2(1)+C2(2))=2/3
            // C2(n)=C2(3)*(n+1)/4=(n+1)/6, n>3
            // 结论
            // C0(n)=C1(n)=(n+1)/3, C2(n)=(n+1)/6
            int n = 1000;
            QuickSortAnalyze sort = new QuickSortAnalyze();
            Console.WriteLine("nt0t1t2");
            for (int i = 0; i < 5; i++)
            {
                int[] a = new int[n];
                for (int j = 0; j < n; j++)
                {
                    a[j] = j;
                }
                SortCompare.Shuffle(a);
                sort.Sort(a);
                Console.WriteLine(n + "t" + sort.Array0Num + "t" + sort.Array1Num + "t" + sort.Array2Num);
                n *= 2;
            }
        }
    }
}

2.1.2 强连通分量

kosaraju算法.

void dfs(int v) {
  vis[v] = true;
  for (int i = 0; i < G[v].size(); i++) {
    if (!vis[G[v][i]])
      dfs(G[v][i]);
  }
  vs.push_back(v);
}
void rdfs(int v, int k) {
  vis[v] = true;
  cnt[v] = k;
  for (int i = 0; i < rG[v].size(); i++) {
    if (!vis[rG[v][i]])
      rdfs(rG[v][i], k);
  }
  vs.push_back(v);
  sc[k].push_back(v);
}
int scc() {
  memset(vis, 0, sizeof(vis));
  vs.clear();
  for (int v = 1; v <= n; v++) {
    if (!vis[v])
      dfs(v);
  }
  memset(vis, 0, sizeof(vis));
  int k = 0;
  for (int i = vs.size() - 1; i >= 0; i--) {
    if (!vis[vs[i]]) {
      rdfs(vs[i], k++);
    }
  }
  return k;
}

二、矩阵使用参考

另请参阅

Quick

What is the expected number of subarrays of size 0, 1 and 2 when
quicksort is used to sort an array of N items with distinct keys?-Stack
Overflow

2.2 最短路与最小生成树

1.如何输入无框矩阵

在开头使用 begin{matrix} ,在结尾使用 end{matrix}
,在中间插入矩阵元素,每个元素之间插入 & ,并在每行结尾处使用 \

例子:

  1. $$
  2. begin{matrix}
  3. 1 & x & x^2 \
  4. 1 & y & y^2 \
  5. 1 & z & z^2 \
  6. end{matrix}
  7. $$

显示:

1 1 1 x 2 2 2

2.3.8

2.2.1 SPFA

虽然是NOIp(professional)知识, 但是由于在省选中非常常用,
还是写一下.

最短路算法也会在分层图中考察.

spfa也可以运用在DP中的转移.

void spfa() {
  memset(dist, 0x3f, sizeof(dist));
  dist[s][0] = 0;
  queue<state> q;
  q.push((state){s, 0});
  memset(inq, 0, sizeof(inq));
  inq[s][0] = 1;
  while (!q.empty()) {
    state u = q.front();
    q.pop();
    inq[u.pos][u.k] = 0;
    for (int i = 0; i < G[u.pos].size(); i++) {
      edge &e = G[u.pos][i];
      if (dist[e.to][u.k] > dist[u.pos][u.k] + e.value) {
        dist[e.to][u.k] = dist[u.pos][u.k] + e.value;
        if (!inq[e.to][u.k]) {
          q.push((state){e.to, u.k});
          inq[e.to][u.k] = 1;
        }
      }
      if (u.k < k && dist[e.to][u.k + 1] > dist[u.pos][u.k]) {
        dist[e.to][u.k + 1] = dist[u.pos][u.k];
        if (!inq[e.to][u.k + 1]) {
          q.push((state){e.to, u.k + 1});
          inq[e.to][u.k + 1] = 1;
        }
      }
    }
  }
}

spfa可以用来判负环. 所谓负环就是环上边权和为负的环.
一般使用dfs版本spfa判负环.

double dist[maxn];
inline void spfa(int x) {
  int i;
  vis[x] = false;
  for (i = 0; i < rg[x].size(); i++) {
    edge &e = rg[x][i];
    if (dist[e.to] > dist[x] + e.value)
      if (!vis[e.to]) {
        flag = true;
        break;
      } else {
        dist[e.to] = dist[x] + e.value;
        spfa(e.to);
      }
  }
  vis[x] = true;
}
bool check(double lambda) {
  for (int i = 1; i <= n; i++) {
    rg[i].clear();
    for (int j = 0; j < G[i].size(); j++) {
      rg[i].push_back((edge){G[i][j].to, (double)G[i][j].value - lambda});
    }
  }
  memset(vis, 1, sizeof(vis));
  memset(dist, 0, sizeof(dist));
  flag = false;
  for (int i = 1; i <= n; i++) {
    spfa(i);
    if (flag)
      return true;
  }
  return false;
}

2.如何输入边框矩阵

在开头将 matrix 替换为 pmatrix bmatrix Bmatrix vmatrix
Vmatrix

例子:

  1. $ begin{matrix} 1 & 2 \ 3 & 4 \ end{matrix} $
  2. $ begin{pmatrix} 1 & 2 \ 3 & 4 \ end{pmatrix} $
  3. $ begin{bmatrix} 1 & 2 \ 3 & 4 \ end{bmatrix} $
  4. $ begin{Bmatrix} 1 & 2 \ 3 & 4 \ end{Bmatrix} $
  5. $ begin{vmatrix} 1 & 2 \ 3 & 4 \ end{vmatrix} $
  6. $ begin{Vmatrix} 1 & 2 \ 3 & 4 \ end{Vmatrix} $

显示:

matrix pmatrix bmatrix Bmatrix vmatrix Vmatrix
1 3 2 4
题目

Quick.sort() 在处理 N 个全部重复的元素时大约需要多少次比较?

2.2.2 动态最小生成树

最小生成树算是很常见的考点.

关于最小生成树, 我们有以下结论:

  • 对于连通图中的任意一个环 C
    :如果C中有边e的权值大于该环中任意一个其它的边的权值,那么这个边不会是最小生成树中的边.
  • 在一幅连通加权无向图中,给定任意的切分,它的横切边中权值最小的边必然属于图的最小生成树。
  • 如果图的具有最小权值的边只有一条,那么这条边包含在任意一个最小生成树中。
  • 次小生成树: 树上倍增+lca
  • 两个点之间的最大权最小路径一定在最小生成森林上(水管局长)
  • 欧几里德最小生成树
    动态最小生成树: 使用Link-Cut Tree维护.

  • 矩阵树定理(Matrix-Tree)

    下面我们介绍一种新的方法——Matrix-Tree定理(Kirchhoff矩阵-树定理)。Matrix-Tree定理是解决生成树计数问题最有力的武器之一。它首先于1847年被Kirchhoff证明。在介绍定理之前,我们首先明确几个概念:
    1、G的度数矩阵 class=”math inline”>(D[G])是一个 class=”math inline”>(n times
    n)的矩阵,并且满足:当(inot
    = j)时, class=”math inline”>(d_{ij}=0);当 class=”math inline”>(i=j)时, class=”math inline”>(d_{ij})等于 class=”math inline”>(v_i)的度数。
    2、G的邻接矩阵 class=”math inline”>(A[G])也是一个 class=”math inline”>(n times n)的矩阵,
    并且满足:如果(v_i)、 class=”math inline”>(v_j)之间有边直接相连,则 class=”math inline”>(a_{ij})=1,否则为0。
    我们定义 class=”math inline”>(G)的Kirchhoff矩阵(也称为拉普拉斯算子)C[G]为C[G]=D[G]-A[G],则Matrix-Tree定理可以描述为:G的所有不同的生成树的个数等于其Kirchhoff矩阵C[G]任何一个n-1阶主子式的行列式的绝对值。所谓n-1阶主子式,就是对于r(1≤r≤n),将C[G]的第r行、第r列同时去掉后得到的新矩阵,用Cr[G]表示。

  • kruskal 算法: 贪心地选取每一条边

3.如何输入带省略符号的矩阵

使用 cdots

,

ddots

,

vdots

来输入省略符号。

例子:

  1. $$
  2. begin{pmatrix}
  3. 1 & a_1 & a_1^2 & cdots & a_1^n \
  4. 1 & a_2 & a_2^2 & cdots & a_2^n \
  5. vdots & vdots & vdots & ddots & vdots \
  6. 1 & a_m & a_m^2 & cdots & a_m^n \
  7. end{pmatrix}
  8. $$

显示:

1 1 ⋮ 1 a 1 a 2 ⋮ a m a 2 1 a 2 2 ⋮ a 2 m ⋯ ⋯ ⋱ ⋯ a n 1 a n 2 ⋮ a n m

解答

每次切分都会把数组平分,共切分 logN 次(二分法),每次切分比较 N 次(i
和 j 会一位一位地从两边向中间靠拢)。
共比较 NlogN 次。

2.3网络流

4.如何输入带分割符号的矩阵

详见”数组使用参考”。

例子:

  1. $$ left[
  2. begin{array}{cc|c}
  3. 1&2&3\
  4. 4&5&6
  5. end{array}
  6. right] $$

显示:

[ 1 4 2 5 3 6 ]

其中 cc|c 代表在一个三列矩阵中的第二和第三列之间插入分割线。

2.3.9

2.3.1 预备知识

  • 流网络(G=(V,E))是一个有向图,
    其中每条边(<u, v> in
    E)均为有一非负容量(c(u, v)
    geqslant 0), 规定: 若(<u,v> not in E), 则(c(u,v)=0). 网络中有两个特殊点(s)和(t).
  • 网络的流是一个实值函数(f):(V times V rightarrow R),
    且满足三个性质: 容量限制, 反对称性, 流守恒性.
  • 最大的流是指该网络中流值最大的流.
  • 残留网络由可以容纳更多流的边构成.
  • 增广路径(p)为残留网络上(s)到(t)的一条简单路径.
  • 流网络(G=(V, E))的割([S, T])将点集划分为(S)和(T)两部分, 使得(s in S and t in T).
    符号([S, T]={<u,v>|<u,v>
    in E, u in S, v in T}), 通过割的净流为(f(S,T)), 容量定义为(c(S,T)).
  • 一个网络的最小割就是网络中容量最小的割.

5.如何输入行中矩阵

若想在一行内显示矩阵,

使用 bigl(begin{smallmatrix} ... end{smallmatrix}bigr)

例子:

  1. 这是一个行中矩阵的示例 $bigl( begin{smallmatrix} a & b \ c & d end{smallmatrix} bigr)$ 。

显示:

这是一个行中矩阵的示例 ( a c b )

题目

请说明 Quick.sort()
在处理只有两种主键值时的行为,以及在处理只有三种主键值的数组时的行为。

2.3.2 最大流最小割定理与线性规划

首先我们假设读者已经有了线性规划的基本知识.

最大流问题的线性规划描述:
$$
begin{alignat}{2}

maxquad &f_{ts} &{}& tag{LP1} label{eqn – lp}

mbox{s.t.}quad

&f_{u,v}leqslant c_{u,v}, &quad& (u,v)in E

&sum_{v} f_{uv} = sum_v f_{vu}, &{}& u in V
& f_{uv} geqslant 0, &{}& (u,v) in E cup{(t,s)}

end{alignat}
[ 最小割问题的线性规划描述: ]
begin{alignat}{2}

minquad &sum_{(u,v) in E}c_{uv}d_{uv} &{}& tag{LP2}

mbox{s.t.}quad

&d_{u,v}-p_u+p_v &geqslant 0, &quad& (u,v)in E
&p_s-p_t &geqslant 1
&p_u, d_{uv} in {0, 1}

end{alignat}
($ 令)p_u=[u in S]$, (d_{uv}=max{p_u-p_v, 0}).

考虑最大流的对偶: 记由容量限制产生的变量为(d_{uv}), 由点(u)的流量守恒产生的变量为(p_u), 那么对偶问题就是:
$$
begin{alignat}{2}

minquad &sum_{(u,v) in E}c_{uv}d_{uv} &{}& tag{LP3}

mbox{s.t.}quad

&d_{u,v}-p_u+p_v &geqslant 0, &quad& (u,v)in E
&p_s-p_t &geqslant 1
&d_{uv} &geqslant 0, &{}&(u,v)in E

end{alignat}
($ 我们得出结论:
(最大流最小割定理)给定一个源为)s(,
汇为)t(的网络, 则)s,t(的最大流等于)s,t$的最小割.

三、方程式序列使用参考

解答

切分时,枢轴左侧都是小于(或等于)枢轴的,
右侧都是大于(或等于)枢轴的
只有两种主键值时,
第一次切分之后,某一侧的元素将全部相同
(如果枢轴选了较大的,那么右侧将全部相同,反之则左侧全部相同)

只有三种主键值时,和一般快速排序并无不同。
但如果第一次切分时选择了中间值作为枢轴,且中间值只有一个
那么只需要一次切分数组便会有序。

2.3.3 最大流算法

1.如何输入一个方程式序列

人们经常想要一列整齐且居中的方程式序列。使用 begin{align}…end{align}
来创造一列方程式,其中在每行结尾处使用 \

例子:

  1. begin{align}
  2. sqrt{37} & = sqrt{frac{73^2-1}{12^2}} \
  3. & = sqrt{frac{73^2}{12^2}cdotfrac{73^2-1}{73^2}} \
  4. & = sqrt{frac{73^2}{12^2}}sqrt{frac{73^2-1}{73^2}} \
  5. & = frac{73}{12}sqrt{1 - frac{1}{73^2}} \
  6. & approx frac{73}{12}left(1 - frac{1}{2cdot73^2}right)
  7. end{align}

显示:

= 73 2 − 1 12 2 √ = 73 2 12 2 ⋅ 73 2 − 1 73 2 √ = 73 2 12 2 √ 73 2 − 1
73 2 √ = 73 12 1 − 1 73 2 √ ≈ 73 12 ( 1 − 1 2 ⋅ 73 2 ) (2) (3) (4) (5)
(6)

方程式序列中无需再次声明公式符号 $$$

2.3.10

2.3.3.1 Dinic算法
int dist[maxn], iter[maxn];
inline void bfs(int s) {
  memset(dist, -1, sizeof(dist));
  dist[s] = 0;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    for (int i = 0; i < G[u].size(); i++) {
      edge &e = edges[G[u][i]];
      if (e.cap > 0 && dist[e.to] == -1) {
        dist[e.to] = dist[u] + 1;
        q.push(e.to);
      }
    }
  }
}
inline int dfs(int s, int t, int flow) {
  if (s == t)
    return flow;
  for (int &i = iter[s]; i < G[s].size(); i++) {
    edge &e = edges[G[s][i]];
    if (e.cap > 0 && dist[e.to] > dist[s]) {
      int d = dfs(e.to, t, min(e.cap, flow));
      if (d > 0) {
        e.cap -= d;
        edges[G[s][i] ^ 1].cap += d;
        return d;
      }
    }
  }
  return 0;
}
inline int dinic(int s, int t) {
  int flow = 0;
  while (1) {
    bfs(s);
    if (dist[t] == -1)
      return flow;
    memset(iter, 0, sizeof(iter));
    int d;
    while (d = dfs(s, t, inf))
      flow += d;
  }
  return flow;
}

四、条件表达式使用参考

题目

Chebyshev 不等式表明,一个随机变量的标准差距离均值大于 k 的概率小于
1/k^2 。
对于 N=100 万,用 Chebyshev 不等式计算快速排序所使用的比较次数大于 1000
亿次的概率(0.1N^2)。

2.3.3.2 费用流

泛指一种与费用相关的流算法.EK算法比较常用

bool spfa(ll &flow, ll &cost) {
  for (int i = 0; i <= n + 1; i++) {
    dist[i] = -inf;
  }
  memset(inq, 0, sizeof(inq));
  dist[s] = 0, inq[s] = 1, pre[s] = 0, fi[s] = inf;
  queue<int> q;
  q.push(s);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    inq[u] = 0;
    for (int i = 0; i < G[u].size(); i++) {
      edge &e = E[G[u][i]];
      if (e.cap > e.flow && dist[e.to] < dist[u] + e.cost) {
        dist[e.to] = dist[u] + e.cost;
        pre[e.to] = G[u][i];
        fi[e.to] = min(fi[u], e.cap - e.flow);
        if (!inq[e.to]) {
          q.push(e.to);
          inq[e.to] = 1;
        }
      }
    }
  }
  if (dist[t] <= -inf)
    return false;
  if (cost + dist[t] * fi[t] < 0) { 
    ll temp = cost / (-dist[t]); //temp:还能够增加的流
    flow += temp;
    return false;
  }
  flow += fi[t];
  cost += dist[t] * fi[t];
  int u = t;
  while (u != s) {
    E[pre[u]].flow += fi[t];
    E[pre[u] ^ 1].flow -= fi[t];
    u = E[pre[u]].from;
  }
  return true;
}
ll mcmf(int s, int t) {
  ll flow = 0;
  ll cost = 0;
  while (spfa(flow, cost))
    ;
  return flow;
}

1.如何输入一个条件表达式

使用 begin{cases} 来创造一组条件表达式,在每一行条件中插入 &
来指定需要对齐的内容,并在每一行结尾处使用 \ ,以 end{cases} 结束。

条件表达式需要指定 $$$

例子:

  1. $$
  2. f(n) =
  3. begin{cases}
  4. n/2, & text{if $n$ is even} \
  5. 3n+1, & text{if $n$ is odd}
  6. end{cases}
  7. $$

显示:

( n ) = { n / 2 , 3 n + 1 , if n is even if n is odd

解答

切比雪夫不等式(Chebyshev’s inequality)
[ P(|X-mu|geq ksigma)leq
frac{1}{k^2} ]
其中,$ mu $ 代表期望,$ sigma $ 代表标准差。
对于快速排序的比较次数来说,$ mu = 2Nln N $ ,$ sigma=0.65N $。
(这两个结论见 2.3 节的命题 K 和命题 L)
题目中要求比较次数大于 $ 0.1N^2 $ ,可以求得 $ k $ 的值。
[ 0.65kN=0.1N^2 \ k=frac{2N}{13}
]
将 $ N=1,000,000 $ 代入
[ P(|X-27,631,021|geq
100,000,000,000)leq 0.00000000004225 ]

2.3.4 建模方法

2.如何输入一个左侧对齐的条件表达式

若想让文字在 左侧对齐显示 ,则有如下方式:

例子:

  1. $$
  2. left.
  3. begin{array}{l}
  4. text{if $n$ is even:}&n/2\
  5. text{if $n$ is odd:}&3n+1
  6. end{array}
  7. right}
  8. =f(n)
  9. $$

显示:

if n is even: if n is odd: n / 2 3 n + 1 } = ( n )

另请参阅

切比雪夫不等式到底是个什么概念? – 马同学的回答 –
知乎

2.3.4.1 基本建模
  • 多个源点和汇点(超级源点, 超级汇点)
  • 无向图: 拆成两条边
  • 顶点容量限制: 拆点
  • 不相交的两条路径: 拆点
  • 上下界网络流:图片 10
  • 上下界费用流:图片 11
  • 图部分发生变化: 重复利用之前的结果
  1. 容量增加, 直接跑最大流
  2. 容量减少, 如果(f(e) leq
    c(e)-1), 那么不用动, 否则退流

    for (int i = 1; i <= n; i++) {
      int now = cc[i].id;
      int u = now, v = now + n;
      bfs(u);
      if (dist[v] != -1)
        continue;
      rec[tot++] = now;
      dinic(t, v);
      dinic(u, s);
      edges[(now - 1) * 2].cap = edges[(now - 1) * 2 + 1].cap = 0;
    }
    
  • 容量为负数: 适当变形
  • 费用为负数的情况:
  1. 消负圈
  2. 通过适当的变形. 比如说, 如果每次增广所用的边数都是相同的(记做m),
    那么把所有边的费用都加上常数(k), 然后从最短路减去(mk)就得到了原图最短路的长度
  3. 图片 12

3.如何使条件表达式适配行高

在一些情况下,条件表达式中某些行的行高为非标准高度,此时使用 \[2ex]
语句代替该行末尾的 \ 来让编辑器适配。

例子:

  1. f(n) =
  2. begin{cases}
  3. frac{n}{2}, & text{if $n$ is even} \
  4. 3n+1, & text{if $n$ is odd}
  5. end{cases}

  1. f(n) =
  2. begin{cases}
  3. frac{n}{2}, & text{if $n$ is even} \[2ex]
  4. 3n+1, & text{if $n$ is odd}
  5. end{cases}

显示:

不适配[2ex]
( n ) = { n 2 , 3 n + 1 , if n is even if n is odd
适配[2ex]
( n ) = n 2 , 3 n + 1 , if n is even if n is odd

一个 [ex] 指一个 “X-Height”,即x字母高度。可以根据情况指定多个 [ex]
,如 [3ex] [4ex] 等。

2.3.11

2.3.4.2 最大流建模
  • 与棋盘有关的题目可以考虑最大流

五、数组与表格使用参考

题目

假如在遇到和切分元素重复的元素时我们继续扫描数组而不是停下来,
证明使用这种方法的快速排序在处理只有若干种元素值的数组时运行时间是平方级别的。

2.3.4.3 最小割建模
  • 用容量为(infty)的边表示冲突
  • 从两点关系的角度进行最小割建模

1.如何输入一个数组或表格

通常,一个格式化后的表格比单纯的文字或排版后的文字更具有可读性。数组和表格均以
begin{array} 开头,并在其后定义列数及每一列的文本对齐属性, c l
r 分别代表居中、左对齐及右对齐。若需要插入垂直分割线,在定义式中插入
| ,若要插入水平分割线,在下一行输入前插入 hline
。与矩阵相似,每行元素间均须要插入 & ,每行元素以 \ 结尾,最后以
end{array} 结束数组。

例子:

  1. begin{array}{c|lcr}
  2. n & text{左对齐} & text{居中对齐} & text{右对齐} \
  3. hline
  4. 1 & 0.24 & 1 & 125 \
  5. 2 & -1 & 189 & -8 \
  6. 3 & -20 & 2000 & 1+10i
  7. end{array}

显示:

n 1 2 3 左 对 齐 0.24 − 1 − 20 居 中 对 齐 1 189 2000 右 对 齐 125 − 8 1

  • 10 i
解答

只有若干种元素值意味着大量的连续重复。
(由于存在打乱这一步骤,不存在连续重复的可能性是很低的)
接下来我们考虑这样的连续重复在修改后的快排下的性能。
1 1 1 1 1 1 1
对于这样的数组,枢轴选为 1,j 将会在 j = lo 处终止。
因此最后的结果将是每次只有数组的第一个元素被排序
已知每次切分都是 O(k – 1) 的(i 和 j 都将走完整个子数组)
因此这样的快速排序所需时间 = $ 2 (N – 1 + N – 2 + cdots + 1) = (N –
1)N $
因此对于值相同的子数组,这样的快排运行时间是平方级别的
那么当数组中这样的连续重复内容越多,运行时间就越接近平方级别。

2.3.4.4 费用流建模

2.如何输入一个嵌套的数组或表格

多个数组/表格可 互相嵌套 并组成一组数组/一组表格。

使用嵌套前必须声明 $$ 符号。

例子:

  1. $$
  2. % outer vertical array of arrays 外层垂直表格
  3. begin{array}{c}
  4. % inner horizontal array of arrays 内层水平表格
  5. begin{array}{cc}
  6. % inner array of minimum values 内层"最小值"数组
  7. begin{array}{c|cccc}
  8. text{min} & 0 & 1 & 2 & 3\
  9. hline
  10. 0 & 0 & 0 & 0 & 0\
  11. 1 & 0 & 1 & 1 & 1\
  12. 2 & 0 & 1 & 2 & 2\
  13. 3 & 0 & 1 & 2 & 3
  14. end{array}
  15. &
  16. % inner array of maximum values 内层"最大值"数组
  17. begin{array}{c|cccc}
  18. text{max}&0&1&2&3\
  19. hline
  20. 0 & 0 & 1 & 2 & 3\
  21. 1 & 1 & 1 & 2 & 3\
  22. 2 & 2 & 2 & 2 & 3\
  23. 3 & 3 & 3 & 3 & 3
  24. end{array}
  25. end{array}
  26. % 内层第一行表格组结束
  27. \
  28. % inner array of delta values 内层第二行Delta值数组
  29. begin{array}{c|cccc}
  30. Delta&0&1&2&3\
  31. hline
  32. 0 & 0 & 1 & 2 & 3\
  33. 1 & 1 & 0 & 1 & 2\
  34. 2 & 2 & 1 & 0 & 1\
  35. 3 & 3 & 2 & 1 & 0
  36. end{array}
  37. % 内层第二行表格组结束
  38. end{array}
  39. $$

显示:

min 0 1 2 3 0 0 0 0 0 1 0 1 1 1 2 0 1 2 2 3 0 1 2 3 max 0 1 2 3 0 0 1 2
3 1 1 1 2 3 2 2 2 2 3 3 3 3 3 3 Δ 0 1 2 3 0 0 1 2 3 1 1 0 1 2 2 2 1 0 1
3 3 2 1 0

2.3.12

2.3.4.5 流量平衡思想

3.如何输入一个方程组

使用 begin{array}…end{array}left{…right. 来创建一个方程组。

例子:

  1. $$
  2. left{
  3. begin{array}{c}
  4. a_1x+b_1y+c_1z=d_1 \
  5. a_2x+b_2y+c_2z=d_2 \
  6. a_3x+b_3y+c_3z=d_3
  7. end{array}
  8. right.
  9. $$

显示:

$$
left{
begin{array}{c}
a_1x+b_1y+c_1z=d_1
a_2x+b_2y+c_2z=d_2
a_3x+b_3y+c_3z=d_3
end{array}
right.
$$
或者使用条件表达式组 begin{cases}…end{cases} 来实现相同效果:

例子:

  1. $$begin{cases}
  2. a_1x+b_1y+c_1z=d_1 \
  3. a_2x+b_2y+c_2z=d_2 \
  4. a_3x+b_3y+c_3z=d_3
  5. end{cases}
  6. $$

显示:

$$
begin{cases}
a_1x+b_1y+c_1z=d_1
a_2x+b_2y+c_2z=d_2
a_3x+b_3y+c_3z=d_3
end{cases}
$$

题目

按照代码所示轨迹的格式给出信息量最佳的快速排序第一次是如何切分
数组 B A B A B A B A C A D A B R A 的。

2.4二分图

  • 二分图, 指顶点可以分为两个不相交的几个(U)和(V)((U
    and V)皆为独立集), 使得在同一个集内的顶点不相邻的图.
  • 无向图G为二分图(Leftrightarrow)G至少有两个顶点,
    且所有回路的长度均为偶数(Leftrightarrow)没有奇圈
  • 最大边独立集的基数等于最大独立集的基数
  • 最大独立集的基数和最大匹配基数之和, 等于顶点数目.
  • 对于连通的二分图: 最小顶点覆盖集的基数等于最大匹配的基数
  • Hall定理是一个用于判定二分图是否具有最大匹配的定理。
    首先对于二分图G=(X∪Y,E),点集被分为了XX和YY两部分。
    是否具有最大匹配,首先一个最基本的条件就是|X|=|Y||X|=|Y|。
    Hall定理则在此基础上给出了一个更强的条件。
    首先对于一个点集T⊆X,定义Γ(T)Γ(T)如下:
    Γ(T)={v∣u→v∈E,u∈T,v∈Y}
    Γ(T)={v∣u→v∈E,u∈T,v∈Y}
    即表示TT中所有点能够直接到达的YY中的点的集合。
    图片 13
    上图中,Γ({1,3})={4,5,6}Γ({1,3})={4,5,6}。
    那么Hall条件则用于判断一个二分图是否存在最大匹配。Hall条件如下:
    对于任意的点集T⊆X,均存在:
    |T|≤|Γ(T)|
    |T|≤|Γ(T)|
    那么此二分图必定存在最大匹配。

六、连分数使用参考

就像输入分式时使用 frac 一样,使用 cfrac 来创建一个连分数。

例子:

  1. $$
  2. x = a_0 + cfrac{1^2}{a_1
  3. + cfrac{2^2}{a_2
  4. + cfrac{3^2}{a_3 + cfrac{4^4}{a_4 + cdots}}}}
  5. $$

显示:

$$
x = a_0 + cfrac{1^2}{a_1

  • cfrac{2^2}{a_2
  • cfrac{3^2}{a_3 + cfrac{4^4}{a_4 + cdots}}}}
    $$
    不要使用普通的 fracover 来创建,否则会看起来 很恶心

例子:

  1. $$
  2. x = a_0 + frac{1^2}{a_1
  3. + frac{2^2}{a_2
  4. + frac{3^2}{a_3 + frac{4^4}{a_4 + cdots}}}}
  5. $$

显示:

$$
x = a_0 + frac{1^2}{a_1

  • frac{2^2}{a_2
  • frac{3^2}{a_3 + frac{4^4}{a_4 + cdots}}}}
    $$
    当然,你可以使用 frac 来表达连分数的 紧缩记法

例子:

  1. $$
  2. x = a_0 + frac{1^2}{a_1+}
  3. frac{2^2}{a_2+}
  4. frac{3^2}{a_3 +} frac{4^4}{a_4 +} cdots
  5. $$

显示:

$$
x = a_0 + frac{1^2}{a_1+}
frac{2^2}{a_2+}
frac{3^2}{a_3 +} frac{4^4}{a_4 +} cdots
$$
Continued fractions are too big to put inline. Display them with $$…$$
or use a notation like [a0;a1,a2,a3,…] .

连分数通常都太大以至于不易于排版,所以建议在连分数前后声明 $$
符号,或使用像 [a0;a1,a2,a3,…] 一样的紧缩记法。

解答

图片 14

2.5 其他常用结论

  • 对于不存在孤立点的图,|最大匹配|+|最小边覆盖| = |V|

  • 最大独立集合 + 最小顶点覆盖 = V

  • 对于二分图:|最大匹配| = |最小顶点覆盖|

  • 平面圖的頂點個數、邊數和面的個數之間有一個以歐拉命名的公式:图片 15

其中,V是頂點的数目,E是邊的數目,F是面的數目,C是组成圖形的連通部分的數目。當圖是單連通圖的時候,公式簡化為:
图片 16

  • 任何一个平面图的对偶图仍然是平面图

七、一些特殊的注意事项

These are issues that won’t affect the correctness of formulas, but
might make them look significantly better or worse. Beginners should
feel free to ignore this advice; someone else will correct it for them,
or more likely nobody will care.

现在指出的小问题并不会影响方程式及公式等的正确显示,但能让它们看起来明显更好看。初学者可无视这些建议,自然会有强迫症患者替你们改掉它的,或者更可能地,根本没人发现这些问题。

Don’t use frac in exponents or limits of integrals; it looks bad and
can be confusing, which is why it is rarely done in professional
mathematical typesetting. Write the fraction horizontally, with a slash:

在以e为底的指数函数、极限和积分中尽量不要使用 frac
符号:它会使整段函数看起来很怪,也正是因此它在专业数学排版中从不出现。横着写这些分式,中间使用斜线间隔
/

例子:

  1. begin{array}{cc}
  2. mathrm{Bad} & mathrm{Better} \
  3. hline \
  4. e^{ifrac{pi}2} quad e^{frac{ipi}2}& e^{ipi/2} \
  5. int_{-fracpi2}^fracpi2 sin x,dx & int_{-pi/2}^{pi/2}sin x,dx \
  6. end{array}

显示:

$$
begin{array}{cc}
mathrm{Bad} & mathrm{Better}
hline
e^{ifrac{pi}2} quad e^{frac{ipi}2}& e^{ipi/2}
int_{-fracpi2}^fracpi2 sin x,dx &
int_{-pi/2}^{pi/2}sin x,dx
end{array}
$$
The | symbol has the wrong spacing when it is used as a divider, for
example in set comprehensions. Use mid instead:

| 符号在被当作分隔符时会产生错误的间隔,因此在需要分隔时最好使用
mid 来代替它。

例子:

  1. begin{array}{cc}
  2. mathrm{Bad} & mathrm{Better} \
  3. hline \
  4. {x|x^2inBbb Z} & {xmid x^2inBbb Z} \
  5. end{array}

显示:

$$
begin{array}{cc}
mathrm{Bad} & mathrm{Better}
hline
{x|x^2inBbb Z} & {xmid x^2inBbb Z}
end{array}
$$
For double and triple integrals, don’t use intint or intintint
. Instead use the special forms iint and iiint :

使用多重积分符号时,不要多次使用 int 来声明,直接使用 iint 来表示
二重积分 ,使用 iiint 来表示 三重积分
等。对于无限次积分,可以用 int cdots int 表示。

例子:

  1. begin{array}{cc}
  2. mathrm{Bad} & mathrm{Better} \
  3. hline \
  4. intint_S f(x),dy,dx & iint_S f(x),dy,dx \
  5. intintint_V f(x),dz,dy,dx & iiint_V f(x),dz,dy,dx
  6. end{array}

显示:

$$
begin{array}{cc}
mathrm{Bad} & mathrm{Better}
hline
intint_S f(x),dy,dx & iint_S f(x),dy,dx
intintint_V f(x),dz,dy,dx & iiint_V f(x),dz,dy,dx
end{array}
$$
无 限 次 积 分 : ⋯

Use , , to insert a thin space before differentials; without this

will mash them together:

在微分符号前加入 , 来插入一个小的间隔空隙;没有 , 符号的话,

将会把不同的微分符号堆在一起。

例子:

  1. begin{array}{cc}
  2. mathrm{Bad} & mathrm{Better} \
  3. hline \
  4. iiint_V f(x)dz dy dx & iiint_V f(x),dz,dy,dx
  5. end{array}

显示:

$$
begin{array}{cc}
mathrm{Bad} & mathrm{Better}
hline
iiint_V f(x)dz dy dx & iiint_V f(x),dz,dy,dx
end{array}
$$

2.3.13

MATHEMATICS

题目

在最佳、平均和最坏情况下,快速排序的递归深度分别是多少?
这决定了系统为了追踪递归调用所需的栈的大小。
在最坏情况下保证递归深度为数组大小的对数级的方法请见练习 2.3.20。

3.数学知识

解答

快速排序先将数组分为
(小于枢轴)枢轴(大于枢轴)三部分,然后再分别递归的排序左右两部分数组。
在这里,我们可以将快速排序的递归树看作是一棵二叉搜索树(BST, Binary
Search Tree)。
枢轴作为根结点,左子树即为左数组构造的 BST,右子树即为右数组构造的
BST。
这样题目中所求的递归深度即为所构造的 BST 的高度。

最坏情况,每次都只有枢轴和大于枢轴两部分,BST 退化为链表,高度为 $ n-1
$。

最好情况,每次枢轴都正好平分数组,构造一棵完全二叉树,高度为 $ log n
$。

平均情况,问题转化为:一个由 $ n $ 个元素随机构造的 BST
的平均高度是多少?
《算法导论》给出的结论是 $ log n $ ,具体证明如下:
设由 $ n $ 个结点随机构成的 BST 的高度为 $ h_n $,那么有:
[ h_n=1+max(h_{l}+h_{r})
]
其中,$ h_l $ 和 $ h_r $ 分别代表左数组和右数组构造的 BST 的高度。
设枢轴位置为 $ i $,上式可简化为:
[ h_n=1+max(h_{i-1}, h_{n-i})
]
由于枢轴位置可以在 1~n 之间任意取值且概率相等,因此 BST
的平均高度(即高度的期望)为:
[
E(h_n)=frac{1}{n}sum_{i=1}^{n}lbrack 1+max(h_{i-1}, h_{n-i})
rbrack ]
我们令 $ Y_n=2^{h_n} $,可得:
[ Y_n=2timesmax(Y_{i-1},Y_{n-i})
]
我们把 $ Y_n $ 代入,可得:
[ begin{align*} E(Y_n)
&=sum_{i=1}^{n}frac{1}{n}Elbrack2timesmax(Y_{i-1},
Y_{n-i})rbrack\
&=frac{2}{n}sum_{i=1}^{n}Elbrackmax(Y_{i-1},Y_{n-i})rbrack\
end{align*} ]
接下来我们去掉最大值运算,根据最大值的性质,下式显然成立:
[ Elbrackmax(X,Y)rbrackle
Elbrackmax(X,Y)+min(X,Y)rbrack=Elbrack X+Yrbrack=Elbrack
Xrbrack+Elbrack Yrbrack ]
代入可得:
[ E(Y_n)
lefrac{2}{n}sum_{i=1}^{n}(Elbrack Y_{i-1}rbrack + Elbrack
Y_{n-i} rbrack) =frac{2}{n}sum_{i=0}^{n-1}2Elbrack
Y_irbrack =frac{4}{n}sum_{i=0}^{n-1}Elbrack Y_irbrack
]
大小为 0 的数组构成的 BST 的高度显然为 0,我们设 $ Y_0=0 $
。接下来用一个组合数公式来构造上界:
[ begin{align*} 0&=Y_0=Elbrack Y_0
rbrackle
frac{1}{4}begin{pmatrix}3\3end{pmatrix}=frac{1}{4}\
1&=Y_1=Elbrack Y_1 rbracklefrac
{1}{4}begin{pmatrix}3+1\3end{pmatrix}=1 \ vdots \ Y_i
&=Elbrack
Y_irbracklefrac{1}{4}begin{pmatrix}i+3\3end{pmatrix}
end{align*} ]
注意这里的组合数公式为:
[
begin{pmatrix}n\rend{pmatrix}=frac{r!}{r!(n-r)!} ]
代入可得:
[ begin{align*} E(Y_n) &le
frac{4}{n}sum_{i=0}^{n-1}Elbrack Y_irbrack \
&lefrac{4}{n}sum_{i=0}^{n-1}frac{1}{4}begin{pmatrix}i+3\3end{pmatrix}
\
&=frac{1}{n}sum_{i=0}^{n-1}begin{pmatrix}i+3\3end{pmatrix}
end{align*} ]
接下来我们去掉求和符号,首先根据组合数的性质,有以下等式成立
[ begin{align*}
begin{pmatrix}n\kend{pmatrix}&=begin{pmatrix}n-1\k-1end{pmatrix}+begin{pmatrix}n-1\kend{pmatrix}
\ begin{pmatrix}n\nend{pmatrix}&=1 end{align*}
]
我们把求和式展开得到:
[ begin{align*}
sum_{i=0}^{n-1}begin{pmatrix}i+3\3end{pmatrix}
&=begin{pmatrix}3\3end{pmatrix} +
begin{pmatrix}4\3end{pmatrix}+cdots+begin{pmatrix}n+2\3end{pmatrix}
\ &=begin{pmatrix}4\4end{pmatrix} +
begin{pmatrix}4\3end{pmatrix}+cdots+begin{pmatrix}n+2\3end{pmatrix}
\ &=begin{pmatrix}n+3\4end{pmatrix} end{align*}
]
代入可得:
[ begin{align*} E(Y_n)
&lefrac{1}{n}sum_{i=0}^{n-1}begin{pmatrix}i+3\3end{pmatrix}\
&=frac{1}{n}begin{pmatrix}n+3\4 end{pmatrix} \
&=frac{1}{n}cdotfrac{(n+3)!}{4!(n-1)!} \
&=frac{1}{4}cdotfrac{(n+3)!}{3!n!} \
&=frac{(n+1)(n+2)(n+3)}{24} \ &=frac{n^3+6n^2+11n+6}{24}
end{align*} ]
由于 (Y_n=2^{h_n}) ,因此 (Elbrack Y_n rbrack=Elbrack 2^{h_n}
rbrack)。
由于 (f(x)=2^x)
是个凸函数,可以应用延森不等式(凸函数的割线一定在函数上方),即 (2^{Elbrack h_nrbrack}le Elbrack
Y_nrbrack)。
于是得到结论:
[ 2^{Elbrack h_nrbrack} le
frac{n^3+6n^2+11n+6}{24} \ Elbrack h_n rbrackle
log(frac{n^3+6n^2+11n+6}{24}) ]

3.1数论

另请参阅

快速排序的递归树可以视为 BST 的结论可以在下面这个 PPT 的第 5 页找到。
QuickSort-纽约大学
《算法导论》中关于随机 BST 高度的证明(P321 Theorem12.4)
Introduction to
Algorithms
也可以参考下面这个链接获得更详细的解释。
Proof that a randomly built binary search tree has logarithmic
height-StackExchange

3.1.1扩展欧几里德算法

首先我们有欧几里德算法:

[gcd(a, b) = gcd(a mod b,
b)]

扩展欧几里德算法解决了这样的问题:

[ ax + by = gcd(a,b)]

我们先考察一种特殊的情况:

当(b=0)时,我们直接可以有解:
[ begin{eqnarray} left{
begin{array}{lll} x = 1 \ y = 0 end{array} right.
end{eqnarray} ]
一般地,我们令(c = a mod
b),递归地解下面的方程:

[bx^{‘}+cy^{‘}=gcd(b,c)]

根据欧几里德算法,有

[bx^{‘}+cy^{‘}=gcd(a,b)]

根据(mod)的定义我们可以有

[c = a –
blfloorfrac{a}{b}rfloor]

带入原式

[bx^{‘}+(a –
blfloorfrac{a}{b}rfloor)y^{‘}=gcd(a,b)]

为了体现与(a,b)的关系

[ay^{‘}+b(x^{‘}-lfloorfrac{a}{b}rfloor
y^{‘})=gcd(a,b)]

所以这样就完成了回溯。

这个算法的思想体现在了下面的程序里。

void gcd(int a, int b, int &d, int &x, int &y) {
  if(!b) {d = a; x = 1; y = 0; }
  else { gcd(b, a%b, d, y, x); y -= x * (a/b); }
}

2.3.14

3.1.2线性筛与积性函数

题目

证明在用快速排序处理大小为 N 的不重复数组时,
比较第 i 大和第 j 大元素的概率为 2/(j – i + 1),并用该结论证明命题 K。

3.1.2.1线性筛素数

首先给出线性筛素数的程序。

void get_su(int n) {
  tot = 0;
  for(int i = 2; i <= n; i++) {
    if(!check[i]) prime[tot++] = i;
    for(int j = 0; j < tot; j++) {
      if(i * prime[j] > n) break;
      check[i * prime[j]] = true;
      if(i % prime[j] == 0) break;
    }
  }
}

可以证明的是,每个合数都仅仅会被他的最小质因数筛去,这段代码的时间复杂度是(Theta (n))的,也就是所谓线性筛。

证明:设合数 class=”math inline”>(n)最小的质因数为 class=”math inline”>(p),它的另一个大于 class=”math inline”>(p)的质因数为 class=”math inline”>(p^{‘}),另 class=”math inline”>(n = pm=p^{‘}m^{‘})。
观察上面的程序片段,可以发现 class=”math inline”>(j)循环到质因数 class=”math inline”>(p)时合数n第一次被标记(若循环到 class=”math inline”>(p)之前已经跳出循环,说明 class=”math inline”>(n)有更小的质因数),若也被 class=”math inline”>(p^{‘})标记,则是在这之前(因为 class=”math inline”>(m^{‘}<m)),考虑 class=”math inline”>(i)循环到 class=”math inline”>(m^{‘}),注意到 class=”math inline”>(n=pm=p^{‘}m^{‘})且 class=”math inline”>(p,p^{‘})为不同的质数,因此 class=”math inline”>(p|m^{‘}),所以当j循环到质数p后结束,不会循环到 class=”math inline”>(p^{‘}),这就说明 class=”math inline”>(n)不会被 class=”math inline”>(p^{‘})筛去。

解答

中文版题目有误,详见官方勘误页面:

假设 $ i < j $ 。
首先,在快速排序中,如果两个元素要发生交换,意味着其中一个元素被选为枢轴。
而且数组中的元素各不相同,那么两个特定的元素的比较最多发生一次。

那么先考虑一个特殊情况,$ i = 1, j = n $
,即求最大值和最小值比较的概率。
此时,一旦枢轴不是这两个元素之一,
最大值和最小值会被分到两个不同的子数组,无法发生比较。
因此在这种特例下第 $ i $ 大的元素和第 $ j $ 大的元素发生比较的概率为 $
frac{2}{n} = frac{2}{j-i+1} $ 。

接下来考虑一般情况,如果枢轴选择了第 $ i $ 到第 $ j $ 大之外的元素,
那么第 $ i $ 大和第 $ j $
大的元素会被分到同一个子数组里,重复上述过程。
因此我们所求的概率只和从第 $ i $ 大到第 $ j $ 大之间的元素有关,概率为
(frac{2}{j-i+1})。
(举个例子,一个箱子里有 2 个红球、1个蓝球和 7
个白球,现在摸球而不放回。
如果摸到白球可以再摸一次,直到摸到红球或蓝球为止。
显然在这样的规则下摸到红球或蓝球的概率为 1,即白球对概率没有影响。)

现在我们已经得到了某两个元素比较的概率 (E(X_{ij})),接下来我们求每两个元素比较的概率
$ E(X) $。
[ begin{align*} E(X) &=
sum_{i=1}^{n}sum_{j=i+1}^{n}E(X_{ij})\
&=sum_{i=1}^{n}2(frac{1}{2}+frac{1}{3}+cdots+frac{1}{n-i+1})
\ &=2n(frac{1}{2}+frac{1}{3}+cdots+frac{1}{n-i+1})
end{align*} ]
根据调和级数的性质($ ln (n) < 1+ frac{1}{2}+ cdots +
frac{1}{n} < 1+ln(n) $),可以得到结论:
[ E(X) le 2n ln(n) ]

3.1.2.2积性函数
  • 考虑一个定义域为(mathbb{N}^{+})的函数(f)(数论函数),对于任意两个互质的正整数(a,b),均满足

[f(ab) =
f(a)f(b)],则函数f被称为积性函数。

  • 如果对于任意两个正整数(a,b),都有(f(ab)=f(a)f(b)),那么就被称作完全积性函数。

容易看出,对于任意积性函数,(f(1)=1)。

  • 考虑一个大于1的正整数(N),设(N
    = prod p_{i}^{a_i}),那么

[f(N)=f(prod p_i^{a_i})=prod
f(p_i^{a_i})],如果(f)还满足完全积性,那么

[f(N)=prod f(p_i)^{a_i}]

  • 如果(f)是一个任意的函数,它使得和式(g(m) =
    sum_{d|m}f(d))为积性函数,那么(f)也一定是积性函数。
  • 积性函数的Dirichlet前缀和也是积性函数。这个定理是上面定理的反命题。
  • 两个积性函数的Dirichlet卷积也是积性函数。
另请参阅

下面这个链接里的 3.4.2 节给出了解法。
lect0906 –
卡内基梅隆大学
如果还是不能理解为什么多次切分不影响概率,可以参考三门问题的解释:
蒙提霍尔问题 –
维基百科
蒙提霍尔问题(又称三门问题、山羊汽车问题)的正解是什么?-
知乎

3.1.2.3欧拉函数(varphi)
  • (varphi(n))表示(1..n)中与(n)互质的整数个数。
  • 我们有欧拉定理:

[n^{varphi(m)}equiv 1 pmod m
nperp m]

可以使用这个定理计算逆元。

  • 如果(m)是一个素数幂,则容易计算(varphi(m)),因为有$n perp p^{k}
    Leftrightarrow p nmid n $ 。在({0,1,…,p^k-1})中的(p)的倍数是({0, p, 2p, …,
    p^k-p}),从而有(p^{k-1})个,剩下的计入(varphi(p^k))

[varphi(p^k) =
p^k-p^{k-1}=(p-1)p^{k-1}]

  • 由上面的推导我们不难得出欧拉函数一般的表示:

[varphi(m) =
prod_{p|m}(p^{m_p}-p^{m_p-1}) = m
prod_{p|m}(1-frac{1}{p})=prod(p-1)p^{m_p-1}]

  • 运用Mobius反演,不难得出(sum_{d|n}varphi(d) = n)。
  • 当(n>1)时,(1..n)中与(n)互质的整数和为(frac{nvarphi(n)}{2})
  • 降幂大法[A^B mod C=A^{B mod
    varphi(C)+varphi(C)} mod C]

2.3.15

3.1.2.4线性筛法求解积性函数
  • 积性函数的关键是如何求(f(p^k))。
  • 观察线性筛法中的步骤,筛掉n的同时还得到了他的最小的质因数(p),我们希望能够知道(p)在(n)中的次数,这样就能够利用(f(n)=f(p^k)f(frac{n}{p^k}))求出(f(n))。
  • 令(n=pm),由于(p)是(n)的最小质因数,若(p^2|n),则(p|m),并且(p)也是(m)的最小质因数。这样在筛法的同时,记录每个合数最小质因数的次数,就能算出新筛去合数最小质因数的次数。
  • 但是这样还不够,我们还要能够快速求解(f(p^k)),这时一般就要结合(f)函数的性质来考虑。
  • 例如欧拉函数(varphi),(varphi(p^k)=(p-1)p^{k-1}),因此进行筛法求(varphi(p*m))时,如果(p|m),那么(p*m)中(p)的次数不为1,所以我们可以从(m)中分解出(p),那么(varphi(p*m) = varphi(m) *
    p),否则(varphi(p * m)
    =varphi(m) * (p-1))。

  • 再例如默比乌斯函数(mu),只有当(k=1)时(mu(p^k)=-1),否则(mu(p^k)=0),和欧拉函数一样根据(m)是否被(p)整除判断。

    void Linear_Shaker(int N) {
    phi[1] = mu[1] = 1;
    for (int i = 2; i <= N; i++) {

    if (!phi[i]) {
      phi[i] = i - 1;
      mu[i] = -1;
      prime[cnt++] = i;
    }
    for (int j = 0; j < cnt; j++) {
      if (prime[j] * i > N)
        break;
      if (i % prime[j] == 0) {
        phi[i * prime[j]] = phi[i] * prime[j];
        mu[i * prime[j]] = 0;
        break;
      } else {
        phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        mu[i * prime[j]] = -mu[i];
      }
    }
    

    }
    for (int i = 2; i <= N; i++) {

    phi[i] += phi[i - 1];
    mu[i] += mu[i - 1];
    

    }
    }

题目

螺丝和螺帽。(G.J.E.Rawlins)
假设有 N 个螺丝和 N 个螺帽混在一堆,你需要快速将它们配对。
一个螺丝只会匹配一个螺帽,一个螺帽也只会匹配一个螺丝。
你可以试着把一个螺丝和一个螺帽拧在一起看看谁大了,但不能直接比较两个螺丝或者两个螺帽。
给出一个解决这个问题的有效方法。

3.1.2.5线性筛逆元

令(f(i))为(i)在(mod
p)意义下的逆元。显然这个函数是积性函数,我们可以使用线性筛求。但是其实没有那么麻烦。

我们设(p = ki+r),那么(ki+r equiv 0 (mod
p)),两边同时乘(i^{-1}r^{-1}),有(kr^{-1}+i^{-1}equiv 0),那么(i^{-1} equiv -kr^{-1}=-lfloor frac {p}{i}
rfloor * (p mod i)^{-1}),这样就可以递推了。

void getinv(int n) {
  inv[1] = 1;
  for(int i = 2; i <= x; i++)
    inv[i] = (long long)(p - p/i)*inv[p % i] % p;
}

有了逆元,我们就可以预处理阶乘的逆元

[n!^{-1} equiv prod_{k=1}^n k^{-1}
mod p]

解答

事实上只需要修改快速排序的切分方法,分两次进行切分。
首先选第一个螺母作为枢轴,找到对应的螺丝($ O(n)
$)放到第一位,对螺丝数组进行切分。
然后再用找到的螺丝对螺母数组进行切分。

螺母类,实现了对螺丝类的 IComparable 接口

/// <summary>
/// 螺母类。
/// </summary>
public class Nut<T> : IComparable<Bolt<T>> where T : IComparable<T>
{
    /// <summary>
    /// 螺母的值。
    /// </summary>
    public T Value { get; set; }

    /// <summary>
    /// 螺母的构造函数。
    /// </summary>
    /// <param name="value">螺母的值。</param>
    public Nut(T value) => this.Value = value;

    /// <summary>
    /// 比较方法,螺母只能和螺丝比较。
    /// </summary>
    /// <param name="other">需要比较的螺丝。</param>
    /// <returns></returns>
    public int CompareTo(Bolt<T> other)
    {
        return this.Value.CompareTo(other.Value);
    }
}

类似的有螺丝类。

/// <summary>
/// 螺丝类。
/// </summary>
public class Bolt<T> : IComparable<Nut<T>> where T : IComparable<T>
{
    /// <summary>
    /// 螺丝的值。
    /// </summary>
    public T Value { get; set; }

    /// <summary>
    /// 螺丝的默认构造函数。
    /// </summary>
    /// <param name="value">螺丝的值。</param>
    public Bolt(T value) => this.Value = value;

    /// <summary>
    /// 比较方法,螺丝只能和螺母比较。
    /// </summary>
    /// <param name="other">需要比较的螺母。</param>
    /// <returns></returns>
    public int CompareTo(Nut<T> other)
    {
        return this.Value.CompareTo(other.Value);
    }
}

3.1.3默比乌斯反演与狄利克雷卷积

代码

修改后的排序方法。

using System;

namespace _2._3._15
{
    /// <summary>
    /// 用快排的方式解决螺母和螺帽的问题。
    /// </summary>
    public class BoltsAndNuts
    {
        private readonly Random random = new Random();

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public BoltsAndNuts() { }

        /// <summary>
        /// 对螺丝和螺母排序。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="bolts">螺母数组。</param>
        /// <param name="nuts">螺丝数组。</param>
        public void Sort<T>(Bolt<T>[] bolts, Nut<T>[] nuts) where T : IComparable<T>
        {
            if (bolts.Length != nuts.Length)
                throw new ArgumentException("数组长度必须一致");

            Shuffle(bolts);
            Shuffle(nuts);
            Sort(bolts, nuts, 0, bolts.Length - 1);
        }

        /// <summary>
        /// 对螺丝和螺母排序。
        /// </summary>
        /// <typeparam name="T">需要排序的元素类型。</typeparam>
        /// <param name="bolts">螺母数组。</param>
        /// <param name="nuts">螺丝数组。</param>
        /// <param name="lo">起始下标。</param>
        /// <param name="hi">终止下标。</param>
        public void Sort<T>(Bolt<T>[] bolts, Nut<T>[] nuts, int lo, int hi) where T : IComparable<T>
        {
            if (hi <= lo)
                return;
            int j = Partition(bolts, nuts, lo, hi);
            Sort(bolts, nuts, lo, j - 1);
            Sort(bolts, nuts, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="bolts">螺母数组。</param>
        /// <param name="nuts">螺丝数组。</param>
        /// <param name="lo">起始下标。</param>
        /// <param name="hi">终止下标。</param>
        /// <returns>切分位置。</returns>
        private int Partition<T>(Bolt<T>[] bolts, Nut<T>[] nuts, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            Bolt<T> pivotB = bolts[lo];
            // 找到对应螺丝
            for (int k = lo; k <= hi; k++)
            {
                if (nuts[k].CompareTo(pivotB) == 0)
                {
                    Exch(nuts, k, lo);
                    break;
                }
            }
            // 先用螺母去套螺丝
            while (true)
            {
                while (nuts[++i].CompareTo(pivotB) < 0)
                    if (i == hi)
                        break;
                while (pivotB.CompareTo(nuts[--j]) < 0)
                    if (j == lo)
                        break;

                if (i >= j)
                    break;
                Exch(nuts, i, j);
            }
            Exch(nuts, lo, j);

            // 再用螺丝去比较螺母
            Nut<T> pivotN = nuts[j];
            i = lo;
            j = hi + 1;
            while (true)
            {
                while (bolts[++i].CompareTo(pivotN) < 0)
                    if (i == hi)
                        break;
                while (pivotN.CompareTo(bolts[--j]) < 0)
                    if (j == lo)
                        break;

                if (i >= j)
                    break;

                Exch(bolts, i, j);
            }
            Exch(bolts, lo, j);

            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + this.random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }

        /// <summary>
        /// 交换两个元素。
        /// </summary>
        /// <typeparam name="T">元素类型。</typeparam>
        /// <param name="a">需要交换的第一个元素。</param>
        /// <param name="b">需要交换的第二个元素。</param>
        private void Exch<T>(T[] a, int lo, int hi)
        {
            T t = a[lo];
            a[lo] = a[hi];
            a[hi] = t;
        }
    }
}
3.1.3.1初等积性函数(mu)

(mu)就是容斥系数。
[ mu(n) = begin{cases} 0, & text{if
$exists x^2|n$} \ (-1)^k&n=prod_limits{i=1}^{k}p_i \
end{cases} ]
(mu)函数也是一个积性函数。

下面的公式可以从容斥的角度理解。
[ sum_{d|n}mu(d)=[n=1] ]

另请参阅

下面这个网站给出了这道题的解法,还给出了另一种确定性算法(非随机的算法)的论文链接。
Matching Nuts and Bolts –
Solution

3.1.3.2默比乌斯反演

首先给出Mobius反演的公式:

[ F(n)=sum_{d|n}f(d) Rightarrow
f(n)=sum_{d|n}mu(frac{n}{d})F(d) ]
有两种常见的证明,一种是运用Dirichlet卷积,一种是使用初等方法。

证明:
[ sum_{d|n}mu(d)F(frac{n}{d}) =
sum_{d|n}mu(frac{n}{d})F(d)=sum_{d|n}mu(frac{n}{d})sum_{k|d}f(k)\=sum_{d|n}sum_{k|d}mu(frac{n}{d})f(k)=sum_{k|n}sum_{d|frac{n}{k}}mu(frac{n}{kd})f(k)\
=sum_{k|n}sum_{d|frac{n}{k}}mu(d)f(k)=sum_{k|n}[frac{n}{k}
= 1]f(k)=f(n) ]
默比乌斯反演的另一种形式:
[ F(n)=sum_{n|d}f(d)Rightarrow
f(n)=sum_{n|d}mu(frac{d}{n})F(d) ]
这个式子的证明与上式大同小异,我在这里写一下关键步骤
[
sum_{n|d}sum_{d|k}mu(frac{d}{n})f(k)=sum_{n|k}sum_{d|frac{k}{n}}mu(d)f(k)=f(n)
]
对于一些函数(f(n)),如果我们很难直接求出他的值,而容易求出倍数和或者因数和(F(n)),那么我们可以通过默比乌斯反演来求得(f(n))的值

2.3.16

3.1.3.3狄利克雷卷积

定义两个数论函数(f(x)),(g(x))的(Dirichlet)卷积
[ (f*g)(n)=sum_{d|n}f(d)g(frac nd)
]
Dirichlet卷积满足交换律,结合律,分配律,单位元。

运用狄利克雷卷积不难证明默比乌斯反演。

题目

最佳情况。
编写一段程序来生成使算法 2.5 中的 sort()
方法表现最佳的数组(无重复元素):
数组大小为 N 且不包含重复元素,每次切分后两个子数组的大小最多差 1
(子数组的大小与含有 N 个相同元素的数组的切分情况相同)。
(对于这道练习,我们不需要在排序开始时打乱数组。)

3.1.4积性函数求和与杜教筛

解答

官方实现见:

类似于快速排序的结构,只要中点的两边都是最佳情况,那么整个数组就是最佳情况了。
具体方法是:
首先构造一个有序数组,
然后找到中点(作为枢轴),
对中点左右两侧子数组进行构造,
将选择的枢轴放到开始处(a[lo])。

3.1.4.1概述

如果能通过狄利克雷卷积构造一个更好计算前缀和的函数,且用于卷积的另一个函数也易计算,则可以简化计算过程。

设(f(n))为一个数论函数,需要计算(S(n)=sum_{i=1}^n f(i))。

根据函数(f(n))的性质,构造一个(S(n))关于(S(lfloor frac ni
rfloor))的递推式,如下例:

找到一個合适的数论函数(g(x))
[ sum_{i=1}^nsum_{d|i}f(d)g(frac
id)=sum_{i=1}^ng(i)S(lfloorfrac nirfloor) ]
可以得到递推式
[
g(1)S(n)=sum_{i=1}^n(f*g)(i)-sum_{i=2}^ng(i)S(lfloor
frac{n}{i}rfloor) ]
在递推计算(S(n))的过程中,需要被计算的(S(lfloor frac ni rfloor))只有(O(sqrt n))种。

代码

用于构造最佳数组的类。

namespace Quick
{
    /// <summary>
    /// 构建快速排序最佳情况的类。
    /// </summary>
    public class QuickBest
    {
        /// <summary>
        /// 构造函数,这个类不应该被实例化。
        /// </summary>
        private QuickBest() { }

        /// <summary>
        /// 构造适用于快速排序的最佳数组。
        /// </summary>
        /// <param name="n">数组长度。</param>
        /// <returns></returns>
        public static int[] Best(int n)
        {
            int[] a = new int[n];
            for (int i = 0; i < n; i++)
            {
                a[i] = i;
            }
            Best(a, 0, n - 1);
            return a;
        }

        /// <summary>
        /// 递归的构造数组。
        /// </summary>
        /// <param name="a">需要构造的数组。</param>
        /// <param name="lo">构造的起始下标。</param>
        /// <param name="hi">构造的终止下标。</param>
        private static void Best(int[] a, int lo, int hi)
        {
            if (hi <= lo)
                return;
            int mid = lo + (hi - lo) / 2;
            Best(a, lo, mid - 1);
            Best(a, mid + 1, hi);
            Exch(a, lo, mid);
        }

        /// <summary>
        /// 交换数组中的两个元素。
        /// </summary>
        /// <typeparam name="T">数组的元素类型。</typeparam>
        /// <param name="a">包含要交换元素的数组。</param>
        /// <param name="x">需要交换的第一个元素下标。</param>
        /// <param name="y">需要交换的第二个元素下标。</param>
        private static void Exch(int[] a, int x, int y)
        {
            int t = a[x];
            a[x] = a[y];
            a[y] = t;
        }
    }
}

用于测试的方法

using System;
using Quick;

namespace _2._3._16
{
    /*
     * 2.3.16
     * 
     * 最佳情况。
     * 编写一段程序来生成使算法 2.5 中的 sort() 方法表现最佳的数组(无重复元素):
     * 数组大小为 N 且不包含重复元素,
     * 每次切分后两个子数组的大小最多差 1
     * (子数组的大小与含有 N 个相同元素的数组的切分情况相同)。
     * (对于这道练习,我们不需要在排序开始时打乱数组。)
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSortAnalyze quick = new QuickSortAnalyze
            {
                NeedShuffle = false,            // 关闭打乱
                NeedPath = true                 // 显示排序轨迹
            };
            int[] a = QuickBest.Best(10);
            for (int i = 0; i < 10; i++)
            {
                Console.Write(a[i] + " ");
            }
            Console.WriteLine();
            quick.Sort(a);
            for (int i = 0; i < 10; i++)
            {
                Console.Write(a[i] + " ");
            }
            Console.WriteLine();
        }
    }
}
3.1.4.1欧拉函数求前缀和

利用(varphi *
I=id)的性质,可以有:
[
S(n)=sum_{i=1}^ni-sum_{i=2}^nS(lfloor frac nirfloor)
]

另请参阅

Quick

3.1.4.2默比乌斯函数前缀和

利用(mu * I =
e)的性质,可以有:
[ S(n)=1-sum_{i=2}^nS(lfloorfrac
nirfloor) ]

2.3.17

3.1.4.3模板
ll get_p(int x) { return (x <= m) ? phi[x] : p[n / x]; };
ll get_q(int x) { return (x <= m) ? mu[x] : q[n / x]; };
void solve(ll x) {
  if (x <= m)
    return;
  int i, last = 1, t = n / x;
  if (vis[t])
    return;
  vis[t] = 1;
  p[t] = ((x + 1) * x) >> 1;
  q[t] = 1;
  while (last < x) {
    i = last + 1;
    last = x / (x / i);
    solve(x / i);
    p[t] -= get_p(x / i) * (last - i + 1);
    q[t] -= get_q(x / i) * (last - i + 1);
  }
}
//注:本代码为了避免数组过大,p[]和q[]记录的是分母的值。
题目

哨兵。
修改算法 2.5,去掉内循环 while 中的边界检查。
由于切分元素本身就是一个哨兵(v 不可能小于
a[lo]),左侧边界检查是多余的。
要去掉另一个检查,可以在打乱数组后将数组的最大元素方法 a[length – 1]
中。
该元素永远不会移动(除非和相等的元素交换),可以在所有包含它的子数组中成为哨兵。
注意:在处理内部子数组时,右子数组中最左侧的元素可以作为左子数组右边界的哨兵。

3.1.5中国剩余定理

中国剩余定理给出了以下的一元线性同余方程组有解的判定条件:
[ left{ begin{array}{c} x equiv
a_1 pmod {m_1}\ x equiv a_2 pmod {m_2}\ vdots \ x
equiv a_n pmod {m_n} end{array} right. ]
中国剩余定理指出,如果模数两两互质,那么方程组有解,并且通解可以构造得到:

  1. 设(M = prod_{i=1}^n
    m_i),并设(M_i=frac{M}{m_i})。
  2. 设(t_i=M_i^{-1} pmod
    {m_i})。
  3. 那么通解(x = sum_{i=1}^n
    a_it_iM_i)。
解答

按照题意修改代码即可,在调用 Suffle()
之后添加一段用于寻找最大值的方法($ O(n) $)。

/// <summary>
/// 用快速排序对数组 a 进行升序排序。
/// </summary>
/// <typeparam name="T">需要排序的类型。</typeparam>
/// <param name="a">需要排序的数组。</param>
public override void Sort<T>(T[] a)
{
    Shuffle(a);

    // 把最大元素放到最后一位
    int maxIndex = 0;
    for (int i = 0; i < a.Length; i++)
    {
        if (Less(a[maxIndex], a[i]))
            maxIndex = i;
    }
    Exch(a, maxIndex, a.Length - 1);

    Sort(a, 0, a.Length - 1);
    Debug.Assert(IsSorted(a));
}

3.1.6高斯消元

Gauss消元法就是使用初等行列式变换把原矩阵转化为上三角矩阵然后回套求解。给定一个矩阵以后,我们考察每一个变量,找到它的系数最大的一行,然后根据这一行去消除其他的行。

double a[N][N]
void Gauss(){
    for(int i=1;i<=n;i++){
        int r=i;
        for(int j=i+1;j<=n;j++)
            if(abs(a[j][i])>abs(a[r][i])) r=j;
        if(r!=i) for(int j=1;j<=n+1;j++) swap(a[i][j],a[r][j]);

        for(int j=i+1;j<=n;j++){
            double t=a[j][i]/a[i][i];
            for(int k=i;k<=n+1;k++) a[j][k]-=a[i][k]*t;
        }
    }
    for(int i=n;i>=1;i--){
        for(int j=n;j>i;j--) a[i][n+1]-=a[j][n+1]*a[i][j];
        a[i][n+1]/=a[i][i];
    }
}

对于xor运算,我们可以使用同样的方法消元。

另外,xor的话可以使用bitset压位以加速求解。

代码

修改后的快速排序类。

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._17
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortX : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortX() { }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);

            // 把最大元素放到最后一位
            int maxIndex = 0;
            for (int i = 0; i < a.Length; i++)
            {
                if (Less(a[maxIndex], a[i]))
                    maxIndex = i;
            }
            Exch(a, maxIndex, a.Length - 1);

            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        private void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;
            int j = Partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v)) ;
             //     if (i == hi)
             //         break;
                while (Less(v, a[--j])) ;
             //     if (j == lo)
             //         break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}

主方法。

using System;
using Quick;

namespace _2._3._17
{
    /*
     * 2.3.17
     * 
     * 哨兵。
     * 修改算法 2.5,去掉内循环 while 中的边界检查。
     * 由于切分元素本身就是一个哨兵(v 不可能小于 a[lo]),
     * 左侧边界检查是多余的。
     * 要去掉另一个检查,可以在打乱数组后将数组的最大元素方法 a[length - 1] 中。
     * 该元素永远不会移动(除非和相等的元素交换),
     * 可以在所有包含它的子数组中成为哨兵。
     * 注意:在处理内部子数组时,
     * 右子数组中最左侧的元素可以作为左子数组右边界的哨兵。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quick = new QuickSort();
            QuickSortX quickSortX = new QuickSortX();
            int arrayLength = 1000000;
            int[] a = SortCompare.GetRandomArrayInt(arrayLength);
            int[] b = new int[arrayLength];
            a.CopyTo(b, 0);

            double time1 = SortCompare.Time(quick, a);
            double time2 = SortCompare.Time(quickSortX, b);
            Console.WriteLine("QSorttQSort with Sentinelst");
            Console.WriteLine(time1 + "t" + time2 + "t");
        }
    }
}

3.1.7大步小步BSGS算法

大步小步算法用于解决:

已知(A,B,C),求(x)使得, 其中(C is a prime).
[ A^xequiv Bpmod C ]
我们令(x=itimes m-frac{j}{m}=lceil
sqrt C rceil, i in [1,m], j in [0,m])

那么原式就变成了[A^{im}=A^jtimes
B] .我们先枚举(j),把(A^j
times B)加入哈希表,然后枚举(i),在表中查找(A^{im}),如果找到了,就找到了一个解。时间复杂度为(Theta (sqrt n))。

ll BSGS(ll A, ll B, ll C) {
    mp.clear();
    if(A % C == 0) return -2;
    ll m = ceil(sqrt(C));
    ll ans;
    for(int i = 0; i <= m; i++) {
        if(i == 0) {
            ans = B % C;
            mp[ans] = i;
            continue;
        }
        ans = (ans * A) % C;
        mp[ans] = i;
    }
    ll t = pow(A, m, C); 
    ans = t;
    for(int i = 1; i <= m; i++) {
        if(i != 1)ans = ans * t % C;
        if(mp.count(ans)) {
            int ret = i * m % C - mp[ans] % C;
            return (ret % C + C)%C;
        }
    }
    return -2;
} 
另请参阅

Quick

3.2组合数学

2.3.18

3.2.1组合计数与二项式定理

题目

三取样切分。
为快速排序实现正文所述的三取样切分(参见 2.3.3.2
节)。运行双倍测试来确认这项改动的效果。

3.2.1.1二项式定理

[ (a+b)^n=sum_{i=0}^n C_n^i
a^{i}b^{n-i} ]

其中(C_n^m)为二项式系数,满足几个结论:
[ C_n^i=C_n^{n-i} ]

[ C_{n+1}^m=C_n^m+C_n^{m-1} ]

[ sum_{i=0}^nC_n^i=2^n ]

[ C_n^k=frac{k}{n}C_{n-1}^{k-1}
]

解答

每次切分时都取前三个元素的中位数作为枢轴,这可以带来约 5%~10%
的性能提升。
这里通过三次比较将前三个数排序,然后把三个数中的中位数放到数组开头,最大值放到数组末尾。
最大值被放到了末尾,枢轴不可能大于末尾的这个数,因此右边界判断可以去掉。
同时由于枢轴不可能小于自身,因此左边界判断也可以去掉。
这样就可以把切分中的两个边界判断全部去掉了。
最后对于大小为 2 的数组做特殊处理,通过一次比较直接排序并返回。

测试结果:
图片 17

3.2.1.2排列组合
  • 隔板法与插空法

  • n元素集合的循环r排列的数目是(frac{P_n^r}r)

  • 多重集合全排列[frac{n!}{prod_i
    n_i!}]

  • 多重集合的组合,无限重复数,设S是有k种类型对象的多重集合,r组合的个数为[C_{r+k-1}^r=C_{r+k-1}^{k-1}]。

  • (Lucas)定理(p为素数) :
    [ C_n^m equiv C_{n / p}^{m/p}
    times C_{n mod p}^{m mod p} pmod p ]

    int C(int n, int m, int P) {

    if (n < m) return 0;
    return (ll)fac[n] * inv(fac[n-m], P) % P * inv(fac[m], P)%P;
    

    }
    int lucas(int n, int m, int P) {

    if(!n && !m) return 1;
    return (ll)lucas(n/P, m/P, P) * C(n%P, m%P, P) % P;
    

    }

代码

QuickSortMedian3

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._18
{
    /// <summary>
    /// 三取样快速排序
    /// </summary>
    public class QuickSortMedian3 : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortMedian3() {}

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        private void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;

            // 只有两个元素的数组直接排序
            if (hi == lo + 1)
            {
                if (Less(a[hi], a[lo]))
                    Exch(a, lo, hi);

                return;
            }

            int j = Partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;

            if (Less(a[lo + 1], a[lo]))
                Exch(a, lo + 1, lo);
            if (Less(a[lo + 2], a[lo]))
                Exch(a, lo + 2, lo);
            if (Less(a[lo + 2], a[lo + 1]))
                Exch(a, lo + 1, lo + 2);

            Exch(a, lo, lo + 1);        // 中位数放最左侧
            Exch(a, hi, lo + 2);        // 较大的值放最右侧作为哨兵

            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v)) ;
                while (Less(v, a[--j])) ;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}

测试用例

using System;
using Quick;

namespace _2._3._18
{
    /*
     * 2.3.18
     * 
     * 三取样切分。
     * 为快速排序实现正文所述的三取样切分(参见 2.3.3.2 节)。
     * 运行双倍测试来确认这项改动的效果。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quickNormal = new QuickSort();
            QuickSortMedian3 quickMedian = new QuickSortMedian3();
            int arraySize = 200000;                         // 初始数组大小。
            const int trialTimes = 4;                       // 每次实验的重复次数。
            const int trialLevel = 5;                       // 双倍递增的次数。

            Console.WriteLine("ntmediantnormaltratio");
            for (int i = 0; i < trialLevel; i++)
            {
                double timeMedian = 0;
                double timeNormal = 0;
                for (int j = 0; j < trialTimes; j++)
                {
                    int[] a = SortCompare.GetRandomArrayInt(arraySize);
                    int[] b = new int[a.Length];
                    a.CopyTo(b, 0);
                    timeNormal += SortCompare.Time(quickNormal, b);
                    timeMedian += SortCompare.Time(quickMedian, a);

                }
                timeMedian /= trialTimes;
                timeNormal /= trialTimes;
                Console.WriteLine(arraySize + "t" + timeMedian + "t" + timeNormal + "t" + timeMedian / timeNormal);
                arraySize *= 2;
            }
        }
    }
}

3.2.2常见数列

  • 错位排列 [D_n = (n-1) * (D_{n-1} +
    D_{n-2})]
  • Catanlan数
    [C(n) = sum (C(n-I) *
    C(I))]
    计算公式:
    [C(n) =
    frac{C(2n,n)}{n+1}]
    应用:
    满足递推关系的均可表示成catalan数,比如:
    出栈顺序,二叉树种类个数,门票问题,格子问题(不穿过对角线),括号配对问题等等。
另请参阅

Quick

3.2.3置换群与(Polya)定理

  • (Burnside)引理((Z_k):(k)不动置换类,(c_1(a)):一阶循环的个数:
    [l=frac1{|G|}sum_{k=1}^n|Z_k|=frac1{|G|}sum_{j=1}^gc_1(a_j)]
  • 设置换群G作用于有限集合χ上,用k种颜色涂染集合χ中的元素,则χ在G作用下等价类的数目为((m(f))为置换(f)的循环节):[N=frac 1{|G|}sum_{f in
    G}k^{m(f)}]

2.3.19

3.2.4容斥原理

[
|cup_{i=1}^nA_i|=sum_{i=1}^nA_i-sum_{i,j:inot=j}|A_i cap
A_j|+sum_{i,j,k:inot=jnot=k}|A_i cap A_j cap A_k|-cdots
pm |A_1 cap cdots cap A_n| ]

void calc(){
    for(int i = 1; i < (1 << ct); i++) {
        //do sth
        for(int j = 0; j < ct; j++) {
            if(i & (1 << j)) {
                cnt++;
                //do sth 
            }
        }
        if(cnt & 1) ans += tmp;
        else ans -= tmp;
    }
}
题目

五取样切分。
实现一种基于随机抽取子数组中 5 个元素并取中位数进行切分的快速排序。
将取样元素放在数组的一侧以保证只有中位数元素参与了切分。
运行双倍测试来确定这项改动的效果,并和标准的快速排序以及三取样的快速排序(请见上一道练习)进行比较。
附加题:找到一种对于任意输入都只需要少于 7 次比较的五取样算法。

3.3常见结论与技巧

解答

主要介绍一下这个少于七次比较的五取样算法。
首先假设五个数字为 a b c d e
对 b c 排序,d e 排序。(两次比较)
比较 b 和 d,把较小那一组换到 b c 的位置上去。(一次比较)
此时会有 b < c, b < d < e。
交换 a, b,重新对 b c 排序。(一次比较)
再次比较 b 和 d,把较小的那一组换到 b c 的位置上。(一次比较)
最后比较 c 和 d,较小的那一个即为中位数。(一次比较)
总共需要 6 次比较,严格小于 7 次。

取样完毕后,a b 是最小值和次小值(这里没有对应关系,a
也可以是次小值)。
d 和 e 是最大值和次大值(同样没有对应关系)。
我们把 d 和 e 放到数组的最后作为哨兵,去掉右边界的判断。
同时让左右两侧指针都向中间移动两位,减少不必要的比较。

测试结果,对比普通快排性能提升约 10%,和三取样快排区别不大。
图片 18

3.3.1裴蜀定理

若a,b是整数,且(a,b)=d,那么对于任意的整数x,y,ax+by都一定是d的倍数,特别地,一定存在整数x,y,使ax+by=d成立。

它的一个重要推论是:a,b互质的充要条件是存在整数x,y使ax+by=1.

代码

五取样快排

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._19
{
    /// <summary>
    /// 五取样快速排序
    /// </summary>
    public class QuickSortMedian5 : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortMedian5() {}

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        private void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;

            // 少于五个元素的数组直接进行插入排序
            if (hi - lo + 1 < 5)
            {
                int n = hi - lo + 1;
                for (int i = lo; i - lo < n; i++)
                {
                    for (int k = i; k > 0 && Less(a[k], a[k - 1]); --k)
                    {
                        Exch(a, k, k - 1);
                    }
                }

                return;
            }

            int j = Partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;

            // 假设为 a b c d e 五个数字
            // 首先对 b c 排序
            if (Less(a[lo + 2], a[lo + 1]))
                Exch(a, lo + 2, lo + 1);
            // 然后再排序 d e
            if (Less(a[lo + 4], a[lo + 3]))
                Exch(a, lo + 4, lo + 3);

            // 这时满足 b < c, d < e
            // 比较 b d,把较小的一组放到 b c 的位置上去
            if (Less(a[lo + 3], a[lo + 1]))
            {
                Exch(a, lo + 1, lo + 3);
                Exch(a, lo + 2, lo + 4);
            }

            // 这时满足 b < c, b < d < e,即 b 是 b c d e 中的最小值
            // 交换 a 和 b
            Exch(a, lo, lo + 1);

            // 重新排序 b c
            if (Less(a[lo + 2], a[lo + 1]))
                Exch(a, lo + 2, lo + 1);

            // 这时再次满足 b < c, d < e
            // 比较 b d,把最小的一组放到 b c 的位置上去
            if (Less(a[lo + 3], a[lo + 1]))
            {
                Exch(a, lo + 1, lo + 3);
                Exch(a, lo + 2, lo + 4);
            }

            // 这时 a 和 b 为五个数中的最小值和次小值(顺序不固定,a 也可以是次小值)
            // 最后比较 c 和 d,较小的那一个即为中位数(即第三小的数)
            if (Less(a[lo + 3], a[lo + 2]))
                Exch(a, lo + 3, lo + 2);

            // 此时 c 即为中位数
            Exch(a, lo, lo + 2);

            // d e 放到数组末尾充当哨兵
            Exch(a, lo + 3, hi);
            Exch(a, lo + 4, hi - 1);

            // 调整指针位置,前两位和后两位都已经在合适位置了
            j -= 2;
            i += 2;

            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v)) ;
                while (Less(v, a[--j])) ;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}

三取样快排

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._19
{
    /// <summary>
    /// 三取样快速排序
    /// </summary>
    public class QuickSortMedian3 : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortMedian3() {}

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        private void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;

            // 少于五个元素的数组直接进行插入排序
            if (hi - lo + 1 < 5)
            {
                int n = hi - lo + 1;
                for (int i = lo; i - lo < n; i++)
                {
                    for (int k = i; k > 0 && Less(a[k], a[k - 1]); --k)
                    {
                        Exch(a, k, k - 1);
                    }
                }

                return;
            }

            int j = Partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;

            if (Less(a[lo + 1], a[lo]))
                Exch(a, lo + 1, lo);
            if (Less(a[lo + 2], a[lo]))
                Exch(a, lo + 2, lo);
            if (Less(a[lo + 2], a[lo + 1]))
                Exch(a, lo + 1, lo + 2);

            Exch(a, lo, lo + 1);        // 中位数放最左侧
            Exch(a, hi, lo + 2);        // 较大的值放最右侧作为哨兵

            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v)) ;
                while (Less(v, a[--j])) ;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}

测试用例

using System;
using Quick;

namespace _2._3._19
{
    /*
     * 2.3.19
     * 
     * 五取样切分。
     * 实现一种基于随机抽取子数组中 5 个元素并取中位数进行切分的快速排序。
     * 将取样元素放在数组的一侧以保证只有中位数元素参与了切分。
     * 运行双倍测试来确定这项改动的效果,
     * 并和标准的快速排序以及三取样的快速排序(请见上一道练习)进行比较。
     * 附加题:找到一种对于任意输入都只需要少于 7 次比较的五取样算法。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quickNormal = new QuickSort();
            QuickSortMedian3 quickMedian3 = new QuickSortMedian3();
            QuickSortMedian5 quickMedian5 = new QuickSortMedian5();
            int arraySize = 200000;                         // 初始数组大小。
            const int trialTimes = 4;                       // 每次实验的重复次数。
            const int trialLevel = 6;                       // 双倍递增的次数。

            Console.WriteLine("ntmedian5tmedian3tnormaltmedian5/normalttmedian5/median3");
            for (int i = 0; i < trialLevel; i++)
            {
                double timeMedian3 = 0;
                double timeMedian5 = 0;
                double timeNormal = 0;
                for (int j = 0; j < trialTimes; j++)
                {
                    int[] a = SortCompare.GetRandomArrayInt(arraySize);
                    int[] b = new int[a.Length];
                    int[] c = new int[a.Length];
                    a.CopyTo(b, 0);
                    a.CopyTo(c, 0);
                    timeNormal += SortCompare.Time(quickNormal, a);
                    timeMedian3 += SortCompare.Time(quickMedian3, b);
                    timeMedian5 += SortCompare.Time(quickMedian5, c);
                }
                timeMedian5 /= trialTimes;
                timeMedian3 /= trialTimes;
                timeNormal /= trialTimes;
                Console.WriteLine(arraySize + "t" + timeMedian5 + "t" + timeMedian3 + "t" + timeNormal + "t" + timeMedian5 / timeNormal + "t" + timeMedian5/timeMedian3);
                arraySize *= 2;
            }
        }
    }
}

3.3.2底和顶

  • 若连续且单调增的函数(f(x))满足当(f(x))为整数时可推出(x)为整数,则[lfloor f(x) rfloor = lfloor
    f(lfloor x rfloor) rfloor]和(lceil f(x) rceil = lceil f(lceil
    xrceil) rceil)
  • [lfloor frac {lfloorfrac{x}{a}
    rfloor}{b}rfloor = lfloor frac{x}{ab}rfloor]
  • 对于(i),(lfloor frac{n}{lfloor
    frac{n}{i}rfloor}rfloor)是与(i)被(n)除并下取整取值相同的一段区间的右端点
另请参阅

Quick

Code to calculate “median of five” in
C#

3.3.3和式

2.3.20

3.3.3.1三大定律
  • 分配律 [sum_{k in K} c a_k = c
    sum_{k in K} a_k]
  • 结合律[sum_{k in K}(a_k +
    b_k)=sum_{k in K}a_k+sum_{k in K}b_k]
  • 交换律[sum_{k in
    K}a_k=sum_{p(k) in K}
    a_{p(k)}]其中p(k)是n的一个排列
  • 松弛的交换律:若对于每一个整数(n),都恰好存在一个整数(k)使得(p(k)=n),那么交换律同样成立。

    ##### 3.3.3.2求解技巧

  • 扰动法,用于计算一个和式,其思想是从一个未知的和式开始,并记他为(S_n):[S_n=sum_{0 leqslant k leqslant n}
    a_k],然后,通过将他的最后一项和第一项分离出来,用两种方法重写(S_{n+1}),这样我们就得到了一个关于(S_n)的方程,就可以得到其封闭形式了。

  • 一个常见的交换
    [sum_{d|n}f(d)=sum_{d|n}f(frac{n}{d})]

    ##### 3.3.3.3多重和式

  • 交换求和次序:

[
sum_jsum_ka_{j,k}[P(j,k)]=sum_{P(j,k)}a_{j,k}=sum_ksum_ja_{j,k}[P(j,k)]
]

  • 一般分配律:[sum_{j in J, k in
    K}a_jb_k=(sum_{j in J}a_j)(sum_{k in K}b_k)]

  • (Rocky Road)
    [ sum_{j in J}sum_{k in
    K(j)}a_{j,k}=sum_{k in K^{‘}}sum_{j in J^{‘}}a_{j,k}
    ]

[ [j in J][k in K(j)]=[k in
K^{‘}][j in J^{‘}(k)] ]

事实上,这样的因子分解总是可能的:我们可以设(J=K^{‘})是所有整数的集合,而(K(j))和(J^{‘}(K))是与操控二重和式的性质(P(j,k))相对应的集合。下面是一个特别有用的分解。

[[1leqslant j leqslant n][j
leqslant k leqslant n] = [1 leqslant j leqslant k leqslant
n] = [1 leqslant k leqslant n][1 leqslant j leqslant
k]]

  • 一个常见的分解
    [
    sum_{d|n}sum_{k|d}=sum_{k|m}sum_{d|frac{m}{k}}
    ]

  • 一个技巧

如果我们有一个包含(k+f(j))的二重和式,用(k-f(j))替换(k)并对(j)求和比较好。

题目

非递归的快速排序。
实现一个非递归的快速排序,使用一个循环来将弹出栈的子数组切分并将结果子数组重新压入栈。
注意:先将较大的子数组压入栈,这样就可以保证栈最多只会有 lgN 个元素。

3.3.4数论问题的求解技巧

  • ({lfloor frac{n}{i} rfloor|i
    in [1,n]})只有(O(sqrt
    n))种取值。所以可以使用这个结论降低复杂度。

例如,在bzoj2301中,我们最终解出了[f(n,
m)=sum_{1 leqslant d leqslant min(n, m)}mu(d)lfloor frac
{n}{d} rfloor lfloor frac {m}{d}
rfloor]我们就可以使用杜教筛计算出默比乌斯函数的前缀和,计算出商与除以i相同的最多延伸到哪里,下一次直接跳过这一段就好了。下面是这个题的一段程序。

int calc(int n, int m) {
    int ret = 0, last;
    if(n > m) std::swap(n, m);
    for(int i = 1; i <= n; i = last + 1) { //i就相当于原式中的d
        last = min(n / (n/i), m / (m/i));  //last计算了商与除以i相同的最多延伸到哪里,不难证明这样计算的正确性
        ret += (n / i) * (m / i) * (sum[last] - sum[i-1]);
    }
    return ret;
}
解答

事实上就是用一个栈保存每次切分后的子数组下标。
关键代码如下,这里用到的栈(链栈)是在 1.3 中构建的:

/// <summary>
/// 用快速排序对数组 a 进行升序排序。
/// </summary>
/// <typeparam name="T">需要排序的类型。</typeparam>
/// <param name="a">需要排序的数组。</param>
public override void Sort<T>(T[] a)
{
    Shuffle(a);
    Stack<int> stack = new Stack<int>();
    stack.Push(0);
    stack.Push(a.Length - 1);

    while (!stack.IsEmpty())
    {
        // 压入顺序是先 lo,再 hi,故弹出顺序是先 hi 再 lo
        int hi = stack.Pop();
        int lo = stack.Pop();

        if (hi <= lo)
            continue;

        int j = Partition(a, lo, hi);

        // 让较大的子数组先入栈(先排序较小的子数组)
        if (j - lo > hi - j)
        {
            stack.Push(lo);
            stack.Push(j - 1);

            stack.Push(j + 1);
            stack.Push(hi);
        }
        else
        {
            stack.Push(j + 1);
            stack.Push(hi);

            stack.Push(lo);
            stack.Push(j - 1);
        }
    }
    Debug.Assert(IsSorted(a));
}

由于栈操作比函数调用操作耗费时间更长,因此测试后的结果会比原有快排慢 20%
左右。
图片 19

3.3.5一些可能会用到的定理

代码

QuickSortNonRecursive

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._20
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortNonRecursive : BaseSort
    {
        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortNonRecursive() { }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);
            Stack<int> stack = new Stack<int>();
            stack.Push(0);
            stack.Push(a.Length - 1);

            while (!stack.IsEmpty())
            {
                // 压入顺序是先 lo,再 hi,故弹出顺序是先 hi 再 lo
                int hi = stack.Pop();
                int lo = stack.Pop();

                if (hi <= lo)
                    continue;

                int j = Partition(a, lo, hi);

                // 让较大的子数组先入栈(先排序较小的子数组)
                if (j - lo > hi - j)
                {
                    stack.Push(lo);
                    stack.Push(j - 1);

                    stack.Push(j + 1);
                    stack.Push(hi);
                }
                else
                {
                    stack.Push(j + 1);
                    stack.Push(hi);

                    stack.Push(lo);
                    stack.Push(j - 1);
                }
            }
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}

测试用例

using System;
using Quick;

namespace _2._3._20
{
    /*
     * 2.3.20
     * 
     * 非递归的快速排序。
     * 实现一个非递归的快速排序,
     * 使用一个循环来将弹出栈的子数组切分并将结果子数组重新压入栈。
     * 注意:
     * 先将较大的子数组压入栈,这样就可以保证栈最多只会有 lgN 个元素。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quickNormal = new QuickSort();
            QuickSortNonRecursive quickNonRecursive = new QuickSortNonRecursive();
            int arraySize = 200000;                         // 初始数组大小。
            const int trialTimes = 4;                       // 每次实验的重复次数。
            const int trialLevel = 5;                       // 双倍递增的次数。

            Console.WriteLine("ntnon-recursivetnormaltratio");
            for (int i = 0; i < trialLevel; i++)
            {
                double timeRecursive = 0;
                double timeNormal = 0;
                for (int j = 0; j < trialTimes; j++)
                {
                    int[] a = SortCompare.GetRandomArrayInt(arraySize);
                    int[] b = new int[a.Length];
                    a.CopyTo(b, 0);
                    timeNormal += SortCompare.Time(quickNormal, b);
                    timeRecursive += SortCompare.Time(quickNonRecursive, a);

                }
                timeRecursive /= trialTimes;
                timeNormal /= trialTimes;
                Console.WriteLine(arraySize + "t" + timeRecursive + "tt" + timeNormal + "t" + timeRecursive / timeNormal);
                arraySize *= 2;
            }
        }
    }
}

用到的栈的实现

using System;
using System.Collections;
using System.Collections.Generic;
using System.Text;

namespace _2._3._20
{
    /// <summary>
    /// 栈类。
    /// </summary>
    /// <typeparam name="Item">栈中存放的元素类型。</typeparam>
    public class Stack<Item> : IEnumerable<Item>
    {
        private Node<Item> first;
        private int count;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public Stack()
        {
            this.first = null;
            this.count = 0;
        }

        /// <summary>
        /// 复制构造函数。
        /// </summary>
        /// <param name="s"></param>
        public Stack(Stack<Item> s)
        {
            if (s.first != null)
            {
                this.first = new Node<Item>(s.first);
                for (Node<Item> x = this.first; x.next != null; x = x.next)
                {
                    x.next = new Node<Item>(x.next);
                }
            }
            this.count = s.count;
        }

        /// <summary>
        /// 检查栈是否为空。
        /// </summary>
        /// <returns></returns>
        public bool IsEmpty()
        {
            return this.first == null;
        }

        /// <summary>
        /// 返回栈内元素的数量。
        /// </summary>
        /// <returns></returns>
        public int Size()
        {
            return this.count;
        }

        /// <summary>
        /// 将一个元素压入栈中。
        /// </summary>
        /// <param name="item">要压入栈中的元素。</param>
        public void Push(Item item)
        {
            Node<Item> oldFirst = this.first;
            this.first = new Node<Item>();
            this.first.item = item;
            this.first.next = oldFirst;
            this.count++;
        }

        /// <summary>
        /// 将一个元素从栈中弹出,返回弹出的元素。
        /// </summary>
        /// <returns></returns>
        public Item Pop()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Stack Underflow");
            Item item = this.first.item;
            this.first = this.first.next;
            this.count--;
            return item;
        }

        /// <summary>
        /// 返回栈顶元素(但不弹出它)。
        /// </summary>
        /// <returns></returns>
        public Item Peek()
        {
            if (IsEmpty())
                throw new InvalidOperationException("Stack Underflow");
            return this.first.item;
        }

        /// <summary>
        /// 将两个栈连接。
        /// </summary>
        /// <param name="s1">第一个栈。</param>
        /// <param name="s2">第二个栈(将被删除)。</param>
        /// <returns></returns>
        public static Stack<Item> Catenation(Stack<Item> s1, Stack<Item> s2)
        {
            if (s1.IsEmpty())
            {
                s1.first = s2.first;
                s1.count = s2.count;
            }
            else
            {
                Node<Item> last = s1.first;
                while (last.next != null)
                {
                    last = last.next;
                }
                last.next = s2.first;
                s1.count += s2.count;
            }
            s2 = null;
            return s1;
        }

        /// <summary>
        /// 创建栈的浅表副本。
        /// </summary>
        /// <returns></returns>
        public Stack<Item> Copy()
        {
            Stack<Item> temp = new Stack<Item>();
            temp.first = this.first;
            temp.count = this.count;
            return temp;
        }

        public override string ToString()
        {
            StringBuilder s = new StringBuilder();
            foreach (Item n in this)
            {
                s.Append(n);
                s.Append(' ');
            }
            return s.ToString();
        }

        public IEnumerator<Item> GetEnumerator()
        {
            return new StackEnumerator(this.first);
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }

        private class StackEnumerator : IEnumerator<Item>
        {
            private Node<Item> current;
            private Node<Item> first;

            public StackEnumerator(Node<Item> first)
            {
                this.current = new Node<Item>();
                this.current.next = first;
                this.first = this.current;
            }

            Item IEnumerator<Item>.Current => this.current.item;

            object IEnumerator.Current => this.current.item;

            void IDisposable.Dispose()
            {
                this.current = null;
                this.first = null;
            }

            bool IEnumerator.MoveNext()
            {
                if (this.current.next == null)
                    return false;

                this.current = this.current.next;
                return true;
            }

            void IEnumerator.Reset()
            {
                this.current = this.first;
            }
        }
    }
}
3.3.5.1费马小定理

[ a^{p-1}equiv1pmod p ]

条件:(p is prime and
(a,p)=1)

另请参阅

Quick

Generics

3.3.5.2欧拉定理

[ a^{varphi(p)}equiv 1pmod p
]

条件:(a,p in mathbb{Z^+}, (a,
p)=1)

2.3.21

3.3.5.3威尔逊定理

[ (p-1)!equiv-1pmod p Leftrightarrow
p is prime ]

题目

将重复元素排序的比较次数的下界。
完成命题 M 的证明的第一部分。
参考命题 I 的证明并注意当有 $ k $ 个主键值时所有元素存在 $
N!/f_1!f_2!…f_k!$ 种不同的排列,
其中第 $ i $ 个主键值出现的概率为 $ f_1 $(即 $ N_{p_i} $,按照命题 M
的记法),且 $ f_1+… +f_k=N $。

3.3.5.4皮克定理

[ S=n+frac s2-1 ]

(其中(n)表示多边形内部的点数,(s)表示多边形边界上的点数,(S)表示多边形的面积)

解答

首先引入命题 I
的结论,对于互不相同的主键值,基于比较的排序算法的下界等于所形成的比较树的高度,即:
[ h ge log_2{N!} ]
那么我们题目即可转化为求证
[ h ge log_2
(frac{N!}{f_1!f_2!cdots f_k!}) ge log_2 N! ]
这里的 $ f_i $ 为某个主键值出现的频率,即某个主键值出现的次数,因此
(f_ige 1) 。
根据题目给出的条件,如果主键互不重复,此时 $ k=N $,且 $
f_1=f_2=cdots=f_k=1 $ 。
那么 $ f_1!f_2!cdots f_k!=1 $ ,待证式子即为命题 I 的结论。

那么当主键有重复时,此时 $ k < N $,为使 $ f_1+f_2+ cdots +
f_k=N $ ,至少存在一个 $ f_m ge 2 $。
故此时:
[ f_1!f_2!cdots f_k!
>1Rightarrow frac{N!}{f_1!f_2!cdots f_k!}<N! Rightarrow
\ h ge log_2 (frac{N!}{f_1!f_2!cdots f_k!}) ge log_2
N! blacksquare ]
得证。

3.4其他数学工具

另请参阅

lower bounds of sorting-The University of
Maryland

3.4.1快速乘

inline ll mul(ll a, ll b) {
  ll x = 0;
  while (b) {
    if (b & 1)
      x = (x + a) % p;
    a = (a << 1) % p;
    b >>= 1;
  }
  return x;
}

2.3.22

3.4.2快速幂

inline ll pow(ll a, ll b, ll p) {
  ll x = 1;
  while (b) {
    if (b & 1)
      x = mul(x, a);
    a = mul(a, a);
    b >>= 1;
  }
  return x;
}
题目

快速三向切分。(J.Bently,D.McIlroy)
用将重复元素放置于子数组两端的方式实现一个信息量最优的排序算法。
使用两个索引 p 和 q,使得 a[lo…p-1] 和 a[q+1..hi] 的元素都和
a[lo] 相等。
使用另外两个索引 i 和 j,使得 a[p…i-1] 小于 a[lo],a[j+i..q]
大于 a[lo]。
在内循环中加入代码,在 a[i] 和 v 相等时将其与 a[p] 交换(并将 p 加
1),
在 a[j] 和 v 相等且 a[i] 和 a[j] 尚未和 v 进行比较之前将其与
a[q] 交换。
添加在切分循环结束后将和 v 相等的元素交换到正确位置的代码,如图 2.3.6
所示。
请注意:
这里实现的代码和正文中给出的代码时等价的,
因为这里额外的交换用于和切分元素相等的元素,
而正文中的代码将额外的交换用于和切分元素不等的元素。

3.4.3更相减损术

第一步:任意给定两个正整数;判断它们是否都是偶数。若是,则用2约简;若不是则执行第二步。

第二步:以较大的数减较小的数,接着把所得的差与较小的数比较,并以大数减小数。继续这个操作,直到所得的减数和差相等为止。

则第一步中约掉的若干个2与第二步中等数的乘积就是所求的最大公约数。

解答

官方实现见:

快速三向切分

论文引用见「另请参阅」部分。
算法演示
图片 20

Ninther 算法

官方实现中用到了 Ninther 算法用于选取近似中位数(作为枢轴),
该算法由 John Tukey 在 1978 年提出,论文引用见「另请参阅」部分。
这个算法的思想其实很简单,假设我们有三个数 $ y_1, y_2, y_3 $
,那么其中位数为:
[ y_A= {rm median}lbrace
y_1,y_2,y_3 rbrace ]
现在对于九个数,我们以三个为一组,取三个中位数:
[ y_A= {rm median}lbrace
y_1,y_2,y_3 rbrace \ y_B= {rm median}lbrace y_4,y_5,y_6
rbrace \ y_C= {rm median}lbrace y_7,y_8,y_9 rbrace
]
接下来取这三个中位数的中位数,有:
[ y_E= {rm median}lbrace
y_A,y_B,y_C rbrace ]
我们把上述过程封装成函数,即 $ y_E= {rm ninther}lbrace
y_1,y_2,cdots,y_9 rbrace $ 。
于是我们获得的 $ y_E $ 即为近似中位数,如果 $ lbrace
y_1,y_2,cdots,y_9 rbrace $ 是单调数列,那么 $ y_E $ 就是中位数。

获取三个数中的中位数

事实上,我们可以直接画出三个数排列的所有可能,获得决策树。
图片 21
然后根据决策树写出取中位数的算法:

private int Median3<T>(T[] a, int i, int j, int k) where T : IComparable<T>
{
    return
        (Less(a[i], a[j]) ?
        (Less(a[j], a[k]) ? j : Less(a[i], a[k]) ? k : i) :
        (Less(a[k], a[j]) ? j : Less(a[k], a[i]) ? k : i));
}

测试结果

提高约 20% 左右的性能。
图片 22

3.4.4逆元

根据费马小定理(p是质数),

int inv(int x, int P){return pow(x, P-2, P);}

或使用扩展欧几里德:

int inv(int x, int P) {
  int d, a, b;
  gcd(x, P, d, a, b);
  return d == 1 ? (a+P)%P : -1;
}
代码

QuickBentleyMcIlroy

using System;
using System.Diagnostics;

namespace Quick
{
    public class QuickBentleyMcIlroy : BaseSort
    {
        /// <summary>
        /// 小于这个数值的数组调用插入排序。
        /// </summary>
        private readonly int INSERTION_SORT_CUTOFF = 8;

        /// <summary>
        /// 小于这个数值的数组调用中位数作为枢轴。
        /// </summary>
        private readonly int MEDIAN_OF_3_CUTOFF = 40;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickBentleyMcIlroy() { }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 对指定范围内的数组进行排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序的起始下标。</param>
        /// <param name="hi">排序的终止下标。</param>
        private void Sort<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int n = hi - lo + 1;

            if (n <= this.INSERTION_SORT_CUTOFF)
            {
                InsertionSort(a, lo, hi);
                return;
            }
            else if (n <= this.MEDIAN_OF_3_CUTOFF)
            {
                // 对于较小的数组,直接选择左中右三个元素中的中位数作为枢轴。
                int m = Median3(a, lo, lo + n / 2, hi);
                Exch(a, m, lo);
            }
            else
            {
                // 对于较大的数组使用 Turkey Ninther 作为枢轴。
                int eps = n / 8;
                int mid = lo + n / 2;
                int m1 = Median3(a, lo, lo + eps, lo + eps + eps);
                int m2 = Median3(a, mid - eps, mid, mid + eps); 
                int m3 = Median3(a, hi - eps - eps, hi - eps, hi);
                int ninther = Median3(a, m1, m2, m3);
                Exch(a, ninther, lo);
            }

            // 三向切分
            int i = lo, j = hi + 1;
            int p = lo, q = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;

                if (i == j && IsEqual(a[i], v))
                    Exch(a, ++p, i);
                if (i >= j)
                    break;

                Exch(a, i, j);
                if (IsEqual(a[i], v))
                    Exch(a, ++p, i);
                if (IsEqual(a[j], v))
                    Exch(a, --q, j);
            }

            i = j + 1;
            for (int k = lo; k <= p; k++)
                Exch(a, k, j--);
            for (int k = hi; k >= q; k--)
                Exch(a, k, i++);

            Sort(a, lo, j);
            Sort(a, i, hi);
        }

        /// <summary>
        /// 判断两个元素是否值相等。
        /// </summary>
        /// <typeparam name="T">需要判断的元素类型。</typeparam>
        /// <param name="a">进行比较的第一个元素。</param>
        /// <param name="b">进行比较的第二个元素。</param>
        /// <returns>两个元素的值是否相等。</returns>
        private bool IsEqual<T>(T a, T b) where T : IComparable<T>
        {
            return a.CompareTo(b) == 0;
        }

        /// <summary>
        /// 用插入排序对指定范围内的数组排序。
        /// </summary>
        /// <typeparam name="T">数组的元素类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序的起始下标。</param>
        /// <param name="hi">排序的终止下标。</param>
        private void InsertionSort<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            for (int i = lo; i <= hi; i++)
            {
                for (int j = i; j > lo && Less(a[j], a[j - 1]); j--)
                {
                    Exch(a, j, j - 1);
                }
            }
        }

        /// <summary>
        /// 获取三个元素中的中位数。
        /// </summary>
        /// <typeparam name="T">用于排序的元素。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="i">第一个待选元素的下标。</param>
        /// <param name="j">第二个待选元素的下标。</param>
        /// <param name="k">第三个待选元素的下标。</param>
        /// <returns></returns>
        private int Median3<T>(T[] a, int i, int j, int k) where T : IComparable<T>
        {
            return
               (Less(a[i], a[j]) ?
               (Less(a[j], a[k]) ? j : Less(a[i], a[k]) ? k : i) :
               (Less(a[k], a[j]) ? j : Less(a[k], a[i]) ? k : i));
        }
    }
}

测试用例

using System;
using Quick;

namespace _2._3._22
{
    /*
     * 2.3.22
     * 
     * 快速三向切分。(J.Bently,D.McIlroy)
     * 用将重复元素放置于子数组两端的方式实现一个信息量最优的排序算法。
     * 使用两个索引 p 和 q,使得 a[lo...p-1] 和 a[q+1..hi] 的元素都和 a[lo] 相等。
     * 使用另外两个索引 i 和 j,
     * 使得 a[p...i-1] 小于 a[lo],a[j+i..q] 大于 a[lo]。
     * 在内循环中加入代码,在 a[i] 和 v 相当时将其与 a[p] 交换(并将 p 加 1),
     * 在 a[j] 和 v 相等且 a[i] 和 a[j] 尚未和 v 进行比较之前将其与 a[q] 交换。
     * 添加在切分循环结束后将和 v 相等的元素交换到正确位置的代码,如图 2.3.6 所示。
     * 请注意:
     * 这里实现的代码和正文中给出的代码时等价的,
     * 因为这里额外的交换用于和切分元素相等的元素,
     * 而正文中的代码将额外的交换用于和切分元素不等的元素。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quickNormal = new QuickSort();
            QuickBentleyMcIlroy quickBentleyMcIlroy = new QuickBentleyMcIlroy();
            int arraySize = 800000;                         // 初始数组大小。
            const int trialTimes = 1;                       // 每次实验的重复次数。
            const int trialLevel = 8;                       // 双倍递增的次数。

            Console.WriteLine("ntt3waytnormaltratio");
            for (int i = 0; i < trialLevel; i++)
            {
                double timeBentleyMcIlroy = 0;
                double timeNormal = 0;
                for (int j = 0; j < trialTimes; j++)
                {
                    int[] a = SortCompare.GetRandomArrayInt(arraySize);
                    int[] b = new int[a.Length];
                    a.CopyTo(b, 0);
                    timeNormal += SortCompare.Time(quickNormal, b);
                    timeBentleyMcIlroy += SortCompare.Time(quickBentleyMcIlroy, a);

                }
                timeBentleyMcIlroy /= trialTimes;
                timeNormal /= trialTimes;
                if (arraySize < 10000000)
                    Console.WriteLine(arraySize + "tt" + timeBentleyMcIlroy + "t" + timeNormal + "t" + timeBentleyMcIlroy / timeNormal);
                else
                    Console.WriteLine(arraySize + "t" + timeBentleyMcIlroy + "t" + timeNormal + "t" + timeBentleyMcIlroy / timeNormal);
                arraySize *= 2;
            }
        }
    }
}

3.4.5博弈论

  • Nim游戏
  • SG函数

定义[SG(x)=mex(S)],其中(S)是(x)的后继状态的(SG)函数集合,(mex(S))表示不在(S)内的最小非负整数。

  • SG定理

组合游戏和的(SG)函数等于各子游戏(SG)函数的(Nim)和。

另请参阅

有关这种快速排序算法的来源以及三个数的中位数的选取算法,请参阅下面这篇
1993 年的论文:
Bentley J L, McIlroy M D. Engineering a sort function[J]. Software:
Practice and Experience, 1993, 23(11):
1249-1265.
下面这份 2002 年的 PPT 详细解释和分析了官方实现代码的思路和性能:
Sedgewick R, Bentley J. Quicksort is optimal[J]. Knuthfest, Stanford
University, Stanford,
2002.
有关选取中位数 Ninther 算法,请参阅下面这篇 1978 年的论文:
Tukey J W. The ninther, a technique for low-effort robust (resistant)
location in large samples[M]//Contributions to Survey Sampling and
Applied Statistics. 1978:
251-257.
以及按照惯例给出本题用到的类库链接:
Quick

3.4.6概率与数学期望

  • 全概率公式[P(A)=P(A|B_1)*P(B_1)+P(A|B_2)*P(B_2)+cdots+P(A|B_n)*P(B_n)]
  • 数学期望

2.3.23

3.4.7快速傅立叶变换

题目

Java 的排序库函数。
在练习 2.3.22 的代码中使用 Tukey’s ninther
方法来找出切分元素——选择三组,
每组三个元素,分别取三组元素的中位数,然后取三个中位数的中位数作为切分元素,
且在排序小数组时切换到插入排序。

3.4.7.1基本定义

快速傅立叶变换(FFT)用于求解多项式的卷积.

  • 单位根:单位圆的(n)等分点为终点,作(n)个向量,所得的幅角为正且最小的向量对应的复数为(omega_n),称为(n)次单位根.
    [omega_n^k=coskfrac{2pi}{n}+isin
    kfrac{2pi}n]
  • 单位根的性质:[omega_{2n}^{2k}=omega_n^k]
  • 单位根的性质:[omega_{n}^{k+frac
    nk}=-omega _n^k]
解答

官方实现见:
见 2.3.22 的解答,其中已经包含了这些改动。

3.4.7.2快速傅立叶变换

考虑将多项式(A_1(x)=a_0+a_2x^2+a_4x^4+cdots+a_{n-2}x^{frac
n2 -1})

[A_2(x)=a_1+a_3x+a_5x^2+cdots+a_{n-1}x^{frac
n2 -1}]

则有[A(x)=A_1(x)+xA_2(x)]

有[A(omega_n^k)=A_1(omega_n^{2k})+omega_n^kA_2(omega_n^{2k})]

有[A(omega_n^{k+frac
n2})=A_1{omega_frac n2^k-omega_n^kA_2(omega_frac n2 ^
k)}].

注意到,当(k)取遍([0,frac n2 -1])时,(k)和(k+frac n2)取遍了([0,n-1]),也就是说,如果已知(A_1(x))和(A_2(x))在(omega_{n/2}^0,omega_{n/2}^1,cdots,omega_{n/2}^{n/2-1})处的点值,就可以在(O(n))的时间内求得(A(x))在(omega_n^0,omega_n^1,cdots,omega_n^{n-1})处的取值。而关于
(A_1(x)) 和 (A_2(x))
的问题都是相对于原问题规模缩小了一半的子问题,分治的边界为一个常数项(a_0).

该算法的复杂度为(O(nlogn)).

代码

QuickBentleyMcIlroy

using System;
using System.Diagnostics;

namespace Quick
{
    public class QuickBentleyMcIlroy : BaseSort
    {
        /// <summary>
        /// 小于这个数值的数组调用插入排序。
        /// </summary>
        private readonly int INSERTION_SORT_CUTOFF = 8;

        /// <summary>
        /// 小于这个数值的数组调用中位数作为枢轴。
        /// </summary>
        private readonly int MEDIAN_OF_3_CUTOFF = 40;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickBentleyMcIlroy() { }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 对指定范围内的数组进行排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序的起始下标。</param>
        /// <param name="hi">排序的终止下标。</param>
        private void Sort<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int n = hi - lo + 1;

            if (n <= this.INSERTION_SORT_CUTOFF)
            {
                InsertionSort(a, lo, hi);
                return;
            }
            else if (n <= this.MEDIAN_OF_3_CUTOFF)
            {
                // 对于较小的数组,直接选择左中右三个元素中的中位数作为枢轴。
                int m = Median3(a, lo, lo + n / 2, hi);
                Exch(a, m, lo);
            }
            else
            {
                // 对于较大的数组使用 Turkey Ninther 作为枢轴。
                int eps = n / 8;
                int mid = lo + n / 2;
                int m1 = Median3(a, lo, lo + eps, lo + eps + eps);
                int m2 = Median3(a, mid - eps, mid, mid + eps); 
                int m3 = Median3(a, hi - eps - eps, hi - eps, hi);
                int ninther = Median3(a, m1, m2, m3);
                Exch(a, ninther, lo);
            }

            // 三向切分
            int i = lo, j = hi + 1;
            int p = lo, q = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v)) ;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;

                if (i == j && IsEqual(a[i], v))
                    Exch(a, ++p, i);
                if (i >= j)
                    break;

                Exch(a, i, j);
                if (IsEqual(a[i], v))
                    Exch(a, ++p, i);
                if (IsEqual(a[j], v))
                    Exch(a, --q, j);
            }

            i = j + 1;
            for (int k = lo; k <= p; k++)
                Exch(a, k, j--);
            for (int k = hi; k >= q; k--)
                Exch(a, k, i++);

            Sort(a, lo, j);
            Sort(a, i, hi);
        }

        /// <summary>
        /// 判断两个元素是否值相等。
        /// </summary>
        /// <typeparam name="T">需要判断的元素类型。</typeparam>
        /// <param name="a">进行比较的第一个元素。</param>
        /// <param name="b">进行比较的第二个元素。</param>
        /// <returns>两个元素的值是否相等。</returns>
        private bool IsEqual<T>(T a, T b) where T : IComparable<T>
        {
            return a.CompareTo(b) == 0;
        }

        /// <summary>
        /// 用插入排序对指定范围内的数组排序。
        /// </summary>
        /// <typeparam name="T">数组的元素类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序的起始下标。</param>
        /// <param name="hi">排序的终止下标。</param>
        private void InsertionSort<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            for (int i = lo; i <= hi; i++)
            {
                for (int j = i; j > lo && Less(a[j], a[j - 1]); j--)
                {
                    Exch(a, j, j - 1);
                }
            }
        }

        /// <summary>
        /// 获取三个元素中的中位数。
        /// </summary>
        /// <typeparam name="T">用于排序的元素。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="i">第一个待选元素的下标。</param>
        /// <param name="j">第二个待选元素的下标。</param>
        /// <param name="k">第三个待选元素的下标。</param>
        /// <returns></returns>
        private int Median3<T>(T[] a, int i, int j, int k) where T : IComparable<T>
        {
            return
               (Less(a[i], a[j]) ?
               (Less(a[j], a[k]) ? j : Less(a[i], a[k]) ? k : i) :
               (Less(a[k], a[j]) ? j : Less(a[k], a[i]) ? k : i));
        }
    }
}
3.4.7.3傅立叶逆变换

设((y_0,y_1,cdots,y_{n-1}))为((a_0,cdots,a_{n-1}))的快速傅立叶变换.
考虑另一个向量((c_0,cdots,c_{n-1}))满足

[c_k=sum_{i=0}^{n-1}y_i(omega_n^{-k})^i].

即多项式(B(x)=y_0+y_1x+cdots+y_{n-1}x^{n-1})在(omega_n^0,cdots,omega_n^{-(n-1)})处的点值表示.

可以得到(证明略)

[a_i=frac 1n c_i].

所以,使用单位根的倒数代替单位根,做一次类似快速傅里叶变换的过程,再将结果每个数除以(n),即为傅里叶逆变换的结果。

另请参阅

Quick

3.7.4.4代码实现

FFT有两种常见的代码实现:
递归版本和迭代版本,一般来讲递归效率很差,但由于我非常菜,一轮省选就先使用递归版本骗分.迭代版本以后会更新.

const double PI = acos(-1);
bool inversed = false;
inline std::complex<double> omega(const int n, const int k) {
  if (!inversed)
    return std::complex<double>(cos(2 * PI / n * k), sin(2 * PI / n * k));
  else
    return std::conj(
        std::complex<double>(cos(2 * PI / n * k), sin(2 * PI / n * k)));
}
void fft(std::complex<double> *a, std::complex<double> *ans, int n) {
  if (n == 1) {
    ans[0] = a[0];
    return;
  }
  std::complex<double> buf[maxn];
  int m = n >> 1;
  for (int i = 0; i < m; i++) {
    buf[i] = a[i * 2];
    buf[i + m] = a[i * 2 + 1];
  }
  std::complex<double> tmp[maxn];
  fft(buf, tmp, m);
  fft(buf + m, tmp + m, m);
  for (int i = 0; i < m; i++) {
    std::complex<double> x = omega(n, i);
    ans[i] = tmp[i] + x * tmp[i + m];
    ans[i + m] = tmp[i] - x * tmp[i + m];
  }
}
void solve() {
  //sth
  while (N < n + 1)
    N <<= 1;
  N <<= 1;
  fft(a, ans1, N);
  fft(b, ans2, N);
  std::complex<double> ans3[maxn];
  for (int i = 0; i < N; i++)
    ans3[i] = ans1[i] * ans2[i];
  std::complex<double> tmp[maxn];
  inversed = true;
  fft(ans3, tmp, N);
  for (int i = 0; i < N; i++)
    c[i] = tmp[i].real() / N;
  //sth
}

$mathtt{COPYRIGHT}© mathtt{2017,KONJAC,MIT LICENSE} $

2.3.24

题目

取样排序。(W.Frazer,A.McKellar)
实现一个快速排序,取样大小为 2^k-1。
首先将取样得到的元素排序,然后在递归函数中使用样品的中位数切分。
分为两部分的其余样品元素无需再次排序并可以分别应用于原数组的两个子数组。
这种算法称为取样排序。

解答

取样排序的想法很简单:
常规快排的枢轴只有一个。
如果用一个数组来充当枢轴,根据排序位置的不同自动选择对应的枢轴,
显然能够更好的估计中位数,以求更好的切分效果。
于是引入了「取样」的概念,假如我们从源数组中随机取了 3
个元素并对其排序,
那么这 3
个元素的中位数可以作为第一次切分的枢轴,剩余两个元素则可以充当切分后两个子数组的枢轴。
那么当取样元素到达一个合适的数量时,就能达到提升切分效率的目标。

大致思路如下:
首先先从输入数组里随机取一些元素,作为「取样数组」。
用任意排序算法(比如快排)对取样数组进行排序。
(由于取样数组通常都比较小,这一步的时间消耗通常不会影响性能)
取出取样数组里面的中位数,当作枢轴对剩下的数组进行切分。
之后的切分中,根据排序区间在剩余数组中的相对位置,
用取样数组中对应位置的数作为枢轴,直到整个排序完成。

论文里提到了两种实现方式。
第一种方法
取样数组和剩余数组是分开保存的。
每次切分完成后,并不把枢轴放入剩余数组中,
而是等到剩余数组全部排序完毕之后再用一次归并(merge)操作将取样数组和剩余数组归并。
第二种方法
取样数组和剩余数组保存在同一片空间里,这也是这份题解所实现的方法。
图片 23
在打乱输入数组之后,取前 2^k-1 个元素作为取样数组,用快排对其排序。
然后把取样数组的后半部分放到整个数组的末尾。
这样操作的结果是输入数组分为了四个部分:
有序的取样数组、取样数组的中位数、无序的剩余数组、有序的取样数组。
中位数则位于第一部分的末尾,我们将其作为枢轴对剩余数组进行切分,数组变为:
有序的取样数组、小于中位数的部分、枢轴、大于中位数的部分、有序的取样数组
接下来我们再对第一个部分取半,放到中位数之前;对最后一部分取半,放到中位数之后:
0 ~ 1/4 取样数组、小于中位数、1/4 ~ 1/2 取样数组、枢轴、1/2~3/4
取样数组、大于中位数、3/4~1 取样数组
你会发现枢轴前后又分别变回了初始条件,递归执行上述操作,便能对整个数组排序。
注意当取样数组用完的时候,直接变回普通的快排。

现代的取样排序
这里的「现代」并不意味着更好,只是让取样排序能更好的适应多线程排序。
首先仍然是取样,取样的数量往往取决于线程的数量,比如说取了 p-1
个,就将数组分为 p 份。
对取样数组进行排序,获得 p 个区间(桶)。
遍历输入的数组,把元素扔到相应的桶里面。
把每个桶和对应的枢轴送到对应的线程进行排序。
汇总各个桶中的结果,排序完毕。

测试结果:
图片 24
大概能提升 5%~10% 的性能。

代码
using System;
using System.Diagnostics;

namespace Quick
{
    /// <summary>
    /// 取样排序类。
    /// </summary>
    public class SampleSort : QuickSort
    {
        /// <summary>
        /// 取样数组长度 2^k - 1 的阶数。
        /// </summary>
        public int K { get; set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public SampleSort()
        {
            this.K = 8;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            if (a.Length < Math.Pow(2, this.K + 1))
            {
                // 小于 2^(k+1) 的数组直接进行快排
                base.Sort(a);
                return;
            }

            Shuffle(a);
            int samplehi = (int)Math.Pow(2, this.K) - 2;
            // 利用快速排序对取样数组进行排序
            base.Sort(a, 0, samplehi);
            // 找到取样数组的中位数
            int sampleMedian = samplehi / 2;
            // 将取样数组后半部分放到数组末尾
            int i = samplehi, j = a.Length - 1;
            while (i != sampleMedian)
                Exch(a, i--, j--);
            // 根据取样数组进行排序
            Sort(a, 0, sampleMedian, j, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="samplelo">取样数组的起始下标。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        /// <param name="samplehi">取样数组的终止下标。</param>
        private void Sort<T>(T[] a, int samplelo, int lo, int hi, int samplehi) where T : IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;

            int j = Partition(a, lo, hi);
            // 将前部的有序取样数组取半,后半部分放在枢轴前面。
            if (lo - samplelo > 1)
            {
                // p 应该始终指向有序部分的最后一项
                // v 应该始终指向有序部分的前面一项
                int p = lo - 1, v = j - 1;
                for (int i = 0; i < (lo - samplelo) / 2; i++)
                {
                    Exch(a, p--, v--);
                }
                Sort(a, samplelo, p, v, j - 1);
            }
            else
            {
                // 取样数组已经用完,退化为普通 Quicksort
                base.Sort(a, samplelo, j - 1);
            }

            // 将尾部有序取样数组取半,前半部分放在枢轴后面。
            if (samplehi - hi > 1)
            {
                // p 应该始终指向有序部分的前面一项
                // v 应该始终指向有序部分的最后一项
                int p = hi, v = j;
                for (int i = 0; i < (samplehi - hi) / 2; i++)
                {
                    Exch(a, ++p, ++v);
                }
                Sort(a, j + 1, v, p, samplehi);
            }
            else
            {
                // 取样数组已用完,退化为普通 Quicksort
                base.Sort(a, j + 1, samplehi);
            }
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}

测试用例:

using System;
using Quick;

namespace _2._3._24
{
    /*
     * 2.3.24
     * 
     * 取样排序。(W.Frazer,A.McKellar)
     * 实现一个快速排序,
     * 取样大小为 2^k-1。首先将取样得到的元素排序,
     * 然后在递归函数中使用样品的中位数切分。
     * 分为两部分的其余样品元素无需再次排序并可以分别应用于原数组的两个子数组。
     * 这种算法称为取样排序。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSort quickNormal = new QuickSort();
            SampleSort sampleSort = new SampleSort();
            int arraySize = 1600000;                        // 初始数组大小。
            const int kSteps = 10;                          // 取样 k 值的递增次数。
            const int trialTimes = 1;                       // 每次实验的重复次数。
            const int trialLevel = 2;                       // 双倍递增的次数。

            Console.WriteLine("ktnttsampletnormaltratio");
            for (int i = 0; i < kSteps; i++)
            {
                int array = arraySize;
                for (int j = 0; j < trialLevel; j++)
                {
                    double timeSample = 0;
                    double timeNormal = 0;
                    for (int k = 0; k < trialTimes; k++)
                    {
                        int[] a = SortCompare.GetRandomArrayInt(array);
                        int[] b = new int[a.Length];
                        a.CopyTo(b, 0);
                        timeNormal += SortCompare.Time(quickNormal, b);
                        timeSample += SortCompare.Time(sampleSort, a);

                    }
                    timeSample /= trialTimes;
                    timeNormal /= trialTimes;
                    if (arraySize < 10000000)
                        Console.WriteLine(sampleSort.K + "t" + array + "tt" + timeSample + "t" + timeNormal + "t" + timeSample / timeNormal);
                    else
                        Console.WriteLine(sampleSort.K + "t" + array + "t" + timeSample + "t" + timeNormal + "t" + timeSample / timeNormal);
                    array *= 2;
                }
                sampleSort.K++;
            }

        }
    }
}
另请参阅

关于取样排序的论文(1970 年):
Frazer W D, McKellar A C. Samplesort: A sampling approach to minimal
storage tree sorting[J]. Journal of the ACM (JACM), 1970, 17(3):
496-507.
维基百科中的取样排序:
Samplesort-Wikipedia
本题用到的类库链接:
Quick

2.3.25

题目

切换到插入排序。
实现一个快速排序,在子数组元素少于 M 时切换到插入排序。
用快速排序处理大小 N 分别为 10^3、10^4、10^5 和 10^6 的随机数组,
根据经验给出使其在你的环境中运行速度最快的 M 值。
将 M 从 0 变化到 30 的每个值所得到的平均运行时间绘成曲线。
注意:你需要为算法 2.2 添加一个需要三个参数的 sort() 方法以使
Insertion.sort(a, lo, hi) 将子数组 a[lo…hi] 排序。

解答

切换到插入排序的实现比较简单,在类内添加一个成员变量 M,在 Sort
方法里添加如下代码:

protected void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
{
    if (hi <= lo)                   // 别越界
        return;
    if (hi - lo <= this.M)
    {
        // 调用插入排序
        for (int i = lo; i <= hi; i++)
            for (int k = i; k > lo && Less(a[k], a[k - 1]); k--)
                Exch(a, k, k - 1);
        return;
    }
    int j = Partition(a, lo, hi);
    Sort(a, lo, j - 1);
    Sort(a, j + 1, hi);
}

下面放上实验结果:
N=1000
图片 25
N=10000
图片 26
N=100000
图片 27
N=1000000
图片 28

小于 8 的 M 值会比较合适。

代码

这里使用了 Background Worker 来防止程序失去响应,更多信息可以看
「另请参阅」部分。

using System;
using System.ComponentModel;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;
using Quick;

namespace _2._3._25
{
    public partial class Form2 : Form
    {
        /// <summary>
        /// 测试数组大小。
        /// </summary>
        public int N = 100;

        public Form2(int n)
        {
            InitializeComponent();
            this.N = n;
        }

        /// <summary>
        /// 启动页面时启动后台测试。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void Form2_Shown(object sender, EventArgs e)
        {
            this.Text = "正在绘图";
            this.backgroundWorker1.RunWorkerAsync();
        }

        /// <summary>
        /// 后台测试方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e)
        {
            BackgroundWorker worker = sender as BackgroundWorker;
            QuickSortInsertion quickSortInsertion = new QuickSortInsertion();
            double[] timeRecord = new double[31];
            for (int i = 0; i <= 30; i++)
            {
                worker.ReportProgress(i * 3);
                quickSortInsertion.M = i;
                int[] data = SortCompare.GetRandomArrayInt(this.N);
                timeRecord[i] = SortCompare.Time(quickSortInsertion, data);
            }
            e.Result = timeRecord;
        }

        /// <summary>
        /// 更新后台进度方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_ProgressChanged(object sender, ProgressChangedEventArgs e)
        {
            this.Text = "正在绘图,已完成 " + e.ProgressPercentage + " %";
        }

        /// <summary>
        /// 测试完毕,进行绘图的方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
        {
            if (e.Error != null)
            {
                MessageBox.Show(e.Error.Message);
            }
            double[] result = e.Result as double[];

            Graphics graphics = this.CreateGraphics();

            // 获得绘图区矩形。
            RectangleF rect = this.ClientRectangle;
            float unitX = rect.Width / 10;
            float unitY = rect.Width / 10;

            // 添加 10% 边距作为文字区域。
            RectangleF center = new RectangleF
                (rect.X + unitX, rect.Y + unitY,
                rect.Width - 2 * unitX, rect.Height - 2 * unitY);

            // 绘制坐标系。
            graphics.DrawLine(Pens.Black, center.Left, center.Top, center.Left, center.Bottom);
            graphics.DrawLine(Pens.Black, center.Left, center.Bottom, center.Right, center.Bottom);
            graphics.DrawString(result.Max().ToString(), this.Font, Brushes.Black, rect.Location);
            graphics.DrawString(result.Length.ToString(), this.Font, Brushes.Black, center.Right, center.Bottom);
            graphics.DrawString("0", this.Font, Brushes.Black, rect.Left, center.Bottom);

            // 初始化点。
            PointF[] bluePoints = new PointF[result.Length];
            unitX = center.Width / result.Length;
            unitY = center.Height / (float)result.Max();

            for (int i = 0; i < result.Length; i++)
            {
                bluePoints[i] = new PointF(center.Left + unitX * (i + 1), center.Bottom - (float)(result[i] * unitY) - 10);
            }

            // 绘制点。
            for (int i = 0; i < result.Length; i++)
            {
                graphics.FillEllipse(Brushes.Blue, new RectangleF(bluePoints[i], new Size(10, 10)));
            }

            graphics.Dispose();

            this.Text = "绘图结果";
            int min = 0;
            for (int i = 0; i < result.Length; i++)
            {
                if (result[i] < result[min])
                    min = i;
            }
            string report = "M " + min + "rntime " + result[min];
            MessageBox.Show(report, "最优结果");
        }
    }
}

快速排序类

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._25
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortInsertion : BaseSort
    {
        /// <summary>
        /// 切换到插入排序的阈值。
        /// </summary>
        public int M { get; set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortInsertion()
        {
            this.M = 8;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        protected void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;
            if (hi - lo <= this.M)
            {
                // 调用插入排序
                for (int i = lo; i <= hi; i++)
                    for (int k = i; k > lo && Less(a[k], a[k - 1]); k--)
                        Exch(a, k, k - 1);
                return;
            }
            int j = Partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}
另请参阅

BackgroundWorker 组件 | Microsoft
Docs
Quick

2.3.26

题目

子数组的大小。
编写一个程序,在快速排序处理大小为 N 的数组的过程中,
当子数组的大小小于 M 时,排序方法需要切换为插入排序。
将子数组的大小绘制成直方图。
用 N=10^5,M=10、20 和 50 测试你的程序。

解答

在切换为插入排序之前先记录一下当前子数组的大小。
在排序类内添加一个大小为 M+1 的数组,用于记录每种数组大小出现的次数。

结果如下(N=100000):
M=10
图片 29
M=20
图片 30
M=50
图片 31

代码
using System;
using System.ComponentModel;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;
using Quick;

namespace _2._3._26
{
    public partial class Form2 : Form
    {
        private int M;
        private int N;

        public Form2(int m, int n)
        {
            InitializeComponent();
            this.M = m;
            this.N = n;
        }

        /// <summary>
        /// 启动页面时启动后台测试。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void Form2_Shown(object sender, EventArgs e)
        {
            this.Text = "正在绘图";
            this.backgroundWorker1.RunWorkerAsync();
        }

        /// <summary>
        /// 后台测试方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e)
        {
            BackgroundWorker worker = sender as BackgroundWorker;
            QuickSortInsertion quickSortInsertion = new QuickSortInsertion
            {
                M = this.M
            };
            int[] data = SortCompare.GetRandomArrayInt(this.N);
            worker.ReportProgress(50);
            quickSortInsertion.Sort(data);
            e.Result = quickSortInsertion.Counts;
        }

        /// <summary>
        /// 更新后台进度方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_ProgressChanged(object sender, ProgressChangedEventArgs e)
        {
            this.Text = "正在绘图,已完成 " + e.ProgressPercentage + " %";
        }

        /// <summary>
        /// 测试完毕,进行绘图的方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
        {
            if (e.Error != null)
            {
                MessageBox.Show(e.Error.Message);
            }
            //新建画布
            Graphics graphics = this.CreateGraphics();

            //翻转默认坐标系
            graphics.TranslateTransform(0, this.Height);
            graphics.ScaleTransform(1, -1);

            int[] countsOrigin = e.Result as int[];
            int[] counts = new int[countsOrigin.Length - 1];
            for (int i = 0; i < counts.Length; i++)
            {
                counts[i] = countsOrigin[i + 1];
            }

            //获取最大值
            double max = counts.Max();
            //计算间距
            double unit = this.Width / (3.0 * counts.Length + 1);
            double marginTop = 100;
            //计算直方图的矩形
            Rectangle[] rects = new Rectangle[counts.Length];
            rects[0].X = (int)unit;
            rects[0].Y = 0;
            rects[0].Width = (int)(2 * unit);
            rects[0].Height = (int)((counts[0] / max) * (this.Height - marginTop));
            for (int i = 1; i < counts.Length; ++i)
            {
                rects[i].X = (int)(rects[i - 1].X + 3 * unit);
                rects[i].Y = 0;
                rects[i].Width = (int)(2 * unit);
                rects[i].Height = (int)((counts[i] / (max + 1)) * (this.Height - marginTop));
            }

            //绘图
            graphics.FillRectangles(Brushes.Black, rects);

            //释放资源
            graphics.Dispose();

            this.Text = "绘图结果,最高次数:" + counts.Max() + " 最低次数:" + counts.Min();
        }
    }
}

快速排序类

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._26
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortInsertion : BaseSort
    {
        /// <summary>
        /// 切换到插入排序的阈值。
        /// </summary>
        public int M { get; set; }

        public int[] Counts;

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortInsertion()
        {
            this.M = 8;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            this.Counts = new int[this.M + 1];
            for (int i = 0; i < this.M + 1; i++)
            {
                this.Counts[i] = 0;
            }
            Shuffle(a);
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        protected void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;
            if (hi - lo <= this.M)
            {
                this.Counts[hi - lo]++;
                // 调用插入排序
                for (int i = lo; i <= hi; i++)
                    for (int k = i; k > lo && Less(a[k], a[k - 1]); k--)
                        Exch(a, k, k - 1);
                return;
            }
            int j = Partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}
另请参阅

BackgroundWorker 组件 | Microsoft
Docs
Quick

2.3.27

题目

忽略小数组。
用实验对比以下处理小数组的方法和练习 2.3.25 的处理方法的效果:
在快速排序中直接忽略小数组,仅在快速排序结束后运行一次插入排序。
注意:可以通过这些实验估计出电脑的缓存大小,因为当数组大小超出缓存时这种方法的性能可能会下降。

解答

实验结果如下:
图片 32
P.S. 测试机上的缓存是 L1 128K,L2 512K,L3 4MB。

代码

QuickSortIgnore

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._27
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortIgnore : BaseSort
    {
        /// <summary>
        /// 切换到插入排序的阈值。
        /// </summary>
        public int M { get; set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortIgnore()
        {
            this.M = 10;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);
            Sort(a, 0, a.Length - 1);

            // 插入排序处理小数组
            for (int i = 0; i < a.Length; i++)
                for (int j = i; j > 0 && Less(a[j], a[j - 1]); j--)
                    Exch(a, j, j - 1);

            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        protected void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;
            if (hi - lo <= this.M)
            {
                return;     // 直接忽略
            }
            int j = Partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}

QuickSortInsertion

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._27
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortInsertion : BaseSort
    {
        /// <summary>
        /// 切换到插入排序的阈值。
        /// </summary>
        public int M { get; set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortInsertion()
        {
            this.M = 10;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        protected void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;
            if (hi - lo <= this.M)
            {
                // 调用插入排序
                for (int i = lo; i <= hi; i++)
                    for (int k = i; k > lo && Less(a[k], a[k - 1]); k--)
                        Exch(a, k, k - 1);
                return;
            }
            int j = Partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}

测试用例

using System;
using Quick;

namespace _2._3._27
{
    /*
     * 2.3.27
     * 
     * 忽略小数组。
     * 用实验对比以下处理小数组的方法和练习 2.3.25 的处理方法的效果:
     * 在快速排序中直接忽略小数组,仅在快速排序结束后运行一次插入排序。
     * 注意:
     * 可以通过这些实验估计出电脑的缓存大小,
     * 因为当数组大小超出缓存时这种方法的性能可能会下降。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSortInsertion insertion = new QuickSortInsertion();
            QuickSortIgnore ignore = new QuickSortIgnore();
            int arraySize = 20000;                          // 初始数组大小。
            const int mSteps = 1;                           // M 值的递增次数。
            const int trialTimes = 4;                       // 每次实验的重复次数。
            const int trialLevel = 10;                      // 双倍递增的次数。

            Console.WriteLine("Mtnttignoretinserttratio");
            for (int i = 0; i < mSteps; i++)
            {
                int array = arraySize;
                for (int j = 0; j < trialLevel; j++)
                {
                    double timeIgnore = 0;
                    double timeInsertion = 0;
                    for (int k = 0; k < trialTimes; k++)
                    {
                        int[] a = SortCompare.GetRandomArrayInt(array);
                        int[] b = new int[a.Length];
                        a.CopyTo(b, 0);
                        timeInsertion += SortCompare.Time(insertion, b);
                        timeIgnore += SortCompare.Time(ignore, a);

                    }
                    timeIgnore /= trialTimes;
                    timeInsertion /= trialTimes;
                    if (arraySize < 10000000)
                        Console.WriteLine(ignore.M + "t" + array + "tt" + timeIgnore + "t" + timeInsertion + "t" + timeIgnore / timeInsertion);
                    else
                        Console.WriteLine(ignore.M + "t" + array + "t" + timeIgnore + "t" + timeInsertion + "t" + timeIgnore / timeInsertion);
                    array *= 2;
                }
                ignore.M++;
            }
        }
    }
}
另请参阅

Quick

2.3.28

题目

递归深度。
用经验性的研究估计切换阈值为 M 的快速排序在将大小为 N
的不重复数组排序时的平均递归深度,
其中 M=10、20 和 50,N=10^3、10^4、10^5 和 10^6。

解答

对 Sort 方法做修改,添加一个层层传递的 depth 参数,每加一层 depth
就加一,结束时取左右较大的 depth 返回。

protected int Sort<T>(T[] a, int lo, int hi, int depth) where T: IComparable<T>
{
    if (hi <= lo)                   // 别越界
        return depth;
    if (hi - lo <= this.M)
    {
        // 调用插入排序
        for (int i = lo; i <= hi; i++)
            for (int k = i; k > lo && Less(a[k], a[k - 1]); k--)
                Exch(a, k, k - 1);
        return depth;
    }
    int j = Partition(a, lo, hi);
    int left = Sort(a, lo, j - 1, depth + 1);
    int right = Sort(a, j + 1, hi, depth + 1);
    return Less(left, right) ? right : left;
}

测试结果
图片 33

代码
using System;
using System.Diagnostics;
using Quick;

namespace _2._3._28
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortInsertion : BaseSort
    {
        /// <summary>
        /// 切换到插入排序的阈值。
        /// </summary>
        public int M { get; set; }

        /// <summary>
        /// 上一次排序的最大递归深度。
        /// </summary>
        public int Depth { get; private set; }

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortInsertion()
        {
            this.M = 10;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <returns>递归深度。</returns>
        public override void Sort<T>(T[] a)
        {
            Shuffle(a);
            this.Depth = Sort(a, 0, a.Length - 1, 0);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        protected int Sort<T>(T[] a, int lo, int hi, int depth) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return depth;
            if (hi - lo <= this.M)
            {
                // 调用插入排序
                for (int i = lo; i <= hi; i++)
                    for (int k = i; k > lo && Less(a[k], a[k - 1]); k--)
                        Exch(a, k, k - 1);
                return depth;
            }
            int j = Partition(a, lo, hi);
            int left = Sort(a, lo, j - 1, depth + 1);
            int right = Sort(a, j + 1, hi, depth + 1);
            return Less(left, right) ? right : left;
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        private void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}

测试用例

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace _2._3._28
{
    /*
     * 2.3.28
     * 
     * 递归深度。
     * 用经验性的研究估计切换阈值为 M 的快速排序
     * 在将大小为 N 的不重复数组排序时的平均递归深度,
     * 其中 M=10、20 和 50,N=10^3、10^4、10^5 和 10^6。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("MtNtDepth");
            Trial(10);
            Trial(20);
            Trial(50);
        }

        /// <summary>
        /// 进行一次测试。
        /// </summary>
        /// <param name="m">要使用的阈值</param>
        static void Trial(int m)
        {
            QuickSortInsertion sort = new QuickSortInsertion();
            int trialTime = 5;

            // 由于排序前有 Shuffle,因此直接输入有序数组。
            // M=10
            sort.M = m;
            int totalDepth = 0;
            for (int N = 1000; N < 10000000; N *= 10)
            {
                for (int i = 0; i < trialTime; i++)
                {
                    int[] a = new int[N];
                    for (int j = 0; j < N; j++)
                    {
                        a[j] = j;
                    }
                    sort.Sort(a);
                    totalDepth += sort.Depth;
                }
                Console.WriteLine(sort.M + "t" + N + "t" + totalDepth / trialTime);
            }
        }
    }
}
另请参阅

Quick

2.3.29

题目

随机化。
用经验性的研究对比随机选择切分元素和正文所述的一开始就将数组随机化这两种策略的效果。
在子数组大小为 M 时进行切换,
将大小为 N 的不重复数组排序,其中 M=10、20 和 50,N=10^3、10^4、10^5 和
10^6。

解答

在快排类内部添加一个随机数发生器,每次随机取枢轴并交换至第一位进行切分。

private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
{
    int i = lo, j = hi + 1;
    int pivot = this.RandomGenerator.Next(hi - lo) + lo;
    Exch(a, pivot, lo);
    T v = a[lo];
    while (true)
    {
        while (Less(a[++i], v))
            if (i == hi)
                break;
        while (Less(v, a[--j]))
            if (j == lo)
                break;
        if (i >= j)
            break;
        Exch(a, i, j);
    }
    Exch(a, lo, j);
    return j;
}

测试结果:
图片 34

代码

使用随机枢轴的快排

using System;
using System.Diagnostics;
using Quick;

namespace _2._3._29
{
    /// <summary>
    /// 快速排序类。
    /// </summary>
    public class QuickSortRandomPivot : BaseSort
    {
        /// <summary>
        /// 切换到插入排序的阈值。
        /// </summary>
        public int M { get; set; }

        /// <summary>
        /// 随机数发生器。
        /// </summary>
        private readonly Random RandomGenerator = new Random();

        /// <summary>
        /// 默认构造函数。
        /// </summary>
        public QuickSortRandomPivot()
        {
            this.M = 10;
        }

        /// <summary>
        /// 用快速排序对数组 a 进行升序排序。
        /// </summary>
        /// <typeparam name="T">需要排序的类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        public override void Sort<T>(T[] a)
        {
            Sort(a, 0, a.Length - 1);
            Debug.Assert(IsSorted(a));
        }

        /// <summary>
        /// 用快速排序对数组 a 的 lo ~ hi 范围排序。
        /// </summary>
        /// <typeparam name="T">需要排序的数组类型。</typeparam>
        /// <param name="a">需要排序的数组。</param>
        /// <param name="lo">排序范围的起始下标。</param>
        /// <param name="hi">排序范围的结束下标。</param>
        protected void Sort<T>(T[] a, int lo, int hi) where T: IComparable<T>
        {
            if (hi <= lo)                   // 别越界
                return;
            if (hi - lo <= this.M)
            {
                // 调用插入排序
                for (int i = lo; i <= hi; i++)
                    for (int k = i; k > lo && Less(a[k], a[k - 1]); k--)
                        Exch(a, k, k - 1);
                return;
            }
            int j = Partition(a, lo, hi);
            Sort(a, lo, j - 1);
            Sort(a, j + 1, hi);
        }

        /// <summary>
        /// 对数组进行切分,返回枢轴位置。
        /// </summary>
        /// <typeparam name="T">需要切分的数组类型。</typeparam>
        /// <param name="a">需要切分的数组。</param>
        /// <param name="lo">切分的起始点。</param>
        /// <param name="hi">切分的末尾点。</param>
        /// <returns>枢轴下标。</returns>
        private int Partition<T>(T[] a, int lo, int hi) where T : IComparable<T>
        {
            int i = lo, j = hi + 1;
            int pivot = this.RandomGenerator.Next(hi - lo) + lo;
            Exch(a, pivot, lo);
            T v = a[lo];
            while (true)
            {
                while (Less(a[++i], v))
                    if (i == hi)
                        break;
                while (Less(v, a[--j]))
                    if (j == lo)
                        break;
                if (i >= j)
                    break;
                Exch(a, i, j);
            }
            Exch(a, lo, j);
            return j;
        }
    }
}

测试用例

using System;
using Quick;

namespace _2._3._29
{
    /*
     * 2.3.29
     * 
     * 随机化。
     * 用经验性的研究对比随机选择切分元素和正文所述的一开始就将数组随机化这两种策略的效果。
     * 在子数组大小为 M 时进行切换,将大小为 N 的不重复数组排序,
     * 其中 M=10、20 和 50,N=10^3、10^4、10^5 和 10^6。
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine("MtNtshuffletrandomtshuffle/random");
            Trial(10);
            Trial(20);
            Trial(50);
        }

        /// <summary>
        /// 进行一次测试。
        /// </summary>
        /// <param name="m">要使用的阈值</param>
        static void Trial(int m)
        {
            QuickSortInsertion withShuffle = new QuickSortInsertion();
            QuickSortRandomPivot randomPivot = new QuickSortRandomPivot();
            int trialTime = 5;

            // M=10
            withShuffle.M = m;
            randomPivot.M = m;
            double timeShuffle = 0;
            double timeRandomPivot = 0;
            for (int N = 1000; N < 10000000; N *= 10)
            {
                for (int i = 0; i < trialTime; i++)
                {
                    int[] a = new int[N];
                    int[] b = new int[N];
                    for (int j = 0; j < N; j++)
                    {
                        a[j] = j;
                    }
                    Shuffle(a);
                    a.CopyTo(b, 0);
                    timeShuffle += SortCompare.Time(withShuffle, a);
                    timeRandomPivot += SortCompare.Time(randomPivot, b);
                }
                timeShuffle /= trialTime;
                timeRandomPivot /= trialTime;
                Console.WriteLine(withShuffle.M + "t" + N + "t" + timeShuffle + "t" + timeRandomPivot + "t" + timeShuffle / timeRandomPivot);
            }
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <typeparam name="T">需要打乱的数组类型。</typeparam>
        /// <param name="a">需要打乱的数组。</param>
        static void Shuffle<T>(T[] a)
        {
            Random random = new Random();
            for (int i = 0; i < a.Length; i++)
            {
                int r = i + random.Next(a.Length - i);
                T temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}
另请参阅

Quick

2.3.30

题目

极端情况。
用初始随机化和非初始随机化的快速排序测试练习 2.1.35 和练习 2.1.36
中描述的大型非随机数组。
在将这些大数组排序时,乱序对快速排序的性能有何影响?

解答

结果如下,在 N=5000000 时,随机选择枢轴会比事先打乱快一点。
图片 35

代码
using System;
using Quick;

namespace _2._3._30
{
    /*
     * 2.3.30
     * 
     * 极端情况。
     * 用初始随机化和非初始随机化的快速排序测试练习 2.1.35 和练习 2.1.36 中描述的大型非随机数组。
     * 在将这些大数组排序时,乱序对快速排序的性能有何影响?
     * 
     */
    class Program
    {
        static void Main(string[] args)
        {
            QuickSortInsertion insertionSort = new QuickSortInsertion();
            QuickSortRandomPivot randomSort = new QuickSortRandomPivot();
            int n = 5000000;

            // 高斯分布(正态分布)
            double[] arrayInsertion = SortCompare.GetNormalDistributionArray(n);
            double[] arraySelection = new double[n];

            arrayInsertion.CopyTo(arraySelection, 0);

            Console.WriteLine("Normal Distribution:");
            Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Random Pivot: " + SortCompare.Time(randomSort, arraySelection));
            Console.WriteLine();

            // 泊松分布
            arrayInsertion = SortCompare.GetPossionDistributionArray(n);
            arrayInsertion.CopyTo(arraySelection, 0);

            Console.WriteLine("Poission Distribution:");
            Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Random Pivot: " + SortCompare.Time(randomSort, arraySelection));
            Console.WriteLine();

            // 几何分布
            arrayInsertion = SortCompare.GetGeometricDistributionArray(n, 0.3);
            arrayInsertion.CopyTo(arraySelection, 0);

            Console.WriteLine("Geometric Distribution:");
            Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Random Pivot: " + SortCompare.Time(randomSort, arraySelection));
            Console.WriteLine();

            // 离散分布
            arrayInsertion = SortCompare.GetDiscretDistributionArray(n, new double[] { 0.1, 0.2, 0.3, 0.1, 0.1, 0.1, 0.1 });
            arrayInsertion.CopyTo(arraySelection, 0);

            Console.WriteLine("Discret Distribution:");
            Console.WriteLine("Insertion: " + SortCompare.Time(insertionSort, arrayInsertion));
            Console.WriteLine("Random Pivot: " + SortCompare.Time(randomSort, arraySelection));
            Console.WriteLine();

            // 一半是 0 一半是 1
            int[] arrayNormalInsertion = HalfZeroHalfOne(n);
            int[] arrayRandomPivot = new int[n];
            arrayNormalInsertion.CopyTo(arrayRandomPivot, 0);

            Console.WriteLine("half 0 and half 1");
            Console.WriteLine("Insertion:" + SortCompare.Time(insertionSort, arrayNormalInsertion));
            Console.WriteLine("Random Pivot:" + SortCompare.Time(randomSort, arrayRandomPivot));
            Console.WriteLine();

            // 一半是 0, 1/4 是 1, 1/8 是 2……
            arrayNormalInsertion = HalfAndHalf(n);
            arrayNormalInsertion.CopyTo(arrayRandomPivot, 0);

            Console.WriteLine("half and half and half ...");
            Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, arrayNormalInsertion));
            Console.WriteLine("Random Pivot:" + SortCompare.Time(randomSort, arrayRandomPivot));
            Console.WriteLine();

            // 一半是 0,一半是随机 int 值
            arrayNormalInsertion = HalfZeroHalfRandom(n);
            arrayNormalInsertion.CopyTo(arrayRandomPivot, 0);

            Console.WriteLine("half 0 half random");
            Console.WriteLine("Insertion Sort:" + SortCompare.Time(insertionSort, arrayNormalInsertion));
            Console.WriteLine("Random Pivot:" + SortCompare.Time(randomSort, arrayRandomPivot));
        }

        /// <summary>
        /// 获取一半是 0 一半是 1 的随机 <see cref="int"/> 数组。
        /// </summary>
        /// <param name="n">数组大小。</param>
        /// <returns>一半是 0 一半是 1 的 <see cref="int"/>数组。</returns>
        static int[] HalfZeroHalfOne(int n)
        {
            int[] result = new int[n];
            Random random = new Random();
            for (int i = 0; i < n; i++)
            {
                if (random.NextDouble() >= 0.5)
                {
                    result[i] = 0;
                }
                else
                {
                    result[i] = 1;
                }
            }
            return result;
        }

        /// <summary>
        /// 生成 1/2 为 0, 1/4 为 1, 1/8 为 2 …… 的 <see cref="int"/> 数组。
        /// </summary>
        /// <param name="n">数组长度。</param>
        /// <returns>1/2 为 0, 1/4 为 1, 1/8 为 2 …… 的 <see cref="int"/> 数组。</returns>
        static int[] HalfAndHalf(int n)
        {
            int[] array = new int[n];
            HalfIt(0, 0, n / 2, array);
            Shuffle(array);
            return array;
        }

        /// <summary>
        /// 递归生成 1/2 为 0, 1/4 为 1, 1/8 为 2 …… 的 <see cref="int"/> 数组。
        /// </summary>
        /// <param name="start">填充起点。</param>
        /// <param name="number">起始编号。</param>
        /// <param name="length">填充长度</param>
        /// <param name="array">用于填充的数组。</param>
        /// <returns>一个 <see cref="int"/> 数组。</returns>
        static int[] HalfIt(int start, int number, int length, int[] array)
        {
            if (length == 0)
                return array;

            for (int i = 0; i < length; i++)
            {
                array[start + i] = number;
            }

            return HalfIt(start + length, number + 1, length / 2, array);
        }

        /// <summary>
        /// 生成一半是 0 一半是随机整数的 <see cref="int"/> 数组。
        /// </summary>
        /// <param name="n">数组大小。</param>
        /// <returns>生成一半是 0 一半是随机整数的 <see cref="int"/> 数组。</returns>
        static int[] HalfZeroHalfRandom(int n)
        {
            int[] array = new int[n];
            Random random = new Random();
            for (int i = 0; i < n / 2; i++)
            {
                array[i] = 0;
            }

            for (int i = n / 2; i < n; i++)
            {
                array[i] = random.Next();
            }

            Shuffle(array);

            return array;
        }

        /// <summary>
        /// 打乱数组。
        /// </summary>
        /// <param name="a">需要打乱的数组。</param>
        static void Shuffle(int[] a)
        {
            int N = a.Length;
            Random random = new Random();
            for (int i = 0; i < N; i++)
            {
                int r = i + random.Next(N - i);// 等于StdRandom.uniform(N-i)
                int temp = a[i];
                a[i] = a[r];
                a[r] = temp;
            }
        }
    }
}
另请参阅

Quick

2.3.31

题目

运行时间直方图。
编写一个程序,接受命令行参数 N 和 T,
用快速排序对大小为 N 的随机浮点数数组进行 T 次排序,
并将所有运行时间绘制成直方图。
令 N=10^3、10^4、10^5 和 10^6,
为了使曲线更平滑,T 值越大越好。
这个练习最关键的地方在于找到适当的比例绘制出实验结果。

解答

以下所有结果 T=70
N=1000
图片 36
N=10000
图片 37
N=100000
图片 38
N=1000000
图片 39

代码
using System;
using System.ComponentModel;
using System.Drawing;
using System.Linq;
using System.Windows.Forms;
using Quick;

namespace _2._3._31
{
    public partial class Form2 : Form
    {
        private int N;
        private int T;

        public Form2(int n, int t)
        {
            InitializeComponent();
            this.N = n;
            this.T = t;
        }

        /// <summary>
        /// 启动页面时启动后台测试。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void Form2_Shown(object sender, EventArgs e)
        {
            this.Text = "正在绘图";
            this.backgroundWorker1.RunWorkerAsync();
        }

        /// <summary>
        /// 后台测试方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_DoWork(object sender, DoWorkEventArgs e)
        {
            BackgroundWorker worker = sender as BackgroundWorker;
            QuickSort quick = new QuickSort();

            double percentPerTrial = 100.0 / this.T;
            double[] totalTime = new double[this.T];
            for (int i = 0; i < this.T; i++)
            {
                double[] data = SortCompare.GetRandomArrayDouble(this.N);
                totalTime[i] = SortCompare.Time(quick, data);
                worker.ReportProgress((int)(percentPerTrial * i));
            }

            e.Result = totalTime;
        }

        /// <summary>
        /// 更新后台进度方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_ProgressChanged(object sender, ProgressChangedEventArgs e)
        {
            this.Text = "正在测试,已完成 " + e.ProgressPercentage + " %";
        }

        /// <summary>
        /// 测试完毕,进行绘图的方法。
        /// </summary>
        /// <param name="sender"></param>
        /// <param name="e"></param>
        private void backgroundWorker1_RunWorkerCompleted(object sender, RunWorkerCompletedEventArgs e)
        {
            if (e.Error != null)
            {
                MessageBox.Show(e.Error.Message);
            }
            //新建画布
            Graphics graphics = this.CreateGraphics();

            //翻转默认坐标系
            graphics.TranslateTransform(0, this.Height);
            graphics.ScaleTransform(1, -1);

            double[] counts = e.Result as double[];

            //获取最大值
            double max = counts.Max();
            //计算间距
            double unit = this.Width / (3.0 * counts.Length + 1);
            double marginTop = 100;
            //计算直方图的矩形
            Rectangle[] rects = new Rectangle[counts.Length];
            rects[0].X = (int)unit;
            rects[0].Y = 0;
            rects[0].Width = (int)(2 * unit);
            rects[0].Height = (int)((counts[0] / max) * (this.Height - marginTop));
            for (int i = 1; i < counts.Length; ++i)
            {
                rects[i].X = (int)(rects[i - 1].X + 3 * unit);
                rects[i].Y = 0;
                rects[i].Width = (int)(2 * unit);
                rects[i].Height = (int)((counts[i] / (max + 1)) * (this.Height - marginTop));
            }

            //绘图
            graphics.FillRectangles(Brushes.Black, rects);

            //释放资源
            graphics.Dispose();

            this.Text = "绘图结果,最高耗时:" + counts.Max() + " 最低耗时:" + counts.Min();
        }
    }
}
另请参阅

BackgroundWorker 组件 | Microsoft
Docs
Quick

发表评论

电子邮件地址不会被公开。 必填项已用*标注