====== 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. ===== ==== 专题 ==== 本周暂无 ==== 比赛 ==== 主要是两场CF，一场涨了一场跌了，基本等于没打（苍天啊） ==== 题目 ==== ===== Hardict ===== ==== 专题 ==== 经纬度求解两点球面距离 [[.hardict:haversine_formula|Haversine formula]] ==== 比赛 ==== 自闭一场cf ==== 题目 ==== CF917D Stranger Trees 51nod 1363 最小公倍数之和 ===== MountVoom ===== ==== 专题 ==== 无 ==== 比赛 ==== 因为没有cf div.1，所以一直在慢慢补cf的和牛客的题。 ==== 题目 ==== 无 ====== 个人总结 ====== ===== 陈铭煊 Max.D. ===== 要多加强思维训练 ===== 龙鹏宇 Hardict ===== 多补题，本地多测试 ===== 肖思炀 MountVoom ===== 感觉还行，补题应该再积极一点。 ====== 本周推荐 ====== ===== 陈铭煊 Max.D. ===== === 来源： === [[https://codeforces.com/contest/1388/problem/C|Codeforces 660（Div.2）C . Uncle Bogdan and Country Happiness]] 发现自己CF面对不熟悉的问题，思维总是很慢，写下这道题主要是给自己引以为戒的。这周开始尽量多vp，提高自己的思维能力。 === 标签： === 思维，树的遍历 === 题意： === 给你$n$个城市和$n-1$条道路，城市$i$生活了$p_i$个人，他们都工作在城市$1$，工作结束要返回各自城市，每个人回家时有的有好心情，有的有坏心情，经过一条边时，某些好心情的人会变成坏心情。定义一个城市的开心指数$h_i$为经过（或者到达）的好心情的人的数量减去坏心情的人的数量。出所有$h_i,p_i$，询问是否存在这样的可能情况。$1\le t\le 10000,1\le n\le 10^5,1\le m=\sum p_i\le 10^9,-10^9\le h^i\le 10^9, \sum n\le 2*10^5$。 === 题解： === 用一个子树中$p_i$的和，以及$h_i$，可以求出经过$i$的开心的人数和不开心的人数，当然这个人数要在$[0,p_i]$中。这是第一个条件。由于开心的人数递减，所以所有儿子的开心人数之和不会多于父亲。这是第二个条件。 === 评论： === 当时赛场上莫名奇妙想了一些多余的条件，比如儿子的$h$之和不超过子树中$p$之和$-p_i$，这个显然是很多余的，因为第一个条件满足这个肯定满足。第二个条件当时一直在想不开心人数，居然没有稍微反着一点。这种题目写了一个小时，我也是很自闭。 ===== 龙鹏宇 Hardict ===== === 来源： === [[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 ===== === 来源： === [[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的个数，所以进行相应的分类讨论。