hackerchef - 博客园

2024年4月

摘要：原题链接：https://www.luogu.com.cn/problem/P1347 题意解读：在给出多对关系字母的比较关系之后，判断能否确定所有字母的顺序。解题思路：对字母的关系建立图，如A<B建立A指向B的一条边。如果在拓扑排序过程中，每次寻找入度为0的点只有一个，且最终可以形成拓扑序，阅读全文

posted @ 2024-04-03 15:01 hackerchef 阅读(134) 评论(0) 推荐(0)

洛谷题单指南-图的基本应用-P1363 幻象迷宫

摘要：原题链接：https://www.luogu.com.cn/problem/P1363 题意解读：迷宫可以无限扩展，对第一个样例进行模拟，扩展4块的示意图：从起点S，沿着红色虚线，是可以无限走下去的，要判断是否能够无限走下去。解题思路：直观上，会考虑把迷宫复制多块，但是会面临2个问题： 1、内阅读全文

posted @ 2024-04-03 11:25 hackerchef 阅读(144) 评论(0) 推荐(0)

2024年3月

洛谷题单指南-图的基本应用-P2853 [USACO06DEC] Cow Picnic S

摘要：原题链接：https://www.luogu.com.cn/problem/P2853 题意解读：找到所有奶牛都可以到达的牧场，就是要从奶牛所在位置开始遍历，求所有奶牛能重合的点的个数。解题思路：直接从从牛奶所在位置进行DFS，记录每个位置有奶牛能到的个数，个数等于奶牛总数的即合适的牧场。 10 阅读全文

posted @ 2024-03-30 15:02 hackerchef 阅读(773) 评论(0) 推荐(0)

洛谷题单指南-图的基本应用-P1127 词链

摘要：原题链接：https://www.luogu.com.cn/problem/P1127 题意解读：排列单词，使得相邻单词的首尾字母一样，找到字典序最小的词链。解题思路：由于单词之间可以相邻的条件是前一个单词的末尾字母和后一个单词的开头字母一样，因此可以遍历每一个单词，再找到每一个可以接在其后面的阅读全文

posted @ 2024-03-30 14:40 hackerchef 阅读(172) 评论(2) 推荐(0)

洛谷题单指南-图的基本应用-P1807 最长路

摘要：原题链接：https://www.luogu.com.cn/problem/P1807 题意解读：由于对于每一条边u->v，都有u < v，因此节点1的入度一定是0，且是有向无环图，直观上可以通过拓扑排序法搜索每一个节点，计算1到每一个节点的最长距离。但问题在于，入度为0的节点可能不止一个，这样在计阅读全文

posted @ 2024-03-28 16:11 hackerchef 阅读(175) 评论(0) 推荐(0)

洛谷题单指南-图的基本应用-P4017 最大食物链计数

摘要：原题链接：https://www.luogu.com.cn/problem/P4017 题意解读：食物链的顶端不会被其他生物吃，在图结构中设定为入度是0，食物链的底端不会吃其他生物，在图结构中设定为出度是0，此题就是要计算所有入度是0的点到所有出度是0的点一共有多条路径。解题思路：首先，来模拟样阅读全文

posted @ 2024-03-28 13:47 hackerchef 阅读(152) 评论(0) 推荐(0)

洛谷题单指南-图的基本应用-P1113 杂务

摘要：原题链接：https://www.luogu.com.cn/problem/P1113 题意解读：要计算所有任务完成的最早时间，其实取决于最晚完成的那一个任务，计算每一个任务的完成时间，找最大值即可。解题思路：下面介绍两种做法：递推法、拓扑排序法 1、递推法由于杂务k (k>1) 的准备工作只阅读全文

posted @ 2024-03-28 09:53 hackerchef 阅读(158) 评论(0) 推荐(0)

洛谷题单指南-图的基本应用-P3916 图的遍历

摘要：原题链接：https://www.luogu.com.cn/problem/P3916 题意解读：寻找每个点所能到达的最大的点。解题思路：直观上，可以依次从每个点开始DFS搜索，记录经过的最大点，复杂度是O(n^2)级别，会超时。可以换一种角度，既然要找每个点可以达到的最大值，那么可以反向建图阅读全文

posted @ 2024-03-27 14:24 hackerchef 阅读(169) 评论(0) 推荐(0)

洛谷题单指南-图的基本应用-P5318 【深基18.例3】查找文献

摘要：原题链接：https://www.luogu.com.cn/problem/P5318 题意解读：图的建立、DFS、BFS模版题。解题思路：本题主要考察建图、图的DFS、BFS遍历。建图方式：邻接表vector<int> g[N]; 需要注意的是，在DFS、BFS搜索邻接点时，需要先将邻接点编阅读全文

posted @ 2024-03-26 19:58 hackerchef 阅读(187) 评论(0) 推荐(0)

洛谷题单指南-集合-P2814 家谱

摘要：原题链接：https://www.luogu.com.cn/problem/P2814 题意解读：已知多组父子关系，找某个人最早的祖先，并查集的应用。解题思路：由于存在真正的父子关系，所以在并查集合并的时候，要把p[x] = y中x设置为子，y设置为父，其余都是并查集的常规操作。由于是计算姓名阅读全文

posted @ 2024-03-26 17:32 hackerchef 阅读(78) 评论(0) 推荐(0)

公告