- 博客(119)
- 收藏
- 关注
RSS订阅原创 ZOJ--3574--Under Attack II【线段树+欧拉公式】
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3574题意：一个坐标系，给出x1、x2限定左右边界，有n条直线，告诉每条直线的k和b，问在x1、x2区间内空间被直线分割成几部分思路：这道题是比赛时做的，AC之后发现别人都是用归并排序求逆序对数来解的。说我的解法吧，首先拿到题的时候发现是划分
2014-11-20 23:50:44
963
原创 POJ--2892--Tunnel Warfare【线段树】区间合并
链接：http://poj.org/problem?id=2892题意：有n个村庄排成一排，三种操作：1. D x 摧毁村庄x2. Q x 询问村庄x的最长一段没有被摧毁的村庄数量3. R 恢复上一个被摧毁的村庄思路：线段树区间合并，lsum记录当前节点往左的最长连续距离，rsum记录当前节点往右的最长连续距离。#include#include#in
2014-11-13 17:43:53
734
原创 POJ--1128--Frame Stacking【拓扑排序】
链接：http://poj.org/problem?id=1128题意：有几张图片，给你叠加到一起之后的图，问叠加的可能性，如有多种可能则按字典序由小到大输出。思路：根据给出的图形建一个图，被覆盖的图片向覆盖它的图片建边，然后拓扑排序。拓扑排序按照字母顺序从小到大找入度为0的点，用dfs形式的拓扑排序，就按照字典序输出了。POJ1270的做法也类似： 代码
2014-11-02 00:33:57
993
原创 UvaLive--3211--Now or later【2-SAT+二分答案】
链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1212题意：有n架飞机需要着陆，每架飞机都可以选择“早着陆”或“晚着陆”两种方式，第i架飞机早着陆时间为Ei，晚着陆时间为Li，不得在其他时间着陆。你的任务是为这些飞机安排着陆方式，
2014-10-23 17:24:13
660
原创 Uva--11324--The Largest Clique【有向图强连通分量】
链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=25&problem=2299&mosmsg=Submission+received+with+ID+14404690题意：一个有向图，找一个最大的点集使得任意两点u、v间都存在一条路（单向或双向）
2014-10-23 15:00:43
775
原创 POJ--2284--That Nice Euler Circuit【平面图欧拉公式】
链接：http://poj.org/problem?id=2284题意：一个自动画图的机器在纸上（无限大）画图，笔尖从不离开纸，有n个指令，每个指令是一个坐标，因为笔尖不离开纸，所以相邻的坐标会连有一条直线，最后画笔再回到起始点。所以这个图是一个连通图，并且画笔走过的路径是一个欧拉回路。现在问题来了，这个图形将平面分成了几部分。思路：题目说明白一些就是告诉你一些几何信息问平面被分成
2014-10-23 13:02:18
888
原创 HDU--1054--Strategic Game【最小点覆盖】
链接：http://acm.hdu.edu.cn/showproblem.php?pid=1054题意：一个熊孩子玩策略游戏，他需要用最少的士兵守卫最多的道路，如果这个顶点有士兵，则和这个点相连的所有边都会被保护，问保护所有的道路最少需要的士兵数量。思路：这实际上就是一个最小点覆盖，二分图的最小点覆盖 == 最大匹配，这不是一个二分图，我们把n个点扩成2 * n个，把他转换为二分图
2014-10-18 23:11:08
741
原创 HDU--3829--Cat VS Dog【最大点独立集】
链接：http://acm.hdu.edu.cn/showproblem.php?pid=3829题意：动物园有n条狗，m头猫，p个小孩，每个小孩有一个喜欢的动物和讨厌的动物，现在动物园要转移一些动物，如果一个小孩喜欢的动物在，不喜欢的动物不在，他就会happy，问动物最多能使几个小孩happy。思路：一个比较明显的二分图，不能以猫狗为顶点，那样找到的是哪些动物会转移，以小孩为顶点
2014-10-18 20:40:48
919
原创 POJ--2019--Cornfields【二维RMQ】
#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing namespace std;#define PI acos(-1.0)#def
2014-10-17 16:19:41
654
原创 POJ--1966--Cable TV Network【无向图顶点连通度】
链接：http://poj.org/problem?id=1966题意：一个无向图，n个点，m条边，求此图的顶点连通度。思路：顶点连通度，即最小割点集里的割点数目，一般求无向图顶点连通度的方法是转化为网络流的最小割。建图：（1）原图每个点i拆点，拆为i‘和i’‘，i’到i‘’连一条弧容量为1。（2）对于原图中存在的边(u, v)，连两条弧(u‘, v')和(v'', u
2014-10-16 11:20:40
868
原创 POJ--2289--Jamie's Contact Groups【二分图多重匹配+二分答案】
链接：http://poj.org/problem?id=2289题意：有n个人，m个分组，每个人可以分配到一些组别，问如何分能使得人数最多的组别人数最少。思路：这道题二分+网络流也可以做，我这里是二分图多重匹配的做法。因为一个组别是一对多的关系，所以是多重匹配，我们二分多重匹配的限制，得到最小的限制可使二分图匹配，这个限制就是答案。网上找的模板#include#
2014-10-16 10:57:25
1044
原创 POJ--3368--Frequent values【RMQ】
链接：http://poj.org/problem?id=3368题意：给你一个序列，n个数，序列是有序的，q个询问，问区间（l，r）中出现频率最高的数字出现了几次。思路：因为序列是有序的，可以把序列相同部分合并，然后存成一个新的数组，并增加一个值num表示数字出现的次数，找区间（l，r）中出现频率最高的数字，就是找num的最大值了，区间最大值，RMQ可做，线段树也可做，我用RMQ
2014-09-25 11:20:25
711
原创 ZOJ--1654--Place the Robots【二分图最大匹配】
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=654
2014-09-23 00:32:46
935
原创 UVALive--6571--It Can Be Arranged【拆点+isap】最小割
链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4582题意：有n门课程，每个课程有个开始时间和结束时间，和参加人数，现要租借教室来上课。再告诉你一个矩阵，a[i][j]表示第j门课如果在第i门课后使用第i门课的教室，需要a[i][
2014-09-17 01:44:08
1303
原创 HDU--2586--How far away ？【LCA】
链接：http://acm.hdu.edu.cn/showproblem.php?pid=2586题意：一棵有边权的树，问任意两点间的长度是多少。思路：做LCA题目看到的这道题，就用LCA做了，其实只用LCA的递归部分就能做这道题了。用一个数组dis记录根节点到每个节点的距离，则任意两节点a、b间的距离就是dis[a]+dis[b]-2*dis[lca(a,b)]。我用ve
2014-09-15 22:31:43
878
原创 POJ--1699--Best Sequence【扩展KMP+DFS】
链接：http://poj.org/problem?id=1699题意：给出n个字符串，求他们相连的最小长度，如果首尾字母相同则可以共用相同部分，比如两个串ABCDEF和DEFGHI，他们相连为ABCDEFGHI，最小长度为9，中间的DEF部分共用了。思路：由于数据量较小，首先对每两个字符串a，b用扩展KMP求出a连在b之后可以共用的长度，用数组B[i][j]表示第j个字符串连接在
2014-09-11 02:05:43
1148
原创 HDU--3746--Cyclic Nacklace【KMP】
链接：http://acm.hdu.edu.cn/showproblem.php?pid=3746题意：在一个字符串后最少加几个字符才能使这个字符串是某个串重复两次而得。思路：借助了这篇博文的结论：传送门结论：len-next[i]为此字符串的最小循环节(i为字符串的结尾)，另外如果len%(len-next[i])==0,此字符串的最小周期就为len/(len-next[i]
2014-09-05 23:02:07
587
原创 ZOJ--3602--Count the Trees【DFS+Hash】树的同构
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3602题意：给出一棵有n个节点的二叉树和一棵有m个节点的二叉树，给出每个节点的左右子树信息，问这两棵树有几个相同的子树。思路：树的同构，比赛时没想法，赛后看的别人的解题报告。实际上是给每个节点的左右子树一个哈希值，不用像字符串哈希那么麻烦，直接给每个子树
2014-09-05 16:54:24
896
原创 POJ--2752--Seek the Name, Seek the Fame【KMP】
链接：http://poj.org/problem?id=2752题意：
2014-09-03 00:57:09
889
原创 ZOJ--3612--Median【线段树+离散化】
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4736题意：有最多10000次操作，在一个初始为空的数列中添加或移除元素并保持数列有序，每次操作后，如果数列个数为奇数就输出中间值，如果为偶数就输出中间两个值得平均值。思路：刚开始写了一发multiset模拟，看吴琦TLE了估计他也是multiset写的，就
2014-09-01 15:37:40
615
原创 ZOJ--3631--Watashi's BG【枚举】
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4777题意：有n天，告诉你每天的花费，别人给你一笔资金m，你自己也有一部分资金（可以假设花不完），每天只能花自己的钱或者花资金m中的钱，不能混着花，问m最多能花多少？思路：考虑到数据比较小，n最多只有30，可以用枚举来做，枚举每天花m或者不花m，二进制枚举，
2014-08-29 01:11:41
1015
原创 UVa1151&POJ2784--Buy or Build【kruskal+二进制枚举】
链接：UVa http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3592POJ http://poj.org/problem?id=2784题意：告诉你n个点的坐标，建立一颗最小生成树，不过有q个套餐，套餐是连通某些点，并有一定花费，求
2014-08-28 16:51:33
985
原创 UVa1395&POJ3522--Slim Span【kruskal】瓶颈生成树
链接：http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=4141题意：给出n个顶点，m条边，求一个生成树，使得最大边与最小边的差值最小。思路：求一个生成树使最大边最小是瓶颈生成树。对于此题，我们枚举每一条边做最小边的情况，找对应的最小生成树的最
2014-08-28 14:23:37
997
原创 POJ--2585--Window Pains【拓扑排序】
链接：http://poj.org/problem?id=2585题意：有一个4*4的屏幕，有9个窗口各占2*2大小，保证不会存在一个窗口完全覆盖任一个窗口，但每个窗口都会部分被其他窗口覆盖（因为4*4和2*2 = =、）现在需要你判断电脑是否死机。（死机的话会出现无法判断A覆盖B还是B覆盖A的情况）思路：无法判断A覆盖B还是B覆盖A，可以当做是图中A和B之间存在环，我们可以把每个
2014-08-26 15:11:39
790
原创 POJ--1094--Sorting It All Out【拓扑排序】
链接：http://poj.org/problem?id=1094题意&思路：直接拓扑排序。多解输出一串英文，有环输出一段英文，唯一解输出一段英文及排序结果。细节：题目描述不是很清楚，如果不看discuss我肯定要WA出翔。discuss里总结了两点关键的：1. 输入一条边时如果此时拓扑有解就输出这个解，即使后面的边成有向环也不管了，所以每次输入的时候都得进行拓扑排序。
2014-08-25 21:36:48
543
原创 HDUOJ--4888--Redraw Beautiful Drawings【isap】网络流+判环
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4888题意：
2014-08-23 00:17:52
1021
原创 POJ--4973--A simple simulation problem.【线段树】
链接：http://acm.hdu.edu.cn/showproblem.php?pid=4973题意：有一段数字，长度n，数字为1~n，有两种操作，第一种是使区间[l,r]内的所有数字变成两个，长度n随之增大，第二种操作是查询区间[l,r]中相同的数字最多有多少个。思路：比赛时扫了一眼，看区间要扩大，没有细想就觉得线段树做不了，而且当时没有人交这道题就没管了，然后看解题报告居然真
2014-08-22 14:54:16
920
原创 POJ--1465--Multiple【BFS+同余定理】
链接：http://poj.org/problem?id=1465题意：给一个数字n，和m个数字，找一个由这些数字组成的最小的n的倍数，如果不存在输出0。思路：这题怎么想都想不到bfs上去，看了别人的解题报告，其实是用bfs来枚举，但是加了一个牛逼的剪枝：同余。即如果A%X==B%X，则（A*10+K）%X==（B*10+K）%X。我们枚举m中每一个数字做这个K，实际上是枚举了
2014-08-21 21:23:07
691
原创 POJ--1386--Play on Words【判断有向图欧拉通路、欧拉回路】
链接：http://poj.org/problem?id=1386题意：要开启一扇门，n个单词是密码，n个单词中，如果一个单词的首字母和前一个单词的尾字母相同，并且每个单词都能这么连起来且只用一次，则门可以开启，否则不能开启，现给出单词，判断门是否可以开。有向图欧拉通路充要条件：D为有向图，D的基图连通，并且所有顶点的出度与入度都相等；或者除两个顶点外，其余顶点的出度与入度都相等，
2014-08-18 14:16:00
1042
原创 POJ--1300--Door Man【判断无向图欧拉通路】
链接：http://poj.org/problem?id=1300题意：有n个房间，每个房间有若干个门和别的房间相连，管家从m房间开始走，要回到自己的住处（0），问是否有一条路可以走遍所有的门并且没有重复的路。思路：判断是否存在欧拉通路，根据欧拉通路、欧拉回路的性质来做。有两种情况：一种是欧拉回路，所有房间的门的个数都是偶数个，并且此时初始房间不是0，此时存在要求的路径，如果初始是
2014-08-17 00:08:04
1098
原创 POJ--3422--Kaka's Matrix Travels【最小费用最大流+拆点】
链接：http://poj.org/problem?id=3422卡卡题意：卡卡的矩阵之旅，有一个n*n的矩阵，卡卡要从左上角走到右下角，每次他只能往右或往下走，卡卡可以走k遍这个矩阵，每个点有一个num值，卡卡走到这里可以获得num点，一个点只能获得一次num值，问卡卡走完k遍后身上num值最大可以是多少？思路：其实看到这题时没思路，图论书上说了建图的方式，但
2014-08-16 20:55:37
1179
1
原创 POJ--2516--Minimum Cost【最小费用最大流】
链接：http://poj.org/problem?id=2516题意：有k种货物，n个客户对每种货物有一定需求量，有m个仓库，每个仓库里有一定数量的k种货物，然后k个n*m的矩阵，告诉从各个仓库到各个客户位置运送单位第k种货物所需的运费，问满足所有客户需求的最小费用，如满足不了所有客户，则输出-1。思路：题目有点绕，不过多看看也就理解了。这道题算是最小费用最大流的入门题吧，建图很
2014-08-16 13:35:46
754
原创 POJ2396&ZOJ1994--Budget【有源汇上下界可行流】
链接：http://poj.org/problem?id=2396题意：给一个n*m的矩阵，给出每行的总和以及每列的总和，再给出某些位置的最小或最大限制，问是否存在可能的矩阵，如果存在输出一种矩阵信息。思路：这是一个有源汇的上下界可行流，对于这种题，从汇点连一条弧到源点，容量为INF，这不会影响流量平衡条件，并且此时原图转换为了无源汇的上下界可行流，剩下的做法和无源汇一样。建图
2014-08-15 19:01:50
934
原创 ZOJ--2314--Reactor Cooling【无源汇上下界可行流】
链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1314题意：某恐怖组织要建立一个核反应堆，他们需要设计一个冷却系统，n个点由m个管子连接，为使液体循环流动，每个节点的总流入量需要等于总流出量，现告诉你每根管子的最小流量及最大流量及它们连接的两点（有向），问是否存在可行流，如存在，输出每个管子的流量。有上下
2014-08-15 01:15:07
1128
原创 POJ--3308--Paratroopers【Dinic】二分图顶点覆盖+网络最大流
链接：http://poj.org/problem?id=3308题意：未来世界火星人要入侵地球，他们要派一些伞兵来摧毁地球的兵工厂，兵工厂可以视为一个m*n的矩阵，现在知道了他们每个伞兵的降落位置。为了粉碎火星人的阴谋，我们需要在某行或某列来架一个机关枪来消灭一整行或一整列的火星人，但是在这需要一定的花费，告诉每行及每列架机关枪的花费，总花费是每行及每列的花费相乘。求使得火星人全部被消灭的最
2014-08-13 20:51:01
667
原创 POJ--2391--Ombrophobic Bovines【拆点+Floyd+Dinic优化+二分答案】网络最大流
链接：http://poj.org/problem?id=2391题意：有f个草场，每个草场当前有一定数目的牛在吃草，下雨时它可以让一定数量的牛在这里避雨，f个草场间有m条路连接，每头牛通过一条路从一点到另一点有一定的时间花费，现在要下雨了，农场主发出警报牛就会立即去避雨。现在告诉每个草场的情况，以及m条边的信息。农场主至少需要提前多久发出警报才能保证所有牛都能避雨？如果不是所有牛都能成功避雨
2014-08-12 03:12:21
1203
原创 CUGBACM_Summer_Tranning5
A.Number AssignmentUvaLive6434简单题#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#include#includeusing
2014-08-11 20:20:11
624
原创 HDUOJ--2121--Ice_cream’s world II【朱刘算法】不定根最小树形图
链接：http://acm.hdu.edu.cn/showproblem.php?pid=2121题意：n个顶点，m条边，求从某一点起建立有向图最小生成树并且花费最小，输出最小花费和根节点下标。思路：这道题根是不确定的，我们可以先假设一个根，从这个根出发到任何一点的距离（sum）都比原图总权值还大，这样保证了虚拟的边不会是最小入边，也为之后判断是否生成了最小树形图提供方便，从这个点
2014-08-10 16:25:06
876
原创 POJ--3164--Command Network【朱刘算法】最小树形图
链接：http://poj.org/problem?id=3164题意：告诉n个点坐标，m条边表示两个点之间有路，从1点开始建立一个有向图最小生成树。朱刘算法模板题========================== 分割线之下摘自Sasuke_SCUT的blog==================================================最 小树形图，就是给
2014-08-10 15:33:23
1093
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人