[综合] POJ---3685（Matrix，二分搜索）

题意： 给定一个N*N矩阵，其中Aij=i2+100000×i+j2-100000×j+i×j。 求矩阵中第K大的数。 题解： 自然的想法还是算出来所有的Aij，排序，然后二分找第K大的数，时间复杂度又来打了O（N2），肯定会超时。 注意观察Aij=i2+100000×i+j2-100000×j...

[综合] POJ---2010（Moo University - Financial Aid，优先队列）

题意： 一共C个学生，学校要录N(奇数)个，每个学生的分数和需要的aid给出，学校最多能提供F资金，求录取的学生中分数中位数最大。 题解： 方法1：对所有的学生按照分数进行从小到大排序，左边从第N/2+1个学生开始，到第C-N/2个学生结束，算出每个学生以他的分数为中位数，左边需要的最小总aid，需...

[综合] POJ---3662（Telephone Lines，最短路+二分*好题）

题意： 给定一个无向有权图，权值代表修建电线需要的花费，公司给报销K条线，这个人需要付款剩下的线路中花费最大的那个线路。 题解： 最短路问题，只不过这时候的最短路不是让求最短的距离了，而是给定一个花费X，是否有一条通路能够满足，恰好有K+1条路满足>=X，这个X就是可行解。二分去求最小的可行...

[综合] POJ---1759（Garland，二分一个，求另一个的最优）

题意： N个点，每个点离X轴的距离满足如下关系：H1=AHi=(Hi-1+Hi+1)/2-1,forall1<i<NHN=BHi>=0,forall1<=i<=N 一直A，求B的最小值。 题解： 由递推关系式可以知道，确定H2，剩下的所有H都可以确定，二分求H2的最小，...

[综合] POJ---3484（Showstopper，二分）

题意： 给定若干个等差序列，这些个等差序列中每个元素出现的次数为偶数才算正常，现在有一个BUG：仅有一个元素出现了奇数次，让你找出这个元素和它出现的次数！ 题解： 找特性：仅有一个元素出现了奇数次。举个栗子。 12345678910 4 12345 678910 很明显bug元素是4。也就是前...

[综合] POJ---1308（并查集，判连通，无环）

题意： 给定一组数据（u，v）代表u指向v。判断这组数据是否形成一棵树。 题解： 利用树的特性：连通且无环。或者利用树的性质：无环(或者联通)且v=e+1； 无环可以用并查集去判定。连通可以根据并查集确定有几个根节点来判断。 边数V是加的边数，点E可以用set得出。 ①：无环。E...

[综合] POJ---1611（并查集，求规模，按规模归并）

题意： N个学生，m个团体，0号学生带传染病，每个集合内有一个带传染病的，则会感染该集合内所有的学生。 题解： 并查集基础题，归并函数写的时候要按照按规模归并。根节点root的parents【root】=-k记录集合的规模k。 最后输出-pa【findset(0)】。 #inclu...

[综合] POJ---1456（Supermarket ，贪心，并查集优化，处理冲突）

题意： N个商品，每个在截止日期dx之前卖出，可以获得dp利润，问获得利润的最大值。 题解： 将商品按照dp排序，然后依次将商品放在截止日期当天卖出，如果后来的与前面的发生冲突（两个商品截止日期相同），然后往前查找没有卖商品的日期，去卖后来的那个商品。 这个思想和哈希表线性处理冲突的方法类似，可以直...

[综合] Corporative Network（LA 3027,带权并查集母题）

题意： 两个操作：Iuv：把节点u的父节点设为v，距离为|u-v|%1000。输入的u无父节点。 Eu：询问u到根节点的距离。 题解： 这个可以说是带权并查集的母题了，只不过这里的距离是最直观的节点到根节点的距离，开个权值数组，记录每个节点到根节点的距离即可。 像食物链那类的带权并查集题，距离就是显...

[综合] HDU---1213（How Many Tables，并查集判连通分支数）

题意： 判断连通分支数 题解： 并查集 #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #include<queue> ...

[综合] POJ---2912 Rochambeau（枚举+带权种类并查集）

题意： 有n个人玩剪刀石头布，其中有一个人是裁判，剩下的人被分为三组，每组每次出的手型一样，裁判可以任意出，问是否能判断出哪个人为裁判。 题解： 枚举每个人为裁判的情况，然后问题就转化为了种类并查集问题（食物链），判断离了这个人，数据是否存在矛盾，如果不矛盾，说明这个人为裁判。 ...

[综合] POJ 1733 Parity game(带权并查集）

题意： 一个长度为n的0,1字符串，给出m行数据，每行数据给出区间[xi,yi]内的1的个数为奇数个或者偶数个。 输出最小k，使得前k行数据不矛盾。 题解： 带权并查集类型题： 区间[xi,yi]内1的个数为偶数个，代表区间[1,xi-1]，[1,yi]内含1的个数同奇偶，xi-1,yi...

[综合] poj2236?Wireless?Network（基础并查集）

题意： 修复n台已经被损坏的电脑，两者距离小于d可以直接连接，否则只能通过其他电脑进行连接。 两种操作，Ox表示修复第x台电脑，Sxy表示判断xy间是否链接。 题解： 并查集的基础应用： 每次修复，将其加入能够加入的集合。每次判断是否连接，看是否在一个集合内就可以了。 #include<i...

[综合] HDU 1754 I Hate It(线段树:单点set，区间max)

题意： 当C为'Q'的时候，表示这是一条询问操作，它询问ID从A到B(包括A,B)的学生当中，成绩最高的是多少。当C为'U'的时候，表示这是一条更新操作，要求把ID为A的学生的成绩更改为B。 题解： 线段树模板题：单点set，区间max。 #include<iostream> ...

[综合] POJ 3468 A Simple Problemwith Integers(线段树:区间add,区间sum)

题意： "Cabc"meansaddingctoeachofAa,Aa+1,...,Ab.-10000≤c≤10000."Qab"meansqueryingthesumofAa,Aa+1,...,Ab. 题解： 线段树模板题：区间add，区间sum。 区间add这里有必要说些pushdown函数...

[综合] HDU 1698 Just a Hook(线段树:区间set，整体区间sum)

题意： 题解： 线段树模板题：区间add，区间sum。 这里没必要写query函数了，让求全体sum，所以这道题不用线段树也是可以滴~~~暴力呗。既然在线段树专题训练了，就老实线段树~！ #include<iostream> #include<cstdio> #inclu...

[综合] POJ 2528 Mayor's posters(线段树：区间set，整体查询+离散化)

题意： 为了竞选市长，竞选者在一墙上同一高度进行贴海报为自己拉票。海报覆盖一块连续的区域，后来贴的可以覆盖前面贴的，问到最后一共可以看多多少张海报。 整块墙可以看做是一个水平数轴，每张海报就是数轴上的一个区间。 题解： 数据规模为千万级别的，直接建立线段树，内存时间都会超。 需要对这些大点的数据进...

[综合] ZOJ 1610 Count the Colors （线段树：区间染色set，整体查询）

题意： 在一条长度为8000的线段上染色，每次把区间[a,b]染成c颜色。后面染的会覆盖前面染的。求染完之后，每个颜色在线段上有多少个间断的区间。 题解： 线段树：区间set，整体查询。 区间染色问题，这里所求的是每种颜色在线段上出现的次数（有多少个间断的区间）。 注意： 一般染色问题直接对应区...

[综合] POJ 3264 Balanced Lineup(线段树，简单区间query）

题意： 求区间最大值和最小值的差值。 题解： 线段树简单query，修改都没有~~~。 #include<iostream> #include<cstdio> #include<cstdlib> #include<algorithm> #incl...

[综合] HDU 4027 Can you answer these queries? (线段树：区间set变形，区间求和）

题意： 给n个数字，修改操作为：区间[a,b]内的每个值改为他的平方根。询问操作：给出区间[c,d]内的总和。 题解： 线段树：区间set，区间sum。 这道题的set不是简单的每个节点都加加减减的问题了，而是每个节点开根号，所有就不能用懒惰标记进行优化了，但是反过来想，由于每个节点都是开方，所以...