POJ-1182 食物链:最经典的并查集,参考1,参考2:食物链(种类并查集)

1248:Safecracker:【密码+暴力+水题】:参考

1252 Euro Efficiency:正负完全背包. 参考1,参考2,参考2

1481:The Die Is Cast:两层 DFS 搜索中搜索。参考

1287:Networking:最小生成树。一个网络中,一些节点间存在网路,你现在需要找出一条可以连接所有点的最短网路。参考

1323:Game Prediction:贪心 参考

Poj 1339 poker card game:哈夫曼树。n张扑克牌放到如图1的空框上,得分是扑克牌点数 乘 空框到树根距离。如图2,非空框(Q)的孩子不能再放纸牌。求最小得分。 参考

1664:放苹果

1703:发现它,抓住它:并查集,

1840:Eqs:Hash方法。参考

1847:Tram:最短路径。参考:Floyd参考2:Dijkstra

1922:Ride to School

1976:A Mini Locomotive:背包问题,有三个火车头,n个车厢,每个车厢里面对应的有一定的人数。规定每个火车头最多拉m个连续的车厢而且他们拉的车厢一定是从左到右连续的,问它能够拉的最多的人数;题意:一个数列,n个数,找三个k个连续数的子数列,使其和最大。

2051:Argus

2115:C Looooops参考:扩展欧几里德 + 解同余方程

2240:Arbitrage:Floyd

2355 Railway tickets:线性dp,注意理解,POJ 2355 Railway tickets (线性dp)

2356:Find a multiple:组合数学:鸽巢原理,抽屉原理, 题意:给出n个数,任选几个数,使其和为n的倍数。 编程思想:鸽巢原理的简单应用。设前k项和Sk表示a1+a2+……ak,如果Sk是n的倍数,那就直接取Sk了,否则S1-Sn除n的余数分布在1---(n-1)这n-1个数中,运用鸽巢原理,必然有两个的余数相同,即(Si%n)=(Sj%n),即(Sj-Si)%n=0,证毕。所以落在区间i+1至j的所有数的和就是n的倍数。 参考1参考2POJ 3370 Halloween treats 同题型

2387:Til the Cows Come Home:最短路径 参考:spfa算法:邻接矩阵+SLF策略, 参考:dijkstra

2492:A Bug’s Life: 并查集,参考

2312:Battle City:BFS变形 优先队列,参考1,参考2

POJ-2502 Subway:(最短路 Dijkstra) 参考

2736:大整数减法:python

2737:大整数除法:python

2250:Compromise: DP问题,DFS输出序列,经典.参考

2756:二叉树

2760:数字三角形

2778:Ride to School

2783:Holiday Hotel

2788:二叉树

2805:正方形:STL map struct, 参考1:使用map参考2:map, 参考3:详细讲解,使用hash

2812:恼人的青蛙

2814:拨钟问题:枚举问题:参考

2816:红与黑

2871:整数奇偶排序:循环使用时,要注意两点:一是,参数的初始化位置,防止参数值受循环影响;二是,结尾数据的输出可能有换行。

2910:提取数字:???,这题比较坑,题目中说是连续字符字符组成的正整数,容易理解出现偏差,首先不要考虑负号的问题,就当没看到,其次,数字不是连续出现的也可以输出,比如a8b,你要输出8.最后,不要考虑超出整数范围,没必要。

2912:三个完全平方数

2915:字符串排序:这个题要注意一下,在cin读入整数后,会把换行符留下,在接下来使用getline(cin,str)时,会导致读取0个字符的情况,所以在cin读入整数后必须使用getchar()将回车符读取掉。

2945:拦截导弹

2950:摘花生

2981:大整数加法:重视,比较经典

2982:Sudoku:DFS,参考

3126 Prime Path:BFS, 经典。参考:

3142:球弹跳高度的计算

3247:回文素数:参考,参考2

POJ 3259 Wormholes:Bellman_ford 判断负环问题 参考:代码很好,比书上好

3343:热血格斗场: STL map pair,low_bound().

3727:摘花生2

4002:谁是你的潜在朋友

4116:拯救行动:BFS+优先队列,拯救公主系列之杀死卫士.参考1,参考2:注意几点,一是多组数据初始化,fill如何初始化二维数组,二是BFS的返回值问题,默认返回值-1,要么就把输出直接写入BFS

4147:汉诺塔问题(Hanoi):递归问题。参考

4128:单词序列:BFS 数组搜索, 或者使用Floyd。参考,参考:Floyd

4135:月度开销:二分查找。参考

4078:实现堆结构:使用STL priority_queue实现堆。priority_queue<int, vector<int>, greater<int> > Q;,注意,push、top、pop操作。

4977:怪盗基德的滑翔翼:注意两点:1.在多组数据时,一定要数组、数据初始化;2.能加括号尽量加括号。 注意理解题意,基德可以降落在任何一个地方,意味着求最长升序或降序子序列。参考

NOI 1.13 41判断元素是否存在:递归。参考

Contents