bcoi系列目录直达

前言(必看)

本blog将在很短时间内崩坏！！！如未出现图片请立即刷新！！！刷新无果后立即退出！！！

会议摘要

本次会议主要围绕图的存储方法及最短路径搜索展开，重点讲解了邻接表的应用、图的存储实现、以及如何使用广度优先搜索（BFS）求解奇数步与偶数步的最短路径问题。此外，还涉及了图论中的分层思想和位运算在实际编程中的注意事项。

图的存储方法 使用邻接表来存储图结构，通过Vector实现动态数组，简化了存储与访问过程。 每个节点维护一个链表或Vector，记录与该节点相连的所有其他节点。 与邻接矩阵相比，邻接表更节省空间，适用于稀疏图。 BFS在奇偶最短路径中的应用 引入两个数组分别记录从起点出发到达每个节点的奇数步和偶数步的最短路径。 初始状态下，起点的偶数步为0，奇数步为一个极大值（表示不可达）。 使用BFS遍历图，通过松弛操作不断更新奇偶最短路径数组。 对于每个节点，奇数步可以由前一个节点的偶数步+1得到，偶数步由前一个节点的奇数步+1得到。 分层图与位运算的注意事项 将图分为奇数层和偶数层，通过BFS进行状态更新，本质上是分层图思想。 实际编程中，需要注意运算符优先级的问题，避免因位运算导致逻辑错误。 例如，判断奇偶性时若未正确加括号，可能导致运算顺序错误，从而影响结果。 实际问题求解与特判处理 针对每组查询，根据输入的L值判断是否满足奇数步或偶数步的可达条件。 特判处理：若图中存在孤立节点（如1号节点没有任何边），则应直接返回不可达。 该特判在当年CSP比赛中未被测试点覆盖，但理论上仍需考虑。 其他题目简要说明 提到“优秀的拆分”问题，即将整数拆分为若干个2的幂次之和，难度较低，无需深入讲解。 提到另一道题目为实时统计分数线问题，模拟评奖过程，根据百分比动态调整获奖人数和分数线。