并查集 简单图论概念 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 | 条评论 | 阅读次数:412
新年的第一周,决定尝试坚持把每日一题做完 那么问题来了,窝能坚持几天呢QAQ Alyona and Triangles Fibonotci Boxes Cleaning Valera and Number Tree Game Different Subsets For All Tuples Checking cubes Multipliers Eefun Guessing Words Bit Difference Decreasing Number of Visible Box Alyona and Triangles 找到面积最大的三角形面积。然后做A关于BC中心的对称点A’,同理做出B’,C’,那么A’B’C’构成的三角形会包含所有的点,且面积<=4S 找最大三角形面积,是一个经典的题,先求个凸包,然后在凸包上两点法就好了 #include <map>#include <set>#include <cmath>#include <ctime>#include <stack>#include <queu
发表于 2017-02-09 20:29:47 | 条评论 | 阅读次数:163
Mahmoud and Longest Uncommon Subsequence Mahmoud and a Triangle Mahmoud and a Message Mahmoud and a Dictionary Mahmoud and a xor trip Mahmoud and Longest Uncommon Subsequence 其实只要比较两个字符串是否相等就好了 #include <map>#include <set>#include <cmath>#include <ctime>#include <stack>#include <queue>#include <cstdio>#include <cctype>#include <bitset>#include <string>#include <vector>#include <climits>#include <cstring>#include <iostr
发表于 2017-02-09 20:19:01 | 条评论 | 阅读次数:273
前缀和 一维前缀和 问题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 | 条评论 | 阅读次数:408
总结 smarty mysql php js html & css OVER 总结 这次花了快6天的时间,才把这个博客写好。中间最大的几个问题分别如下: 中间拜年什么的花了一些时间T^T 对smarty,js,和前端都非常的不熟悉,几乎是全程在百度,浪费了非常多的时间 后台方面的话,对mysql也非常的不熟,所以也占用了非常多的时间 一些代码的实现,虽然相对于acm的编程难度来说,非常简单实现,但是写起来非常的烦躁,导致中间浪费了很多时间去看电视或者做别的,而不能专心的抓紧时间解决 界面在最开始的时候并没有完全的弄好,导致一边写前端,一边改后端,然后又改前端,再改后端,浪费了很多时间在修改上面,应该先确定目的,然后一次性写好 总而言之,感觉不足的地方还有很多,也希望这次机会能多积累一些经验。 smarty php部分的函数 require '/smarty/libs/Smarty.class.php';$smarty = new Smarty();$smarty->caching = true;//设置开启缓存$smarty->cache_lifeti
发表于 2017-02-05 11:30:54 | 条评论 | 阅读次数:455
莫比乌斯函数和莫比乌斯反演问题,其实是属于两种问题。 这里我们只讨论莫比乌斯函数,首先来看莫比乌斯函数的定义: μ(n)=1\mu(n)=1μ(n)=1,如果n=1 μ(n)=−1\mu(n)=-1μ(n)=−1,如果n只由x个质数相乘得到,且质数各不相同,且x为奇数 μ(n)=1\mu(n)=1μ(n)=1,如果n只由x个质数相乘得到,且质数各不相同,且x为偶数 μ(n)=0\mu(n)=0μ(n)=0,n为其他情况时 其实单纯的莫比乌斯函数的题,就是容斥定理而已… 我们来个题来抛砖引玉 传送门 对于这个题,我们很容易的就会考虑到求A[B[i]]序列和B[A[i]]序列,然后把值相等的下标都选出来,现在问题就转换成了,给定两个集合A和集合B,在集合A中选一个数,在集合B中选一个数,使得两个数互质,问有多少对 我们用num[i]来表示,集合A中有多少个数字,是i的倍数。 那么很容易就能想到下面这个容斥定理的做法: #include <map>#include <set>#include <cmath>#include <ctime>#include
发表于 2017-02-04 14:51:31 | 条评论 | 阅读次数:363
Codeforces758A Holiday Of Equality Codeforces758B Blown Garland Codeforces758C Unfair Poll Codeforces758D Ability To Convert Codeforces758E Broken Tree Codeforces758F Geometrical Progression Codeforces758A Holiday Of Equality 水题 #include <map>#include <set>#include <cmath>#include <ctime>#include <stack>#include <queue>#include <cstdio>#include <cctype>#include <bitset>#include <string>#include <vector>#include <cstring>#inclu
发表于 2017-02-02 14:35:12 | 条评论 | 阅读次数:251
Copyright © 2017 - 2018 qwb's blog
blog.csustacm.com All Rights Reserved
Powered by qwb Contact me