2020-2021:teams:intrepidsword:2020-nowcoder-multi-3
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:intrepidsword:2020-nowcoder-multi-3 [2020/07/24 16:37] chielo [H. Sort the Strings Revision] |
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 ===== | ||
| 行 29: | 行 26: | ||
| ===== D. Points Construction Problem ===== | ===== D. Points Construction Problem ===== | ||
| - | **题目大意**： | + | **题目大意**：在平面上，开始时所有整点都是白点，你需要将其中 $n$ 个点染黑，使得相邻的（四联通）黑白点对数量为 $m$。 |
| - | **题解**： | + | **题解**：$m$ 必然为偶数，可以归纳证明。$m$ 至多为 $4n$。而要使 $m$ 小，注意到图形内部不应存在空行和空列，否则将两边合并起来显然不坏。这样一来，注意到答案数至少为黑点外接矩形的周长。因而最小值就是按螺旋线来摆放，或者说拼成长、宽尽可能接近的图形。 |
| + | 理论分析完后，并不需要真的去讨论、构造。由于数据范围很小，可以事先打表。首先枚举一个 ''%%L%%'' 形，然后在它上面依次摆放黑点——这不会改变周长，但是可以调节黑点数量。此外还需要一些散点以向最大值靠近。实践证明，''%%ac is ok%%''。 | ||
| ===== E. Two Matchings ===== | ===== E. Two Matchings ===== | ||
| 行 53: | 行 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.1595579832.txt.gz · 最后更改: 2020/07/24 16:37 由 chielo
