poj专题

poj 3974 and hdu 3068 最长回文串的O（n）解法(Manacher算法)

求一段字符串中的最长回文串。因为数据量比较大，用原来的O（n^2）会爆。小白上的O(n^2)解法代码：TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码： #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离，求来回到点1的最短路中的边权和。因为边很大，不能用原来的dijkstra什么的，所以用spfa来做。并且注意要用long long int 来存储。稍微改了一下学长的模板。 stack stl 实现代码： #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259：题意：John的农场里n块地，m条路连接两块地，w个虫洞，虫洞是一条单向路，不但会把你传送到目的地，而且时间会倒退Ts。任务是求你会不会在从某块地出发后又回来，看到了离开之前的自己。判断树中是否存在负权回路就ok了。 bellman代码： #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net（最小生成树模板代码）

感觉用这题来当模板更适合。题意就是给你邻接矩阵求最小生成树啦。~ prim代码：效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking（prim or kruscal最小生成树）

题意给你点与点间距离，求最小生成树。注意点是，两点之间可能有不同的路，输入的时候选择最小的，和之前有道最短路WA的题目类似。 prim代码： #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369（prim or kruscal最小生成树）

题目很麻烦，因为不熟悉最小生成树的算法调试了好久。感觉网上的题目解释都没说得很清楚，不适合新手。自己写一个。题意：给你点的坐标，然后两点间可以有两种方式来通信：第一种是卫星通信，第二种是无线电通信。卫星通信：任何两个有卫星频道的点间都可以直接建立连接，与点间的距离无关；无线电通信：两个点之间的距离不能超过D，无线电收发器的功率越大，D越大，越昂贵。计算无线电收发器D

poj 1502 MPI Maelstrom（单源最短路dijkstra）

题目真是长得头疼，好多生词，给跪。没啥好说的，英语大水逼。借助字典尝试翻译了一下，水逼直译求不喷 Description： BIT他们的超级计算机最近交货了。（定语秀了一堆词汇那就省略吧再见） Valentine McKee的研究顾问Jack Swigert，要她来测试一下这个系统。 Valentine告诉Swigert：“因为阿波罗是一个分布式共享内存的机器，所以它的内存访问

uva 10061 How many zero's and how many digits ?（不同进制阶乘末尾几个0）+poj 1401

题意是求在base进制下的 n！的结果有几位数，末尾有几个0。想起刚开始的时候做的一道10进制下的n阶乘末尾有几个零，以及之前有做过的一道n阶乘的位数。当时都是在10进制下的。 10进制下的做法是： 1. n阶位数：直接 lg（n！）就是得数的位数。 2. n阶末尾0的个数：由于2 * 5 将会在得数中以0的形式存在，所以计算2或者计算5，由于因子中出现5必然出现2，所以直接一

poj 3159 （spfa差分约束最短路） poj 1201

poj 3159: 题意：每次给出b比a多不多于c个糖果，求n最多比1多多少个糖果。解析：差分约束。这个博客讲差分约束讲的比较好： http://www.cnblogs.com/void/archive/2011/08/26/2153928.html 套个spfa。代码： #include <iostream>#include <cstdio>#i

poj 1734 （floyd求最小环并打印路径）

题意：求图中的一个最小环，并打印路径。解析： ans 保存最小环长度。一直wa，最后终于找到原因，inf开太大爆掉了。。。虽然0x3f3f3f3f用memset好用，但是还是有局限性。代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#incl

poj 1113 凸包+简单几何计算

题意：给N个平面上的点，现在要在离点外L米处建城墙，使得城墙把所有点都包含进去且城墙的长度最短。解析：韬哥出的某次训练赛上A出的第一道计算几何，算是大水题吧。用convexhull算法把凸包求出来，然后加加减减就A了。计算见下图：好久没玩画图了啊好开心。代码： #include <iostream>#include <cstdio>#inclu

poj 3190 优先队列+贪心

题意：有n头牛，分别给他们挤奶的时间。然后每头牛挤奶的时候都要在一个stall里面，并且每个stall每次只能占用一头牛。问最少需要多少个stall，并输出每头牛所在的stall。 e.g 样例： INPUT: 51 102 43 65 84 7 OUTPUT: 412324 HINT: Explanation of the s

poj 3050 dfs + set的妙用

题意: 给一个5x5的矩阵，求由多少个由连续6个元素组成的不一样的字符的个数。解析： dfs + set去重搞定。代码： #include <iostream>#include <cstdio>#include <set>#include <cstdlib>#include <algorithm>#include <cstring>#include <cm

poj 3169 spfa 差分约束

题意：给n只牛，这些牛有些关系。 ml个关系：fr 与 to 牛间的距离要小于等于 cost。 md个关系：fr 与 to 牛间的距离要大于等于 cost。隐含关系： d[ i ] <= d[ i + 1 ] 解析：用以上关系建图，求1-n间最短路即可。新学了一种建图的方法。。。。。。代码： #include <iostream>#include

poj 3723 kruscal，反边取最大生成树。

题意：需要征募女兵N人，男兵M人。每征募一个人需要花费10000美元，但是如果已经招募的人中有一些关系亲密的人，那么可以少花一些钱。给出若干的男女之间的1~9999之间的亲密关系度，征募某个人的费用是10000 - （已经征募的人中和自己的亲密度的最大值）。要求通过适当的招募顺序使得征募所有人的费用最小。解析：先设想无向图，在征募某个人a时，如果使用了a和b之间的关系

poj 3255 次短路（第k短路） A* + spfa 或 dijkstra

题意：给一张无向图，求从1到n的次短路。解析： A* + spfa 或者 dijkstra。详解见上一题：http://blog.csdn.net/u013508213/article/details/46400189 本题，spfa中，stack超时，queue的效率最高，priority_queue次之。代码： #include <iostream>#i

poj 2449 第k短路 A* + spfa

poj 2449：题意：给一张有向图，求第k短路。解析： A* + spfa。一下转自：http://blog.csdn.net/mbxc816/article/details/7197228 “描述一下怎样用启发式搜索来解决K短路。首先我们知道A*的基础公式：f(x)=g(x)+h(x);对h(x)进行设计，根据定义h(x)为当前的x点到目标点t所需要的实际距

poj 1182 并查集食物链类

题意：有n只动物，分别编号1....n。所有动物都属于A，B，C中的一种，已知A吃B，B吃C，C吃A。按顺序给出下面两种共K条信息： 1. x 和 y 属于同一类。 2. x 吃 y 。然而这些信息可能会出错，有可能有的信息和之前给出的信息矛盾，也有的信息可能给出的 x 和 y 不在n的范围内。求k条信息中有多少条是不正确的。解析：对于每只动物，创建3个元素 i

poj 2431 poj 3253 优先队列的运用

poj 2431：题意：一条路起点为0，终点为l。卡车初始时在0点，并且有p升油，假设油箱无限大。给n个加油站，每个加油站距离终点 l 距离为 x[i]，可以加的油量为fuel[i]。问最少加几次油可以到达终点，若不能到达，输出-1。解析：《挑战程序设计竞赛》： “在卡车开往终点的途中，只有在加油站才可以加油。但是，如果认为“在到达加油站i时，就获得了一

poj 2976 分数规划二分贪心（部分对总体的贡献度） poj 3111

poj 2976：题意：在n场考试中，每场考试共有b题，答对的题目有a题。允许去掉k场考试，求能达到的最高正确率是多少。解析：假设已知准确率为x，则每场考试对于准确率的贡献值为： a - b * x，将贡献值大的排序排在前面舍弃掉后k个。然后二分x就行了。代码： #include <iostream>#include <cstdio>#incl

poj 3104 二分答案

题意： n件湿度为num的衣服，每秒钟自己可以蒸发掉1个湿度。然而如果使用了暖炉，每秒可以烧掉k个湿度，但不计算蒸发了。现在问这么多的衣服，怎么烧事件最短。解析：二分答案咯。代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <c

poj 3258 二分最小值最大

题意：有一些石头排成一条线，第一个和最后一个不能去掉。其余的共可以去掉m块，要使去掉后石头间距的最小值最大。解析：二分石头，最小值最大。代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <c

poj 2187 凸包or旋转qia壳法

题意：给n（50000）个点，求这些点与点之间距离最大的距离。解析：先求凸包然后暴力。或者旋转卡壳大法。代码： #include <iostream>#include <cstdio>#include <cstdlib>#include <algorithm>#include <cstring>#include <cmath>#include <s

poj 1127 线段相交的判定

题意：有n根木棍，每根的端点坐标分别是 px, py, qx, qy。判断每对木棍是否相连，当他们之间有公共点时，就认为他们相连。并且通过相连的木棍相连的木棍也是相连的。解析：线段相交的判定。首先，模板中的线段相交是不判端点的，所以要加一个端点在直线上的判定；然后，端点在直线上的判定这个函数是不判定两个端点是同一个端点的情况的，所以要加是否端点相等的判断。最后

poj 2175 最小费用最大流TLE

题意：一条街上有n个大楼，坐标为xi，yi，bi个人在里面工作。然后防空洞的坐标为pj，qj，可以容纳cj个人。从大楼i中的人到防空洞j去避难所需的时间为 abs（xi - pi） + （yi - qi） + 1。现在设计了一个避难计划，指定从大楼i到防空洞j避难的人数 eij。判断如果按照原计划进行，所有人避难所用的时间总和是不是最小的。若是，输出“OPETIMAL",若