Loading... ## A. 猴子摘桃 按题意倒推即可 答案：`22` ## B. 数学家 穷举-5000~5000内所有数字，需要进行1e12次枚举。 但是，容易想到，要让三个绝对值很大的数的三次方之和等于一个小数，这三个数必然不可能符号全相同。 因此，对于第一个数，只枚举-5000~0，第二个数只枚举0~5000，第三个数枚举-5000~5000，这样就将枚举次数缩小到了1/4. 一个更好的优化策略是先枚举第一，第二个数，计算它们的三次方之和，储存到map里，然后再枚举第三个数，将第三个数求立方后，在map里寻找有无和此数相加得到答案的，此时运算次数降到了$(5000 \times 5000)+10000 \times log(5000\times 5000) \approx 2.5e7 $ 答案：`-1972，-4126，4271` ## C. 死亡游戏 此题面原本来自于一道概率dp，但是比原来那道简单得多。只需要观察到，老虎必然是一对一对死亡，那么，奇数个老虎的情况下，最终必然会剩下一只老虎与人匹配上，因此人不可能活下来。 有能力的同学，可以思考一下，编写一个程序，计算老虎数量为偶数的情况下，人活到游戏结束的概率。 答案：`0.000000` ## D. 逆元问题 可以暴力求解，也可以用费马小定理求解，也可以用扩展gcd求解。 答案：`703240518` ## E. NP完全问题 本题的数据共有30个，完全暴力枚举，运算次数是$2^{30} \approx 1e9 $ ，考虑到大常数，这个解法很勉强。 正解的思想是折半，先枚举前15个物品取或不取，将它们存放进map里，再枚举后15个物品，在map中寻找相加能够得到所求答案的方案，运算次数是$ 2^{15}+2^{15}\times log(2^{15}) \approx 5e5 $ 本题保证答案唯一，因为数据是用背包密码算法体系的思想生成的，如上暴力求解答案的过程实际上就是暴力破解密码的过程，尝试将上述数据逐个求它们在模140737488355337意义下的逆元，看看能不能找到一些有趣的性质。 答案：`110010000011111110101001001001` ## F. 火星救援 经简单计算分析可知，题目叫我们求的是$s*(1+\frac{1}{2}+\cdots+\frac{1}{n})$。由于运算次数较多，后面的部分可以算预处理前缀和解决。 ## G. 龙龙的数字游戏 其实是一个简单的计数问题，只需要考虑每次新加一个数的贡献的即可。分三类情况讨论 - 加入$0$：乘积为$0$的区间个数加上当前总个数 - 加入正数/负数：乘积为$0$的区间个数加上上一个$0$及之前的部分。只需要统计上个$0$以后的区间后缀积的正负个数对应加上即可。 ## H. Liang The Mighty 由冗长的题面分析可知，题目需要求$n^2$的距离里求第$p\%$的距离。直接求解可以得到$50\%$的分数，使用`nth-element`将复杂度降到$O(n^2)$即可通过此题。 ## I. 传球游戏 不难注意到关系只有3个，一共只有8种可能。暴力枚举8个情况，计算出对应的方案数，和输入进行对比判定。 另解：$k=1$时特判，$k>=2$时取出每个人做两轮游戏后球回到自己手里的方案，这相当于该点的度数。据此可唯一确定一种连边方案，只做一次判定即可。 ## J. strawberrry and geometry 其实就是两个圆交一个简单多边形的面积并问题……![QQ图片20191123212849.jpg][1] [1]: http://xzm2001.cn/usr/uploads/2019/11/1794280847.jpg Last modification：November 23rd, 2019 at 09:29 pm © 允许规范转载 Support If you think my article is useful to you, please feel free to appreciate ×Close Appreciate the author Sweeping payments Pay by AliPay Pay by WeChat
