526互联

Educational Codeforces Round 151 (Rated for Div. 2) B. Come Together

发布时间 2023-09-05 21:22:53作者: zsxuan

给三个点 \(A, B, C\) ，两个人一开始都在 \(A\) 点，一个人希望最快到达 \(B\) ，另一个人希望最快到达 \(C\) ，且他们希望尽可能走一条路径。则这条路径最长是多长。

经典的高维可以由低维叠加的问题。

  • 坐标问题
  • 动态规划问题

并非所有高维问题都可由低维叠加，但任何二维问题都可由一维叠加。因为不同维度基本是独立的。

典：拆维考虑时考虑边数而不考虑点数

  • 不同维度的点可能重复，而边不会
  • 每一个独立的问题都可以视为成另一维，比如二维数点应用

单独考虑水平方向和竖直方向，两条路径能覆盖的最长共同距离，然后相加。

一个维度上，两条路径的起点相同，终点不同时。

  • 两个终点在起点的同一侧，即 \(A - B \geq 0\ and\ A - C \geq 0\) 或 \(A - B \leq 0\ and\ A - C \leq 0\) ，重复路径的长度为 \(min(abs(A - B), abs(A - C))\) 。
  • 两个终点在起点的不同测，重复路径长度为 \(0\) 。

典：路径长度为路径中边的数量，\(v_{tot} = e_{tot} + 1\) 。

  • 覆盖节点个数为 \(len + 1\) 。
  • 多个维度覆盖节点个数为 \(lenx + leny + lenz + \cdots + 1\) 。
view 
#include <bits/stdc++.h>
void solve() {
	int xa, ya, xb, yb, xc, yc;
	std::cin >> xa >> ya >> xb >> yb >> xc >> yc;
	int lenx = 0, leny = 0;
	if ((xa - xb >= 0 && xa - xc >= 0) || (xa - xb <= 0 && xa - xc <= 0))
		lenx = std::min(abs(xa - xb), abs(xa - xc));
	else
		lenx = 0;
	if ((ya - yb >= 0 && ya - yc >= 0) || (ya - yb <= 0 && ya - yc <= 0))
		leny = std::min(abs(ya - yb), abs(ya - yc));
	else
		leny = 0;
	std::cout << lenx + leny + 1 << '\n';
}
signed main() {
	int _ = 1; std::cin >> _;
	while (_--) { solve(); }
	return 0;
}