浙大 acm oj 解题报告

 搞编程的都知道的浙江大学ACM题库．本书是收集了所有经典的ZJU题解集，集合并附有原题目和详细的注释，最终的代码．
动态规划:
暴力DP :ZJU1039 难度:中等偏难
暴力DP :ZJU1227 难度:比较难
经典问题 :ZJU1149 难度:如果不会用剩余类,感觉比较难。可以考查骗分技巧(就是那种砍到多少多少以下)
经典问题 :ZJU1366 难度:同上。但这题用搜索用得好的话可以瞬过。
状态表示 :ZJU2059 难度:中等偏难。这个题考状态表示的
状态表示 :ZJU1757 难度:中等偏难。一类NP问题的动规解法。
经典问题 :ZJU2096 难度:中等偏难。狗狗的题目。
经典问题 :ZJU1717 难度:中等偏易。就是走格子的复杂一点版
经典问题 :ZJU1986 难度:中等。传说中的最长不XX子序列。听说这个题不用O(nlogn)的过不了？我是O(nlogn)的。
非纯动规 :ZJU1953 难度:中等。传说中的最长公共子序列。不过这个题只是用到这个,后面还要用构造法。

数据结构:
线段树 :ZJU1128 难度:中等偏难。求面积并,扫描线法+线段树。以前的国家队论文有过的题。

线段树 :ZJU1659 难度:中等偏难。求面积并。
表达式计算:ZJU1958 难度:中等
去括号 :ZJU2021 难度:中等

搜索题,BFS/DFS:
BFS :ZJU1063 难度:中等偏易
BFS + DFS :ZJU1085 难度:中等偏易
经典的BFS :ZJU1136 难度:中等偏难
分类搜索 :ZJU1732 难度:中等偏难。这个题目的意思比较难理解
搜索策略 :ZJU1411 难度:中等。搜索策略不对的话铁定TLE。可以用位操作优化。

无数人WA :ZJU1101 难度:中等。就是枚举顺序那里死活有人错。
ID-DFS :ZJU1204 难度:中等。我当时做的时候错得莫名其妙的。
估界+搜索 :ZJU1269 难度:中等。我觉得想不出估界就没法做。
简单搜索题:ZJU1403 难度:简单
建图+搜索 :ZJU1424 难度:中等偏易。金牌之路上面有的。
奇偶+搜索 :ZJU1457 难度:简单。不加奇偶性判断就TLE,加了基本上都能对。
常规搜索 :ZJU1639 难度:中等偏易。无非就是可性行剪枝加最优解剪枝
简单搜索 :ZJU1861 难度:简单
树的最长路:ZJU2013 难度:有点难。没听说过方法的硬想比较困难。

图论题:
纯最短路径:太多了,ZJU1082比较好。
纯最小生成树:太多了,ZJU1203一个就够了。
EULER路径 :ZJU1919 难度:中等偏难。
极大极小路径问题:ZJU1542 难度:中等。
极小极大路径问题:ZJU1942 难度:中等偏易。
这两个题的解法太多了。FLOYD可以,DIJKSTRA可以,最小生成树可以,二分答案+判定也可以。不错的题目。


贪心思想:
会议安排 :ZJU1076 难度:简单
区间覆盖 :ZJU1360 难度:中等
经典过河 :ZJU1877 难度:中等。没做过估计就做不出来的。
经典贪心 :ZJU1756 难度:中等偏易。贪心应该是O(N^2),这道题其实是:用不下降子序列去覆盖一个序列,求最少要多少个不下降子序列。有O(nlogn)的动态规划。国家队论文有讲。
二分+贪心 :ZJU2002 难度:中等偏难。如果用动态规划肯定超时,顺便考考二分也不错的。而且这个搭配经常出现。