原帖: 一些图论、网络流入门题总结、汇总 hi.baidu/zfy0701/blog/item/b8332b5c7b2dd545fbf2c052.html 搜索题目推荐及解题报告 hi.baidu/zfy0701/blog/item/c6e216ed18a9d24a78f05589.html 字符串题目推荐及解题报告 hi.baidu/zfy0701/blog/item/440e923e1bc4183870cf6c89.html ------------------------ POJ 2449 Remmarguts' Date(中等) 对外经济贸易大学车祸acm.pku.edu/JudgeOnline/problem?id=2449 题意:经典问题:K短路 解法:dijkstra+A*(rec),方法很多 相关:acm.pku.edu/JudgeOnline/showcontest?contest_id=1144 该题亦放在搜索推荐题中 POJ 3013 - Big Christmas Tree(基础) acm.pku.edu/JudgeOnline/problem?id=3013 题意:最简单最短路,但此题要过,需要较好的程序速度和,还要注意精度 解法:Dijkstra POJ 3463 - Sightseeing(中等) acm.pku.edu/JudgeOnline/problem?id=3463 题意:最短路和比最短路大1的路的数量 解法:需要真正理解dijkstra POJ 3613 - Cow Relays(较难) acm.pku.edu/JudgeOnline/problem?id=3613 题意:求经过N条边的最短路 解法:floyd + 倍增,贪心 POJ 3621 - Sightseeing Cows(中等) acm.pku.edu/JudgeOnline/problem?id=3621 题意:求一个环路,欢乐值 / 总路径最大 解法:参数搜索 + 最短路(ms 原始的bellman tle, 用spfa才过) POJ 3635 - full tank?(中等) acm.pku.edu/JudgeOnline/problem?id=3635 题意:最短路变形 解法:广搜 相关:hi.baidu/hnu_reason/blog/item/086e3dccfc8cb21600e9286b.html 生成树问题 基本的生成树就不放上来了 POJ 1639 - Picnic Planning(较难) acm.pku.edu/JudgeOnline/problem?id=1639 题意:顶点度数有限制的最小生成树 解法:贪心 + prim/kruskal POJ 1679 - The Unique MST(基础) acm.pku.edu/JudgeOnline/problem?id=1679 题意:判断MST是否唯一 解法:prim就行,不过还是易错的题 POJ 2728 - Desert King(中等) acm.pku.edu/JudgeOnline/problem?id=2728 题意:所谓最优比率生成树 解法:参数搜索 + prim POJ 3164 - Command Network(难) acm.pku.edu/JudgeOnline/problem?id=3164 题意:最小树形图 解法:刘朱算法,这个考到的可能性比较小吧? POJ 3522 - Slim Span(基础) acm.pku.edu/JudgeOnline/problem?id=3522 题意:求一颗生成树,让最大边最小边差值最小 解法:kruskal活用 连通性,度数,拓扑问题 此类问题主要牵扯到DFS,缩点等技巧 POJ 1236 - Network of Schools(基础) acm.pku.edu/JudgeOnline/problem?id=1236 题意:问添加多少边可成为完全连通图 解法:缩点,看度数 POJ 1659 - Frogs' Neighborhood(基础) acm.pku.edu/JudgeOnline/problem?id=1659 题意:根据度序列构造图 解法:贪心,详细证明参见havel定理 POJ 2553 - The Bottom of a Graph(基础) acm.pku.edu/JudgeOnline/problem?id=2553 POJ 2186 - Popular Cows(基础) acm.pku.edu/JudgeOnline/problem?id=2186 题意:强连通分量缩点图出度为0的点 POJ 2762 - Going from u to v or from v to u?(中等) acm.pku.edu/JudgeOnline/problem?id=2762 题意:单向连通图判定 解法:缩点 + dp最长链 POJ 2914 - Minimum Cut(难) acm.pku.edu/JudgeOnline/problem?id=2914 题意:无向图最小割 解法:Stoer-Wagner算法,用网络流加枚举判定会挂 POJ 2942 - Knights of the Round Table(难) acm.pku.edu/JudgeOnline/problem?id=2942 题意:求双联通分量(或称块)中是否含奇圈 解法:求出双连通分量后做黑白染进行二分图图判定 相关:hi.baidu/zfy0701/blog/item/57ada7ed104ce9d2b31cb104.html POJ 3177 - Redundant Paths(中等) acm.pku.edu/JudgeOnline/problem?id=3177 POJ 3352 - Road Construction(中等) acm.pku.edu/JudgeOnline/problem?id=3352 题意:添加多少条边可成为双向连通图 解法:把割边分开的不同分量缩点构树,看入度 建议对比下1236,有向图添加多少条边变成强连通图 POJ 3249 - Test for Job(基础) acm.pku.edu/JudgeOnline/problem?id=3249 解法:bfs / dfs + dp POJ 3592 - Instantaneous Transference(基础) acm.pku.edu/JudgeOnline/problem?id=3592 解法:缩点,最长路,少人做的水题,注意细节 POJ 3687 - Labeling Balls(中等) acm.pku.edu/JudgeOnline/problem?id=3687 解法:拓扑排序 POJ 3694 - Network(中等) acm.pku.edu/JudgeOnline/problem?id=3694 解法:双连通分量+并查集 2-SAT问题 此类问题理解合取式的含义就不难 POJ 2723 - Get Luffy Out(中等) acm.pku.edu/JudgeOnline/problem?id=2723 POJ 2749 - Building roads(较难) acm.pku.edu/JudgeOnline/problem?id=2749 解法:二分 + 2-SAT判定 POJ 3207 - Ikki's Story IV - Panda's Trick(基础) acm.pku.edu/JudgeOnline/problem?id=3207 解法:简单的2-sat,不过其他方法更快 POJ 3648- Wedding(中等) acm.pku.edu/JudgeOnline/problem?id=3648 解法:用2-sat做会比较有意思,但是暴搜照样0ms POJ 3678 - Katu Puzzle(基础) acm.pku.edu/JudgeOnline/problem?id=3678 解法:直接按合取式构图验证就行了 POJ 3683 - Priest John's Busiest Day(中等) acm.pku.edu/JudgeOnline/problem?id=3683 解法:n^2枚举点之间的相容性构图,求解2-SAT 最大流问题 变形很多,最小割最大流定理的理解是关键 POJ 1149 - PIGS(较难) acm.pku.edu/JudgeOnline/problem?id=1149 绝对经典的构图题 POJ 1273 - Drainage Ditches(基础) acm.pku.edu/JudgeOnline/problem?id=1273 最大流入门 POJ 1459 - Power Network(基础) acm.pku.edu/JudgeOnline/problem?id=1459 基本构图 POJ 1637 - Sightseeing tour(Crazy) acm.pku.edu/JudgeOnline/problem?id=1637 题意:求混合图的欧拉迹是否存在 解法:无向边任意定向,构图,详建黑书P324 POJ 1815 - Friendship(中等) acm.pku.edu/JudgeOnline/problem?id=1815 题意:求最小点割 解法:拆点转换为边割 相关:hi.baidu/zfy0701/blog/item/a521f230b06dea9fa9018e0e.html POJ 1966 - Cable TV Network(中等) acm.pku.edu/JudgeOnline/problem?id=1966 题意:去掉多少点让图不连通 解法:任定一源点,枚举汇点求点割集(转换到求边割),求其中最小的点割 POJ 2112 - Optimal Milking(基础) acm.pku.edu/JudgeOnline/problem?id=2112 二分枚举,最大流 POJ 2391 - Ombrophobic Bovines(中等) acm.pku.edu/JudgeOnline/problem?id=2391 题意:floyd, 拆点,二分枚举 相关:hi.baidu/zfy0701/blog/item/3e0006c4f73f0eaf8226acff.html POJ 2396 - Budget(中等) acm.pku.edu/JudgeOnline/problem?id=2396 题意:有源汇的上下界可行流 解法:用矩阵-网络流模型构图,然后拆边 相关:hi.baidu/zfy0701/blog/item/6449d82a64e15e3e5343c1ba.html ,最小割模型在竞赛中的应用 POJ 2455 - Secret Milking Machine(基础) acm.pku.edu/JudgeOnline/problem?id=2455 二分枚举,一般来说需要写对边容量的更新操作而不是每次全部重新构图 POJ 2699 - The Maximum Number of Strong Kings(较难) acm.pku.edu/JudgeOnline/problem?id=2699 解法:枚举人数 + 最大流(感谢xpcnq_71大牛的建图的提示) POJ 2987 - Firing(较难) acm.pku.edu/JudgeOnline/problem?id=2987 题意:最大权闭包 解法:先边权放大,第一问总量-最大流,第二问求最小割 相关:wywcgs.spaces.live/blog/cns!?&_c02_owner=1 Profit(中等) www.vijos/Problem_Show.asp?id=1352 最大权闭包图的特殊情况 ZOJ 2071 - Technology Trader 也是此类型,懒了没做 acm.zju.edu/show_problem.php?pid=2071 POJ 3084 - Panic Room(中等,好题) acm.pku.edu/JudgeOnline/problem?id=3084 题意:略 解法:根据最小割建模 POJ 3155 - Hard Life(很挑战一题) acm.pku.edu/JudgeOnline/problem?id=3155 题意:最大密度子图 解法:参数搜索 + 最大权闭合图,A.V.Goldberg的论文(nb解法) 最小割模型在信息学竞赛中的应用 一文中也有讲 POJ 3189 - Steady Cow Assignment(中等) acm.pku.edu/JudgeOnline/problem?id=3189 题意:寻最小的区间完成匹配 解法:这题充分说明SAP的强大,纯暴力可过。更好的方法是在枚举区间的过程中不断删边和加边继续网络流过程 POJ 3204 - Ikki's Story I - Road Reconstruction(基础) acm.pku.edu/JudgeOnline/problem?id=3204 ZOJ 2532 - Internship(基础) acm.zju.edu/show_problem.php?pid=2532 题意:确定边是否是某个割中的边 解法:两边dfs求割, 或暴力枚举(需要写取消某条增广路的操作(但数据弱,也许不取消也能混过)) POJ 3308 - Paratroopers(较难) acm.pku.edu/JudgeOnline/problem?id=3308 POJ 2125 - Destroying The Graph(难) acm.pku.edu/JudgeOnline/problem?id=2125 题意:最小点权覆盖 POJ 3469 - Dual Core CPU(中等) acm.pku.edu/JudgeOnline/problem?id=3469 题意:最小割 POJ 3498 - March of the Penguins(中等) acm.pku.edu/JudgeOnline/problem?id=3498 题意:满足点容量限制的网络流 解法:拆点把点容量转换为边容量,枚举汇点 ZOJ 2587 - Unique Attack(较难) acm.zju.edu/show_problem.php?pid=2587 题意:确定最小割是否是唯一的 解法:得理解dfs求最小割算法的本质 SPOJ 839 - Optimal Marks(难) www.spoj.pl/problems/OPTM/ 题意:略 解法:很经典哦,见amber的集训队论文,根据标号的每一位求最小割 SGU 326 - Perspective(中等) acm.sgu.ru/problem.php?contest=0&problem=326 比较经典的构图法 费用流问题 可以KM解的就不放在这里,另外,感觉除非很特殊的图,一般用连续增广路的算法就够了 POJ 2175 - Evacuation Plan(中等) acm.pku.edu/JudgeOnline/problem?id=2175 题意:判断是否给定解是最优解,比较阴的一题 解法:根据给出的计划构造流,然后消且只消一次负圈 POJ 3422 - Kaka's Matrix Travels(中等)成相篇 acm.pku.edu/JudgeOnline/problem?id=3422 题意:略 解法:拆点 POJ 3680 - Intervals(较难) acm.pku.edu/JudgeOnline/problem?id=3680 题意:略,这题还是蛮经典 解法:discuss卫慧作品中比较详细 SPOJ 371 - Boxes(简单) www.spoj.pl/problems/BOXES/ 题意:略 解法:费用流,但似乎有比网络流更好的做法 SGU 185 - Two shortest(中等) acm.sgu.ru/problem.php?contest=0&problem=185 题意:求两条不想交的最短路径 解法:费用流,也可以最短路 + 最大流。 匹配问题 正确理解KM算法是很重要的 这里我还要说几句:最正确解最小权匹配的办法是用一个很大的数-当前边权值,而不是直接对边权取反(这样只能处理左右点相等的完全二分图,即K(n, n) 以上有可能还是说的有点问题,以后补充 POJ 1486 - Sorting Slides(中等) acm.pku.edu/JudgeOnline/problem?id=1486 题意:二分图的必须边 解法:需正真理解最大匹配算法,详见hi.baidu/kevin0602/blog/item/1d5be63b5bec9bec14cecb44.html POJ 1904 - King's Quest(中等,好题) acm.pku.edu/JudgeOnline/problem?id=1904 题意:求二分图所有可能的匹配边 解法:虽然最终不是用匹配算法,但需要理解匹配的思想转换成强连通分量问题。 POJ 2060 -Taxi Cab Scheme(基础) acm.pku.edu/JudgeOnline/problem?id=2060 题意:最小路径覆盖 POJ 2594 -Treasure Exploration(中等) acm.pku.edu/JudgeOnline/problem?id=2594 题意:可相交最小路径覆盖 解法:先传递闭包转化下 POJ 3041 - Asteroids(基础) acm.pku.edu/JudgeOnline/problem?id=3041 POJ 2226 - Muddy Fields(基础) acm.pku.edu/JudgeOnline/problem?id=2226 题意:行列的覆盖 解法:最小点集覆盖 = 最大匹配 POJ 2195 - Going Home(基础) acm.pku.edu/JudgeOnline/problem?id=2195 题意:最小权值匹配 解法:KM算法 POJ 2400 - Supervisor, Supervisee(中等) acm.pku.edu/JudgeOnline/problem?id=2400 题意:输出所有最小权匹配 解法:KM, 然后回溯解,汗,输入的两个矩阵居然是反过来的 POJ 2516 -Minimum Cost(中等) acm.pku.edu/JudgeOnline/problem?id=2516 题意:最小权值匹配或最小费用流 解法:拆点 + KM算法中国养老金发展报告2012(只有正确的才能过),费用流(ms错的可能也能过) POJ 3686 - The Windy's(较难) acm.pku.edu/JudgeOnline/problem?id=3686 题意:最小权值匹配 解法:拆点,然后尽管用KM算法去水吧,数据其实弱得不得了 O(50 * 50 * 2500) -> 16ms 相关:hi.baidu/kevin0602/blog/item/2829dc01d7143b087bec2c97.html SPOJ 412 - K-path cover(较难) www.spoj.pl/problems/COVER/ 题意:略 解法:很牛叉的一道匹配 相关:hi.baidu/roba/blog/item/c842fdfac10d24dcb48f31d7.html SGU 206. Roads(较难) acm.sgu.ru/problem.php?contest=0&problem=206 解法:经典题目,也可以使用spoj 412那题的优化 NP问题 一般是搜索或dp解的 POJ 1419 - Graph Coloring(基础) acm.pku.edu/JudgeOnline/problem?id=1419 题意:图的着 解法:搜索,可惜题目的数据真是太弱了 POJ 2989 - All Friends(难) acm.pku.edu/JudgeOnline/problem?id=2989 题意:极大团数量 解法:开始狂tle, 后来了论文:Finding All Cliques of an Undirected Graph(Coen Bron & Joep Kerboscht) ZOJ 1492 - Maximum Clique(基础) acm.zju.edu/show_problem.php?pid=1492 题意:图的最大团 解法:搜索,如果要求速度,可参考下相应论文 其他 不能成大类的 POJ 1470 - Closest Common Ancestors(基础) acm.pku.edu/JudgeOnline/problem?id=1470 题意:LCA问题 解法:tarjan或RMQ,另外输入很恶心 POJ 1985 - Cow Marathon(基础) acm.pku.edu/JudgeOnline/problem?id=1985 题意:树上的最长路径 解法:dp POJ 1986 - Distance Queries(中等) acm.pku.edu/JudgeOnline/problem?id=1986 题意:LCA 解法:tarjan或RMQ HOJ 11192 - Justice League(有趣的图论) acm.hnu:8080/online/?action=problem&type=show&id=11192&courseid=99 HOJ 11277 - New Island(有趣的图论) acm.hnu:8080/online/?action=problem&type=show&id=11277&courseid=109 ----------------- 搜索题目推荐及解题报告 以前的帖子要么太分散,要么太凌乱,故现在开始,对每一个分类做一个长期更新的汇总贴。 格式说明:题目名后面列出个人此题的大致难度(对菜鸟而言) POJ 1069 -The Bermuda Triangle(难) acm.pku.edu/JudgeOnline/problem?id=1069 题意:用给定三角型填充六边形 解法:此题的思想上精华在于坐标化 ps:传说中比较bt,确实比较bt,主要很容易写错,我ac了,但程序没完全对.... POJ 1077 - Eight(中等,此题不做人生不完整) acm.pku.edu/JudgeOnline/problem?id=1077 题意:八数码问题,超经典题 解法:广搜,A*,双向广搜 相关:hi.baidu/zfy0701/blog/item/7fcaba2c3d5425e98a1399cf.html (百度之星的版本,强烈推荐):acm.hnu:8080/online/?action=problem&type=show&id=10466&courseid=0 POJ 1084 - Square Destroyer(中等,经典题) acm.pku.edu/JudgeOnline/problem?id=1084 题意:把每个正方型看做集合中的元素,每个木棒看做是一个子集,求最小的子集覆盖 解法:dfs,A*,广搜肯定爆空间 POJ 1167 - The Buses(好难啊) acm.pku.edu/JudgeOnline/problem?id=1167 题意:这道题综合了很多经典的深搜技巧,狂顶 解法:dfs POJ 1190 - 生日蛋糕(基础,好题) acm.pku.edu/JudgeOnline/problem?id=1190 题意:略 解法:dfs,题偏简单,但做出来还是有些感觉的 POJ 1324 - Holedox Moving(中等) acm.pku.edu/JudgeOnline/problem?id=1324 题意:略 解法:A*,dfs + 上界剪枝,广搜 相关:hi.baidu/zfy0701/blog/item/7fcaba2c3d5425e98a1399cf.html hi.baidu/zfy0701/blog/item/a3c44ecc049b1c1501e92806.html POJ 1376 - Robot(基础) acm.pku.edu/JudgeOnline/problem?id=1376 题意:略 解法:bfs,A*.... POJ 1475 - Pushing Boxes(中等,很推荐) acm.pku.edu/JudgeOnline/problem?id=1475 题意:推箱子游戏 解法:双重bfs(对箱子bfs 时 对人bfs),A* POJ 1945 - Power Hungry Cows(??) acm.pku.edu/JudgeOnline/problem?id=1945 题意:略 解法:在一份解题报告中被列为难题,不过好好像写了个很简单很暴力的bfs就过了...速度还是有些慢,暂时想不到好的启发函数 POJ 2044 - Weather Forecast(中等) acm.pku.edu/JudgeOnline/problem?id=2044 题意:略 解法:广搜,dp,深搜 相关:hi.baidu/zfy0701/blog/item/d7b6490f847948e8ab6457c6.html POJ 2286 - The Rotation Game(较难) acm.pku.edu/JudgeOnline/problem?id=2286 题意:略 解法:IDA*(迭代加深+上下界强剪 相关:hi.baidu/zfy0701/blog/item/ce0f802261bfbba14723e871.html POJ 2308 - Dearboy's Puzzle(中等,但做的人少?) acm.pku.edu/JudgeOnline/problem?id=2308 题意:判断连连看是否有解 解法:DFS + BFS 相关:hi.baidu/zfy0701/blog/item/c62f41af65aa1fca7cd92afc.html POJ 2426 Remainder(较难,=) acm.pku.edu/JudgeOnline/problem?id=2426 题意:略,主要是数论部分比较容易让人抓狂 解法:bfs 相关:hi.baidu/zfy0701/blog/item/7fcaba2c3d5425e98a1399cf.html POJ 2449 Remmarguts' Date(中等,强烈推荐)王立人 acm.pku.edu/JudgeOnline/problem?id=2449 题意:经典问题:K短路 解法:dijkstra+A*,方法很多 相关:acm.pku.edu/JudgeOnline/showcontest?contest_id=1144 POJ 2688 - Cleaning Robot(基础) acm.pku.edu/JudgeOnline/problem?id=2688 题意:bfs后转换为tsp问题 解法:bfs+dp,bfs+dfs 相关:hi.baidu/zfy0701/blog/item/ceb06f261749a6128a82a1b2.html POJ 2908 - Quantum(中等) acm.pku.edu/JudgeOnline/problem?id=2908 题意:其实就是单源最短路径 解法:优先队列广搜(即dijkstra),建议用位运算优化 POJ 3074 - Sudoku(中等) acm.pku.edu/JudgeOnline/problem?id=3074 题意:数独游戏,数据比2676强很多,但比3076弱 解法:用dfs回溯基本可过,不过每次应选择可能填的数字最少的格子搜 更快的方法是先转换成exact cover问题,然后用经典dancing links解决, dancing links原始论文:/PS_cache/cs/pdf/0011/0011047v1.pdf 翻译:sqybi/works/dlxcn/ POJ 3322 - Bloxorz I(基础) acm.pku.edu/JudgeOnline/problem?id=3322 题意:略,这个游戏本身很好玩(jandan/2008/01/24/bloxorz.html) 解法:广搜,双向广搜 相关:hi.baidu/zfy0701/blog/item/d7b6490f847948e8ab6457c6.html POJ 3460 - Booksort(较难,很推荐) acm.pku.edu/JudgeOnline/problem?id=3460 题意:略 解法:IDA*,A*,DFS* 相关:hi.baidu/zfy0701/blog/item/5c5a404b0f73ecf582025ce4.html POJ 3523 - The Morning after Halloween(较难) acm.pku.edu/JudgeOnline/problem?id=3523 题意:把所有机器人移到各自的位置,不能相撞或重合 解法:我的状态设计太暴力了:以所有机器人位置表示状态。然后用A*过,排倒数第几,郁闷。谁知道好的状态设计方法告诉我^_^ POJ 3633 - Copying DNA(较难) acm.pku.edu/JudgeOnline/problem?id=3633 题意:一个填充字符串的搜索题 解法:各种搜法皆宜 相关:算法的实现较挑战,我是参考了 www.wiskey86/wordpress/?p=54 才搞定的 POJ 3635 full tank?(中等) acm.pku.edu/JudgeOnline/problem?id=3635 题意:最短路变形 解法:广搜 相关:hi.baidu/hnu_reason/blog/item/086e3dccfc8cb21600e9286b.html --------------------- 字符串题目推荐及解题报告 说明:小弟才疏学浅,最近发现此文点击率较高,还有一些转载,实在是万分惭愧。 这份题目推荐里面,实在水题烂题太多,上不得台面,等今年赛区赛结束后,本菜一定好好清理下此贴。 POJ 1002 - 487-3279(基础) acm.pku.edu/JudgeOnline/problem?id=1002 题意:略 解法:二叉查数,map,快排... POJ 1200 - Crazy Search(基础) acm.pku.edu/JudgeOnline/problem?id=1200 题意:出不相同的子串数量,字母表大小和子串长度会给定,这题很推荐hash入门者一做 解法:hash(建议karp-rabin) POJ 1204 - Word Puzzles(基础) acm.pku.edu/JudgeOnline/problem?id=1204 题意:基本多串匹配 解法:多串匹配自动机(单串去弄肯定会超时) POJ 1229 - Wild Domains(中等) acm.pku.edu/JudgeOnline/problem?id=1229 题意:模糊匹配 解法:dp POJ 1625 - Censored!(中等) acm.pku.edu/JudgeOnline/problem?id=1625 题意:求长度为n不包括给定模式串的字符串数量。(题意同2778,但不能按2778的方法,建议先做此题,再做2778) 解法:Aho-Corasick自动机 + dp 相关:hi.baidu/zfy0701/blog/item/c62f41afca8180ca7cd92a19.html POJ 1743 - Musical Theme(中等) acm.pku.edu/JudgeOnline/problem?id=1743 题意:一个串中最长不重叠子串 解法:后缀数组+二分枚举答案,后缀数组+栈扫描,RK+二分枚举答案 相关:hi.baidu/zfy0701/blog/item/f2278a0928991dca3bc763a0.html POJ 1816 - Wild Words(中等,绝对的Trie应用好题,同时又是搜索好题) acm.pku.edu/JudgeOnline/problem?id=1816 题意:扩展多串模式匹配(含?, *) 解法:Trie + dfs,有兴趣也可用基于位并行的自动机(可参考柔性字符串匹配,扩展匹配章节) POJ 2185 - Milking Grid(中等) acm.pku.edu/JudgeOnline/problem?id=2185 题意:最小矩型的覆盖 解法:KMP (不多的KMP好题) 相关:acm.pku.edu/JudgeOnline/showmessage?message_id=33571 POJ 2513 - Colored Sticks(基础) acm.pku.edu/JudgeOnline/problem?id=2513 题意:转化成欧拉回路 解法:并查集+hash,并查集+Trie POJ 2774 - Long Long Message(中等) acm.pku.edu/JudgeOnline/problem?id=2774 题意:两个串的公共最长子串 解法:后缀数组,Oracle Factor自动机,后缀自动机 相关:hi.baidu/zfy0701/blog/item/f2278a0928991dca3bc763a0.html hi.baidu/zfy0701/blog/item/d9fedbd14581113d9b5027ab.html POJ 2778 - DNA Sequence(中等) acm.pku.edu/JudgeOnline/problem?id=2778 题意:求长度为n不包括给定模式串的字符串数量。 解法:Aho-Corasick自动机(前缀树) + 矩阵快速乘法 相关:hi.baidu/zfy0701/blog/item/f2278a0928991dca3bc763a0.html 类似于1625,建议先做1625 POJ 1699 - Best Sequence(基础) acm.pku.edu/JudgeOnline/problem?id=1699 题意:转换为TSP问题(注意子串的包含关系!) 解法:回溯,状态dp POJ 3376 - Finding Palindromes(中等) acm.pku.edu/JudgeOnline/problem?id=3376 题意:回文串组合 解法:出规律,然后Trie + kmp推广形式 POJ 3415 - Common Substrings(较难) acm.pku.edu/JudgeOnline/problem?id=3415 题意:统计两个串中长度>=k的公共子串的数量 解法:后缀数组+栈扫描,后缀自动机 相关:hi.baidu/zfy0701/blog/item/f2278a0928991dca3bc763a0.html POJ 3080 - Blue Jeans(如果用暴力,就很简单) acm.pku.edu/JudgeOnline/problem?id=3080 题意:求n个串的最长公共子串 解法:后缀数组+栈扫描,后缀数组+二分枚举,暴力 相关:hi.baidu/zfy0701/blog/item/57ada7edf5f44ed1b31cb1cc.html POJ 3208 - Apocalypse Someday(较难) acm.pku.edu/JudgeOnline/problem?id=3208 题意:略 解法:有意思的自动机dp POJ 3261 - Milk Patterns(中等) acm.pku.edu/JudgeOnline/problem?id=3261 题意:求一个串中重复出现至少k次的最长子串 解法:后缀数组+栈扫描,hash + 二分 POJ 3294 - Life Forms(较难,强烈推荐) acm.pku.edu/JudgeOnline/problem?id=3294 题意:n个串中,为大于n/2个串所共有的所有最长子串 解法:后缀数组+栈扫描,暴力(很容易被卡掉),后缀数组+线段树(?) 相关:hi.baidu/zfy0701/blog/item/57ada7edf5f44ed1b31cb1cc.html POJ 3576 - Language Recognition(中等) acm.pku.edu/JudgeOnline/problem?id=3576 题意:求一个dfa,它满足两个条件,1、能识别所有词的dfa,2、要求状态数最少。 解法:trie + hash 相关:hi.baidu/zfy0701/blog/item/b8332b5cd90e7b45fbf2c033.html POJ 3581 - Sequence(中等) acm.pku.edu/JudgeOnline/problem?id=3581 题意:把原串分三段并反转,求字典序最小的那串 解法:后缀数组 本来觉得很水,但却是我目前做得最失败的一道后缀数组题 POJ 3630 - Phone List(基础,强烈推荐用此题练Trie) acm.pku.edu/JudgeOnline/problem?id=3630 题意:给n个串,看是否有一个串是另一个串的前缀 解法:快排,Trie POJ 3690 - Constellations(基础) acm.pku.edu/JudgeOnline/problem?id=3690 题意:二维串匹配 解法:转换为一维,或者用多串匹配 POJ 3691 - DNA repair(中等电解液) acm.pku.edu/JudgeOnline/problem?id=3691 题意:修复非法字符串需要替换的最少字符数 解法:动态规划,如果使用AC自动机去做dp的话比较简单且只需要二维,用dp[i][j]表示第i个字符时,第j种状态(不是非法状态)所需要最小的修改量 POJ 3693 - Maximum repetition substring(难) acm.pku.edu/JudgeOnline/problem?id=3693 题意:求最循环节最多的子串 解法:我所知道的最好的做法应该是先做s-factorization(也就是lempel-ziv),然后在分解之后的每一段中枚举周期,周期可以通过 推导关系式确定是否合法,然后可确定循环次数,取最大的,中间还用到了对kmp的扩展。具体来说有KK算法,和ML算法两种,其中ML不能遍历所有的 runs。 其他OJ: SPOJ 2743 - Prefix Tiling www.spoj.pl/problems/PRETILE/ 规律 空罐 Cans(这个自动机dp还是有意思的) cat.nknush.kh.edu.tw/ZeroJudge/ShowProblem?problemid=b179 HDOJ 2471 - History of Languages(杭州现场赛) acm.hdu.edu/showproblem.php?pid=2471 自动机的等价性,划分集合的dp |
本文发布于:2024-09-22 12:39:19,感谢您对本站的认可!
本文链接:https://www.17tex.com/xueshu/470932.html
版权声明:本站内容均来自互联网,仅供演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,我们将在24小时内删除。
留言与评论(共有 0 条评论) |