2020-2021:teams:alchemist:weekly_digest_8
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_8 [2020/07/31 11:16] hardict [专题] |
2020-2021:teams:alchemist:weekly_digest_8 [2020/07/31 11:43] (当前版本) hardict [龙鹏宇 Hardict] |
||
|---|---|---|---|
| 行 2: | 行 2: | ||
| ===== 比赛简记 ===== | ===== 比赛简记 ===== | ||
| + | |||
| + | 2020.07.25 2020牛客暑期多校训练营（第五场） ''pro 5/6/11 rank 46/???'' | ||
| + | |||
| + | 2020.07.27 2020牛客暑期多校训练营（第六场） ''pro 7/8/11 rank 35/???'' | ||
| ===== Max.D. ===== | ===== Max.D. ===== | ||
| 行 17: | 行 21: | ||
| 经纬度求解两点球面距离 | 经纬度求解两点球面距离 | ||
| - | [[Haversine formula|Haversine formula]] | + | [[.hardict:haversine_formula|Haversine formula]] |
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | 自闭一场cf | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | CF917D Stranger Trees | ||
| + | |||
| + | 51nod 1363 最小公倍数之和 | ||
| ===== MountVoom ===== | ===== MountVoom ===== | ||
| 行 42: | 行 51: | ||
| ===== 龙鹏宇 Hardict ===== | ===== 龙鹏宇 Hardict ===== | ||
| + | 多补题，本地多测试 | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| 行 71: | 行 81: | ||
| === 来源： === | === 来源： === | ||
| + | |||
| + | [[http://acm.hdu.edu.cn/showproblem.php?pid=6333|HDU 6333]] | ||
| === 标签： === | === 标签： === | ||
| + | |||
| + | 分块 组合 | ||
| === 题意： === | === 题意： === | ||
| + | |||
| + | 求解$T\leq 10^5$组$\sum_{i=0}^{m}C_{n}^{i}$ | ||
| + | |||
| + | $1\leq n,m\leq 10^5$ | ||
| === 题解： === | === 题解： === | ||
| + | |||
| + | $pre[n][m]=\sum_{i=0}^m C_n^i$ | ||
| + | |||
| + | $pre[n][m]=pre[n][m-1]+C_n^m,pre[n][m]=\sum_{i=0}^m (C_{n-1}^i+C_{n-1}^{i-1})=2pre[n-1][m]-C_{n-1}^i$ | ||
| + | |||
| + | 于是得到了$(n,m)$对于$(n \pm 1,m),(n,m \pm 1)$的转移 | ||
| + | |||
| + | 利用莫队将询问分块对$(n,m)$进行转移，即可解决题目 | ||
| === 评论： === | === 评论： === | ||
| + | |||
| + | 一开始一组想对前缀和推一个公式 | ||
| + | |||
| + | 后面注意到数据范围才考虑是否可以利用暴力转移分块解决题目 | ||
| + | |||
| + | 对于这种状态可以在相邻位快速转移的问题可以根据数据范围考虑是否分块 | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
2020-2021/teams/alchemist/weekly_digest_8.1596165409.txt.gz · 最后更改: 2020/07/31 11:16 由 hardict
