并查集 简单图论概念 kruscal求最小生成树 并查集 基本作用:维护点之间的连通性,支持合并 通常用于一些点,然后可以把一些点和另一些点合并成一类,然后还能查询两个点是否连通。 引入问题 输入n,Q(1≤n,Q≤105)n,Q(1 \leq n,Q \leq 10^5)n,Q(1≤n,Q≤10​5​​),表示n个点,刚开始互相独立。 之后Q行,代表Q次操作。 1 u v,表示在u和v之间连接一条边 2 u v,表示查询,输出u是否和v通过边连通,连通输出YES反之输出NO 如果每次都去搜索,显然复杂度是承受不了的,我们考虑如何去优化 对于一个连通图,我们考虑用一棵有根树去表示它们的连通性。 用P[i]表示一棵树中,i的父节点为P[i],最刚开始时初始化P[i]=iP[i]=iP[i]=i 对操作1,我们就找到u节点所在的那棵树的根节点记为r1,以及找到v节点所在的那棵树的根节点记为r2。如下图1: r1等于r2时,表示现在u和v已经连通了,加了这条边对连通性没有任何影响,所以我们忽略这次操作。 如果r1不等于r2,我们就把P[r1]=r2P[r1]=r2P[r1]=r2当然也可以
发表于 2017-02-12 20:45:39 | 条评论 | 阅读次数:386
前缀和 一维前缀和 问题1:静态区间求和 问题2:求是否有子区间之和%m等于x 问题3:n个数,选数字之和整除n 问题4:从两端延伸的问题 问题5:先区间更新,然后再区间查询 二维前缀和 问题1:静态子矩阵求和 问题2:先子矩阵更新,然后再子矩阵查询 取尺法 问题1:处理同一类连续区间 问题2:一类具有单调性的问题 前缀和 一维前缀和 定义pre[n]=∑ni=1A[i]pre[n] = \sum_n^{i=1}A[i]pre[n]=∑​n​i=1​​A[i] 问题1:静态区间求和 给定大小为n的数组(1≤n≤105)( 1 \leq n \leq 10^5)(1≤n≤10​5​​),接下来读入n个数字表示A[i](1≤A[i]≤109)A[i] (1 \leq A[i] \leq 10^9)A[i](1≤A[i]≤10​9​​) 接下来输入Q(1≤Q≤105)(1 \leq Q \leq 10^5)(1≤Q≤10​5​​),然后有Q行,表示Q次查询。 每次查询,输入l,r(1≤l≤r≤n)l, r(1 \leq l \leq r \leq n)l,r(1≤l≤r≤n)
发表于 2017-02-05 14:12:05 | 条评论 | 阅读次数:387
Copyright © 2017 - 2018 qwb's blog
blog.csustacm.com All Rights Reserved
Powered by qwb Contact me