2020-2021:teams:intrepidsword:2020-nowcoder-multi-3
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2020-nowcoder-multi-3 [2020/07/25 22:08] admin [D. Points Construction Problem] |
2020-2021:teams:intrepidsword:2020-nowcoder-multi-3 [2020/07/25 22:10] (当前版本) admin [B. Classical String Problem] |
||
|---|---|---|---|
| 行 15: | 行 15: | ||
| ===== B. Classical String Problem ===== | ===== B. Classical String Problem ===== | ||
| - | **题目大意**： | + | 签到题。 |
| - | + | ||
| - | **题解**： | + | |
| ===== C. Operation Love ===== | ===== C. Operation Love ===== | ||
| 行 54: | 行 51: | ||
| ===== F. Fraction Construction Problem ===== | ===== F. Fraction Construction Problem ===== | ||
| - | **题目大意**： | + | **题目大意**：设 $\frac{c}{d}-\frac{e}{f}=\frac{a}{b}$，其中 $a,b\le2\times10^{6}$。求出 $c,d,e,f$，要求 $d,f<b$，$c,e\le4\times10^{12}$。 |
| - | + | ||
| - | **题解**： | + | |
| + | **题解**：拓欧签到题。注意 $b$ 虽然为质数幂，但是 $a$ 与 $b$ 不互质的特殊情况。或者优先处理不互质的情况（比较简单）也不错。 | ||
| ===== G. Operating on a Graph ===== | ===== G. Operating on a Graph ===== | ||
| - | **题目大意**： | + | **题目大意**：给你一个图，同时在它上面维护并查集，初始时 $find(i)=i$。随后给一些操作，每次给一个点 $u$，如果 $find(u)\neq u$，那么什么都不干，否则把当前 $u$ 所代表集合中的所有点的邻点加入进该集合。所有操作完成后，询问每个点所在的集合。 |
| - | **题解**： | + | **题解**：对每个点维护一个 ''%%vector%%''，其含义是属于 $u$，但是邻边还没有全部和自己合并的点。那么每次操作合并时，顺带把这些 ''%%vector%%'' 启发式合并即可。 |
| ===== H. Sort the Strings Revision ===== | ===== H. Sort the Strings Revision ===== | ||
2020-2021/teams/intrepidsword/2020-nowcoder-multi-3.1595686083.txt.gz · 最后更改: 2020/07/25 22:08 由 admin
