[综合] UVALive - 3938 Ray, Pass methe dishes!quot;(动态最大连续和子序列，线段树区间合并）

题意： 给出一个长度为n的整数序列D，你的任务是对m各询问做出回答。对于询问(a,b)，需要找到两个下标x和y，使得a<=x<=y<=b，并且Dx+Dx+1+...+Dy尽量大。如果有多组满足条件的x和y，x应该尽量小。如果还有多解，y应该尽量小。 题解： 蓝书上的线段树练习题，...

[综合] HDU 1233 还是畅通工程(最小生成树入门)

题意： 某省调查乡村交通状况，得到的统计表中列出了任意两村庄间的距离。省政府“畅通工程”的目标是使全省任何两个村庄间都可以实现公路交通（但不一定有直接的公路相连，只要能间接通过公路可达即可），并要求铺设的公路总长度为最小。请计算最小的公路总长度。 Input 测试输入包含若干测试用例。每个测试用例的...

[综合] POJ - 2031 Building a Space Station

题意： 给定一些球的坐标，为这些球搭建通路，使得他们能相互连通，如果两个球有重叠的部分则算为已连通，无需再搭桥，求搭建通路的最小费用，费用就是边权，两个球面的距离。 题解： 最小生成树模板题，两个球起初有重叠，视为已经连通，边权为0。 #include<iostream> #in...

[综合] POJ - 2421 Constructing Roads（最小生成树简单应用）

题意： 一些点已经连通，还有一些未连通，求所有的点连通，需要的代价。 题解： 最小生成树模板题，先根据邻接矩阵把边都存起来，然后把已经相邻的边权为0,再存起来。跑一遍kk，这些边权为0的肯定把刚才邻接表存进去的给覆盖(用不到他们)了！ #include<iostream> #i...

[综合] POJ - 2349 Arctic Network （最小生成树，剩S个连通分量）

题意： 有P个站点需要远程通信，他们能通过无线电或者卫星来通信。如果两个站点通过卫星来通信的话，无论多远，都行并不花钱。如果通过无线电通信的话，需要花钱且距离越长花费越大。现有S个卫星接收器，求无线电通信站点间的所有距离中的最大值D尽量小。求这个D。 题解： 最小生成树变形： 一般的最小生成树，k...

[综合] POJ - 3026 Borg Maze（最小生成树+BFS）

题意： 给定一个迷宫，‘#’代表墙，空格代表空地，S开始，到达所有的A，求最少的步数。 题解： 最小生成树： 但是任意点间的距离需要BFS搜索出来。 注意：迷宫的读取用gets（）读一整行！（有空格） #include<iostream> #include<cst...

[综合] POJ - 1679 The Unique MST (次小生成树）

题意： 给一个n个节点，m条边的无向图，问你该图的最小生成树是否唯一？如果唯一输出树的权值，否则输出“Notunique!” 题解： 次小生成树： 一个图的次小生成树(权值<=最小生成树的权值,可能等于最小生成树的权值)肯定至少有一条边与最小生成树的一条边不同.所以我们可以枚举最小生成树上的...

[综合] 最小生成树（MST）模板---Kruskal算法

最小生成树： 给定一个 无向图，如果它的某个子图中任意两个点都相互连通并且是一颗树，那么这棵树就叫生成树。 如果边上的权值和最小的话，生成树就叫做最小生成树。 综合简洁性和效率这里仅提供kruskal算法： 把所有边按照从小到大排序，然后每次拿出来一条边，如果边的两个端点没...

[综合] L2-006. 树的遍历(重建)

L2-006.树的遍历 时间限制 400ms 内存限制 65536kB 代码长度限制 8000B 判题程序 Standard 作者 陈越 给定一棵二叉树的后序遍历和中序遍历，请你输出其层序遍历的序列。这里假设键值都是互不相等的...

[综合] L2-014. 列车调度(贪心模拟，set）

L2-014.列车调度 时间限制 300ms 内存限制 65536kB 代码长度限制 8000B 判题程序 Standard 作者 陈越 火车站的列车调度铁轨的结构如下图所示。 Figure 两端分别是一条入口（Entra...

[综合] L2-013. 红色警报（图连通性基础）

L2-013.红色警报 战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序，当失去一个城市导致国家被分裂为多个无法连通的区域时，就发出红色警报。注意：若该国本来就不完全连通，是分裂的k个区域，而失去一个城市并不改变其他城市之间的连通性，则不要发出警报。 输入格式： ...

[综合] L2-016. 愿天下有情人都是失散多年的兄妹（搜索）

L2-016.愿天下有情人都是失散多年的兄妹 呵呵。大家都知道五服以内不得通婚，即两个人最近的共同祖先如果在五代以内（即本人、父母、祖父母、曾祖父母、高祖父母）则不可通婚。本题就请你帮助一对有情人判断一下，他们究竟是否可以成婚？ 输入格式： 输入第一行给出一个正整数N（2<=N<...

[综合] L3-001. 凑零钱（背包dp，输出路径）

L3-001.凑零钱 韩梅梅喜欢满宇宙到处逛街。现在她逛到了一家火星店里，发现这家店有个特别的规矩：你可以用任何星球的硬币付钱，但是绝不找零，当然也不能欠债。韩梅梅手边有104枚来自各个星球的硬币，需要请你帮她盘算一下，是否可能精确凑出要付的款额。 输入格式： 输入第一行给出两个...

[综合] HDU 1890 Robotic Sort(伸展树---反转应用)

题意： 给一系列数，执行一系列的反转操作，要求最后稳定排序这些数，并且输出每次反转的右边界。 题解： 怎么运用伸展树去解决呢？（反转操作。伸展树的基本操作） 对原始数据记录值和下标，然后按照值优先排序。伸展树存放下标。然后扫描一遍所有的数： 第一个数在x位置，把伸展树值为x的节点伸展到根，左子树...

[综合] HDU 3487 Play with Chain(伸展树基本操作)

题意： 给定一数组，完成两种操作： CUTabc将区间[a,b]的数删除，并接到新数列的第c个数后面 FLIPab将区间[a,b]的数翻转顺序 输出最终的序列 题解： 伸展树的基本操作。 #include<bits/stdc++.h>usingnamespacestd; #define...

[综合] HDU 4453 Looploop(伸展树应用，数列环)

题意： 给定一个环，和一个原点，对这个环有以下操作: addx操作:从队首开始的的连续k2个数都加上x值. reverse操作:从队首开始的连续k1个数都翻转 insertx操作:在第一个元素与第二个元素之间插入一个x值 delete操作:删除原点，新原点顺时针移动一下 move1操作:原点逆时针移...

[综合] HDU 3436 Queue-jumpers(伸展树，元素移至首部+离散化)

题意： PonyoandGarfieldarewaitingoutsidethebox-officefortheirfavoritemovie.Becausequeuingissoboring,thattheywanttoplayagametokillthetime.Thegameiscalled“...

[综合] POJ 1442 Black Box(Treap，第k小)

题意： 给定一个数组，有两种操作: Ax：表示插入x。 Geti：表示返回第i小的数。 题解： Treap实现名次树。 然而这道题出的比较特殊，这一个数组顺序，连续插入一段，然后输出第i大，i从1到n依次增大。可以用两个优先队列去写。 Treap实现： #include<cstdio>...

[综合] POJ 3481 Double Queue(Treap实现二叉树)

题意： 每个顾客有个编号和优先级,银行每次可以添加顾客的要求进队列,且保证队列中当前任意顾客的编号和优先级都不同.银行可以执行先服务最大优先级的顾客或者先服务最小优先级的顾客操作.对于每个服务,输出顾客的编号. 题解： Treap实现二叉树。 节点节点的v值为客户的服务优先级，节点r值为随机的r。 ...

[综合] HDU 1166 敌兵布阵(树状数组入门题)

题意： 单点add，区间sum。 题解： 线段树可以很好的写这个题，但是树状数组显得更加有效，快捷！ #include<bits/stdc++.h>usingnamespacestd; constintmaxn=50000+10;intc[maxn]; intlowbit(intx)...