训练指南——数学专题一的总结

怼烎@ 2022-08-09 13:46 151阅读 0赞

差不多一个星期过去了，在这一个多星期里，我做了一个数学专题和两场训练赛，要说对自己的感觉，只能说很差劲，开始的时候以为环境会比现在宽松很多，后来才发现想法是错误的，实验室室里室一种紧张的气氛，感觉就像稍微不努力就会，就会被落在后面，确实，在这种紧张的氛围之下，收获会不少，当然也暴漏了许多大大小小的问题，这是以前所没有预料到的！

回顾专题一，发现大概约有一小半的的题目是来自于刘汝佳——训练指南的课后题，不过又一大部分都是所谓的水题，因为稍微推导，便就可以得出答案，比如A题的GCD和LCM，只要g能被l整除，那么就输出g和l，否则的话就是\-1，因为如果要想使得a最小，那么a/g就最小，也就是1，所以互质的a，b就都等于1，那么最小值a也就是g不能被l整除构不成公约数。有了这些推论，代码只是三两行，如果要按照模拟的思路硬做，复杂度可想而知！

水题如：

**Square Numbers****（求区间内的平方数）**

**Box of Bricks****（贪心法，求平均值即可，其实没有最小值）**

**Teams****;****我比较喜欢的组合数学的题目用发现其实是n/2\*（2^(n-1)）,一开始还觉得会难一些，高估题目了，注意的是要用二分幂（以前不常用的东西，发现也不过如此），直接求不知道会不会T;**

**LCM Cardinality****：一开始就想到了朴素的算法，苦思悯想很久（大概一晚上），是在没有想到更好的办法那就直接用朴素算法吧（找出所有约数，然后暴力搜素）竟然,过了！**

**Traffic Volume** **：****不折不扣的水题开始看有图，以为会很难，求一个速度和车流量，实际上车速就等于根号下2倍的l\*f，我是通过微积分的方法来推导的（高数不是白学的啊）！然后流量什么的全都是浮云了，全是公式！**

**Polynomial Remains** **:****开始被长题目和公式吓到了，仔细阅读，发现也是水题之一，根据他的提示，直接往下除即可，这样f\[i-k\]-=f\[i\];  一直到最后，输出不是0的数即可！**

** **

**需要一点思考的如：**

Minimum Sum LCM：求其约数的最大值，开始没有想到好的方法，实际上把约数都找出来暴力扫一下即可

I**Integer Game****：刘汝佳把他归类成博弈论的题目，只要稍微动动脑子，判断串中的3，6，9个数即可，然后奇数和偶数对应了不同的情况！讨论即可)** ** **

**How do you add?****（卡了很久的一道题，不知道为什么一直不过，开始想到了组合数学的方法，就是所谓的隔板插空法，但是无奈因为0可以重复，这种方法最终放弃，能想到隔板插空法，为自己赞一个，尽管这种方法行不通。最后和P商量，发现他直接打表，于是也打表，过之。）**

**Add Again****：同样是卡了很久的题目，需要一点点推导得到s\*（n-1）！/(各个数出现次数的阶乘) 一直卡在后面式子的推导上，wa了很多次。**

**Benefit;** **因为自己的一些原因（竟然胡思乱想到了拓展欧几里得方程，不过不是正解），在这道题上同样wa了很多次，后来还T了几遍，最终经过学长提醒，原来不断求其最大公约数的因子，一直求到互质即可，这时B也就找了出来！**

**Hardly Hard** **：****稍微经过推理便可以得出要求的四边形为一个矩形，而且45方向上的直线是其平分线，没什么好说的，实际上题目的关键在于推公式的过程！**

** **

**需要推理的题目：**

**Watching Watches****：****这道题就需要一点推理了，根据两个表的时间差推出重合后的天数，然后根据重合后的天数计算出具体时间，要注意计算时间的四舍五入！**

**Back to Intermediate Math** **就像题目中说的那样，真的是“纯数学”题，其实就是高中时学矢量时老师经常讲的小船过河问题，就是让求小船过河的时间差，船速小于水速的话有一种情况是过不去的，其余的一个就是高中的两个公式！**

**Coco Monkey** **在这道题之前，就已经看了他的另个相反的题目，这个题目在以前讲递归的时候老师提到过，不过此处如果使用递归恐怕会超时或爆栈！这道题的思路也是不断地枚举s\*（s-1）的倍数，直到枚举到超过其右限，找出得到的个数即可！**

**Again Prime? No Time.****同样是卡了很久的题目，一开始是考虑到求n的阶乘里有多少m让每个数都除以m，得到个数，后来发现这种是有缺陷的，经过修改，只要找到最小的那个配对数即可！注意分解质因数的处理！**

** ****Coconuts, Revisited** **：****coco monkey****的反向问题，同样反过来枚举人数即可，和coco 解法一样！**

**Leading and Trailing** **：****后三位一眼就知道用同余摸定理，问题的关键在于如何求前三位，一番苦思冥想，想到了用double让乘方的数一直缩小，到最后保留前三位小数即可！**

**The Super Powers** **:****开始想到用素数的合数次方，然后打表排序，后来才知道是所有数的合数次方，最后去重排序，wa了很多次，也T了很多次，最后经学长提醒，找到问题的关键：求二重循环幂的范围ceil\*log（2）/log（i）即可！**

**Educational Journey****：****重要的也是推公式，两个分析的时候可以不考虑其他的！**

** **

**   ** **大概地把题目回顾了一下，没有做到面面俱到，当然慢慢的成长过程中会越来越全面吧！通过这些题感觉自己有很大的提升，比如在做题的时候能够很好的发散思维，不过容易在错误的方向上走的太远而浪费时间，还有缺点是太依赖于学长和资料，问题想不到就去问学长查资料，不容易形成自己的思维****。**