2015-2016 Petrozavodsk Winter Training Camp, SPb SU SPb AU Contest

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;
		}
	}
}