题目导航

图论

BFS

模板题

【easy】hdu1312Red and Black
bfs的基础模板题，会bfs就能做的

双向BFS

【medium】190. 字串变换 模板题 此题做法以及思想参考acwing
题意：求字符串到目标字符串的最小变换次数。
可以用双向BFS，让起点和终点同时搜索，然后判断是否有交点的状态，这样可以省去很大的搜索空间
【hard】hdu6171 Admiral
题意：把一个21元素的排列，通过规则移动，看是否能在20步之内移动到另一个状态。
这题给定了初始状态和目标状态就可以想到是双向BFS算法做，当然也可以用A*算法，只不过双向BFS更好写一些，A*算法要退一个启发函数。
【medium】hdu1401 Solitaire
题解在我博客上，此题细节比较多

求有向图的强连通分量，求无向图割点、割边

模板题

【easy】P2863 [USACO06JAN]牛的舞会The Cow Prom
tarjan算法求强连通分量的个数

【easy】P2341 【模板】强连通分量 / [HAOI2006]受欢迎的牛
题意：图中N个点，找出能被N个点都走到的点的个数
tarjan算法求出各个联通分量，处理缩点之后的拓扑图中出度为0的点的个数

【easy】P3387 【模板】缩点
题意：图中每个点都有一个权值，找一条权值最大的路径，路径点可以重复。也就是先tarjan求各scc的权值总和，缩点之后图就变成了一个有向无环图(拓扑图)，然后使用dp在拓扑图中找一条权值最大的路径就好了，dp[i]表示以结点i结尾的路径权值最大值。

【easy】P3388 【模板】割点
题意：把图中所有的割点都找出来
虽然也是使用的tarjan算法，但是low[v]表示的含义不一样，其次求割点是在无向图中求。这里的low[v]是保存不依靠父结点，v能够走到的最小dfn序号，如果low[v]>=dfn[u](u是父结点的dfn)，就说明u是割点。对于根结点，需要判断他有几颗子树，如果有2颗及以上，则此根结点是割点。

【medium】hdu 4738 Caocao's Bridges 求割桥
2013年icpc杭州网络赛
题意：又一个由图构成的士兵基地，图中可能有割桥，桥上有守卫把守。我方有一个炸弹，要去炸敌方的一座桥(图中的割桥),派送的士兵不能少于桥上的守卫，问最少需要派多少士兵？
不得不说，坑点很多。这题也算是求割桥的模板题，然后加上一堆坑点来坑人。不过细心的话，也能避免这些坑点的。

数据结构

线段树

【easy】hdu1394 Minimum Inversion Number
这题需要花点小功夫，发现是线段树单点修改。首先将数列所有值+1。因为是计算排列逆序数，当新插入点x，就去查询线段树中[x+1,N]的数量，相当于是一个求区间和。之后旋转的时候，把第一个数c移动到最后一位，会损失c-1个逆序对，增加N-c个逆序对，然后循环就可以了。

动态规划

计数类型

【easy】hdu2069 Coin Change
题意：给你一些x元(x<=250),问用1，5，10，25，50的硬币能换取x的方案数，并且方案中硬币不能超过100个
此题需要注意阶段性，先算只用1元硬币去组合，再在此基础上加上5元硬币，然后依次继续；也就是前1种硬币，前2种硬币，前3种硬币。。。而不能是按钱为阶段性，算完x元，再去算x+1元的方案数，因为这里面会有重复方案。

0/1背包模型

【easy】HDU2602 Bone Collector
题意：给N个物品，他们各自有各自的价值和体积，给你一个V体积的包，问能装下的最大价值的是多少。
此题也可以用来练习滚动数组

滚动数组

【hard】HDU1024 Max Sum Plus Plus
具体看我的题解