2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_4
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_4 [2020/07/22 16:45] mountvoom [C. Count New String] |
2020-2021:teams:alchemist:2020_nowcoder_multiuniversity_4 [2020/07/24 11:23] (当前版本) hardict [lpy] |
||
|---|---|---|---|
| 行 11: | 行 11: | ||
| ===== lpy ===== | ===== lpy ===== | ||
| + | |||
| + | 比较函数必须得返回一个准确大小关系，如果关键字全相同可能会炸内存(递归栈) | ||
| + | |||
| + | 字符串方面还得加强 | ||
| ===== xsy ===== | ===== xsy ===== | ||
| 行 16: | 行 20: | ||
| 需要自信一点，相信自己签到难度的数学题还是能做出来的qwq。 | 需要自信一点，相信自己签到难度的数学题还是能做出来的qwq。 | ||
| + | |||
| + | 想题的时候要注意细节，注意特殊情况。 | ||
| ====== 题解 ====== | ====== 题解 ====== | ||
| ===== A. Ancient Distance ===== | ===== A. Ancient Distance ===== | ||
| 行 62: | 行 68: | ||
| ===== D. Dividing Strings ===== | ===== D. Dividing Strings ===== | ||
| + | |||
| + | 首先答案一定是$\leq 9$的，因为分成$n$个一位数。 | ||
| + | |||
| + | 那么相邻的两段的长度一定满足绝对值的差$<= 1$。 | ||
| + | |||
| + | 然后分类讨论： | ||
| + | |||
| + | $x -> x$，从$lcp+1$的位置开始判断相邻只差是否$\leq 9$，注意位数较少时的情况。 | ||
| + | |||
| + | $x -> x + 1$，那么只能为$9999x$和$10000y$，且$x > y$。 | ||
| + | |||
| + | $x -> x - 1, x > 1$，那么只能为$10000x$和$99999y$，且$x < y$。 | ||
| + | |||
| + | 这三种情况当$x \ge 2$时不会同时满足，于是枚举开头一段的长度接下来暴力往后判断即可。 | ||
| + | |||
| + | 当$x = 1$时，需要先进行$x -> x + 1$的特判，因为两个相邻的个位数之差一定$\leq 9$。 | ||
| + | |||
| + | 因为只能求出两个数的差值，所以可以维护一下每一段相对于第一段的差值，最后用最大差值减去最小差值即可。 | ||
| + | |||
| + | by MountVoom | ||
| + | |||
| + | ===== H. Harder Gcd Problem ===== | ||
| + | |||
| + | 据说是原题,$1 \sim n$取二元组$(a,b),gcd(a,b)>1$,使数量最多 | ||
| + | |||
| + | 首先每个数只与有哪些素因子有关，用贪心的思想，易想到较大的素因子应该优先匹配，素因子越少的数优先匹配 | ||
| + | |||
| + | 从后向前枚举每个素因子$p$，然后把$p|x$且没匹配的数放一起 | ||
| + | |||
| + | 按素因子个数与从大到小第一个不同的素因子大小排序，然后贪心取即可 | ||
| + | |||
| + | by Hardict | ||
| ====== 补题 ====== | ====== 补题 ====== | ||
2020-2021/teams/alchemist/2020_nowcoder_multiuniversity_4.1595407530.txt.gz · 最后更改: 2020/07/22 16:45 由 mountvoom
