TKK-ICPC Round#6 题解

1、比大小

如果我们用 double 或 long double 对它们相除的结果进行比较,势必会出现精度问题导致返回错误的答案。

所以我们考虑比较 a * d 与 b * c 的大小关系。但是题目中给出的数据范围会造成两数相乘后的结果超过 long long 的最大限度。

正确做法是,先比较 a / b 和 c / d 的大小关系,也就是两个数的整数部分,如果整数部分不相等,那么我们会得到一个答案;如果整数部分相等,我们就让 a = a % b、c = c % d,如此以来我们就可以保证 a / b 和 c / d 是两个真分数,这样再去比较 a * d 与 b * c 的大小关系就可以得到答案了。


2、有本事就打表

这道题的做法有很多,这里我提供一种做法:

int i = 0, j = n >> 1, x = 0;
for (int k = 0; k < n * n; k++)
{
	a[i][j] = ++x;
	if (x % n == 0)
	{
		i = (i + 1) % n;
	}
	else
	{
		i = (i + 2) % n;
		j = (j + 1) % n;
	}
}

3、Count The Number

此题序列的长度和询问的次数都是1e5,如果我们每次都去查询一遍区间 [L,R] 内有多少元素等于 X 那必然会超时。

这里用到了前缀和的思想,我们先想这样一个问题:区间 [L,R] 内 X 的数量是不是等于区间 [1,R] 内 X 的数量减去区间 [1,L – 1] 内 X 的数量呢?如此一来,我们可以预处理一个二维数组,其中 a[i][j] 表示区间 [1,i] 中有 a[i][j] 个 j。

那么我们在每次查询的过程中,只需要输出 a[R][X] – a[L – 1][X] 就可以了。


4、计算面积

先把直线化成 Ax + By + C = 0 的标准式,然后利用点到直线距离公式计算出点 C 到直线 L 的距离,最后用海伦公式求解三角形的面积。


5、积木

签到题。按照题目要求做就可以,注意过程和结果都有可能会超过 int 的范围。


6、异或运算

此题主要运用异或性质来做:a ^ a = 0、0 ^ a = a。

我们可以先把所有数字异或起来得到一个结果保存到变量 sum 中。

题目要求删掉一个数字使得异或的结果最大,那么我们是不是可以用 sum 分别对每一个数字进行异或然后在它们之中找到一个最大值呢?