专题地址 http://acm.hust.edu.cn/vjudge/contest/view.action?cid=78210#overview 本专题所有代码都可以在hust上查看 A - Aragorn’s Story 模板题 树链+线段树(区间更新单点查询) B - Housewife Wind 模板题 树链+线段树(区间更新单点查询) C - Tree 模板题 树链+线段树(单点区间更新区间查询) 要注意到的点是区间更新是取反 所以要保存区间的最大值和最小值 D - 染色 好题 树链+线段树(区间更新+稍微变化的区间查询) 每一个每个结点保存这个区间的左端点颜色和右端点颜色 更新的时候 如果左儿子的右端点==右儿子的左端点 那么这个区间的总数等于左儿子线段数+右儿子线段数-1 否则总数为左儿子线段数+右儿子线段数 E - 树的统计Count 模板题 树链+线段树(单点更新区间查询) F - 网络管理Network 线段数套Treap(随机二叉排序树) 求树上的动态区间第k值 具体查看 http://blog.csdn.net/inf_force/articl ...

题意很简单：在一颗树上修改某个点的值，然后查询两点之间路径上的第k大的元素 查阅了很多资料，因为不会Treap，链接如下： http://blog.csdn.net/ssccode/article/details/17351461 (这个代码有点问题。比如未删除分配的空间。update顺序错误等。但是写成类的形式很爽。) http://blog.csdn.net/acdreamers/article/details/11309971 http://www.nocow.cn/index.php/Treap 注：如果rotate看不懂的话 你需要注意参数 node *&x的意义 代码有点长，如下: //author: CHC//First Edit Time: 2015-06-06 09:14#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#inc ...

引入题目 有一道这种题：给一个有向无环图，一个士兵可以沿着某条路径走到底，现求最小需要多少个士兵可以把所有的点都走过。 解法 刚碰这题的时候有几个想法 想法一 计算入度为0的点有多少个，就需要多少个士兵。 然后又自己提出反例。 如图： 这个例子中需要两个士兵 显然单纯算入度和出度是不行的。放弃 想法二 直接在原图基础上跑最大流，然后考虑到流量不好控制，遂放弃 想法三 首先考虑哪些点是起点，假定S是一个起点的集合，那么这个集合满足什么条件？ 一个起点代表一条路径，由这些起点选择的路径可以覆盖全图 也就是说集合S中的点都是“独立”的，也就是说这些点的“入度”都为0.（其实就是这些点不会被其他点经过 那么能不能“拆”点，将一个点拆为出度和入度？ 将图中的点u拆为u’和u’’ 假设原图中存在边e(u,v)∈E，那么建边u’->v’’ 若选择该条边，那么意味着v’‘不是起点集合（因为起点集合不被经过 然而题目就转换为了—求起点集合的最少点数，也就是说v’'不被覆盖的最少点数，也即： 最小点覆盖=|V|-最大匹配 但是需要注意到的是：需要在图G(V,E)基础上建立新图G’ ...

额。第一使用MD，好紧张。 好吧，原来我还是个水货啊。。 最小生成树我们都知道该怎么求吧 把边按照权值大小排序，然后从小到大依次选择这些边，但是选择这些边有一个条件：不能构成环，当然这一点可以用并查集来实现 但是我们怎么求最小生成树？ 首先这么看。假设图为G(V,E) |V|=n |E|=m 先求出一个最小生成树，它的边集合为E’ 我们首先可以得到一个直观的想法。 每次只删除最小生成树中的一条边，然后重新跑最小生成树，得出答案这些最小生成树中最小的即为次小生成树的值 这样的话复杂度为O(n*n*logn) 然后我们考虑次小生成树边集为E’’ 显然|E’‘∩E’|=n-2，和最小生成树只有一条边不同 这条边一定位于E-E’，那么我们可以试着考虑 假设e(a,b)属于E-E’这个集合，在最小生成树中 加入一条边e(a,b)一定会构成环，构成环之后我们需要删除一条边使得它变成另一颗生成树，但是要求这颗树一定是最小生成树 那么现在考虑 我们应该删除哪条边？ 在一颗树中，任意两点之间的路径是唯一的 我们应该删除的边一定位于a到b的最短路径上，并且那条边的边权是最大的 为什么？因为 ...

被虐了。不过也是经常的事。 好了，开始讲。我们都知道二分可以求具有单调性的函数中的某个值。比如f(x)是具有单调性的，我们可以通过二分求f(x)==y的时候x的值是多少(已知y求x)。 但是为什么可以这么做呢？假设f(x)的单调性递增。 首先看二分的伪 代码： bool binary_search(int l,int r,int y,int &ans){ while(l<=r){ int mid=(l+r)>>1; if(f(x)-y>0)r=mid-1; else if(f(x)-y<0)l=mid+1; else { ans=mid; return true; } } return false;} 观察之后发现每次对于L和R的赋值操作都保证值在[L,R]这个区间内，这样就可以逼近要求的那个值。 好了，二分简单说到这。 现在提出一个问题。 现在我想求这个抛 ...

题意：现在有n个停车空位。标号为1~n。 现在有两个操作： 操作A:一个车队要求Mi个空位，但是这个车队停的位置有2个约束，Li为车队队首所在位置距离左边最近的那辆车之间的空位不能超过Li(如果车队左边没有车就忽略此条件)，Ri为车队队尾所在位置距离右边最近的那辆车之间的空位不能超过Ri，如果存在这样的位置，输出最小的位置。 操作B:从左往右数第k个车队离开 思路： 用一颗线段树维护相应空闲的位置的长度的最小位置，比如说，空闲长度为5的位置有很多的话就取其最小的位置坐标，位置坐标可以用set保存。 再用一颗线段树维护车队的名次。 当车队来的时候要特殊处理是否有忽略的Li和Ri条件。。 然后我在第二颗线段树的时候有一句代码写错WA了整整三天。。卧槽。。。 零零散散的加上调试的代码一共有300+行？ WA/TLE的地方：update1(0,n+1,1,…)写成了update1(1,n,1,…)手残~！！！ 代码： //author: CHC//First Edit Time: 2015-03-28 22:11//Last Edit Time: 2015-03-31 09:40#inclu ...

。。。题意在这里。 http://bestcoder.hdu.edu.cn/contests/contest_chineseproblem.php?cid=571&pid=1002 我找出来的规律为 ai+1=ai +2，然后我就用矩阵快速幂。。两个数相乘的时候爆掉范围。。 所以要把乘法变成加法快速幂。。 在矩阵快速幂的基础上再加法快速幂。 代码。 //author: CHC//First Edit Time: 2015-03-14 19:37#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std; ...

题意就是给n个b进制的数，求它们相加的和，有一个条件就是相加不进位，输出结果为没有前导0. （原来有中文题的。只能说英文太渣没有看到输出结果没有前导0这个条件。） 代码： //author: CHC//First Edit Time: 2015-03-14 19:09#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#include <algorithm>#include <limits>using namespace std;typedef long long LL;const int MAXN=1e+4;const int MAXM=1e+5;const int INF = numeric_limits< ...

经典的最大密度子图 裸题 题意：给定一个无向图G(V,E)，现在想要求这样的一个值使得它的值最大： 并按升序输出这些点 关于最大密度子图的解法以及相关证明我是参考 胡伯涛 Amber的《最小割模型在信息学竞赛中的应用》 关于本题我是这么理解的： 将|V’|乘到左边之后我们可以得到一个具有单调性式子，令该式子为h(x)，当且仅当h(x)==0时x即为所需求的分数。 最小割建图模型推演过程为： 第二次推演： 代码： //author: CHC//First Edit Time: 2015-01-12 19:05//Last Edit Time: 2015-01-13 14:35#include <iostream>#include <cstdio>#include <cstring>#include <cmath>#include <set>#include <vector>#include <map>#include <queue>#include <set>#includ ...

题意：有N颗糖和M个小孩，如果like[i][j]==1则代表第i个小孩对第j颗糖有高兴值K，否则代表第i个小孩对第j颗糖的高兴值为1。第i个小孩的高兴值如果大于b[i]就代表这个小孩是高兴的。现在问是否存在一种分配方式使得全部小孩都高兴。 本来是在做最小割专题的。没想到这道题拉错进去了。。难怪怎么都没想出怎么朴素网络流。越想越不对劲。觉得应该是费用流。然后忍不住百度了一发。。发现果然是。。。 因为有两个条件约束： 1.一颗糖只能派发一次 2.欢乐值 思路： 先不管普通的糖。处理特殊的糖使得特殊糖得到的欢乐值最大。 最后判断加上剩余的普通糖欢乐值能不能大于总和，能的话就OK。 参考：http://www.cnblogs.com/wally/p/3287980.html 代码： //author: CHC//First Edit Time: 2014-12-23 15:03//Last Edit Time: 2014-12-23 15:28#include <iostream>#include <cstdio>#include <cstring>#i ...