2020-2021:teams:alchemist:weekly_digest_8
差别
这里会显示出您选择的修订版和当前版本之间的差别。
| 两侧同时换到之前的修订记录 前一修订版 后一修订版 | 前一修订版 | ||
|
2020-2021:teams:alchemist:weekly_digest_8 [2020/07/31 10:12] mountvoom [肖思炀 MountVoom] |
2020-2021:teams:alchemist:weekly_digest_8 [2020/07/31 11:43] (当前版本) hardict [龙鹏宇 Hardict] |
||
|---|---|---|---|
| 行 1: | 行 1: | ||
| ====== Summer Tranning Week 3 ====== | ====== Summer Tranning Week 3 ====== | ||
| + | ===== 比赛简记 ===== | ||
| + | |||
| + | 2020.07.25 2020牛客暑期多校训练营（第五场） ''pro 5/6/11 rank 46/???'' | ||
| + | |||
| + | 2020.07.27 2020牛客暑期多校训练营（第六场） ''pro 7/8/11 rank 35/???'' | ||
| ===== Max.D. ===== | ===== Max.D. ===== | ||
| 行 14: | 行 19: | ||
| ==== 专题 ==== | ==== 专题 ==== | ||
| + | 经纬度求解两点球面距离 | ||
| + | |||
| + | [[.hardict:haversine_formula|Haversine formula]] | ||
| ==== 比赛 ==== | ==== 比赛 ==== | ||
| + | 自闭一场cf | ||
| ==== 题目 ==== | ==== 题目 ==== | ||
| + | |||
| + | CF917D Stranger Trees | ||
| + | |||
| + | 51nod 1363 最小公倍数之和 | ||
| ===== MountVoom ===== | ===== MountVoom ===== | ||
| 行 38: | 行 51: | ||
| ===== 龙鹏宇 Hardict ===== | ===== 龙鹏宇 Hardict ===== | ||
| + | 多补题，本地多测试 | ||
| ===== 肖思炀 MountVoom ===== | ===== 肖思炀 MountVoom ===== | ||
| 行 67: | 行 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 ===== | ||
| === 来源： === | === 来源： === | ||
| + | |||
| + | [[http://codeforces.com/contest/1383/problem/B | B. GameGame ]] | ||
| === 标签： === | === 标签： === | ||
| + | |||
| + | 博弈，贪心 | ||
| === 题意： === | === 题意： === | ||
| + | |||
| + | 给了n个正整数，两人轮流从中取数，最终取得的数异或起来大的人获胜，一样则平局，双方均采取最优策略，求比赛结果。 | ||
| === 题解： === | === 题解： === | ||
| + | |||
| + | 设n个数异或起来的答案为s，先手的答案为x，后手的答案为y。 | ||
| + | |||
| + | 那么平局当且仅当x=y即s=0。 | ||
| + | |||
| + | 当s=0时，考虑s最高位的1，设这一位为p，x和y在这一位一定是一个1和一个0，而更高位无论怎么选x和y一定是相等的，更低位无论怎么选不影响最终结果。 | ||
| + | |||
| + | 所以只需要考虑原数组的第p位的0和1的个数即可，而1的个数一定是奇数，设为m，想胜利的人需要拿到奇数个1。 | ||
| + | |||
| + | 首先，如果有且仅有m个1，且$(m+1)/2$为偶数时先手必败，因为先手只可能拿到偶数个1。 | ||
| + | |||
| + | 假设$(m+1)/2$是一个奇数，如$m = 5, (m + 1) / 2 = 3$，此时先手必胜，只要先手先拿走一个1，然后后手拿什么先手就拿什么，如果后手拿走了最后一个0，先手拿1即可把状态变为刚才说的先手必败的状态。 | ||
| + | |||
| + | 假设$(m+1)/2$是一个偶数，那么考虑0的个数，如果0的个数是奇数，那么先手必胜，因为先手可以先拿走一个0，接下来后手拿什么先手就拿什么，这样后手一定会拿到更多的1也就是偶数个1。如果0的个数是偶数，那么就成了刚才说的情况，不过变成了先手拿什么后手就拿什么，这样先手就一定会拿到更多的1，此时先手必败。 | ||
| === 评论： === | === 评论： === | ||
| + | |||
| + | 关键在于考虑到两个人的答案异或起来等于所有数异或起来，这样就只用考虑某一位的1和0而不用考虑所有位置，一下子简化了问题。 | ||
| + | |||
| + | 而比较大小的关键在于拿到的1的个数，所以进行相应的分类讨论。 | ||
2020-2021/teams/alchemist/weekly_digest_8.1596161556.txt.gz · 最后更改: 2020/07/31 10:12 由 mountvoom
