AtCoder Grand Contest 001E – BBQ Hard 题解

主要思路

也是比较巧妙的一个转换思想。

我们考虑列式:

\[ \sum_{i = 1}^n \sum_{j = i + 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} \]

直接去算或者是按贡献计算都不行,我们考虑转换成这样:

\[ \frac{ \sum_{i = 1}^n \sum_{j = 1}^n {a_i + b_i + a_j + b_j \choose a_i + b_i} – \sum_{i = 1}^n {2(a_i + b_i) \choose a_i + b_i} }{2} \]

前面那个部分我们可以把点\((-a_i, -b_i)\)放在平面上,然后算一个路径计数的 DP 即可(因为平面大小比较小)。前半部分就是所有第三象限的点走到\((x_i, y_i)\)的路径总数,后半部分直接暴力算即可。

继续阅读AtCoder Grand Contest 001E – BBQ Hard 题解

[Fortuna OJ]4605 – 排序 sort 题解

主要思路

这道题好有意思啊,提醒我在任何时候都要想到这种阈值+\(0/1\)转化的方式。

我们可以先二分出\(c\)位置的值,然后令所有大于等于\(c\)的值变成\(1\),小于的则变成\(0\)。然后排序的时候发现,其实就是重新组织零一的位置,所以用线段树区间修改就可以搞定了。最后判断\(c\)位是否为\(0/1\)决定要不要继续二分。

继续阅读[Fortuna OJ]4605 – 排序 sort 题解

P2564:[SCOI2009]生日礼物题解

解法

假的单调队列哦。

考虑将每个类别元素的下标记好,然后先把每个类别标号最小的放入 multiset,然后对答案进行更新:每次取出最大和最小值做差更新,然后把最小值的下标更新后重新扔进 multiset 中。如果 multiset 中所有的类别都已经枚举完毕,那么直接跳出循环进行输出即可。

继续阅读P2564:[SCOI2009]生日礼物题解

Miller-Rabin & Pollard-Rho 算法笔记

Miller-Rabin 素数测试

首先,强烈推荐阅读这篇文章。(看懂了就不用来了)

Miller-Robin 算法包括两个部分,一个是费马测试,还有一个就是二次探测。这两个东西听上去非常的玄学(的确也是),我来讲清楚,并附上代码。我们现在要进行测试的数是\(p\)。

继续阅读Miller-Rabin & Pollard-Rho 算法笔记