写在前面

整个项目都托管在了 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}
$$

发表评论

电子邮件地址不会被公开。 必填项已用*标注