无限循环小数POJ1930
题意：给定一个无限循环小数，求其分数形势，要求分母最小分析：看了别人的题解才做出来的，将无限循环小数转化成分数，分为纯循环和混循环两种形式。(1)对于纯循环：用9做分母，有多少个循环数就几个9，比如0.3，3的循环就是9分之3，0.654，654的循环就是999分之654，0.9，9的循环就是9分之...
POJ 1985 Cow Marathon && POJ 1849 Two(树的直径)
树的直径：树上的最长简单路径。求解的方法是bfs或者dfs。先找任意一点，bfs或者dfs找出离他最远的那个点，那么这个点一定是该树直径的一个端点，记录下该端点，继续bfs或者dfs出来离他最远的一个点，那么这两个点就是他的直径的短点，距离就是路径长度。具体证明见http://www.cnblogs...
POJ3621或洛谷2868 [USACO07DEC]观光奶牛Sightseeing Cows
一道\(0/1\)分数规划+负环POJ原题链接洛谷原题链接显然是\(0/1\)分数规划问题。二分答案，设二分值为\(mid\)。然后对二分进行判断，我们建立新图，没有点权，设当前有向边为\(z=(x,y)\)，\(time\)为原边权，\(fun\)为原点权，则将该边权换成\(mid\timesti...
POJ2533Longest Ordered Subsequence（DP）
http://poj.org/problem?id=2533在经典不过的DP题目了。。。。#include<map>#include<set>#include<stack>#include<queue>#include<cmath>#inc...
POJ 3061 (二分+前缀和or尺取法)
题目链接: http://poj.org/problem?id=3061题目大意：找到最短的序列长度，使得序列元素和大于S。解题思路：两种思路。一种是二分+前缀和。复杂度O(nlogn)。有点慢。二分枚举序列长度，如果可行，向左找小的，否则向右找大的。前缀和预处理之后，可以O(1)内求和。#incl...
poj 1141 Brackets Sequence（区间DP）
题目:http://poj.org/problem?id=1141转载：http://blog.csdn.net/lijiecsu/article/details/7589877定义合法的括号序列如下：1空序列是一个合法的序列2如果S是合法的序列，则(S)和[S]也是合法的序列3如果A和B是合法的序...
POJ 1113 Wall 凸包求周长
WallTimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 26286 Accepted: 8760DescriptionOnceuponatimetherewasagreedyKingwhoorderedhischiefArchitectt...
POJ 2594 Treasure Exploration (Floyd+最小路径覆盖)
<题目链接>题目大意：机器人探索宝藏，有N个点，M条边。问你要几个机器人才能遍历所有的点。解题分析：刚开始还以为是最小路径覆盖的模板题，但是后面才知道，本题允许一个点经过多次，这与最小路径覆盖中，路径之间不能有交点重合相矛盾，所以，我们用Floyd利用传递闭包对原图进行一些处理。所谓传递...
POJ3070 Fibonacci[矩阵乘法]
FibonacciTimeLimit: 1000MS MemoryLimit: 65536KTotalSubmissions: 13677 Accepted: 9697DescriptionIntheFibonacciintegersequence, F0 =0, F1 =1,and Fn = Fn...
POJ 1182 食物链 (并查集)
食物链TimeLimit: 1000MS MemoryLimit: 10000KTotalSubmissions: 50601 Accepted: 14786Description动物王国中有三类动物A,B,C，这三类动物的食物链构成了有趣的环形。A吃B，B吃C，C吃A。 现有N个动物，以1－N编号...
poj 3159 差分约束
思路：班长的糖果要比snoopy的多。并且要用手写堆栈，且堆栈的大小要开到20000000.#include<iostream>#include<cstdio>#include<cstring>#include<algorithm>#include&l...
POJ 2505 A multiplication game（找规律博弈/贪心）
题目链接#include<iostream>#include<cstdio>usingnamespacestd;typedeflonglongll;intmain(){lln;while(~scanf("%I64d",&n)){//其实算是贪心了吧//先手想赢，他会x...
poj 3160 Father Christmas flymouse
//题目描述：从武汉大学ACM集训队退役后，flymouse做起了志愿者，帮助集训队做一些琐碎的事情，比如打扫集训用的机房等等。当圣诞节来临时，flymouse打扮成圣诞老人给集训队员发放礼物。集训队员住在校园通过宿舍的不同寝室里。为了节省体力，flymouse决定从某个寝室出发，沿着一些有向路一个...
POJ 2948 Martian Mining（DP）
题目链接题意：n×m的矩阵，每个格子中有两种矿石，第一种矿石的的收集站在最北，第二种矿石的收集站在最西，需要在格子上安装南向北的或东向西的传送带，但是每个格子中只能装一种传送带，求最多能采多少矿。思路：记忆化搜索。也可以用递推。//#include<stdio.h>#include<...
poj2388解题报告（排序）
POJ 2388，题目链接http://poj.org/problem?id=2388题意：水题一道给定n个数，输出中间值，可以用sort，干脆快捷。代码：//396K32MS#include<cstdio>#include<algorithm>intbuf[10000];i...
poj2823_单调队列简单入门
题目链接：http://poj.org/problem?id=2823#include<iostream>#include<cstdio>#defineM1000001usingnamespacestd;intn,k;inta[M];intq[M];intp[M];voidg...
A:分段函数-poj
A:分段函数总时间限制: 1000ms内存限制: 65536kB描述编写程序，计算下列分段函数y=f(x)的值。y=-x+2.5;0<=x<5y=2-1.5(x-3)(x-3);5<=x<10y=x/2-1.5;10<=x<20输入一个浮点数N,0<=N&l...
POJ 1741 Tree, 树的重心, 树分治, 点分治
最近在学习树的分治，算是比较难，而且代码量比较大的一块。随便拿一道题来就有上百行，故写一篇文章来总结一下这方面的框架。POJ这一题应该算是树分治的入门题，顺便用这一题来详细说明树分治的一些具体内容。http://poj.org/problem?id=1741TreeTimeLimit: 1000MS...
poj 1741 树的分治
题目连接转载博客:http://blog.csdn.net/u010660276/article/details/44920725题意：在一棵树上找点对数，使得两点之间的距离小于等于k，问有多少对思想：找其树的重心，重心即：使得子树个数尽量多，并且子树的结点数尽量少，通俗一点，可以认为就是找个点可以...
【POJ 1741】 Tree (树的点分治)
Tree DescriptionGiveatreewithnvertices,eachedgehasalength(positiveintegerlessthan1001). Definedist(u,v)=Themindistancebetweennodeuandv. Giveanintegerk...