专栏文章

2025-06-28-sol

LLyccriusRecoil
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mip0zknh
此快照首次捕获于
2025/12/03 04:23
3 个月前
此快照最后确认于
2025/12/03 04:23
3 个月前
查看原文

A 植树节

30pts

ai,bi,n≤103a_i, b_i, n \le 10^3
直接使用数组模拟每棵树苗的浇水次数，每次浇水在浇水区间内循环修改。
时间复杂度 O(n2)\mathcal O(n^2)。

40pts

ai=bia_i = b_i
每次浇水区间长度为一，同样直接数组模拟即可，代码与上面相同。

50pts

ai=1,bi=103a_i = 1, b_i = 10^3
每次浇水区间左右端点完全相同，故 1∼1031 \sim 10^3 的树苗浇水次数完全相同，只记录一次即可。

100pts

注意到区间修改单点查询，且先修改后查询，使用差分维护序列即可。
时间复杂度 O(n)\mathcal O(n)。
CPP
#include <iostream>
#include <algorithm>

const int maxN = 1e5;
const int maxA = 1e6;

int n;
int l = maxA, r = 1;
int a[maxN + 10], b[maxN + 10];
int c[maxA + 10], s[maxA + 10];
int ans;

int main() {
	std::cin >> n;
	for (int i = 1; i <= n; i++) {
		std::cin >> a[i] >> b[i];
		l = std::min(l, a[i]);
		r = std::max(r, b[i]);
		c[a[i]] += 1;
		c[b[i] + 1] -= 1;
	}
	for (int i = l; i <= r; i++) {
		s[i] = s[i - 1] + c[i];
		ans = std::max(ans, s[i]); 
	}
	std::cout << ans << std::endl;
	return 0; 
}

B 宴会

30pts

n≤100,0≤xi,ti≤1000n \le 100, 0 \le x_i, t_i \le 1000
注意到数据范围非常小，直接上暴力。
在 0∼10000 \sim 1000 上枚举每一个 x0x_0，每次统计所有人到大宴会的时间的最大值座位宴会开始时间，取宴会开始时间最小的 x0x_0 作为答案。
时间复杂度 O(nx)\mathcal O(nx)。

100pts

保证所有测试数据的 nn 加起来不超过 2×1052 \times 10^5。
数据范围提示时间复杂度为 O(n)\mathcal O(n)。
为了更加直观清晰，首先将答案进行一个数学上的形式化表示，即找到一个 x0x_0，使得 max⁡(∣xi−x0∣+ti)\max(\lvert x_i - x_0 \rvert + t_i) 最小。
  • 当 xi<x0x_i \lt x_0 时，∣xi−x0∣+ti=−xi+x0+ti=x0−(xi−ti)=∣x0−(xi−ti)∣\lvert x_i - x_0 \rvert + t_i = - x_i + x_0 + t_i = x_0 - (x_i - t_i) = \lvert x_0 - (x_i - t_i) \rvert，即 x0x_0 到 xi−tix_i - t_i 的距离；
  • 当 xi>x0x_i \gt x_0 时，∣xi−x0∣+ti=xi−x0+ti=(xi+ti)−x0=∣x0−(xi+ti)∣\lvert x_i - x_0 \rvert + t_i = x_i - x_0 + t_i = (x_i + t_i) - x_0 = \lvert x_0 - (x_i + t_i) \rvert，即 x0x_0 到 xi+tix_i + t_i 的距离。
到这里 xix_i 本身已经对答案不产生影响了，只考虑 xi−tix_i - t_i 及 xi+tix_i + t_i 即可。
由于我们只需要考虑 x0x_0 到这些 xi−tix_i - t_i 及 xi+tix_i + t_i 的最大值，那么我们只需要考虑最小的 xi−tix_i - t_i 及最大的 xi+tix_i + t_i 即可。
要让 x0x_0 到最小的 xi−tix_i - t_i 及 最大的 xi+tix_i + t_i 的距离的最大值最小，显然应当最小的 xi−tix_i - t_i 及最大的 xi+tix_i + t_i 的中点作为 x0x_0。
答案即 min⁡{xi−ti}+max⁡{xi+ti}2\frac{\min \{ x_i - t_i \} + \max \{ x_i + t_i \} }{2}，时间复杂度 O(n)\mathcal O(n)。
CPP
#include <iostream>
#include <iomanip> 
#include <algorithm>
#include <cstdio>
#include <cmath>

const int maxN = 1e5;
const int maxX = 1e8;

int T;
int n;
int x[maxN + 10];
int t[maxN + 10];
int l, r;

void init() {
	l = maxX;
	r = 0;
	return;
}

void mian() {
	std::cin >> n;
	for (int i = 1; i <= n; i++) std::cin >> x[i];
	for (int i = 1; i <= n; i++) std::cin >> t[i];
	for (int i = 1; i <= n; i++) l = std::min(l, x[i] - t[i]);
	for (int i = 1; i <= n; i++) r = std::max(r, x[i] + t[i]);
	if ((l + r) % 2) {
		std::cout << std::fixed << std::setprecision(1) << (1.0 * l + r) / 2 << std::endl; 
	} else {
		std::cout << (l + r) / 2 << std::endl;
	}
	return;
}

int main() {
	std::cin >> T;
	while (T--) init(), mian();
	return 0;
}

其他做法

二分法

三分法

调整法

C 部署

CPP
#include <iostream>

const int maxN = 1e6;
const int maxM = 1e6;
const int maxQ = 1e6;
const int maxA = 1e9;
const int maxX = maxN;
const int maxY = 10;

int n, m, q;
int a[maxN + 10];
int p, x, y;

namespace graph {
	struct Vertex {
		int val;
		int tag1;
		int tag2;
		int head;
	} vertex[maxN + 10];
	
	struct Edge {
		int head;
		int next;
	} edge[2 * maxN + 10];
	
	int ecnt;
	
	void addEdge(int tail, int head) {
		ecnt++;
		edge[ecnt].head = head;
		edge[ecnt].next = vertex[tail].head;
		vertex[tail].head = ecnt;
		return;
	}
	
	void pushDown1(int u, int from) {
		for (int e = vertex[u].head; e; e = edge[e].next) {
			int v = edge[e].head;
			if (v == from) continue;
			vertex[v].val += vertex[u].tag1; 
			vertex[v].tag1 += vertex[u].tag1;
		}
		vertex[u].tag1 = 0;
		return;
	}
	
	void pushDown2(int u, int from) {
		for (int e = vertex[u].head; e; e = edge[e].next) {
			int v = edge[e].head;
			vertex[v].val += vertex[u].tag2;
		}
		return;
	}
	
	void DFS(int u, int from) {
		pushDown1(u, from);
		pushDown2(u, from);
		for (int e = vertex[u].head; e; e = edge[e].next) {
			int v = edge[e].head;
			if (v == from) continue;
			DFS(v, u);
		}
		return;
	}
}

int main() {
	std::cin >> n;
	for (int i = 1; i <= n; i++) std::cin >> a[i], graph::vertex[i].val = a[i];
	for (int i = 1; i <= n - 1; i++) std::cin >> x >> y, graph::addEdge(x, y), graph::addEdge(y, x);
	std::cin >> m;
	for (int i = 1; i <= m; i++) {
		std::cin >> p >> x >> y;
		if (p == 1) graph::vertex[x].tag1 += y, graph::vertex[x].val += y;
		if (p == 2) graph::vertex[x].tag2 += y, graph::vertex[x].val += y;
	}
	graph::DFS(1, 0);
	std::cin >> q;
	for (int i = 1; i <= q; i++) {
		std::cin >> x;
		std::cout << graph::vertex[x].val << std::endl;
	}
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...