每周总结(2020/03/12~2020/03/18)

2020/03/12：NC54148 货物收集 (https://ac.nowcoder.com/acm/problem/54148)

对于最终的答案有一个特定的取值范围时，可以考虑二分法进行求解。
而关于二分法，对于每一个二分值，都会进行一次结果的遍历。
那么对于一些题，要想求的结果，只能（或者也可以说可以）一个一个的数进行遍历，从而求的结果的题目，可以考虑二分法进行求解。

2020/03/13：牛能和小镇(https://ac.nowcoder.com/acm/contest/4743/B)

占有相当比例的题是关于数学的，而且一部分是只与数学有关。
初始时，看到这道题以为最小生成树的问题，但是这种没有明确的给出一共有多少条路径可供选择，而是说任意两镇子之间都可以修路，路径数就是(n-1)*n/2,而这里的n最大可以取值1e5，那么最小生成树的两种解法：Prim（以点为研究对象）、Kruskal(以边为研究对象)都是非常的耗时，会明显地出现时间超限的情况。
而这道题相当于每一个镇子都有一个数值，而两个镇子之间修路所需的花费等于这两个值差的绝对值。那么根据数学思维的计算，最中的结果就是让这些数值的最大值减去最小值就是最终的结果。
所以，要搞好算法，数学是必不可少的(⊙﹏⊙)。

2020/03/14：取石子游戏(https://ac.nowcoder.com/acm/contest/4743/D)

也是一个数学的推导规律的题目。

2020/03/15：蚯蚓(https://ac.nowcoder.com/acm/contest/3888/F)

如果使用优先队列来计算，也是会超时，只不过没有牛能和小镇那道题用最小生成树超时的多而已。深度研究这道题就会发现蚯蚓被切成两段，可以将每次所切的两段分成两类（px,x-px），对于每一类后分配到这一类的一定比早分配这一类的蚯蚓长度较小，而这就是一个数学规律，根据数学规律就可以求解这道题。而这个规律可以优化的算法就是每次求最长的蚯蚓时所花费的时间少，优先队列每次时间是O(log(n+m)),而优化后的就是每次比较三个数组最新前面的元素就好，时间复杂度是O(1)。

2020/03/16:石子搬运(https://ac.nowcoder.com/acm/contest/4743/E)

这道题每次修改一个值，应当优先考虑线段树，而这道题的线段树是与dp相结合的，因为初始化的时候，要想求出结果只能使用dp进行遍历动态规划。但是之后每次修改只需要更改一条路径上的dp就好。

2020/03/17：组合数问题(https://ac.nowcoder.com/acm/contest/3888/A)

对于这道题，每次需要输入多组(t)测试用例，而t最大可以取到1e4,那么对于这种问题，首先应当考虑预处理方法。考虑使用预处理之后，剩下的就是怎么预处理。
如果对C(i,j)单纯的使用组合原理进行求解得数，不管你如何优化，最终的结果是一定的，而且这个最大数的结果是超出基本数据类型的取值范围。
那么再看看这道题是让求组合数结果是否是k的倍数，那么就是关于取模的问题。但是组合数不是全排列，朴素计算方法是分子多个数相乘，分母是多个数想乘，分子除以分母，这里涉及到了除法得的取模，而除法的取模与乘法、加法、减法的取模不相同。
解决方法就是C(i,j)=C(i-1,j)+C(i-1,j-1),这就变成了加法的取模。