2020-2021:teams:hotpot:2020nowcoder5
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:2020nowcoder5 [2020/07/31 16:14] 喝西北风 |
2020-2021:teams:hotpot:2020nowcoder5 [2020/07/31 16:29] (当前版本) 喝西北风 |
||
|---|---|---|---|
| 行 19: | 行 19: | ||
| ===题解=== | ===题解=== | ||
| - | ====B - ==== | + | ====B - Graph==== |
| - | ===solved by === | + | ===solved by gyp,tyx=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 给定一棵树。每次可以添加一条边或删去一条边。保证任何时候一定是连通图，每个环上的边异或和为0。求所有边的和最小是多少 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | $2\le n \le 10^5$,$0 \le w < 2^30$ | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 可以证明，每条边的长度是确定的。任取一点为根，可以计算出每一点到根的所有边的异或和，记为$a_i$。本题等价于求一个最小生成树，第i和第j个点的边权为$a_i \bigoplus a_j$。先按升序排序。从最高位开始，从所有最高位是1和最高位是0的里各选一个数，使得其异或结果最小，这条边被计入。然后再分别从两个部分再进行类似的操作。 | ||
| ====C - Easy==== | ====C - Easy==== | ||
| 行 107: | 行 113: | ||
| ===题解=== | ===题解=== | ||
| - | ====I - ==== | + | ====I - Hard Math Problem==== |
| - | ===solved by === | + | ===solved by gyp=== |
| ===题意=== | ===题意=== | ||
| + | |||
| + | 很奇怪的一道数学题，没有输入，只输出一个结果 | ||
| ===数据范围=== | ===数据范围=== | ||
| + | |||
| + | 无 | ||
| ===题解=== | ===题解=== | ||
| + | |||
| + | 反正答案是2/3。试也能试出来，并不会证。 | ||
| ====J - ==== | ====J - ==== | ||
2020-2021/teams/hotpot/2020nowcoder5.1596183283.txt.gz · 最后更改: 2020/07/31 16:14 由 喝西北风
