POJ 2488 A Knight's Journey （DFS）
poj-2488题意：一个人要走遍一个不大于8*8的国际棋盘，他只能走日字，要输出一条字典序最小的路径题解：（1）题目上说的“The knight can start and end on any square of the board.”，是个坑点，其实要走字典序最小只需从A1开始遍历就行，因为从...
POJ 2488 A Knight's Journey【DFS】
补个很久之前的题解。。。。题目链接：http://poj.org/problem?id=2488题意：马走“日”字，让你为他设计一条道路，走遍所有格，并输出字典序最小的一条。分析：dfs~~~代码：#include<iostream>#include<cstring>#inc...
POJ-2253.Frogger.(求每条路径中最大值的最小值，最短路变形)
做到了这个题，感觉网上的博客是真的水，只有kuangbin大神一句话就点醒了我，所以我写这篇博客是为了让最短路的入门者尽快脱坑......本题思路：本题是最短路的变形，要求出最短路中的最大跳跃距离，基本思路与最短路一样，dist数组为当前点到源结点最短路的最大距离，这样的话我们知道只需要改变松弛方程...
[POJ1144][BZOJ2730]tarjan求割点
求割点一种显然的n^2做法：枚举每个点，去掉该点连出的边，然后判断整个图是否联通用tarjan求割点：分情况讨论如果是root的话，其为割点当且仅当下方有两棵及以上的子树其他情况设当前节点为u，一个儿子节点为v存在low[v]>=dfn[u]，也就是说其儿子节点v能连到的最前面的点都在u的下面...
[USACO2005][POJ3045]Cow Acrobats(贪心)
题目：http://poj.org/problem?id=3045题意：每个牛都有一个wi和si，试将他们排序，每头牛的风险值等于前面所有牛的wj(j<i)之和-si，求风险值最大的牛的最小风险值分析：这就是noip2012 T2的来源= =只不过这里是加，noip里是乘不妨设所有牛都按最优顺...
poj 1845 Sumdiv（约数和，乘法逆元）
题目：求AB的正约数之和。输入：A，B（0<=A，B<=5*107）输出：一个整数，AB的正约数之和 mod 9901。思路：根据正整数唯一分解定理，若一个正整数表示为：A=p1^c1 * p2^c2 * ...... pm^cm 则其正约数之和可以表示为：S=（1+p1+p1^2+.....
POJ 1595 素数打表水题
【题意简述】：给出N和C，让我们求出N以内的包含N的素数，然后依据若N以内的素数为奇数个，就将中间2*c-1个素数输出；若为偶数个。就将中间2*c个素数输出。【分析】：仅仅要题意理解就简单了。详见代码：// 224K 16Ms#include<iostream>using namespa...
POJ - 2385 Apple Catching （dp）
题意：有两棵树，标号为1和2，在Tmin内，每分钟都会有一个苹果从其中一棵树上落下，问最多移动M次的情况下（该人可瞬间移动），最多能吃到多少苹果。假设该人一开始在标号为1的树下。分析：1、dp[x][y][z]---第x分钟移动了y次的情况下，现在位于标号为z的树下最多吃到的苹果数。2、枚举所有的时...
POJ 2385 Apple Catching【DP】
题意：2棵苹果树在T分钟内每分钟随机由某一棵苹果树掉下一个苹果，奶牛站在树#1下等着吃苹果，它最多愿意移动W次，问它最多能吃到几个苹果。思路：不妨按时间来思考，一给定时刻i，转移次数已知为j, 则它只能由两个状态转移而来。即上一时刻同一棵树或上一时刻不同的树 dp[i][j] = max(dp...
poj 2385 Apple Catching 基础dp
Apple CatchingDescriptionIt is a little known fact that cows love apples. Farmer John has two apple trees (which are conveniently numbered 1 and 2) in...
POJ 2385 Apple Catching（01背包）
01背包的基础上增加一个维度表示当前在的树的哪一边。#include<cstdio>#include<iostream>#include<string>#include<cstring>#include<queue>#include<...
最小费用最大流模板 poj 2159 模板水题
Going HomeTime Limit: 1000MS Memory Limit: 65536KTotal Submissions: 15944 Accepted: 8167Description On a grid map there are n little men and n houses....
每日一水 POJ8道水题
1. POJ 3299 Humidex链接： http://poj.org/problem?id=3299这道题是已知H，D，T三者的运算关系，然后告诉你其中两个。求另一个。#include<iostream>#include<cstdio>#include<cstri...
poj 3264 RMQ 水题
题意：找到一段数字里最大值和最小值的差水题 #include<cstdio> #include<iostream> #include<algorithm> #include<cstring> #include<cmath> #include...
poj-2406（kmp水题）
题意：定义一个a*b=字符串a连接字符串b；给你一个字符串s，问你这个字符串最多能用多少个字符串t连接得到；例如：aaaa=4个a构成；解题思路：kmp水题，next数组除了查找字串以外最广泛的一种用法，用来判定一个串是不是循环串，如果是，输出原串的长度/最小的循环节，否则，输出1就行了；代码：#i...
poj 1986 Distance Queries LCA
题目链接：http://poj.org/problem?id=1986Farmer John's cows refused to run in his marathon since he chose a path much too long for their leisurely lifestyle...
生理周期POJ 1006
Time Limit: 1000MS Memory Limit: 10000KTotal Submissions: 138101 Accepted: 44225Description人生来就有三个生理周期，分别为体力、感情和智力周期，它们的周期长度为23天、28天和33天。每一个周期中有一天是高峰。...
二分-poj-3685-Matrix
题目链接：http://poj.org/problem?id=3685题目大意：有n*n的矩阵，第i行第j列的数为Aij= i2 + 100000 × i + j2 - 100000 × j + i × j,求矩阵中第k小的数。解题思路：显然每一列是单调的，二分答案，枚举每一列，再二分行标，求出该列...
POJ 3352 (边双连通分量)
题目链接: http://poj.org/problem?id=3352题目大意：一个连通图中，至少添加多少条边，使得删除任意一条边之后，图还是连通的。解题思路：首先来看下边双连通分量的定义：如果任意两点至少存在两条“边不重复”的路径，那么说这个图是边双连通的。那么本题中，删除任意一条边，就可以看作...
POJ3468 A Simple Problem with Integers(线段树延时标记)
题目地址http://poj.org/problem?id=3468题目大意很简单，有两个操作，一个Q a, b 查询区间[a, b]的和C a, b, c让区间[a, b] 的每一个数+c第一次线段树的延时标记，花了好大的功夫才写好==！很容易看出来使用使用线段树记录区间的和，但是难点在于每次修改...