2024.7.10

T1

题面

请构造一颗有 \(a\) 个度数为 \(1\) 的点与 \(b\) 个度数为 \(3\) 的点的树，无解输出 \(0\)

\(a,b\le 200\)

题解

先满足 \(3\) 度点，再满足 \(1\) 度点即可

T2

题面

给定一个 \(n\) 个点 \(m\) 条边的有向图，便有边权 \(w\)，请找一条从 \(1\) 到 \(n\) 的路径，使得 \(\max_{i=1}^{step}w_i\) 最小。

\(n,m\le 3\times 10^5,1\le w_i\le 10^9\)

题解

直接跑类最短路可过。但正解是二分加BFS。

T3

题面

给你一个 \(n\) 个点 \(m\) 条边的简单无向连通图，最大化度数为奇数的点的个数。
还需要给出构造，即输出一个长度为 \(m\) 的 \(01\) 串，\(1\) 表示保留这个边，\(0\) 表示删掉这个边，请输出字典序最大的方案。

\(n\le 6\times 10^5,n-1\le m\le 9\times 10^5\)

题解

等价于每个点有一个状态，最后要使状态为 \(1\) 的边尽可能的多，保留一条边相当于将这条边连接的两个点状态取反。

考虑保留边，假设原图是一棵树，有一种构造方案：

对于每个子树而言，如果子树根节点其与子树内的点连接后状态为 \(0\)，则子树根节点与其父亲连边，使得这个子树根节点状态为 \(1\)。

这样构造出来，会发现，如果 \(2|n\)，则答案为 \(n\)，否则为 \(n-1\)。可以证明这是最优的答案。如果原图不是棵树，我们可以生成一棵树，选择所有非树边，这是所有点状态一开始不是全为 \(0\)，通过上述方案可以得到答案，由于要求字典序最大，编号小的边应该被当作非树边，所以这里需要最大生成树。

如果 \(2|n\)，那么上述的构造是唯一的方案，因为不论如何调换边的状态，都会使得答案减少。

如果 \(2\not|n\)，那么需要抉择的那个偶数点的位置，因为按照上述构造方法，偶数点一定会在根节点，我们需要将这个点换下来。显然，将偶数点换下来的过程就是将这两个点之间的边状态取反的过程。

因为要构造字典序最大解，每次交换应该找到编号最小的状态为 \(0\) 的边。

于是可以按照如下方案建立新图：

原图上每条边从其上方第一个编号比其小的原图上的边边向它连边，如果其上方不存在编号比其小的边，从虚空节点向其连边。

每次从虚空节点出发，找到他连的边中编号最小的状态为 \(0\) 的边下面的点，取反这两点之间的所有边，并跳到那个点，重复执行直到无法执行。

最后得到字典序最大解。