有点自闭 初赛只考了70pts 被本校神仙吊打

从一个点出发走一走  约定 1. 定义 表示从 的一条边（若无特别说明，即为无向边）2. 定义 表示从 ，经过 两条边的路径3. 定义「孤立点」表示一个度为 0 的点4. 定义「奇顶点」表示一个度数为奇数的点5. 定义对于有向图 G ，将所有的有向边替换为无向边得到图 G 的基图，若图 G 的基图是连通的，则称图 G 是「弱连通图」。6. 表示标号为 的栈。7. 用 表示 的层级结构，其中 为栈顶， 为栈底。8. 表示 里的元素 （表特指） 定义 如果图G中的一个路径包括每个边恰好一次，则该路径称为欧拉路径(Euler path)。如果一个回路是欧拉路径，则称为欧拉回路(Euler circu...

入门级别的分层图最短路  题目地址双倍经验 前言 先介绍一下分层图最短路。 分层图最短路是指在可以进行分层图的图上解决最短路问题。一般模型是：在图上，有k次机会可以直接通过一条边，问起点与终点之间的最短路径。 题目描述 Alice和Bob现在要乘飞机旅行，他们选择了一家相对便宜的航空公司。该航空公司一共在nn个城市设有业务，设这些城市分别标记为00到n-1n−1，一共有mm种航线，每种航线连接两个城市，并且航线有一定的价格。 Alice和Bob现在要从一个城市沿着航线到达另一个城市，途中可以进行转机。航空公司对他们这次旅行也推出优惠，他们可以免费在最多kk种航线上搭乘飞机。那么Alice和Bo...

ProjectDP - 29   需要维护两行状态的状压DP  题目描述 司令部的将军们打算在N*M的网格地图上部署他们的炮兵部队。一个N*M的地图由N行M列组成，地图的每一格可能是山地（用“H” 表示），也可能是平原（用“P”表示），如下图。在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑***域所示： 如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。 现在，将军们规划如何部署炮兵部队...

ProjectDP - 33   状态压缩 + DFS  题面 PDF 解题思路 首先是这个玄学的数据范围（每个组只有5个元素）很容易让人想到状压  首先把 k >= 5 的情况特判一下可以选择超过5个组那么显然选择最大的就行了  对于每一个组，枚举它的每一种状态对于这个状态，统计一下选择这个状态的总和（被选择了的数的和），与所有组里这个状态的总和取个 max 这样我们就获得了每一种状态总和的最大值对它进行一遍 DFS  这里说一个位运算技巧枚举子集 for (int s0 = s; s0; s0 = s & (s0 - 1)); s0 即为 s 的某一个子集 代码实现 // /...

年轻人的第一道国家集训队题目  如果我们不做任何处理，直接跑MST（Minimum Spanning Tree，最小生成树），结果会有三种：  正好跑出 条白边  白边多了  白边少了   第一种情况自然是最好的 剩下两种情况如何解决？  引起白边少的原因：黑边的边权相对较小，程序贪心地选择了更多的黑边 引起白边多的原因：白边的边权相对较小，程序贪心地选择了更多的白边 那么如果我们给白边相应地减去/加上一些边权，不就可以达成目标了？  考虑二分答案。 我们二分一个 表示我们当前要给白边加上 来达成目标 边界分别是边权最小值（-100）和边权最大值（100） 由于题面保证有答案，所以直接输出  ...