2020-2021:teams:hotpot:2020nowcoder1
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:hotpot:2020nowcoder1 [2020/07/17 12:07] 喝西北风 |
2020-2021:teams:hotpot:2020nowcoder1 [2020/07/17 15:25] (当前版本) misakatao 更新 |
||
|---|---|---|---|
| 行 21: | 行 21: | ||
| ===题解=== | ===题解=== | ||
| - | ====B - ==== | + | ====B - Infinite Tree==== |
| ===solved by -, upsolved by tyx=== | ===solved by -, upsolved by tyx=== | ||
| 行 36: | 行 36: | ||
| 显然这棵树上有很多点是不需要的，我们可以仿照建立虚树的方法，把需要的点拉出来建立一棵点数较少的树。因此我们需要知道某两个点的LCA，由于这棵树的性质，我们知道把一个点的编号除以它的最小质因数就到了它的父亲，所以对于两个点数，我们把他们分别质因数分解后把所有质因子从小到大排列，例如20和30，排列后为{2,2,5},{2,3,5}，这是这一排列的最长公共后缀相乘得到的点就是他们的LCA，因为这是两个点不断向父亲移动最早可以到达的同一个点。对于本题，我们只需要对$1!,2!,3! ... m!$这几个点进行处理，当我们从$(i-1)!$进展到$i!$时，我们可以知道$i$有哪些质因子，然后我们发现$i$离他们的LCA的距离它的所有质因子个数和之前有的小于$i$最大质因子的个数，这个数量可以由树状数组查询得到，然后我们从$(i-1)!$不断向上跳，看是否需要新建一个点，之后我们在新建的树上求一个带权重心的答案即可。 | 显然这棵树上有很多点是不需要的，我们可以仿照建立虚树的方法，把需要的点拉出来建立一棵点数较少的树。因此我们需要知道某两个点的LCA，由于这棵树的性质，我们知道把一个点的编号除以它的最小质因数就到了它的父亲，所以对于两个点数，我们把他们分别质因数分解后把所有质因子从小到大排列，例如20和30，排列后为{2,2,5},{2,3,5}，这是这一排列的最长公共后缀相乘得到的点就是他们的LCA，因为这是两个点不断向父亲移动最早可以到达的同一个点。对于本题，我们只需要对$1!,2!,3! ... m!$这几个点进行处理，当我们从$(i-1)!$进展到$i!$时，我们可以知道$i$有哪些质因子，然后我们发现$i$离他们的LCA的距离它的所有质因子个数和之前有的小于$i$最大质因子的个数，这个数量可以由树状数组查询得到，然后我们从$(i-1)!$不断向上跳，看是否需要新建一个点，之后我们在新建的树上求一个带权重心的答案即可。 | ||
| - | |||
| - | ====C - ==== | ||
| - | |||
| - | ===solved by === | ||
| - | |||
| - | ===题意=== | ||
| - | |||
| - | ===数据范围=== | ||
| - | |||
| - | ===题解=== | ||
| ====D - Quadratic Form==== | ====D - Quadratic Form==== | ||
| 行 99: | 行 89: | ||
| 比赛的时候猜如果两个串不同，枚举到更长的字符串两倍长度就能找到不相同，实际上结论是到长度$|a|+|b|-gcd(|a|,|b|)$一定能找到不同，两倍显然长于这个值所以可行 | 比赛的时候猜如果两个串不同，枚举到更长的字符串两倍长度就能找到不相同，实际上结论是到长度$|a|+|b|-gcd(|a|,|b|)$一定能找到不同，两倍显然长于这个值所以可行 | ||
| - | ====G - ==== | + | ====H - Minimum-cost Flow==== |
| - | ===H - Minimum-cost Flow=== | + | |
| ===solved by gyp=== | ===solved by gyp=== | ||
| 行 120: | 行 109: | ||
| ====I - 1 or 2==== | ====I - 1 or 2==== | ||
| - | ===solved by lxh,written by lxh,tyx=== | + | ===solved by lxh, written by lxh,tyx=== |
| ===题意=== | ===题意=== | ||
| 行 150: | 行 139: | ||
| ===思路=== | ===思路=== | ||
| - | 分部积分可以证明，$\int^1_0x^n(1-x)^mdx$=\frac m{n+1}\int^1_0 x^{n+1}(1-x)^mdx$ | + | 分部积分可以证明，$\int^1_0x^n(1-x)^mdx=\frac m{n+1}\int^1_0 x^{n+1}(1-x)^mdx$ |
| - | + | ||
| - | ====K - ==== | + | |
| - | + | ||
| - | ===solved by === | + | |
| - | + | ||
| - | ===题意=== | + | |
| - | + | ||
| - | ===数据范围=== | + | |
| - | + | ||
| - | ===题解=== | + | |
| =====Replay===== | =====Replay===== | ||
| - | 第一小时： | + | 第一小时：tyx和lxh开始想A但是没有什么想法，gyp开始写J，tyx发现F通过的人数很多于是A了F，gyp的J题通过 |
| - | 第二小时： | + | 第二小时：tyx开始想I，gyp和lxh开始想H，但是都没有什么想法 |
| - | 第三小时： | + | 第三小时：gyp和lxh发现H题的性质于是通过了H，tyx开始想B但是没有想出 |
| - | 第四小时： | + | 第四小时：lxh重新开始想A但是依然没有想法，三个人开始想I并想出了一种做法，但是答案错误 |
| - | 第五小时： | + | 第五小时：三个人发现刚刚相处的做法有问题，又重新想了一种做法最后在快结束的时候通过了I题 |
| =====总结===== | =====总结===== | ||
| - | * | + | * 在同一道题上花的时间稍长，应该注意让时间分配更平均 |
2020-2021/teams/hotpot/2020nowcoder1.1594958848.txt.gz · 最后更改: 2020/07/17 12:07 由 喝西北风
