Contest Info

date: 2017.10.09 15:50-20:50

practice link

Solutions

A. Random Points on the Circle

题目大意：在一个圆上有 \(n\) 个点，每个点的坐标在 \([0,L)\) 之间（ \(L\) 是圆的周长），定义两个点之间的距离为 \(\min(|a-b|,L-|a-b|)\) 。现在要在圆上建 \(k\) 个收集器，每个点必须被分配到且只分配到一个收集器，定义一个收集器的花费为分配给它的所有点到它的距离之和，求所有收集器中最大的花费的最小值。

题解：显然二分答案，考虑如何验证。先对所有点进行排序，并且把它们向右扩展一倍。容易知道，要达到最优值，分配给每个收集器的一定是一个区间。而每个点都要被分配到一个收集器，所以这些区间实际上形成了一个划分。对于一个区间，最优的设立收集器的位置显然是这个区间的中位数，通过预处理前缀和我们可以 \(\mathcal{O}(1)\) 知道每个区间的花费。

之后我们可以通过 two pointers 的方法，求得从每一个点开始，通过不超过当前二分的花费，能到达的最右的位置 \(r_i\) 。再枚举 \([1,r_1]\)中的每个点作为开始，贪心（每次走最远）判断一下是否能在 \(k\) 个收集器以内处理完所有点。如果答案为从 \([1,r_1]\) 之外的点开始，那么最后一定在 \([1,r_1]\) 中结束，否则开始和结束的点区间花费不满足要求，所以我们只需要枚举一个区间即可。时间复杂度不好证明，虽然看起来每次验证是 \(r_i\times k\) ，但是实际上这个复杂度没法达到。

tips：参考了一些别人的代码发现了一个优化，我们不在 \([1,r_1]\) 中验证，而是去找到使得 \(r_i-i\) 最小的 \(i\) 。然后枚举 \([i, r_i]\) 中的点进行验证，这样每次我们至少跳 \(r_i-i\) 的距离，复杂度为 \(\mathcal{O}((r_i-i)\cdot \frac{n}{r_i-i})=\mathcal{O}(n)\) 。最后总复杂度为 \(\mathcal{O}(n\log n)\) 。

B. Lines

题目大意：给你平面上互不相同的 \(n\) 的点，让你求出它们连成的 \({n\choose2}\) 条直线的倾斜角的中位数。

题解：二分答案，考虑验证。我们对所有点按照先 \(y\) 后 \(x\) 的顺序排序，只考虑从小的点连到大的点。设当前二分出的倾斜角为 \(\alpha\) ，为了验证答案我们需要知道倾斜角小于等于 \(\alpha\) 的直线有多少条，即 \(\displaystyle{\frac{x_{j}-x_{i}}{y_{j}-y_{i}}\ge\cot\alpha}\) ，即 \(x_{j}-y_{j}\cot\alpha\ge x_{i}-y_{i}\cot\alpha\) ，这样就转化为求顺序对的问题了。复杂度 \(\mathcal{O}(kn\log n)\) 。

tips：还可以使用对偶的方法来做。如果将点 \((a,b)\) 对偶到直线 \(y=ax+b\) ，很容易验证，两点连线的斜率等于它们对偶直线的交点的横坐标的相反数。于是验证就变成了计算 \((-\infty,x_{0}]\) （\(x_0=-\alpha\) ）中间有多少个直线交点，类似于扫描线求线段交点的思想，我们只需要统计 \(x=x_{0}\) 与所有直线的交点相对于 \(x=-\infty\) 与所有直线交点的逆序对数即可。

C. Fraction Factory

题目大意：给你一个分数 \(\displaystyle{\frac{a_{1}\cdots a_{n}}{b_{1}\cdots b_{m}}}\) ，要求你先将它约分，再求分子乘上分母关于 \(k\) 的逆元。所有输入数据小于等于 \(10^{18}\) ，有 \(50\) 组数据。

题解：

法一：我们约分时只需要将分子和 \(k\) 的 gcd，以及分母和 \(k\) 的 gcd 约分即可。剩余部分与 \(k\) 互质，我们可以暴力用逆元直接计算，需要约分的部分会被抵消。我们考虑对 \(k\) 因数分解，然后求出分子分母含每个因子的个数。由于 \(k\) 很大，所以我们要用到 Pollard-Rho 算法，但是这样的计算量还是太大，会导致 MLE ，所以我们可以先将 \(100000\) 以内的质数筛出来，把它们从 \(k\) 中去掉，再对它应用 Pollard-Rho 算法 ，就可通过本题了。由于 cf 不支持 __int128 ，所以我们需要手写 long long 的取模。期望复杂度 \(\mathcal{O}(50\times18\times\sqrt[4]{10^{18}})\) 。

法二：

H. Points

题目大意： 给你 \(n\) 个三维空间中的向量，要求从中选取 \(k\) 个，让这些向量的和的模最大。

题解：标程是 \(\mathcal{O}(n^{5})\) 的确定算法，不太明白它的正确性。还有一种随机算法，每次对所有向量 random_shuffle 一下，然后先将前 \(k\) 个作为当前选取的向量，枚举所有的 \((i,j)\) 对，如果 \(i\) 已经选取，而 \(j\) 未被选取，就看看去掉 \(i\) ，加上 \(j\) 能否让答案更优，如果更优就做这一改变。枚举完后再记录一下当前的最优值，并从头反复执行这一算法。

J. Sort It!

签到题

L. Triangle

题目大意：给你 \(n\) 条长度在 \(1,2,\cdots,C\) 中的边，两两长度不同。问你用这些边能组合出的合法三角形中最小的面积。

题解：我们设三条边为 \(a,b,c\) ，且有 \(a<b<c\) 。假设我们已经知道了 \(c-b\) 的值，容易通过海伦公式证明，\(b,c\) 固定时， \(a\) 越小，面积越小； \(a\) 固定时， \(b,c\) 越小，面积越小。也就是说，我们只需要对每个 \(c-b\) 的值，去寻找最小的 \(a,b,c\) 即可。由于两边之差小于第三边，即 \(a>c-b\) ，所以寻找 \(a\) 可以用 two pointer 在 \(\mathcal{O}(n)\) 中完成。对于最小的 \(b,c\) ，首先我们可以用 bitset 找出所有满足 \(c-b=\text{dif}\) 的 \(b,c\) ，然后再从 bitset 中寻找最小的 \(b,c\) 就可以了。复杂度 \(\mathcal{O}(\frac{C^{2}}{64})\) 。

coldwater’s comment

用 unsigned 类型指针访问 bitset 的黑科技：

int now = 1;
double ans = INF;
for (int dif = 1, sz = c + 2 >> 1; dif <= sz; ++ dif){ 
	while (now <= c && (now <= dif || !set.test(now))){
		++ now;
	}
	if (now > c) break;
	std::bitset <M> x = set >> dif & set;
	bool flag = false;
	for (int i = now + 1, sz = (now >> 5) + 1 << 5; i < sz; ++ i){
		if (x.test(i)){
			ans = std::min(ans, calc(now, i, i + dif));
			flag = true;
			break;
		}
	}
	if (flag) continue;
	unsigned *p = (unsigned *) &x;
	for (int i = (now >> 5) + 1, sz = (c >> 5) + 1; i <= sz; ++ i){
		if (*(p + i)){
			for (int j = 0; j < 32; ++ j){
				if (x.test(i << 5 | j)){
					ans = std::min(ans, calc(now, i << 5 | j, (i << 5 | j) + dif));
					break;
				}
			}
			break;
		}
	}
}