树上算法选讲 July 22, 2018, riteme
|
|
|
- 友亵 高
- 4 years ago
- Views:
Transcription
1 树上算法选讲 July 22, 2018, riteme
2 Overview 今天的课主要讲三个内容 :
3 Overview 今天的课主要讲三个内容 : DFS 序最近公共祖先 (LCA) 倍增算法 Tarjan 离线算法树链剖分
4 Overview 今天的课主要讲三个内容 : DFS 序最近公共祖先 (LCA) 倍增算法 Tarjan 离线算法树链剖分这三个东西是处理与静态树有关的问题中常用的工具
5 DFS 序 DFS 序 就是 DFS 的顺序
6 DFS 序 DFS 序 就是 DFS 的顺序 从树根开始 DFS, 对于每棵子树,DFS 总是要先遍历完子树内部才会从子树根节点走出去
7 DFS 序 DFS 序 就是 DFS 的顺序 从树根开始 DFS, 对于每棵子树,DFS 总是要先遍历完子树内部才会从子树根节点走出去 DFS 访问一棵子树内的所有节点的时间是连续的
8 DFS 序 DFS 序 就是 DFS 的顺序 从树根开始 DFS, 对于每棵子树,DFS 总是要先遍历完子树内部才会从子树根节点走 出去 DFS 访问一棵子树内的所有节点的时间是连续的 记录全局变量 cur 表示时间, 每当访问一个新节点时 cur 加 1
9 DFS 序 DFS 序 就是 DFS 的顺序 从树根开始 DFS, 对于每棵子树,DFS 总是要先遍历完子树内部才会从子树根节点走出去 DFS 访问一棵子树内的所有节点的时间是连续的 记录全局变量 cur 表示时间, 每当访问一个新节点时 cur 加 1 对每个节点记录 in 和 out 两个值, 分别表示 DFS 首次进入的时间和 DFS 离开的时间 in 和强连通分量算法里面的 dfn 实际上是一个东西
10 DFS 序 DFS 序 就是 DFS 的顺序 从树根开始 DFS, 对于每棵子树,DFS 总是要先遍历完子树内部才会从子树根节点走出去 DFS 访问一棵子树内的所有节点的时间是连续的 记录全局变量 cur 表示时间, 每当访问一个新节点时 cur 加 1 对每个节点记录 in 和 out 两个值, 分别表示 DFS 首次进入的时间和 DFS 离开的时间 in 和强连通分量算法里面的 dfn 实际上是一个东西 子树 x 内所有节点的 DFS 序都在区间 [in[x], out[x]] 中 每棵子树对应一个区间
11 DFS 序 DFS 序 就是 DFS 的顺序 从树根开始 DFS, 对于每棵子树,DFS 总是要先遍历完子树内部才会从子树根节点走出去 DFS 访问一棵子树内的所有节点的时间是连续的 记录全局变量 cur 表示时间, 每当访问一个新节点时 cur 加 1 对每个节点记录 in 和 out 两个值, 分别表示 DFS 首次进入的时间和 DFS 离开的时间 in 和强连通分量算法里面的 dfn 实际上是一个东西 子树 x 内所有节点的 DFS 序都在区间 [in[x], out[x]] 中 每棵子树对应一个区间 [1,9] [2,7] [8,9] [3,3] [4,7] [9,9] [5,5] [6,6] [7,7]
12 POJ 3321 Apple Tree 给定一棵 n 个节点的苹果树, 进行 q 次操作 : 1. 在某个节点上摘下或者放上一个苹果 2. 询问某个子树中苹果总数 n, q 10 5
13 POJ 3321 Apple Tree 给定一棵 n 个节点的苹果树, 进行 q 次操作 : 1. 在某个节点上摘下或者放上一个苹果 2. 询问某个子树中苹果总数 n, q 10 5 利用 DFS 序, 将子树与区间相对应 然后使用线性数据结构 ( 线段树 树状数组 ) 来维护
14 最近公共祖先 两个节点的公共祖先中深度最大者被称为最近公共祖先 (Least Common Ancestor)
15 最近公共祖先 两个节点的公共祖先中深度最大者被称为最近公共祖先 (Least Common Ancestor) 假设在询问节点 u 和节点 v 的 LCA, 将一个节点的所有祖先 ( 包括自己 ) 标记, 然后另一个节点向上走, 遇到的第一个被标记的节点就是 LCA
16 最近公共祖先 两个节点的公共祖先中深度最大者被称为最近公共祖先 (Least Common Ancestor) 假设在询问节点 u 和节点 v 的 LCA, 将一个节点的所有祖先 ( 包括自己 ) 标记, 然后另一个节点向上走, 遇到的第一个被标记的节点就是 LCA
17 最近公共祖先 两个节点的公共祖先中深度最大者被称为最近公共祖先 (Least Common Ancestor) 假设在询问节点 u 和节点 v 的 LCA, 将一个节点的所有祖先 ( 包括自己 ) 标记, 然后另一个节点向上走, 遇到的第一个被标记的节点就是 LCA 显然这个暴力算法是 O(h) 的, h 是树的高度
18 另外一种暴力 如果 u 和 v 深度相同, 那么 u 和 v 同时向上走, 走到同一个节点时就是 LCA
19 另外一种暴力 如果 u 和 v 深度相同, 那么 u 和 v 同时向上走, 走到同一个节点时就是 LCA 如果深度不相同, 那就让深度大的先独自走一段, 直到深度相同为止
20 另外一种暴力 如果 u 和 v 深度相同, 那么 u 和 v 同时向上走, 走到同一个节点时就是 LCA 如果深度不相同, 那就让深度大的先独自走一段, 直到深度相同为止 这种算法减少了空间消耗
21 另外一种暴力 如果 u 和 v 深度相同, 那么 u 和 v 同时向上走, 走到同一个节点时就是 LCA 如果深度不相同, 那就让深度大的先独自走一段, 直到深度相同为止 这种算法减少了空间消耗 // depth 表示节点深度,father 是树上节点的父亲 function LCA(int u, int v): if depth[u] < depth[v]: // 方便处理, 令 u 为深度较大者 swap(u, v) while depth[u]!= depth[v]: u = father[u] if u == v: // 如果 v 是 u 的父亲, 那么 LCA(u, v) 就是 v return v while u!= v: u = father[u] v = father[v] return u
22 倍增优化 上一页的暴力算法中, 大部分时间花费在节点上跳这个步骤 确实一步一步地走相当 慢
23 倍增优化 上一页的暴力算法中, 大部分时间花费在节点上跳这个步骤 确实一步一步地走相当 慢 毕竟现在只有一个 father 数组, 每次只能走一步 倍增表尝试打破这个限制 : 计算出 jmp[x][k], 表示从节点 x 开始往上走 2 k 步的节点 father[x] 实际上就是 jmp[x][0]
24 倍增优化 上一页的暴力算法中, 大部分时间花费在节点上跳这个步骤 确实一步一步地走相当慢 毕竟现在只有一个 father 数组, 每次只能走一步 倍增表尝试打破这个限制 : 计算出 jmp[x][k], 表示从节点 x 开始往上走 2 k 步的节点 father[x] 实际上就是 jmp[x][0] 计算出 jmp 并不难, 因为走两个 2 k 1 步就是走一个 2 k 步, 也就是 jmp 有这样的 DP 转移 :
25 倍增优化 上一页的暴力算法中, 大部分时间花费在节点上跳这个步骤 确实一步一步地走相当慢 毕竟现在只有一个 father 数组, 每次只能走一步 倍增表尝试打破这个限制 : 计算出 jmp[x][k], 表示从节点 x 开始往上走 2 k 步的节点 father[x] 实际上就是 jmp[x][0] 计算出 jmp 并不难, 因为走两个 2 k 1 步就是走一个 2 k 步, 也就是 jmp 有这样的 DP 转移 : jmp[x][k] = jmp[ jmp[x][k 1] ][k 1]
26 倍增优化 上一页的暴力算法中, 大部分时间花费在节点上跳这个步骤 确实一步一步地走相当慢 毕竟现在只有一个 father 数组, 每次只能走一步 倍增表尝试打破这个限制 : 计算出 jmp[x][k], 表示从节点 x 开始往上走 2 k 步的节点 father[x] 实际上就是 jmp[x][0] 计算出 jmp 并不难, 因为走两个 2 k 1 步就是走一个 2 k 步, 也就是 jmp 有这样的 DP 转移 : jmp[x][k] = jmp[ jmp[x][k 1] ][k 1] 显然倍增表的大小是 O(n log h) 的
27 倍增优化 上一页的暴力算法中, 大部分时间花费在节点上跳这个步骤 确实一步一步地走相当慢 毕竟现在只有一个 father 数组, 每次只能走一步 倍增表尝试打破这个限制 : 计算出 jmp[x][k], 表示从节点 x 开始往上走 2 k 步的节点 father[x] 实际上就是 jmp[x][0] 计算出 jmp 并不难, 因为走两个 2 k 1 步就是走一个 2 k 步, 也就是 jmp 有这样的 DP 转移 : jmp[x][k] = jmp[ jmp[x][k 1] ][k 1] 显然倍增表的大小是 O(n log h) 的 现在来尝试使用倍增表来优化上跳过程 令 u 为深度较大者, 第一个步骤是调整 u 和 v 的深度, 从最高的幂次 2 M 开始, 如果 jmp[u][m] 的深度没超过 v, 那么 u 就可以先跳到那里 然后尝试 2 M 1 2 M 2...
28 倍增优化 上一页的暴力算法中, 大部分时间花费在节点上跳这个步骤 确实一步一步地走相当慢 毕竟现在只有一个 father 数组, 每次只能走一步 倍增表尝试打破这个限制 : 计算出 jmp[x][k], 表示从节点 x 开始往上走 2 k 步的节点 father[x] 实际上就是 jmp[x][0] 计算出 jmp 并不难, 因为走两个 2 k 1 步就是走一个 2 k 步, 也就是 jmp 有这样的 DP 转移 : jmp[x][k] = jmp[ jmp[x][k 1] ][k 1] 显然倍增表的大小是 O(n log h) 的 现在来尝试使用倍增表来优化上跳过程 令 u 为深度较大者, 第一个步骤是调整 u 和 v 的深度, 从最高的幂次 2 M 开始, 如果 jmp[u][m] 的深度没超过 v, 那么 u 就可以先跳到那里 然后尝试 2 M 1 2 M 2... 这个过程相当于二进制试位, 测试的是两点之间深度差的二进制
29 倍增优化 接下来的步骤是同时上跳 由于上跳的步伐很大, 所以经常会有 跳过头 的情况 k = 2 u v
30 倍增优化 接下来的步骤是同时上跳 由于上跳的步伐很大, 所以经常会有 跳过头 的情况 k = 2 u 这种情况不好判断两点重合是否就是 LCA, 所以换一个策略 : 只跳过不重合的部分 v
31 倍增优化 接下来的步骤是同时上跳 由于上跳的步伐很大, 所以经常会有 跳过头 的情况 k = 2 u v 这种情况不好判断两点重合是否就是 LCA, 所以换一个策略 : 只跳过不重合的部分 从 2 M 步开始枚举, 如果上跳后两个节点不重合, 则执行 这样最后 u 和 v 会停在 LCA 下面 同样是二进制试位的原理
32 倍增优化 接下来的步骤是同时上跳 由于上跳的步伐很大, 所以经常会有 跳过头 的情况 k = 2 u v 这种情况不好判断两点重合是否就是 LCA, 所以换一个策略 : 只跳过不重合的部分 从 2 M 步开始枚举, 如果上跳后两个节点不重合, 则执行 这样最后 u 和 v 会停在 LCA 下面 同样是二进制试位的原理 预处理出 jmp 的时空复杂度是 O(n log h), 之后每次 LCA 询问都是两次上跳, 复杂度均为 O(log h)
33 倍增优化 : 实现 function LCA(int u, int v): if depth[u] < depth[v]: swap(u, v) for k from M to 0: if depth[jmp[x][k]] <= depth[v]: u = jmp[x][k] if u == v: return u for k from M to 0: if jmp[u][k]!= jmp[v][k]: u = jmp[u][k] v = jmp[v][k] return father[u]
34 离线算法 如果允许不即时回答询问, 在已知所有询问的情况下, 最后统一给出答案, 称为离线处 理
35 离线算法 如果允许不即时回答询问, 在已知所有询问的情况下, 最后统一给出答案, 称为离线处理 Tarjan 老爷爷首先提出使用 DFS + 并查集来离线计算 LCA
36 再探 DFS DFS 本身的实现依赖于一个栈 在一棵树上 DFS 到 x 底, 恰好就是 x 的所有祖先 ( 包括 x 在内 ), 按照深度顺序排列 的时候, 栈中的元素从栈顶到栈
37 再探 DFS DFS 本身的实现依赖于一个栈 在一棵树上 DFS 到 x 的时候, 栈中的元素从栈顶到栈 底, 恰好就是 x 的所有祖先 ( 包括 x 在内 ), 按照深度顺序排列 回想第一个暴力 LCA 算法, 假设现在 DFS 到 v, 如果知道 u 在栈中的第一个祖先, 那么这个祖先就是 u 和 v 的 LCA
38 再探 DFS DFS 本身的实现依赖于一个栈 在一棵树上 DFS 到 x 的时候, 栈中的元素从栈顶到栈 底, 恰好就是 x 的所有祖先 ( 包括 x 在内 ), 按照深度顺序排列 回想第一个暴力 LCA 算法, 假设现在 DFS 到 v, 如果知道 u 在栈中的第一个祖先, 那么这个祖先就是 u 和 v 的 LCA u v
39 再探 DFS DFS 本身的实现依赖于一个栈 在一棵树上 DFS 到 x 的时候, 栈中的元素从栈顶到栈 底, 恰好就是 x 的所有祖先 ( 包括 x 在内 ), 按照深度顺序排列 回想第一个暴力 LCA 算法, 假设现在 DFS 到 v, 如果知道 u 在栈中的第一个祖先, 那么这个祖先就是 u 和 v 的 LCA u v 现在的任务就是要维护指向栈内元素的指针 ( 上图绿色箭头 )
40 Tarjan 最近公共祖先算法 当 DFS 在不同的儿子间切换时, 需要更新指针
41 Tarjan 最近公共祖先算法 当 DFS 在不同的儿子间切换时, 需要更新指针 x
42 Tarjan 最近公共祖先算法 当 DFS 在不同的儿子间切换时, 需要更新指针 x
43 Tarjan 最近公共祖先算法 当 DFS 在不同的儿子间切换时, 需要更新指针 x 之前 x 还在栈中, 所以子树 x 中的所有指针都是指向 x 的 当 DFS 离开 x 后, x 从栈顶被弹出, 此时整个子树 x 在栈中的祖先是 x 的父亲 这样可以维护所有已经被访问的节点的祖先指针
44 Tarjan 最近公共祖先算法 当 DFS 在不同的儿子间切换时, 需要更新指针 x 之前 x 还在栈中, 所以子树 x 中的所有指针都是指向 x 的 当 DFS 离开 x 后, x 从栈顶被弹出, 此时整个子树 x 在栈中的祖先是 x 的父亲 这样可以维护所有已经被访问的节点的祖先指针 如果要求 LCA,DFS 访问 v 的时候只需要节点 u 被访问过即可
45 Tarjan 最近公共祖先算法 当 DFS 在不同的儿子间切换时, 需要更新指针 x 之前 x 还在栈中, 所以子树 x 中的所有指针都是指向 x 的 当 DFS 离开 x 后, x 从栈顶被弹出, 此时整个子树 x 在栈中的祖先是 x 的父亲 这样可以维护所有已经被访问的节点的祖先指针 如果要求 LCA,DFS 访问 v 的时候只需要节点 u 被访问过即可 每次修改都是一整棵子树修改, 因此使用并查集把整棵子树连起来, 然后在代表元素处设置祖先指针
46 Tarjan 最近公共祖先算法 当 DFS 在不同的儿子间切换时, 需要更新指针 x 之前 x 还在栈中, 所以子树 x 中的所有指针都是指向 x 的 当 DFS 离开 x 后, x 从栈顶被弹出, 此时整个子树 x 在栈中的祖先是 x 的父亲 这样可以维护所有已经被访问的节点的祖先指针 如果要求 LCA,DFS 访问 v 的时候只需要节点 u 被访问过即可 每次修改都是一整棵子树修改, 因此使用并查集把整棵子树连起来, 然后在代表元素处设置祖先指针 每当一个儿子 DFS 完毕, 就把自己和儿子相连, 然后重新设置祖先指针
47 Tarjan 最近公共祖先算法 当 DFS 在不同的儿子间切换时, 需要更新指针 x 之前 x 还在栈中, 所以子树 x 中的所有指针都是指向 x 的 当 DFS 离开 x 后, x 从栈顶被弹出, 此时整个子树 x 在栈中的祖先是 x 的父亲 这样可以维护所有已经被访问的节点的祖先指针 如果要求 LCA,DFS 访问 v 的时候只需要节点 u 被访问过即可 每次修改都是一整棵子树修改, 因此使用并查集把整棵子树连起来, 然后在代表元素处设置祖先指针 每当一个儿子 DFS 完毕, 就把自己和儿子相连, 然后重新设置祖先指针 在每个节点处挂个链表, 对于询问 LCA(u, v), u 和 v 处的链表都加入这个询问, 方便快速查找
48 Tarjan 最近公共祖先算法 : 实现 function dfs(int x): // ancestor 表示祖先指针,marked 数组表示 DFS 是否遍历过 ancestor[find(x)] = x for v in G[x]: // 遍历 x 的所有儿子 v dfs(v) union(x, v) // 连接 x 和 v ancestor[find(x)] = x marked[x] = true for each query LCA(u, x): if marked[u]: LCA(u, x) = ancestor[find(u)]
49 Tarjan 最近公共祖先算法 : 实现 function dfs(int x): // ancestor 表示祖先指针,marked 数组表示 DFS 是否遍历过 ancestor[find(x)] = x for v in G[x]: // 遍历 x 的所有儿子 v dfs(v) union(x, v) // 连接 x 和 v ancestor[find(x)] = x marked[x] = true for each query LCA(u, x): if marked[u]: LCA(u, x) = ancestor[find(u)] 时间复杂度为 O((n + q)α(n)), 其中 q 为 LCA 的询问总数
50 求树上两点路径长度 给出一棵 n 个点的带权树, q 次询问 每次询问某两点间的距离 n, q
51 求树上两点路径长度 给出一棵 n 个点的带权树, q 次询问 每次询问某两点间的距离 n, q 首先一遍 DFS 求出每个点到根节点的距离 dist
52 求树上两点路径长度 给出一棵 n 个点的带权树, q 次询问 每次询问某两点间的距离 n, q 首先一遍 DFS 求出每个点到根节点的距离 dist 对于点 u 和点 v, 求出其 LCA 点 p, 那么距离就是 dist[u] + dist[v] - 2 * dist [p]
53 JLOI 2014 / LG P3258 松鼠的新家 给定一棵 n 个节点的树, 按照一定顺序依次访问树上的节点 在两个不同节点间是沿着两点间唯一的简单路径移动的 求最后每个节点被经过了多少次 n
54 JLOI 2014 / LG P3258 松鼠的新家 给定一棵 n 个节点的树, 按照一定顺序依次访问树上的节点 在两个不同节点间是沿着两点间唯一的简单路径移动的 求最后每个节点被经过了多少次 n 每次转移位置相当于将一条路径上所有节点的权值加 1
55 JLOI 2014 / LG P3258 松鼠的新家 给定一棵 n 个节点的树, 按照一定顺序依次访问树上的节点 在两个不同节点间是沿着两点间唯一的简单路径移动的 求最后每个节点被经过了多少次 n 每次转移位置相当于将一条路径上所有节点的权值加 1 利用差分的思想, 假设是 u 和 v 两个点, 两点处均 +1, 令 p 为 u 和 v 的 LCA, 如果用 DFS 求出每个节点的子树和, 发现 p 以及 p 的祖先的权值都是 2, 所以 p 和 p 的父亲处均还需要 1 这样求子树和后, 简单路径 u v 上的点权都为 1
56 JLOI 2014 / LG P3258 松鼠的新家 给定一棵 n 个节点的树, 按照一定顺序依次访问树上的节点 在两个不同节点间是沿着两点间唯一的简单路径移动的 求最后每个节点被经过了多少次 n 每次转移位置相当于将一条路径上所有节点的权值加 1 利用差分的思想, 假设是 u 和 v 两个点, 两点处均 +1, 令 p 为 u 和 v 的 LCA, 如果用 DFS 求出每个节点的子树和, 发现 p 以及 p 的祖先的权值都是 2, 所以 p 和 p 的父亲处均还需要 1 这样求子树和后, 简单路径 u v 上的点权都为 1 除了差分求和外就只剩求 LCA 了
57 树链剖分 树链剖分是用于处理树上路径操作的利器
58 树链剖分 树链剖分是用于处理树上路径操作的利器 顾名思义, 将树分解成一条一条的链, 从而可以使用线性数据结构来处理树上路径问 题
59 树链剖分 树链剖分是用于处理树上路径操作的利器 顾名思义, 将树分解成一条一条的链, 从而可以使用线性数据结构来处理树上路径问 题
60 树链剖分 树链剖分是用于处理树上路径操作的利器 顾名思义, 将树分解成一条一条的链, 从而可以使用线性数据结构来处理树上路径问题 为了方便处理, 这些链都没有转折的地方, 都是沿着向上的方向 某些链可能只有一个点
61 树链剖分 树链剖分是用于处理树上路径操作的利器 顾名思义, 将树分解成一条一条的链, 从而可以使用线性数据结构来处理树上路径问题 为了方便处理, 这些链都没有转折的地方, 都是沿着向上的方向 某些链可能只有一个点 此时树上的边分为两种 : 一类是链内部的边, 称为重边 ; 另一类则是链外部的边, 称为 轻边 轻重边的概念在讲并查集的时候提到过
62 树链剖分 树链剖分是用于处理树上路径操作的利器 顾名思义, 将树分解成一条一条的链, 从而可以使用线性数据结构来处理树上路径问题 为了方便处理, 这些链都没有转折的地方, 都是沿着向上的方向 某些链可能只有一个点 此时树上的边分为两种 : 一类是链内部的边, 称为重边 ; 另一类则是链外部的边, 称为 轻边 轻重边的概念在讲并查集的时候提到过 处理一条树上路径的时候, 通过这些链将路径切分成许多区间
63 树链剖分 树链剖分是用于处理树上路径操作的利器 顾名思义, 将树分解成一条一条的链, 从而可以使用线性数据结构来处理树上路径问题 为了方便处理, 这些链都没有转折的地方, 都是沿着向上的方向 某些链可能只有一个点 此时树上的边分为两种 : 一类是链内部的边, 称为重边 ; 另一类则是链外部的边, 称为 轻边 轻重边的概念在讲并查集的时候提到过 处理一条树上路径的时候, 通过这些链将路径切分成许多区间
64 树链剖分 每个节点下面只能有一条重边 通常选择这条重边的策略是根据儿子子树的大小, 选择 其中大小最大的儿子, 这个儿子也称为重儿子
65 树链剖分 每个节点下面只能有一条重边 通常选择这条重边的策略是根据儿子子树的大小, 选择其中大小最大的儿子, 这个儿子也称为重儿子 为什么要这么选择呢? 设当前节点为 x, 重儿子为 u, 显然子树大小超过 size[x] 的儿 子只能有一个, 因此除了 u 之外, 其它的子树大小不超过 size[x]
66 树链剖分 每个节点下面只能有一条重边 通常选择这条重边的策略是根据儿子子树的大小, 选择其中大小最大的儿子, 这个儿子也称为重儿子 为什么要这么选择呢? 设当前节点为 x, 重儿子为 u, 显然子树大小超过 size[x] 的儿 子只能有一个, 因此除了 u 之外, 其它的子树大小不超过 size[x] 这样轻边的定义和并查集时间复杂度分析里面的定义是一样的啦 轻边的性质非常好 : 从任意一个节点到根节点的路径上至多经过 log n 条轻边
67 树链剖分 每个节点下面只能有一条重边 通常选择这条重边的策略是根据儿子子树的大小, 选择其中大小最大的儿子, 这个儿子也称为重儿子 为什么要这么选择呢? 设当前节点为 x, 重儿子为 u, 显然子树大小超过 size[x] 的儿 子只能有一个, 因此除了 u 之外, 其它的子树大小不超过 size[x] 这样轻边的定义和并查集时间复杂度分析里面的定义是一样的啦 轻边的性质非常好 : 从任意一个节点到根节点的路径上至多经过 log n 条轻边
68 树链剖分 每个节点下面只能有一条重边 通常选择这条重边的策略是根据儿子子树的大小, 选择其中大小最大的儿子, 这个儿子也称为重儿子 为什么要这么选择呢? 设当前节点为 x, 重儿子为 u, 显然子树大小超过 size[x] 的儿 子只能有一个, 因此除了 u 之外, 其它的子树大小不超过 size[x] 这样轻边的定义和并查集时间复杂度分析里面的定义是一样的啦 轻边的性质非常好 : 从任意一个节点到根节点的路径上至多经过 log n 条轻边 除了最顶上的链, 其余链上的区间都是因为轻边的原因而被截断的 因此轻边的数量决定了将树上路径拆分成线性区间的数量 根据轻边的性质, 每条树上路径最多被拆分成 2 log n 个区间
69 树链剖分 每个节点下面只能有一条重边 通常选择这条重边的策略是根据儿子子树的大小, 选择其中大小最大的儿子, 这个儿子也称为重儿子 为什么要这么选择呢? 设当前节点为 x, 重儿子为 u, 显然子树大小超过 size[x] 的儿 子只能有一个, 因此除了 u 之外, 其它的子树大小不超过 size[x] 这样轻边的定义和并查集时间复杂度分析里面的定义是一样的啦 轻边的性质非常好 : 从任意一个节点到根节点的路径上至多经过 log n 条轻边 除了最顶上的链, 其余链上的区间都是因为轻边的原因而被截断的 因此轻边的数量决 定了将树上路径拆分成线性区间的数量 根据轻边的性质, 每条树上路径最多被拆分成 2 log n 个区间 如果是树上路径加的数据结构题, 再利用线段树或者树状数组就可以以单次操作 2 O(log n) 的时间复杂度解决了
70 树链剖分 : 实现 一般树链剖分都是两遍 DFS: 第一遍算出一些重要的信息, 如子树大小 size 每个节 点的父亲 father 节点的深度 depth 等
71 树链剖分 : 实现 一般树链剖分都是两遍 DFS: 第一遍算出一些重要的信息, 如子树大小 size 每个节点的父亲 father 节点的深度 depth 等 第二遍则正式进行树链剖分 为了方便寻找区间, 对每个点记录 top 表示自己所处的链的顶端的节点 为了能拆分区间, 同一条链上的节点按照顺序依次编号, 得到 id, 这样一条链在序列上就是连续的
72 树链剖分 : 实现 一般树链剖分都是两遍 DFS: 第一遍算出一些重要的信息, 如子树大小 size 每个节点的父亲 father 节点的深度 depth 等 第二遍则正式进行树链剖分 为了方便寻找区间, 对每个点记录 top 表示自己所处的链的顶端的节点 为了能拆分区间, 同一条链上的节点按照顺序依次编号, 得到 id, 这样一条链在序列上就是连续的 DFS 的时候先找出重儿子并且优先进入 这样 id 实际上也是 DFS 序
73 树链剖分 : 实现 一般树链剖分都是两遍 DFS: 第一遍算出一些重要的信息, 如子树大小 size 每个节点的父亲 father 节点的深度 depth 等 第二遍则正式进行树链剖分 为了方便寻找区间, 对每个点记录 top 表示自己所处的链的顶端的节点 为了能拆分区间, 同一条链上的节点按照顺序依次编号, 得到 id, 这样一条链在序列上就是连续的 DFS 的时候先找出重儿子并且优先进入 这样 id 实际上也是 DFS 序 拆分简单路径 u v 时, 如果 u 和 v 在同一条链上, 那么区间的端点就是 id[u] 和 id[v]
74 树链剖分 : 实现 一般树链剖分都是两遍 DFS: 第一遍算出一些重要的信息, 如子树大小 size 每个节点的父亲 father 节点的深度 depth 等 第二遍则正式进行树链剖分 为了方便寻找区间, 对每个点记录 top 表示自己所处的链的顶端的节点 为了能拆分区间, 同一条链上的节点按照顺序依次编号, 得到 id, 这样一条链在序列上就是连续的 DFS 的时候先找出重儿子并且优先进入 这样 id 实际上也是 DFS 序 拆分简单路径 u v 时, 如果 u 和 v 在同一条链上, 那么区间的端点就是 id[u] 和 id[v] 如果不在同一条链上, 就需要尝试跳到同一条链上 选取 top[u] 和 top[v] 中深度较大者, 因为它不可能在另外一条深度小的链的上方 假设是 top[u], 那么让 u 跳到链的顶端, 路径在链上拆分出一个区间 ( 从 u 到 top[u] ), 然后 u 走过一条轻边来到下一条链上 直到出现第一种情况为止
75 树链剖分 : 实现 一般树链剖分都是两遍 DFS: 第一遍算出一些重要的信息, 如子树大小 size 每个节点的父亲 father 节点的深度 depth 等 第二遍则正式进行树链剖分 为了方便寻找区间, 对每个点记录 top 表示自己所处的链的顶端的节点 为了能拆分区间, 同一条链上的节点按照顺序依次编号, 得到 id, 这样一条链在序列上就是连续的 DFS 的时候先找出重儿子并且优先进入 这样 id 实际上也是 DFS 序 拆分简单路径 u v 时, 如果 u 和 v 在同一条链上, 那么区间的端点就是 id[u] 和 id[v] 如果不在同一条链上, 就需要尝试跳到同一条链上 选取 top[u] 和 top[v] 中深度较大者, 因为它不可能在另外一条深度小的链的上方 假设是 top[u], 那么让 u 跳到链的顶端, 路径在链上拆分出一个区间 ( 从 u 到 top[u] ), 然后 u 走过一条轻边来到下一条链上 直到出现第一种情况为止 此外, 树链剖分也可以求解 LCA, 时间复杂度为 O(log n)
76 树链剖分 : 实现 一般树链剖分都是两遍 DFS: 第一遍算出一些重要的信息, 如子树大小 size 每个节点的父亲 father 节点的深度 depth 等 第二遍则正式进行树链剖分 为了方便寻找区间, 对每个点记录 top 表示自己所处的链的顶端的节点 为了能拆分区间, 同一条链上的节点按照顺序依次编号, 得到 id, 这样一条链在序列上就是连续的 DFS 的时候先找出重儿子并且优先进入 这样 id 实际上也是 DFS 序 拆分简单路径 u v 时, 如果 u 和 v 在同一条链上, 那么区间的端点就是 id[u] 和 id[v] 如果不在同一条链上, 就需要尝试跳到同一条链上 选取 top[u] 和 top[v] 中深度较大者, 因为它不可能在另外一条深度小的链的上方 假设是 top[u], 那么让 u 跳到链的顶端, 路径在链上拆分出一个区间 ( 从 u 到 top[u] ), 然后 u 走过一条轻边来到下一条链上 直到出现第一种情况为止 此外, 树链剖分也可以求解 LCA, 时间复杂度为 O(log n) 模板题 : ZJOI 2008 / LG P 树的统计
77 树链剖分 : 实现 用树链剖分求 LCA:
78 树链剖分 : 实现 用树链剖分求 LCA: int top[], father[], depth[] // 链顶 父亲节点 深度 function LCA(int u, int v): while top[u]!= top[v]: // 如果 u 和 v 不在同一条链上 if depth[top[u]] < depth[top[v]]: // 令 top[u] 为深度较大者, 这样 u 所在的链在 v 所在的链下方 swap(u, v) u = father[top[u]] // 上跳 // 退出 while 循环后, u 和 v 在同一条链上, 其中深度较小的就是 LCA if depth[u] < depth[v]: return u else: return v
79 HAOI 2015 / LG P3178 树上操作 给定一棵 n 个节点的树, 并执行 q 次操作 : 1. 把某个节点 x 的权值增加 a 2. 把以某个节点 x 为根的子树内的所有节点的权值增加 a 3. 查询某个节点 x 到根的路径上所有节点的权值和 n, q 10 5
80 HAOI 2015 / LG P3178 树上操作 给定一棵 n 个节点的树, 并执行 q 次操作 : 1. 把某个节点 x 的权值增加 a 2. 把以某个节点 x 为根的子树内的所有节点的权值增加 a 3. 查询某个节点 x 到根的路径上所有节点的权值和 n, q 10 5 前面提到过, 编号 id 实际上就是 DFS 序
81 HAOI 2015 / LG P3178 树上操作 给定一棵 n 个节点的树, 并执行 q 次操作 : 1. 把某个节点 x 的权值增加 a 2. 把以某个节点 x 为根的子树内的所有节点的权值增加 a 3. 查询某个节点 x 到根的路径上所有节点的权值和 n, q 10 5 前面提到过, 编号 id 实际上就是 DFS 序 所以直接的做法就是用 DFS 序来维护子树加, 用树链剖分来计算路径和
82 HAOI 2015 / LG P3178 树上操作 给定一棵 n 个节点的树, 并执行 q 次操作 : 1. 把某个节点 x 的权值增加 a 2. 把以某个节点 x 为根的子树内的所有节点的权值增加 a 3. 查询某个节点 x 到根的路径上所有节点的权值和 n, q 10 5 前面提到过, 编号 id 实际上就是 DFS 序 所以直接的做法就是用 DFS 序来维护子树加, 用树链剖分来计算路径和 有不使用树链剖分的方法吗?
83 HAOI 2015 / LG P3178 树上操作 给定一棵 n 个节点的树, 并执行 q 次操作 : 1. 把某个节点 x 的权值增加 a 2. 把以某个节点 x 为根的子树内的所有节点的权值增加 a 3. 查询某个节点 x 到根的路径上所有节点的权值和 n, q 10 5 有! 注意到它询问的是某个点到根节点的路径和, 这点十分可疑
84 HAOI 2015 / LG P3178 树上操作 给定一棵 n 个节点的树, 并执行 q 次操作 : 1. 把某个节点 x 的权值增加 a 2. 把以某个节点 x 为根的子树内的所有节点的权值增加 a 3. 查询某个节点 x 到根的路径上所有节点的权值和 n, q 10 5 有! 注意到它询问的是某个点到根节点的路径和, 这点十分可疑 联想到之前 再探 DFS 的类容, 可以考虑使用 DFS 的方式来离线处理
85 HAOI 2015 / LG P3178 树上操作 给定一棵 n 个节点的树, 并执行 q 次操作 : 1. 把某个节点 x 的权值增加 a 2. 把以某个节点 x 为根的子树内的所有节点的权值增加 a 3. 查询某个节点 x 到根的路径上所有节点的权值和 n, q 10 5 有! 注意到它询问的是某个点到根节点的路径和, 这点十分可疑 联想到之前 再探 DFS 的类容, 可以考虑使用 DFS 的方式来离线处理 给每个操作记录时间戳, 对询问而言, 只有时间戳小于自己的修改才是有效的
86 HAOI 2015 / LG P3178 树上操作 给定一棵 n 个节点的树, 并执行 q 次操作 : 1. 把某个节点 x 的权值增加 a 2. 把以某个节点 x 为根的子树内的所有节点的权值增加 a 3. 查询某个节点 x 到根的路径上所有节点的权值和 n, q 10 5 有! 注意到它询问的是某个点到根节点的路径和, 这点十分可疑 联想到之前 再探 DFS 的类容, 可以考虑使用 DFS 的方式来离线处理 给每个操作记录时间戳, 对询问而言, 只有时间戳小于自己的修改才是有效的 能影响到一个关于节点 x 的询问的修改只能在 x 到根节点的路径上 换句话说, 在 DFS 的栈里面
87 HAOI 2015 / LG P3178 树上操作 给定一棵 n 个节点的树, 并执行 q 次操作 : 1. 把某个节点 x 的权值增加 a 2. 把以某个节点 x 为根的子树内的所有节点的权值增加 a 3. 查询某个节点 x 到根的路径上所有节点的权值和 n, q 10 5 有! 注意到它询问的是某个点到根节点的路径和, 这点十分可疑 联想到之前 再探 DFS 的类容, 可以考虑使用 DFS 的方式来离线处理 给每个操作记录时间戳, 对询问而言, 只有时间戳小于自己的修改才是有效的 能影响到一个关于节点 x 的询问的修改只能在 x 到根节点的路径上 换句话说, 在 DFS 的栈里面 按照时间顺序维护一个树状数组, 将栈里面所有的修改都加到树状数组上 DFS 进入 / 离开节点的时候可以及时更新 询问时查询前缀和即可 这样就处理了单点修改
88 HAOI 2015 / LG P3178 树上操作 给定一棵 n 个节点的树, 并执行 q 次操作 : 1. 把某个节点 x 的权值增加 a 2. 把以某个节点 x 为根的子树内的所有节点的权值增加 a 3. 查询某个节点 x 到根的路径上所有节点的权值和 n, q 10 5 子树修改? 当然也是可以的 假设是把子树 x 内所有节点都加上 v, 对于子树 x 内的一个节点 y, 查询 y 到根节点的路径和的时候, 这个修改操作对查询的贡献是 (depth[y] depth[x] + 1) v
89 HAOI 2015 / LG P3178 树上操作 给定一棵 n 个节点的树, 并执行 q 次操作 : 1. 把某个节点 x 的权值增加 a 2. 把以某个节点 x 为根的子树内的所有节点的权值增加 a 3. 查询某个节点 x 到根的路径上所有节点的权值和 n, q 10 5 子树修改? 当然也是可以的 假设是把子树 x 内所有节点都加上 v, 对于子树 x 内的一个节点 y, 查询 y 到根节点的路径和的时候, 这个修改操作对查询的贡献是 (depth[y] depth[x] + 1) v 这个贡献可以视为两部分, 一部分是 depth[x] v, 这一部分只与 x 和 v 有关 ; 另外一部分是 (depth[y] + 1) v, 这一部分与 y 和 v 有关 所以还需要一个树状数组, 记录到根节点的路径上所有子树修改的 v 的和, 用于计算第二个部分 第一个部分则直接加入之前的树状数组
90 HAOI 2015 / LG P3178 树上操作 给定一棵 n 个节点的树, 并执行 q 次操作 : 1. 把某个节点 x 的权值增加 a 2. 把以某个节点 x 为根的子树内的所有节点的权值增加 a 3. 查询某个节点 x 到根的路径上所有节点的权值和 n, q 10 5 子树修改? 当然也是可以的 假设是把子树 x 内所有节点都加上 v, 对于子树 x 内的一个节点 y, 查询 y 到根节点的路径和的时候, 这个修改操作对查询的贡献是 (depth[y] depth[x] + 1) v 这个贡献可以视为两部分, 一部分是 depth[x] v, 这一部分只与 x 和 v 有关 ; 另外一部分是 (depth[y] + 1) v, 这一部分与 y 和 v 有关 所以还需要一个树状数组, 记录到根节点的路径上所有子树修改的 v 的和, 用于计算第二个部分 第一个部分则直接加入之前的树状数组 时间复杂度 O(n + q log n)
91 NOI 水题放送 模板题 : NOI 2015 / LG P 软件包管理器
PowerPoint Presentation
数据结构与算法 ( 六 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 6 章树 C 树的定义和基本术语 树的链式存储结构 子结点表 表示方法 静态 左孩子 / 右兄弟 表示法 动态表示法 动态 左孩子 / 右兄弟 表示法 父指针表示法及其在并查集中的应用
PowerPoint 演示文稿
差分与前缀和 湖南师大附中 ruanxingzhi 区间加 给定一个序列 a( 初值全为 0) 有很多次操作, 每个操作形如 : A l r k 将 a [l,r] 每个值加上 k. 最后输出整个数组 复杂度要求 O(n). 允许离线 区间加 代码 : ( 已经预先指定 a[0]=0) 区间加 我们很自然地想到 : 如果我们知道每一个元素比前一个元素大多少, 我们显然可以推出整个序列 e.g. 已知
IDEO_HCD_0716
IDEO HCD Toolkit Tencent CDC ...? Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC Tencent CDC
团 学 要 闻 我 校 召 开 共 青 团 五 届 九 次 全 委 ( 扩 大 ) 会 议 3 月 17 日, 我 校 共 青 团 五 届 九 次 全 委 ( 扩 大 ) 会 议 在 行 政 办 公 楼 五 楼 会 议 室 举 行, 校 团 委 委 员 各 院 ( 系 ) 团 委 书 记 校 学 生
共 青 团 工 作 简 报 2011 年 第 1 期 共 青 团 大 连 海 洋 大 学 委 员 会 团 学 要 闻 : 导 读 我 校 召 开 共 青 团 五 届 九 次 全 委 ( 扩 大 ) 会 议 我 校 在 大 连 市 大 学 生 创 新 创 意 作 品 大 赛 中 取 得 佳 绩 校 团 委 召 开 学 生 干 部 思 想 动 态 座 谈 会 校 团 委 组 织 开 展 弘 扬 雷 锋
汇集全球21位医生的经验和智慧，总结出最实用的专业建议，这些都是最值得你牢记的健康提醒
彙 集 全 球 21 位 醫 生 的 經 驗 和 智 慧, 總 結 出 最 實 用 的 專 業 建 議, 這 些 都 是 最 值 得 你 牢 記 的 健 康 提 醒 top1. 不 是 每 個 人 都 適 合 做 近 視 矯 行 手 術, 除 非 你 在 手 術 前 已 經 持 續 穩 定 地 佩 戴 了 一 年 以 上 的 近 視 眼 鏡 或 者 隱 形 眼 鏡 如 果 你 時 摘 時 戴 眼 鏡,
1 行 业 发 展 不 平 衡 我 国 房 地 产 中 介 服 务 业 起 步 较 晚, 专 业 分 工 程 度 和 国 外 发 达 国 家 相 比 还 有 很 大 差 距 房 地 产 中 介 服 务 行 业 的 发 展 水 平 与 房 地 产 开 发 行 业 的 市 场 化 水 平 密 切 相 关
房 地 产 中 介 服 务 : 仍 处 于 成 长 期, 市 场 空 间 巨 大 作 者 : 庞 增 华 房 地 产 中 介 服 务 业 内 的 企 业 包 括 依 法 设 立 并 具 备 房 地 产 中 介 资 格 的 房 地 产 顾 问 策 划 房 地 产 代 理 销 售 房 地 产 评 估 房 地 产 经 纪 等 中 介 服 务 机 构, 是 房 地 产 开 发 价 值 链 中 不 可 或 缺
运用伸展树解决数列维护问题
运用伸展树解决数列维护问题 By Crash 1 关键词 数列维护问题 伸展树 摘要 对于数列维护问题, 我们常用的一种手段是线段树 但使用线段树有一定的局限性, 本文介绍运用伸展树解决这类问题, 并且可以实现更多的功能 目录 (1) 伸展树的伸展操作 (2) 在伸展树中对区间进行操作 (3) 实例分析 NOI 2005 维护数列 (Sequence) (4) 和线段树的比较 1 Blog 地址 :http://hi.baidu.com/oimaster
2. 2. 2. 3. 3. 4 6. 6. 10. 20 01 37 02 38 03 39 04 39 05 40 06 42 42.. 43.. 43 45 45 47 48 1
2. 2. 2. 3. 3. 4 6. 6. 10. 20 01 37 02 38 03 39 04 39 05 40 06 42 42.. 43.. 43 45 45 47 48 1 2 5 3 2 4 1 1 1 2 2 2 3 3 3 4 4 1 2 3 4 5 2 1 1 1 2 2 3 4 3 2 2 5 6 7 4 1. 2. 3. 4. 5 6 尙 3 尙 3 2 7 1 5 8 尙
器之 间 向一致时为正 相反时则为负 ③大量电荷的定向移动形成电 流 单个电荷的定向移动同样形成电流 ３ 电势与电势差 １ 陈述概念 电场中某点处 电荷的电势能 Ｅ ｐ 与电荷量 ｑ Ｅｐ 的比值叫做该点处的电势 表达式为 Ｖ 电场中两点之间的 ｑ 电势之差叫做电势差 表达式为 ＵＡＢ Ｖ Ａ ＶＢ ２ 理解概念 电势差是电场中任意两点之间的电势之差 与参考点的选择无关 电势是反映电场能的性质的物理量
Two Mergeable Data Structures
Two Mergeable Data Structures Disjoint-Set 并查集 & Leftist-Tree 左偏树 1 Disjoint-Set(Union-Find Set) 并查集 N distinct elements into a collection of disjoint sets. Op1: Find which set a given element belong in
PowerPoint 演示文稿
The BitCoin Scripting Language 交易实例 交易结构 "result": { "txid": "921a dd24", "hash": "921a dd24", "version": 1, "size": 226, "locktime": 0, "vin": [ ], "vout": [ ], "blockhash": "0000000000000000002c510d
树的非递归中序和层次遍历实现
相信大家对树的各种递归的遍历很了解, 利用递归使得代码变得简单而且比较好理解, 但是利用递归是需要代价的, 特别是当递归层次比较深的时候, 可能会导致递归栈溢出 而且递归一般运行速度比较慢, 那么这种情况下, 我们就可以采用非递归来实现, 非递归相对递归来说, 代码相对比较难理解, 而且代码量也一般比较多, 可是它的执行效率却是很不错的 在树的中序非递归遍历中需要用到栈, 在层次遍历中需要用到队列,
204 */ InitiateStack s ; /* s */ i = n; t = p = new node; /* */ p->data = postorder[i]; while i > q = new node; if parent[i - ] == postorder[i] S,T S
![204 */ InitiateStack s ; /* s */ i = n; t = p = new node; /* */ p->data = postorder[i]; while i > q = new node; if parent[i - ] == postorder[i] S,T S](/thumbs/51/27926443.jpg "204 */ InitiateStack s ; /* s */ i = n; t = p = new node; /* */ p->data = postorder[i]; while i > q = new node; if parent[i - ] == postorder[i] S,T S")
28 4 Vol.28 No.4 4 204 2 JOURNAL OF NANTONG VOCATIONAL UNIVERSITY Dec. 204!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!! doi:0.3969/j.issn.008-5327.204.04.024 唐自立 ( 苏州大学计算机科学与技术学院, 江苏苏州 25006)
强连通分支、桥和割点
北京大学暑期课 ACM/ICPC 竞赛训练 北京大学信息学院郭炜 guo_wei@pku.edu.cn http://weibo.com/guoweiofpku 课程网页 :http://cm.pku.edu.cn/summerschool/pku_cm_trin.htm 强连通分支 桥和割点 北京大学信息学院郭炜 本讲义部分内容参考北京大学信息学院实验班袁洋 陈科吉同学讲义, 特此致谢 定义 在有向图
<5B BECBB0EDB8AEC1F25D312D34B0AD5FC3E2BCAEBCF6BEF7C0DAB7E F31702E504446>
: 2 = 3 4? 0 an ordered set of unambiguous, executable steps that produces a result and terminates in a finite time (computational theory) ( ) 5 6 (C-) int min, max; float degree, b; char ch, token; /,,,
星际探险
2 3 4 5 6 7 8 9 A N 0 N p N T u w u v T + w v A 0, 2, 3,, p 2 p p A 0, 2, 3,, p 2 p A 0 0 A S S 0 0 p S S S 0 0 p S Z w(s) S 0 A Z S 0 Z S w(s ) < w(s 0 ) Z S w(s ) < w(s 0 ) G G w(u, v) u v w 0 G w(u,
版面2
编 辑 的 话 10 月, 田 园 里 吹 过 的 风 清 爽 宜 人, 同 时 风 也 在 轻 声 地 提 醒 田 园, 你 该 换 上 新 衣 啦 这 时, 我 们 的 园 刊 也 悄 悄 翻 过 了 新 的 一 页, 这 次, 它 会 带 你 去 寻 找 新 的 宝 藏 新 的 发 现 我 们 去 了 干 部 学 院, 那 里,3 4 岁 的 孩 子 用 长 长 的 脚 印 寻 找 自 然 的
中共宿迁市委办公室发电
重 点 招 商 产 业 目 录 宿 迁 市 委 市 政 府 重 大 项 目 招 商 办 公 室 二 O 一 四 年 四 月 目 录 一 传 统 支 柱 产 业 ( 一 ) 酿 酒 食 品 产 业 1 ( 二 ) 纺 织 服 装 产 业 1 纺 织 印 染 服 务 中 心 项 目 2 ( 三 ) 林 木 加 工 产 业 2 ( 四 ) 玻 璃 建 材 产 业 2 ( 五 ) 机 械 电 子 产 业 3
Microsoft PowerPoint - 概率统计Ch02.ppt [Compatibility Mode]
![Microsoft PowerPoint - 概率统计Ch02.ppt [Compatibility Mode]](/thumbs/104/161694025.jpg "Microsoft PowerPoint - 概率统计Ch02.ppt [Compatibility Mode]")
66 随机变量的函数.5 随机变量的函数的分布 设 是一随机变量, 是 的函数, g(, 则 也是一个随机变量. 本节的任务 : 当 取值 x 时, 取值 y g 67 ( 一 离散型随机变量的函数 设 是离散型随机变量, 其分布律为 或 P { x } p (,, x x, P p p, x p 已知随机变量 的分布, 并且已知 g 要求随机变量 的分布. (, 是 的函数 : g(, 则 也是离散型随机变
エスポラージュ株式会社 住所 : 東京都江東区大島 東急ドエルアルス大島 HP: ******************* * 关于 Java 测试试题 ******
******************* * 关于 Java 测试试题 ******************* 問 1 运行下面的程序, 选出一个正确的运行结果 public class Sample { public static void main(string[] args) { int[] test = { 1, 2, 3, 4, 5 ; for(int i = 1 ; i System.out.print(test[i]);
未命名-1
1 2 3 4 5 6 7 8 9 10 11 12 ss a c y e vg 13 14 15 16 17 18 19 H 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 发现生命的螺旋 克里克在提出 中心法则 时曾指出 遗传信息是沿 Ｄ Ｎ Ａ - Ｒ Ｎ Ａ - 蛋白质的方向流动的 遗传信息不可能从 Ｒ Ｎ Ａ 回到 Ｄ Ｎ
中 国 共 产 党 广 州 市 花 都 区 委 员 会 政 法 委 员 会 1 广 州 市 海 珠 区 卫 生 局 1 广 州 市 越 秀 区 文 化 广 电 新 闻 出 版 局 1 广 州 市 科 学 技 术 协 会 1 广 州 市 花 都 区 残 疾 人 联 合 会 1 广 州 市 花 都 区
2014 年 度 广 州 市 5489 家 完 成 按 比 例 安 排 残 疾 人 就 业 的 用 人 单 位 名 单 ( 中 央 驻 穗 省 属 单 位 除 外 ) 单 位 名 称 已 安 排 残 疾 人 就 业 人 数 广 州 市 白 云 区 人 民 政 府 同 和 街 道 办 事 处 5 增 城 市 中 新 镇 人 民 政 府 4 从 化 市 城 郊 街 道 办 事 处 4 广 州 市 从 化
离散数学
The number of spanning trees longhuan@sjtu.edu.cn 树的刻画 树 (Tree): 连通无环图 树的例子 : TT 1 TT 2 TT 3 3 叶子 (leaf) 叶子 (leaf): 图 GG 中度数为 1 的顶点被称为叶子或终点 (end-vertex) 引理 : 对任意树 TT, 如果 TT 2, 则 TT 必含有至少两个终点 证明 : 取 TT
帝国CMS下在PHP文件中调用数据库类执行SQL语句实例
帝国 CMS 下在 PHP 文件中调用数据库类执行 SQL 语句实例 这篇文章主要介绍了帝国 CMS 下在 PHP 文件中调用数据库类执行 SQL 语句实例, 本文还详细介绍了帝国 CMS 数据库类中的一些常用方法, 需要的朋友可以参考下 例 1: 连接 MYSQL 数据库例子 (a.php)
untitled
1-1 1-2 1-3 1-4 1-5 1-6 1-7 1-8 1-1-1 C int main(void){ int x,y,z; int sum=0; double avg=0.0; scanf("%d",&x) ; scanf("%d",&y) ; scanf("%d",&z) ; sum=x+y+z ; avg=sum/3.0; printf("%f\n",avg); system("pause");
Figure 1: Game Tree 为 了 方 便 讨 论, 我 们 这 里 设 这 里 讨 论 的 博 弈 树 是 一 棵 有 限 树, 设 有 两 个 棋 手 甲 与 乙 进 行 这 场 博 弈, 这 样, 博 弈 树 分 为 三 类 结 点 : 1. 奇 数 层 的 非 叶 子 结 点 :
从 极 大 极 小 算 法 到 主 要 变 例 搜 索 孙 锴 1 综 述 人 机 对 弈 在 计 算 机 诞 生 前 就 开 始 了 发 展, 时 至 今 日, 人 机 对 弈 领 域 提 出 的 搜 索 算 法 数 目 已 经 非 常 之 多, 但 从 根 本 上 看, 许 多 搜 索 算 法 之 间 的 内 在 的 核 心 思 想 是 一 致 的 本 文 介 绍 将 从 极 大 极 小 搜 索
0.33 URAL Orthography URAL Team.GOV! URAL Fisherman an
2016 2 snowyjone 0.1 LA2512 - Art Gallery................................. 3 0.2 LA3890 - Most Distant Point from the Sea...................... 3 0.3 LA4992 - Jungle Outpost...............................
无类继承.key
无类继承 JavaScript 面向对象的根基 周爱 民 / aimingoo aiming@gmail.com https://aimingoo.github.io https://github.com/aimingoo rand = new Person("Rand McKinnon",... https://docs.oracle.com/cd/e19957-01/816-6408-10/object.htm#1193255
四、實務實習課程之實習工作日誌(請貼上掃描檔)
四 實 務 實 習 課 程 之 實 習 工 作 日 誌 ( 請 貼 上 掃 描 檔 ) 教 育 部 補 助 大 學 校 院 開 設 海 洋 主 題 導 向 專 業 課 程 計 畫 實 務 實 習 課 程 修 課 學 生 工 作 日 誌 表 ( 一 學 生 一 表 ) 課 程 名 稱 : 景 觀 規 劃 ( 海 洋 休 閒 ) 實 習 地 點 : 原 本 山 景 觀 有 限 公 司 時 間 工 作 說
五 參 與 政 治 活 動 之 限 制 綜 觀 中 立 法, 其 重 點 在 於 適 度 規 範 公 務 人 員 參 與 政 治 活 動, 可 分 為 消 極 性 的 行 為 規 範 及 積 極 性 參 與 政 治 活 動 的 限 制 規 範 兩 種 前 者 除 依 法 行 政 公 平 對 待 等
公 務 人 員 本 於 依 法 行 政 之 原 則, 應 熟 悉 中 立 法 之 內 容 並 嚴 守 其 規 定 壹 前 言 公 務 人 員 對 行 政 中 立 應 有 之 認 識 李 志 強 公 務 人 員 行 政 中 立 法 ( 以 下 簡 稱 中 立 法 ) 草 案 於 今 (98) 年 5 月 19 日 經 立 法 院 第 7 屆 第 3 會 期 第 13 次 會 議 完 成 三 讀 程 序,
Microsoft Word - 专升本练习5：图.doc
第五章 图 一 选择题 1. 关键路径是事件结点网络中的 ( ) A. 从源点到汇点的最长路径 B. 从源点到汇点的最短路径 C. 最长的回路 D. 最短的回路 2. 一个具有 n 个顶点和 e 条边的无向图, 采用邻接表表示, 表向量的大小为 ( 1 ), 所有顶点 邻接表的结点总数为 ( 2 ) 1A. n B. n+1 C. n-1 D. n+e 2A. e/2 B. e C. 2e D. n+e
PowerPoint Presentation
数据结构与算法 ( 六 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg A 第 6 章树 B C 树的定义和基本术语 树的链式存储结构 子结点表 表示方法 静态 左孩子 / 右兄弟 表示法 动态表示法 动态 左孩子 / 右兄弟 表示法 父指针表示法及其在并查集中的应用
ç®Šæ³Łç«žèµłè¿łéŸ¶æ„⁄å“Š.pdf
0x00 基本算法 位运算补码表示法, 理解 C++ 无符号 有符号整数在计算机中的存储方式各种按位运算, 包括取位 置位 移位等, 以及一些常见技巧快速幂,64 位整数乘法二进制状态压缩, 使用二进制数对状态进行压缩 提取的方法枚举 模拟 递推能想象问题 状态空间, 理解各种基本算法其实是对状态空间的遍历与映射常见的枚举形式, 无法设计有效算法时能够通过枚举的方式直接遍历状态空间通过模拟, 主要侧重代码实现能力的训练递推边界
幸 福 就 业 工 程 建 设 工 作 提 供 了 参 考
前 言 05 年 就 业 形 势 异 常 严 峻, 高 校 毕 业 生 的 就 业 状 况 受 到 了 党 中 央 的 高 度 重 视 和 全 社 会 的 广 泛 关 注 中 荷 学 院 紧 紧 围 绕 学 校 就 业 工 作 总 目 标, 在 完 善 学 院 高 端 就 业 市 场 建 设 的 同 时, 提 出 促 进 学 生 幸 福 就 业 的 理 念, 并 逐 步 在 毕 业 生 中 推 进
说 : 荀 子 极 偏 驳, 只 一 句 性 恶, 大 本 已 失 5 朱 熹 说 : 荀 扬 不 惟 说 性 不 是, 从 头 到 底 皆 不 识 6 采 取 的 都 是 这 种 理 论 框 架 另 一 种 理 论 框 架 始 于 20 世 纪 前 期, 这 便 是 诸 子 学 研 究 的 框 架
第 一 章 绪 论 1. 问 题 与 文 献 本 文 试 图 探 讨 的 核 心 问 题, 一 言 以 蔽 之, 是 要 理 解 并 诠 释 荀 子 思 想 的 基 本 性 格 先 交 代 研 究 方 法 迄 今 为 止 的 荀 学 研 究 1 大 致 存 在 两 种 研 究 框 架 第 一 种 研 究 框 架 是 理 学 研 究 的 理 论 框 架 2, 该 框 架 主 张 以 孔 孟 作 为 研
C++ 程序设计 告别 OJ1 - 参考答案 MASTER 2019 年 5 月 3 日 1
C++ 程序设计 告别 OJ1 - 参考答案 MASTER 2019 年 月 3 日 1 1 INPUTOUTPUT 1 InputOutput 题目描述 用 cin 输入你的姓名 ( 没有空格 ) 和年龄 ( 整数 ), 并用 cout 输出 输入输出符合以下范例 输入 master 999 输出 I am master, 999 years old. 注意 "," 后面有一个空格,"." 结束,
撰 寫 人 :2B1 王 清 燕 書 名 : 追 風 箏 的 女 孩 條 碼 號 :0112667 4 月 份 閱 讀 心 得 佳 作 我 覺 得 這 是 一 本 教 我 們 用 殘 酷 的 角 度 認 識 生 命 的 小 說 ; 與 同 儕 甚 是 摯 友 間 也 可 能 出 現 競 奪 下 的
4 月 讀 後 心 得 佳 作 撰 寫 人 :2B1 王 芝 蓉 書 名 : 姊 姊 的 守 護 者 條 碼 號 :0117530 乍 看 之 下 你 會 覺 得 莎 菈 是 很 不 公 平 的, 但 是 當 你 讀 完 姐 姐 的 守 護 者 這 本 書, 你 會 發 現 莎 菈 其 實 也 不 過 是 一 位 再 平 凡 不 過 的 母 親, 她 從 沒 想 過 要 如 何 救 凱 特, 她 只
chap07.key
#include void two(); void three(); int main() printf("i'm in main.\n"); two(); return 0; void two() printf("i'm in two.\n"); three(); void three() printf("i'm in three.\n"); void, int 标识符逗号分隔,
给定一个长度为 n 包含 100 个变量的布尔公式 F, 判断 F 是否可满足是 NP-complete, 假设 P NP. 2. Multiple Choices Select One (15 problems, 2 points each) 单选题 (15 题, 每题 2 分 ) Each qu
上海科技大学 2018 年攻读硕士学位研究生 招生考试试题 科目代码 :991 考生须知 : 1. 本试卷满分为 150 分, 全部考试时间总计 180 分钟 2. 所有答案必须写在答题纸上, 写在试题纸上或草稿纸上一律无效 3. 每道题的中文部分均已翻译为英文, 考生可在中英文中任选一种语言作答 1. True or False (5 problems, 2 points each) 判断题 (5
数据结构虐哭空巢 记 啦 by 去不了冬令营的徐叔叔 前 搞过的东西就不再写了 ( 数组队列栈链表 线段树动态树替 KD 树树状数组 Splay 替罪 Treap 线段树合并 Trie 合并 可持久化 Trie 可持久化线段树 线段树优化 DP 优化连边 ) 要写的是 李超线段树吉利线段树线段树分裂
数据结构虐哭空巢 记 啦 by 去不了冬令营的徐叔叔 前 搞过的东西就不再写了 ( 数组队列栈链表 线段树动态树替 KD 树树状数组 Splay 替罪 Treap 线段树合并 Trie 合并 可持久化 Trie 可持久化线段树 线段树优化 DP 优化连边 ) 要写的是 李超线段树吉利线段树线段树分裂虚树树链的并 还要进 步学习 线段树分治 进制分组珂朵莉树 数据结构题注意点 如果更新某点, 为了 便访问到其孩,
恒 大, 薪 酬 总 额 涨 幅 在 30-40% 之 间 ; 一 些 业 绩 增 长 温 和 的 房 企, 如 招 商 地 产, 薪 酬 总 额 增 幅 也 超 过 20% 2 行 业 薪 酬 比 率 维 持 稳 定, 薪 酬 总 额 增 幅 不 净 利 润 增 幅 差 距 加 大 行 业 薪 酬
2014 年 中 国 房 地 产 企 业 薪 酬 报 告 文 /CRIC 研 究 中 心 年 初, 我 们 収 布 了 2013 年 中 国 房 地 产 企 业 薪 酬 报 告, 得 到 业 内 人 士 的 普 遍 关 注 11 月 5 日, 由 中 国 房 地 产 业 协 会 指 导, 地 产 人 网 和 兊 而 瑞 研 究 中 心 将 在 北 京 联 合 収 布 新 一 期 的 2014 年 中
目 录
企 业 人 才 支 持 政 策 汇 编 国 家 千 人 计 划 1 创 新 人 才 长 期 项 目 1 创 新 人 才 短 期 项 目 2 创 业 人 才 项 目 3 外 专 千 人 计 划 项 目 4 青 年 千 人 计 划 项 目 6 国 家 万 人 计 划 7 科 技 创 新 领 军 人 才 7 科 技 创 业 领 军 人 才 9 百 千 万 工 程 领 军 人 才 11 青 年 拔 尖 人
7
孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 10 月 19 日 1 堆与优先队列列 哈夫曼树 2 介绍 一种特殊的完全 二叉树 这种 二叉树的顺序存储表示 堆 优先队列列的概念及使 用堆的实现 方法 3 每个结点的值都 小于 ( 或者都 大于 ) 它的左右 子树的根结点的值 这种 二叉树的 广度优先周游序列列顺序表示中, 用于存放结点的顺序表具有如下性质
演算法導入、ソート、データ構造、ハッシュ
培訓 - 1 演算法導入 ソート データ構造 ハッシュ 演算法導入 ソート データ構造 ハッシュ momohuang c2251393 chiangyo September 23, 2013 1 Schedule of the Year 1.1 Major Competition 9 12 11 10 12 10 TOI 的最 3 TOI 3 TOI 100 20 4 TOI 30 12 5 TOI
OOP with Java 通知 Project 4: 4 月 19 日晚 9 点
OOP with Java Yuanbin Wu cs@ecnu OOP with Java 通知 Project 4: 4 月 19 日晚 9 点 复习 类的复用 组合 (composition): has-a 关系 class MyType { public int i; public double d; public char c; public void set(double x) { d
PowerPoint Presentation
数据结构与算法 ( 七 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 7 章图 7.1 图的定义和术语 7.2 图的抽象数据类型 7.3 图的存储结构 7.5 最短路径 7.6 最小生成树 2 图的遍历 (graph traversal)
北 京 拜 博 拜 尔 口 腔 医 院 知 春 路 门 北 京 市 海 淀 区 白 塔 庵 汉 荣 家 园 1 号 楼 一 层 诊 北 京 拜 博 拜 尔 口 腔 医 院 东 城 门 诊 北 京 市 东 城 区 海 运 仓 一 号 瀚 海 海 运 仓 大 厦 一 层 159 号 北 京 拜 博 拜
齿 科 护 理 门 店 列 表 拜 博 口 腔 门 店 地 址 客 服 热 线 400-0000-033 城 市 门 店 地 址 拜 博 口 腔 建 国 分 院 哈 尔 滨 市 道 里 区 建 国 街 47 号 哈 尔 滨 沈 阳 大 连 成 都 重 庆 北 京 拜 博 口 腔 长 江 总 院 哈 尔 滨 市 南 岗 区 宣 化 街 1 号 拜 博 口 腔 和 平 分 院 哈 尔 滨 市 和 平 路
责任编辑：张望望
2014 年 7 月 31 日 责 任 编 辑 : 张 望 望 投 资 要 点 : 热 点 风 格 渐 变 打 新 资 金 猛 增 权 重 股 休 整 政 策 地 图 开 启 炒 新 炒 小 又 来 了 个 股 信 息 精 粹 大 洲 兴 业 (600603) 收 购 在 扬 影 视 神 剑 股 份 (002361) 上 半 年 业 绩 增 长 33.55% 中 海 达 (300177) 拟 定 增
Microsoft PowerPoint - ds-1.ppt [兼容模式]
![Microsoft PowerPoint - ds-1.ppt [兼容模式]](/thumbs/42/23092976.jpg "Microsoft PowerPoint - ds-1.ppt [兼容模式]")
http://jwc..edu.cn/jxgl/ HomePage/Default.asp 2 说 明 总 学 时 : 72( 学 时 )= 56( 课 时 )+ 16( 实 验 ) 行 课 时 间 : 第 1 ~14 周 周 学 时 : 平 均 每 周 4 学 时 上 机 安 排 待 定 考 试 时 间 : 课 程 束 第 8 11 12 章 的 内 容 为 自 学 内 容 ; 目 录 中 标 有
试卷代号 : 座位号 I II 中央广播电视大学 学年度第二学期 " 开放本科 " 期末考试 数据结构试题 2011 年 7 月! 题号 I - I 二 三 四! 五! 六 总分 分数 I I I 1 1- I ---1 I 得分 评卷人 一 单项选择
试卷代号 : 1 0 1 0 座位号 I II 中央广播电视大学 2 0 1 0-2 0 1 1 学年度第二学期 " 开放本科 " 期末考试 数据结构试题 2011 年 7 月! 题号 I - I 二 三 四! 五! 六 总分 分数 I I I 1 1- I ---1 I 得分 评卷人 一 单项选择题 ( 在括号内填写所选择的标号 每小题 2 分, 共 1 8 分 ) 1. 一种抽象数据类型包括数据和
7. 下图中所使用的数据结构是 ( ) 压入 A 压入 B B 弹出 B 压入 C C A A A A A. 哈希表 B. 栈 C. 队列 D. 二叉树 8. 在 Windows 资源管理器中, 用鼠标右键单击一个文件时, 会出现一个名为 复制 的 操作选项, 它的意思是 ( ) A. 用剪切板中的
第十九届全国青少年信息学奥林匹克联赛初赛 普及组 C++ 语言试题 竞赛时间 :2013 年 10 月 13 日 14:30~16:30 选手注意 : 试题纸共有 9 页, 答题纸共有 2 页, 满分 100 分 请在答题纸上作答, 写在试题纸上的一律无效 不得使用任何电子设备 ( 如计算器 手机 电子词典等 ) 或查阅任何书籍资料 一 单项选择题 ( 共 20 题, 每题 1.5 分, 共计 30
D2 17/10 食 完 早 餐 去 中 山 陵 和 明 孝 陵, 灵 谷 寺 到 景 区 的 巴 士 : 游 1 游 2 游 3 20 9 路 ( 票 价 在 1-2 元 间 ) 三 个 地 点 中 间 凭 门 票 免 费 乘 坐 景 区 小 火 车 往 来 晚 上 有 力 气 的 话 去 夫 子
D1 16/10 火 車 站 搭 藍 色 地 鐵 1 號 綫 ( 往 迈 皋 桥 站 方 向 ) 到 新 街 口 站 6 號 出 口 出 直 行 D2 17/10 食 完 早 餐 去 中 山 陵 和 明 孝 陵, 灵 谷 寺 到 景 区 的 巴 士 : 游 1 游 2 游 3 20 9 路 ( 票 价 在 1-2 元 间 ) 三 个 地 点 中 间 凭 门 票 免 费 乘 坐 景 区 小 火 车 往
6 tree
6 树和二叉树 董洪伟 http://hwdong.com 1 树和二叉树 主要内容一 树的类型定义二 二叉树的类型定义三 二叉树的存储结构四 二叉树的操作五 线索二叉树六 树和森林七 赫夫曼树八 树的计数 2 树的类型定义 树是一个层次结构的抽象模型 树是由具有父子关系的结点构成的 应用示例 : - 组织结构 - 文件系统 Computers R Us Sales Manufacturing R&D
大侠素材铺
编译原理与技术 语法制导翻译 Ⅱ 计算机科学与技术学院 李诚 22/10/2018 Announcement Tutorial on Thursday (25/10/2018) 3B201, Class time Assignment review Q & A Cheng @ Compiler Fall 2018, USTC 2 主要内容 源程序 词法分析器 token 语法分析器 分析树 语义分析
标题，黑体18号
从 商 业 用 地 供 应 看 各 城 市 商 业 地 产 市 场 泡 沫 VIEW 近 几 年, 房 地 产 商 涉 足 商 业 地 产 领 域 的 现 象 越 来 越 普 遍, 包 括 万 科 龙 湖 招 商 等 典 型 房 企 先 后 专 门 设 立 了 商 业 地 产 管 理 部 门, 并 逐 步 加 大 了 对 商 业 地 产 的 投 入 比 例 放 眼 全 国 重 点 城 市, 短 短
Open topic Bellman-Ford算法与负环
Open topic Bellman-Ford 2018 11 5 171860508@smail.nju.edu.cn 1/15 Contents 1. G s BF 2. BF 3. BF 2/15 BF G Bellman-Ford false 3/15 BF G Bellman-Ford false G c = v 0, v 1,..., v k (v 0 = v k ) k w(v i 1,
CC213
: (Ken-Yi Lee), E-mail: feis.tw@gmail.com 49 [P.51] C/C++ [P.52] [P.53] [P.55] (int) [P.57] (float/double) [P.58] printf scanf [P.59] [P.61] ( / ) [P.62] (char) [P.65] : +-*/% [P.67] : = [P.68] : ,
Fuzzy GP
: 林 理論 數 論 1 率 2 類,, 金流量 金 利 數 益,, 3 不 異 (Multi- Valued) (Single-Valued) 數 數 數 (Local Optimum) (Global Optimum) 4 (Multi-valued) (Non-linear) (Self-learning) 5 (Genetic Programming, GP) GP 1. 亂數 2. (individuals)
7. 下图中所使用的数据结构是 ( ) 压入 A 压入 B B 弹出 B 压入 C C A A A A A. 哈希表 B. 栈 C. 队列 D. 二叉树 8. 在 Windows 资源管理器中, 用鼠标右键单击一个文件时, 会出现一个名为 复制 的 操作选项, 它的意思是 ( ) A. 用剪切板中的
第十九届全国青少年信息学奥林匹克联赛初赛 普及组 Pascal 语言试题 竞赛时间 :2013 年 10 月 13 日 14:30~16:30 选手注意 : 试题纸共有 9 页, 答题纸共有 2 页, 满分 100 分 请在答题纸上作答, 写在试题纸上的一律无效 不得使用任何电子设备 ( 如计算器 手机 电子词典等 ) 或查阅任何书籍资料 一 单项选择题 ( 共 20 题, 每题 1.5 分, 共计
水晶分析师
大数据时代的挑战 产品定位 体系架构 功能特点 大数据处理平台 行业大数据应用 IT 基础设施 数据源 Hadoop Yarn 终端 统一管理和监控中心(Deploy,Configure,monitor,Manage) Master Servers TRS CRYSTAL MPP Flat Files Applications&DBs ETL&DI Products 技术指标 1 TRS
8
孙猛 http://www.math.pku.edu.cn/teachers/sunm 2017 年 10 月 26 日 1 树及其抽象数据类型 树的实现 树林林 2 树的 几种不不同表现形式 3 4 html head body meta title h1 ul h2 li li a 5 树是 n(n 0) 个结点的有限集 T,T 非空时满 足 : 有且仅有 一个特殊的称为根 (root) 的结点
清 流 月 刊 中 華 民 國 九 十 七 年 一 月 號 論 述 大 陸 透 視 法 令 天 地 工 作 園 地 科 技 新 知 健 康 生 活 生 態 保 育 文 與 藝 友 善 校 園 快 樂 學 習 其 他 這 一 會 兒 野 鴿 子 飛 去 那 兒 了? 莫 不 是 我 推 窗 時 驚 嚇
清 流 月 刊 中 華 民 國 九 十 七 年 一 月 號 論 述 大 陸 透 視 法 令 天 地 工 作 園 地 科 技 新 知 健 康 生 活 生 態 保 育 文 與 藝 友 善 校 園 快 樂 學 習 其 他 雖 然 聲 名 狼 藉, 但 也 並 非 一 無 用 處 鼠 年 談 鼠 賀 新 年 于 愷 駿 歲 月 匆 匆, 轉 眼 間 丁 亥 豬 年 過 去, 戊 子 鼠 年 到 來 趁 著
这 样 的 俗 语 吗, 就 是 3 岁 养 成 的 习 惯 到 80 岁 所 以 我 们 知 道 在 孩 童 3 岁 的 时 候, 就 基 本 人 格 形 成 的 阶 段 了 所 以 总 认 为 小, 这 样 想 是 不 行 的 因 为 3 岁 就 形 成 了 精 神 判 断 力,6 岁 就 已
日 期 :2001 年 5 月 6 日 题 目 : 教 养 孩 童, 使 他 走 当 行 的 道 证 道 : 赵 镛 基 牧 师 经 文 : 箴 言 22 章 6 节 教 养 孩 童, 使 他 走 当 行 的 道, 就 是 到 老 他 也 不 偏 离 绪 论 今 天 我 与 大 家 分 享 的 题 目 是, 教 养 孩 童, 使 他 走 当 行 的 道 今 天 不 单 是 圣 餐 主 日, 也 是
PowerPoint 演示文稿
数据结构与算法 ( 五 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第五章 的概念 的抽象数据类型 深度优先搜索 宽度优先搜索 的存储结构 D B A E G C H F I 二叉搜索树 堆与优先队列 Huffman 树及其应用 2 5.2
鸿利国际娱乐城在线赌博 ,中保人寿保险有限公司88鸿利终身保险条款（98版
鸿 利 国 际 娱 乐 城 在 线 赌 博 条 款 (98 版, 中 保 人 寿 保 险 有 限 公 司 88 鸿 利 终 身 保 险 189 http://www.unibox2.com 鸿 利 国 际 娱 乐 城 在 线 赌 博, 中 保 人 寿 保 险 有 限 公 司 88 鸿 利 终 身 保 险 条 款 (98 版 本 条 款 有 关 名 词 释 义 如 下 : 意 外 伤 害 : 是 指
关于做好2010年优秀运动员免试进入
体 科 字 2015 163 号 国 家 体 育 总 局 科 教 司 关 于 做 好 2016 年 优 秀 运 动 员 免 试 进 入 高 等 学 校 学 习 有 关 事 宜 的 通 知 各 省 自 治 区 直 辖 市 体 育 局, 总 参 军 训 和 兵 种 部 体 育 训 练 局 总 政 宣 传 部 文 化 体 育 局, 有 关 运 动 项 目 管 理 中 心, 有 关 高 等 学 校 : 根
e bug 0 x=0 y=5/x 0 Return 4 2
e 1 4 1 4 4.1 4.2 4.3 4.4 4.5 e 2 4.1 bug 0 x=0 y=5/x 0 Return 4 2 e 3 4 3 e 4 (true) (false) 4 4 e 5 4 5 4.2 1 G= V E V={n1,n2,,n m } E={e1,e2,,e p } e k ={n i,n j }, n i,n j V e 6 4.2 4 6 1 e 3 n 1 e
C++ 程序设计 OJ9 - 参考答案 MASTER 2019 年 6 月 7 日 1
C++ 程序设计 OJ9 - 参考答案 MASTER 2019 年 6 月 7 日 1 1 CARDGAME 1 CardGame 题目描述 桌上有一叠牌, 从第一张牌 ( 即位于顶面的牌 ) 开始从上往下依次编号为 1~n 当至少还剩两张牌时进行以下操作 : 把第一张牌扔掉, 然后把新的第一张放到整叠牌的最后 请模拟这个过程, 依次输出每次扔掉的牌以及最后剩下的牌的编号 输入 输入正整数 n(n
六域链联盟 SDChain-Matrix 节点搭建指南 2018/07/26 Version : 1.0.0
SDChain-Matrix 节点搭建指南 目录 1 环境要求... 3 2 软件下载... 4 3 安装部署... 4 3.1 部署可执行程序目录... 4 3.2 部署配置文件目录... 4 3.3 部署数据库文件目录... 4 3.4 部署日志文件目录... 4 3.5 部署依赖库文件目录... 4 4 配置参数... 5 5 启动运行... 7 5.1 普通模式启动... 7 5.2 加载启动模式...
幻灯片 1
北京大学暑期课 ACM/ICPC 竞赛训练 北京大学信息学院郭炜 guo_wei@pku.edu.cn http://weibo.com/guoweiofpku 课程网页 :http://acm.pku.edu.cn/summerschool/pku_acm_train.htm 最小生成树 (MST) 问题 北京大学信息学院 郭炜 / 郑聃崴 / 陈国鹏 图的生成树 在一个连通图 G 中, 如果取它的全部顶点和一部分边构成一个子图
第 卷 随着科技的迅速发展 通信网络 电力网络 交通网络已经成为人们生产 生活不可缺少的一部分 对网络定量与定性特征的科学理解 已成为网络时代科学研究中一个极其重要的挑战性课题 甚至被称为 网络的新科学 网络在建立起物质 信息 能量传递桥梁的同时 也为故障传播提供了条件 网络可靠性水平对网络能否正常
年 月 第 卷 第 期! " ** 一种新的有源网络可靠性参数及其算法 李瑞莹 党 炜 北京航空航天大学可靠性与系统工程学院 北京 ** 北京航空航天大学可靠性与环境工程技术重点实验室 北京 ** 中国科学院空间应用工程与技术中心 北京 *** 摘要 为了解决现有有源网络可靠性参数不能描述网络中源点与指定节点集中一定百分比端点间连通能力的问题 提出了一种新的有源网络可靠性参数 4 可靠度 并阐述了参数的具体概念与内涵
通过Hive将数据写入到ElasticSearch
我在 使用 Hive 读取 ElasticSearch 中的数据 文章中介绍了如何使用 Hive 读取 ElasticSearch 中的数据, 本文将接着上文继续介绍如何使用 Hive 将数据写入到 ElasticSearch 中 在使用前同样需要加入 elasticsearch-hadoop-2.3.4.jar 依赖, 具体请参见前文介绍 我们先在 Hive 里面建个名为 iteblog 的表,
PowerPoint Presentation
数据结构与算法 ( 三 ) 张铭主讲 采用教材 : 张铭, 王腾蛟, 赵海燕编写高等教育出版社,2008. 6 ( 十一五 国家级规划教材 ) http://www.jpk.pku.edu.cn/pkujpk/course/sjjg 第 3 章栈与队列 栈 栈的应用 递归到非递归的转换 队列 2 栈 (Stack) 操作受限的线性表 运算只在表的一端进行 队列 (Queue) 运算只在表的两端进行
C/C++ - 函数
C/C++ Table of contents 1. 2. 3. & 4. 5. 1 2 3 # include # define SIZE 50 int main ( void ) { float list [ SIZE ]; readlist (list, SIZE ); sort (list, SIZE ); average (list, SIZE ); bargragh
B. 军队发布命令 第 4 层 司令 第 3 层军长 1 军长 2 第 2 层师长 1 师长 2 师长 3 师长 4 第 1 层团长 1 团长 2 团长 3 团长 4 团长 5 团长 6 团长 7 团长 8 C. 国际会议中, 每个人都与他国地位对等的人直接进行会谈 第 4 层 英国女王 瑞典国王
第十八届全国青少年信息学奥林匹克联赛初赛 提高组 C++ 语言试题 竞赛时间 :2012 年 10 月 13 日 14:30~16:30 选手注意 : 试题纸共有 15 页, 答题纸共有 2 页, 满分 100 分 请在答题纸上作答, 写在试题纸上的一律无效 不得使用任何电子设备 ( 如计算器 手机 电子词典等 ) 或查阅任何书籍资料 一 单项选择题 ( 共 10 题, 每题 1.5 分, 共计 15
Microsoft Word - ACL044900-chapter00a-1ed.docx
+= 1) k k 2) 3) 4) RMQ 5) DP DP DP 6) k iv 7) Bash Wythoff Nim SG surreal number 49 序 號 解 題 策 略 和 重 要 演 算 法 所 在 章 節 1 2 3 k 4 5 1 6 7 8 9 10 11 Dinic 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
什么是函数式编程?
函数式编程 FUNCTIONAL PROGRAMMING byvoid@byvoid.com 什么是函数式编程? 真相是 从停机问题开始 Bug 假设有停机判定算法 function halting(func, input) { } return if_func_will_halt_on_input; 充分利用停机判定 function ni_ma(func) { if (halting(func,
: ( -. [ ~ ] ) [, ],,,, [ ] [ ] [ ],,, :,, [,, ], ;, ;,,,, ~ %,,. [ ],,( ) ; ( ),..
![: ( -. [ ~ ] ) [, ],,,, [ ] [ ] [ ],,, :,, [,, ], ;, ;,,,, ~ %,,. [ ],,( ) ; ( ),..](/thumbs/51/28011839.jpg ": ( -. [ ~ ] ) [, ],,,, [ ] [ ] [ ],,, :,, [,, ], ;, ;,,,, ~ %,,. [ ],,( ) ; ( ),..")
.. * 面向虚拟视点图像绘制的深度图编码算法 1 朱波, 蒋刚毅 **, 张云,, 郁梅 (., ;., ) :,,,, ;,, ;,,,.,,, ~ % : ; ; :. : : - ( ) - -, - **,,, (.,,, ;..,,, ) :, -., -., -,.., -.,..,,, % %. : - ; ;, [, ], (, ), [, ] [, ],, [ ],,,, [ ]
牛客寒假训练营1题解
牛客寒假算法基础集训营 1 By attack204/fastle 小 a 的计算器 考点 : 模拟 本场的良心签到题 由于我们得到了最终的数, 而且整个操作都是可逆的, 因此直接倒序模拟即可 小 a 与 "204" 考点 : 贪心模拟 输入的序列其实用处不大, 因为最终不需要输出方案, 我们只需要记录下 2/0/4 分别出现的次数即可 一个显然的构造策略是首先放置 4, 0, 4, 0, 直到其中一个用光
<4D F736F F D C6F0D6D8D0D4C4DCB1EDA1AAA1AAB9E9B5B5B0E6>
XZJ5940JQZ800 全地面起重机 QAY800 全地面起重机 ( 起重性能表 ) 中华人民共和国徐州工程机械集团有限公司徐州重型机械有限公司 目录 一 七节主臂工况起重性能表 支腿全伸... 7 1 七节主臂 _t-1 支腿全伸 12.8m 13m, 平衡重 0t... 7 2 七节主臂 _t-2 支腿全伸 12.8m 13m, 平衡重 0t... 7 3 七节主臂 _t-1 支腿全伸 12.8m
gta 5 serial key number pciker
Gta 5 Serial Key Number Pciker >>> http://shurll.com/7nott 1 / 5 2 / 5 Keep..rea... 2016 年 1 月 3 日 - download..gta..5..serial..number..of..the..most..exclusive..pageviews..selforganizing..ngos,..live..stories..and..easy..policies..regarding..to..containing..my...
架, 可 考 慮 報 警 處 理 12. 記 住 金 融 卡 只 能 將 款 項 轉 出, 不 能 轉 入 Top
清 流 月 刊 中 華 民 國 九 十 三 年 7 月 號 論 述 大 陸 透 視 法 令 天 地 工 作 園 地 科 技 新 知 健 康 生 活 生 態 保 育 文 與 藝 旅 遊 觀 光 其 他 防 制 不 法 集 團 利 用 金 融 卡 犯 罪 金 融 卡 問 世, 除 減 輕 銀 行 作 業 負 擔 外, 提 供 便 捷 之 提 款 轉 帳 繳 費 查 詢 等 功 能, 已 成 為 民 眾
第 1 题 : 寻宝游戏 (hunt), 运行时限 1s, 内存上限 12M,100 分 问题描述 某大学每年都会有一次 Mystery Hunt 的活动, 玩家需要根据设置的线索解谜, 找到宝藏的位置, 前一年获胜的队伍可以获得这一年出题的机会 作为新生的你, 对这个活动非常感兴趣 你每天都要从西
NOI2018 湖南省组队选拔赛 第一试试题 一. 题目概况 题目名称 寻宝游戏 转盘 毒瘤 目录 hunt circle duliu 可执行文件名 hunt circle duliu 输入文件名 hunt.in circle.in duliu.in 输出文件名 hunt.out circle.out duliu.out 每个测试点时限 1 秒 2 秒 1 秒 测试点数目 10 10 20 每个测试点分值
国家质检总局直属机关党委(政工办)
中 国 出 入 境 检 验 检 疫 协 会 文 件 中 检 协 2014 30 号 关 于 公 布 2014 年 中 国 质 量 诚 信 企 业 名 单 的 通 知 各 地 检 验 检 疫 协 会, 各 有 关 企 业 : 2014 年, 根 据 质 量 诚 信 企 业 管 理 办 法 ( 试 行 ) 质 量 诚 信 活 动 实 施 方 案, 按 照 企 业 申 报 协 会 审 核 直 属 局 同
亮麗水顏
口 夏 口 亀 喘 嗽 之 論 治 演 講 者 : 和 平 中 醫 聯 合 診 所 李 阿 立 醫 師 時 間 :101/08/12 14:00~15:30 地 點 : 臺 中 市 大 墩 文 化 中 心 李 院 長 小 檔 案 62 年 度 國 家 考 試 中 醫 師 特 種 考 試 及 格 台 中 市 中 醫 師 公 會 第 十 五 屆 理 事 長 和 平 中 醫 醫 院 創 院 院 長 日 本
数字带通 带阻 高通滤波器的设计 把一个归一化原型模拟低通滤波器变换成另一个所需类型的模拟滤波器, 再将其数字化 直接从模拟滤波器通过一定的频率变换关系完成所需类型数字滤波器的设计 先设计低通型的数字滤波器, 再用数字频率变化方法将其转换成所需类型数字滤波器
数字带通 带阻 高通滤波器的设计 把一个归一化原型模拟低通滤波器变换成另一个所需类型的模拟滤波器, 再将其数字化 直接从模拟滤波器通过一定的频率变换关系完成所需类型数字滤波器的设计 先设计低通型的数字滤波器, 再用数字频率变化方法将其转换成所需类型数字滤波器 模拟原型方法 : 模拟低通 - 模拟带通 H ( j) H ( j) 3 3 3 模拟原型方法 : 模拟低通 - 模拟带通 H ( j) 模拟低通
新婚夫妇必读（九）.doc
...1...3...4...5...9...9...10...12...14 3...19...20...22...27...28...30...31...35...37 I 13...39...44...48...49...50...51...54...55...58...60...62...63...66...67...68...70...71 TOP10...73...77...79...80
Fig1 Theforceappliedtothetrainwhenrunning :w = w j +w q (3) :w = w = w 0 +w j (4) w i 121 基本阻力 w r = 600 R ( N/kN) (8) :R : [2] w s [3] w s =0
![Fig1 Theforceappliedtothetrainwhenrunning :w = w j +w q (3) :w = w = w 0 +w j (4) w i 121 基本阻力 w r = 600 R ( N/kN) (8) :R : [2] w s [3] w s =0](/thumbs/88/114838964.jpg "Fig1 Theforceappliedtothetrainwhenrunning :w = w j +w q (3) :w = w = w 0 +w j (4) w i 121 基本阻力 w r = 600 R ( N/kN) (8) :R : [2] w s [3] w s =0")
31 4 2012 8 JournalofLanzhouJiaotongUniversity Vol31No4 Aug2012 :1001-4373(2012)04-0097-07 * 张友兵 张 波 ( 100073) : 分析了列车运行过程中的受力情况 给出了制动过程中减速度的计算方法 并采用正向 反向两种迭代方式计算列车制动曲线 两种方式计算出的制动曲线一致 证明了计算制动曲线的方法是正确的
2010年第3期（总第11期）
2016 年 第 2 期 ( 总 第 55 期 ) 图 书 馆 微 信 公 众 号 信 息 荟 萃 广 东 食 品 药 品 职 业 学 院 图 书 馆 编 目 录 高 职 教 育 职 业 院 校 实 习 告 别 放 羊 式 管 理...4 校 企 合 作, 职 业 院 校 的 学 生 还 满 意 吗...7 用 好 互 联 网 +, 读 懂 95 后 高 职 生...10 食 品 资 讯 农 业 部
<4D F736F F D20B3F5B6FEC7EFBCBEB5DACBC4BDB2BFCEBAF3D7F7D2B5B4F0B0B8A3A8BCE2B6CBB0E0A3A92E646F63>
初二秋季第四讲课后作业答案 ( 尖端班 ) 几何变换 旋转 习题. 为等边 内一点, = 3, = 3, 求证 : 以 为边可以构成一个三角形, 并确定所构成的三角形的各内角的度数. 解析 绕点 旋转 到 ', 可得 ' 就是以 为边构成的三 角形, 则 ' = 3 60 = 63, ' = 3 60 = 53, ' = 80 63 53 = 64, 即三角形各个内角度数分别为 53 63 和 64
树的定义 如图, a b a b a b a b c d c d c d c d e f e f e f e f (a) G 1 (b) G 2 (c) G 3 (d) G 4 G 1 和 G 2 是树, 它们都是没有回路的简单图 G 3 不是树, 因为结点 a, b, e, d 构成回路 G 4
Chapter 7 树 Discrete Mathematics November 29, 2011 黄正华, 数学与统计学院, 武汉大学 71 Contents 1 树与生成树 1 2 根树及其应用 8 72 1 树与生成树 树与生成树 1 树的定义 2 生成树 3 最小生成树 4 Kruskal 算法树是图论中重要的概念之一, 在计算机科学中有广泛的运用 73 树的定义 Definition 1
7000() 10 1400 373 1900 1608 1970 3696 5000() 30 1500 446 1920 1790 1975 4066 2500() 40 1600 486 1930 1996 1980 4453 0(, ) 230 1650 545 1940 2252 1981 4530 1000 275 1700 623 1950 2525 1982 4607 1100 306
第四章 １０２ 图 ４唱１６ 基于图像渲染的理论基础 三张拍摄图像以及它们投影到球面上生成的球面图像 拼图的圆心是相同的 而拼图是由球面图像上的弧线图像组成的 因此我 们称之为同心球拼图 如图 ４唱１８ 所示 这些拼图中半径最大的是圆 Ｃｋ 最小的是圆 Ｃ０ 设圆 Ｃｋ 的半径为 ｒ 虚拟相机水平视域为 θ 有 ｒ Ｒ ｓｉｎ θ ２ ４畅１１ 由此可见 构造同心球拼图的过程实际上就是对投影图像中的弧线图像
Microsoft PowerPoint - plan06.ppt
程 序 设 计 语 言 原 理 Principle of Programming Languages 裘 宗 燕 北 京 大 学 数 学 学 院 2012.2~2012.6 6. 基 本 控 制 抽 象 子 程 序 抽 象 子 程 序 活 动 和 局 部 环 境 静 态 实 现 模 型 一 般 实 现 模 型 调 用 序 列 和 在 线 展 开 参 数 机 制 泛 型 子 程 序 异 常 处 理 其
数学分析（Ｉ）短课程 [Part 2] 4mm 自然数、整数和有理数
![数学分析（Ｉ）短课程 [Part 2] 4mm 自然数、整数和有理数](/thumbs/51/27870416.jpg "数学分析（Ｉ）短课程 [Part 2] 4mm 自然数、整数和有理数")
.. 数学分析 (I) 短课程 [Part 2] 自然数 整数和有理数 孙伟 华东师范大学数学系算子代数中心 Week 2 to 18. Fall 2014 孙伟 ( 数学系算子代数中心 ) 数学分析 (I) 短课程 Week 2 to 18. Fall 2014 1 / 78 3. 自然数理论初步 孙伟 ( 数学系算子代数中心 ) 数学分析 (I) 短课程 Week 2 to 18. Fall 2014