【模考 5 - 2】总结

经验分享区
1

死亡回放

【8:30】开 T1，天哪是语法题！不过模拟有点复杂。
【8:45 - 9:00】写完代码，调啊调啊调啊，崩溃了（。
【9:01】看 T2。是个数论简单题，求 L 到 R 内有五个约数的数的个数。
【9:05】写好暴力代码，以便对拍。
【9:06 - 9:20】思考：是不是任何数（1 除外）的 4 次方都有五个约数呢？找了几个数试了一下，认为是对的。于是打了表存那些在数据范围以内的数字的 4 次方。
【9:20 - 9:27】对拍，发现是错的。比如 4^4 = 256，约数有 1,2,4,8,16,32,64,128,256。经过推导，发现只有指质数的 4 次方都有五个约数。
【9:28 - 9:45】T2 打好表，对拍过无误。
【9:46 - 10:10】调好了 T1，怎么连个语法题都调那么久啊！
【10:11- 10:40】开 T3，想到了正解是分治，但不会写。于是写了一个人类智慧：按坐标到原点的距离排序，然后乱搞……但是把自己 hack 了，所以打了个爆力。
【10:41 - 12:00】写 T4，看出来了是和单调栈有关，但是这个蒟蒻忘记单调栈怎么用了！打了一个 dfs 骗分。然后睡觉……

题解

T1 蛇形方阵
语法题，不讲了。

T2 魔法数
思路同“死亡回放”：

质数的 4 次方都有五个约数。

证明
根据约数个数定理，若正整数 n 的质因数分解为 n = p_1^{a_1} \cdot p_2^{a_2} \cdot \ldots \cdot p_k^{a_k}，则其约数个数为：

d(n) = (a_1 + 1)(a_2 + 1) \cdots (a_k + 1)

该定理表明，每个质因子的指数加 1 后相乘的结果即为约数总数。

设 p 为质数，则其四次方可表示为：

p^4 = p^4

此时，p^4 的质因数分解中仅包含一个质因子 p，且指数为 4。

根据约数个数定理，p^4 的约数个数为：

d(p^4) = (4 + 1) = 5

这是因为分解式中仅有一个质因子 p，且其指数为 4。

p^4 的所有约数可表示为 p^0, p^1, p^2, p^3, p^4，即：

1, \ p, \ p^2, \ p^3, \ p^4

Code 不放了。

T3 最小点对

  1. 人类智慧

我们充分发扬人类智慧：
将所有点全部绕原点旋转同一个角度，然后按 x 坐标排序
根据数学直觉，在随机旋转后，答案中的两个点在数组中肯定不会离得太远
所以我们只取每个点向后的 5 个点来计算答案
这样速度快得飞起，在 n=1000000 时都可以在 1 s 内卡过

当然，这是错的。

  1. 正解

首先这是一道分治题，用归并排序的思想，先把这些点按横坐标从左到右排一遍，再把这些点从中间开始左右分成两段的，再把左边一段和右边一段都分成两端。这样一直分下去，直到一段的点数只有一个或两个， 两个点返回这两个点的距离。

一个点怎么办啊？。返回无穷大！

因为一个点没有距离， 然后再比较左右两段的最小距离取更小的.

万一这两个距离最近的点不在同一段咋搞？
假设有 a,b,c,d 这四个点，距离最近的是 b,c 两点， 第一次分完时是这样的:

a,b|c,d

刚好隔开了 b 和 c 。

所以我们要增加一步，在左段的点和右段的点的距离是否小于目前最短距离。

但我们发现：如果左段的点和右段的点距离比目前距离最短的两个点的距离还要短时，这两个点横坐标离左右两段和起来的这一大段的最中间的点的横坐标的距离一定要小于目前的最短距离。

Code

double min_dis(int L, int R) {
	if (L == R)
		return 0x3f3f3f3f;
	if (R - L == 1)
		return dis(a[L], a[R]);

	int mid = (L + R) / 2;
	double d1 = min_dis(L, mid - 1);
	double d2 = min_dis(mid, R);
	double d0 = min(d1, d2);

	vector<Node> v;

	for (int i = L; i <= R; i++) {
		if (fabs(a[i].x - a[mid].x) <= d0) {
			v.push_back(a[i]);
		}
	}

	sort(v.begin(), v.end(), cmp2);
	int len = v.size();
	for (int i = 0; i < len; i++) {
		for (int j = i + 1; j < len && v[j].y - v[i].y <= d0; j++) {
			d0 = min(d0, dis(v[i], v[j]));
		}
	}

	return d0;
}

T4 打怪兽
​可以考虑每次向左或右一直走，走到能增加能力值的位置。可以预处理出每个点向左或右走第一次和为正数的位置，可以使用 前缀合+单调栈 求解。那么我们就可以维护最远可到达的区间，每次向外扩都保证和增加。在扩到下一个端点时查询这过程中和的最小值判断是否合法，这部分可以使用 st 表查询一个区间最值。

Code

int Lm = m, Rm = m;
	ll now = 0;
	
	bool flag = 0;
	
	while (Lm && Rm != n + 1) {
		bool f1 = 0, f2 = 0;
		while (Lm && now + sum[Lm] - getmax(L[Lm]-1, Lm - 1) >= 0) {
			f1 = 1;
			now += sum[Lm] - sum[L[Lm] - 1];
			Lm = L[Lm] - 1;
		}
		
		while (Rm != n + 1 && now + getmin(Rm, R[Rm]) - sum[Rm - 1] >= 0) {
			if (Lm < m && !flag) flag = true, now -= a[m];
			f2 = 1;
			now += sum[R[Rm]] - sum[Rm - 1];
			Rm = R[Rm] + 1;
		}
		
		if (!f1 && !f2) {
			cout << "NO\n";
			return ;
		}
	}
	cout << "YES\n";

点个赞嘛 /kel

8 个赞
2

点个赞再走啊

1 个赞
3

写 完 了