计算机系统概述

邻接表

建无向图的时候，add(a,b), add(b,a) ，所以每条边都是成对的，即编号 \((0,1)、(2,3)、(4,5) \dots\) 是一组 （正向边，反向边）, 所以如果 \(i\) 是正向边，那么它的反向边就是 \(i \oplus 1\)

1
2
3
4
5

int h[N], e[M], w[M], ne[M], idx;
void add(int a, int b, int c)
{
    e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}

线段树

基础知识

以查询区间最大值为例：
由分治的思想可知：区间 \([L,R]\) 的最大值等于 \(\max([L, M], [M + 1, R])\)
在区间 \([1,n]\) 上建线段树，以区间 \([1, 10]\) 为例，如图：

剪枝

1. 优化搜索顺序
2. 排除等效冗余

记忆化搜索与DP

质数拆分 题意：将 \(2019\) 拆分为若干个两两不同的质数之和，一共有多少种不同的方法？注意，交换顺序视为同一种方法

1. Duplicates 题意：给定 \(n \times n\) 的网格，其中每格数都属于 \([1,n]\) ，求最小的修改次数使得这个网格的每行以及每列都包含至少两个相同的数，并输出修改方案。
   Read more »