2020-2021:teams:famerwzyyuki:线性基
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:famerwzyyuki:线性基 [2020/05/29 20:58] yuki |
2020-2021:teams:famerwzyyuki:线性基 [2020/05/29 21:09] (当前版本) yuki |
||
|---|---|---|---|
| 行 329: | 行 329: | ||
| **题意：**给一个无向连通图，求一条从$1$到$n$的路径（可以不是简单路径），使经过的边权的异或和最大。\\ | **题意：**给一个无向连通图，求一条从$1$到$n$的路径（可以不是简单路径），使经过的边权的异或和最大。\\ | ||
| **题解：**首先注意到一个结论：对于所有的简单环，环上边权的异或和都可以无代价的获取。原因是可以从一号点出发进入该环绕一圈后原路返回。由于一条路径绕两边对答案的贡献为 $0$，所以这些简单环的异或和都可以无代价取得。那么现在问题就转化成了寻找一条 $1$到 $n$的路径，再异或上一些简单环的异或和，最大化答案。\\ | **题解：**首先注意到一个结论：对于所有的简单环，环上边权的异或和都可以无代价的获取。原因是可以从一号点出发进入该环绕一圈后原路返回。由于一条路径绕两边对答案的贡献为 $0$，所以这些简单环的异或和都可以无代价取得。那么现在问题就转化成了寻找一条 $1$到 $n$的路径，再异或上一些简单环的异或和，最大化答案。\\ | ||
| - | 我们考虑应该寻找哪一条路径：事实上任选一条路径即可。原因是选择的路径和答案路径一定可以构成一个环，所以异或上该环的权值就可以得到最优解。\\ | + | 我们考虑应该寻找哪一条路径：事实上任选一条路径即可。原因是选择的路径和答案路径一定可以构成一个环，所以异或上该环的权值就可以得到最优解。 |
| <hidden std> | <hidden std> | ||
| <code cpp> | <code cpp> | ||
| 行 394: | 行 394: | ||
| </hidden> | </hidden> | ||
| \\ | \\ | ||
| - | ==== 「BZOJ 2844」albus 就是要第一个出场 - 线性基 ==== | ||
| - | |||
2020-2021/teams/famerwzyyuki/线性基.1590757099.txt.gz · 最后更改: 2020/05/29 20:58 由 yuki
