2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_9
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_9 [2020/08/08 22:42] grapelemonade [G] |
2020-2021:teams:mian:nowcoder_training:2020_multi-university_training_contest_9 [2020/08/14 11:20] (当前版本) gary |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| - | ====== 2020牛客暑期多校训练营（第八场） ====== | + | ====== 2020牛客暑期多校训练营（第九场） ====== |
| ===== Results ===== | ===== Results ===== | ||
| 行 44: | 行 44: | ||
| <code python>print(eval(input().replace('(','**(')))</code> | <code python>print(eval(input().replace('(','**(')))</code> | ||
| ===== B ===== | ===== B ===== | ||
| + | |||
| + | 考虑类似树上DP的过程，记录每个节点完成其子树所需的最小初始HP以及可以获得的HP，最小初始HP可以通过二分来求解，可以增加HP的子树直接选取，减小HP的子树贪心选取 | ||
| ===== C ===== | ===== C ===== | ||
| 行 56: | 行 58: | ||
| $$ | $$ | ||
| - | \large\prod\limits_{i=a}^{b}\prod\limits_{j=c}^{d}\gcd(x^i,y^j)\\ | + | \prod\limits_{i=a}^{b}\prod\limits_{j=c}^{d}\gcd(x^i,y^j)\\ |
| - | \large=\prod\limits_{i=a}^{b}\prod\limits_{j=c}^{d}\gcd((p_1^{u_1}p_2^{u_2}\dots p_n^{u_n})^i,(p_1^{v_1}p_2^{v_2}\dots p_n^{v_n})^j)\\ | + | =\prod\limits_{i=a}^{b}\prod\limits_{j=c}^{d}\gcd((p_1^{u_1}p_2^{u_2}\dots p_n^{u_n})^i,(p_1^{v_1}p_2^{v_2}\dots p_n^{v_n})^j)\\ |
| - | \large=\prod\limits_{i=a}^{b}\prod\limits_{j=c}^{d}\prod\limits_{k=1}^{n}p_k^{\min(i\cdot u_k, j\cdot v_k)}\\ | + | =\prod\limits_{i=a}^{b}\prod\limits_{j=c}^{d}\prod\limits_{k=1}^{n}p_k^{\min(i\cdot u_k, j\cdot v_k)}\\ |
| - | \large=\prod\limits_{k=1}^{n}\prod\limits_{i=a}^{b}\prod\limits_{j=c}^{d}p_k^{\min(i\cdot u_k, j\cdot v_k)}\\ | + | =\prod\limits_{k=1}^{n}\prod\limits_{i=a}^{b}\prod\limits_{j=c}^{d}p_k^{\min(i\cdot u_k, j\cdot v_k)}\\ |
| - | \large=\prod\limits_{k=1}^{n}p_k^{\sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}\min(i\cdot u_k, j\cdot v_k)}\\ | + | =\prod\limits_{k=1}^{n}p_k^{\sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}\min(i\cdot u_k, j\cdot v_k)}\\ |
| $$ | $$ | ||
| - | 考虑对每个质因数 $p_k$ 求 $$\large\sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}\min(i\cdot u_k, j\cdot v_k)$$ | + | 考虑对每个质因数 $p_k$ 求 $$\sum\limits_{i=a}^{b}\sum\limits_{j=c}^{d}\min(i\cdot u_k, j\cdot v_k)$$ |
| 容易发现 $i$ 固定后 $\sum\limits_{j=c}^{d}\min(i\cdot u_k, j\cdot v_k)$ 至多由一段等差数列和一段常数列组成。 | 容易发现 $i$ 固定后 $\sum\limits_{j=c}^{d}\min(i\cdot u_k, j\cdot v_k)$ 至多由一段等差数列和一段常数列组成。 | ||
| 行 71: | 行 73: | ||
| 那么我们枚举 $p_k$，再枚举 $i$ 即可。 | 那么我们枚举 $p_k$，再枚举 $i$ 即可。 | ||
| ===== F ===== | ===== F ===== | ||
| + | |||
| + | 将所有衣服排序，滑动窗口遍历排序后的序列，保证窗口内有m间不同时间的衣服，扫一遍对所有满足条件的状态求最小值 | ||
| ===== G ===== | ===== G ===== | ||
| 行 92: | 行 96: | ||
| ===== I ===== | ===== I ===== | ||
| + | |||
| + | 推算一下会发现，选取最小的一位数和剩余数组成的最小数字是最优的解 | ||
| ===== J ===== | ===== J ===== | ||
| 行 103: | 行 109: | ||
| ===== K ===== | ===== K ===== | ||
| + | 先求出开始追击的节点，只有对追的人遍历所有节点记录他到每个位置的时间，再对逃跑的人遍历，记录所有可以比追击的人先到的节点，对所有可行的时间去最大值 | ||
| ------------- | ------------- | ||
| 行 110: | 行 117: | ||
| ptw: | ptw: | ||
| + | * 我决起而飞 | ||
| + | |||
| + | Gary: | ||
| + | * 大概把会的都做了 | ||
| + | * 读题要仔细，最好两人读题 | ||
2020-2021/teams/mian/nowcoder_training/2020_multi-university_training_contest_9.1596897722.txt.gz · 最后更改: 2020/08/08 22:42 由 grapelemonade
