专栏文章

题解：P4876 [USACO14MAR] The Lazy Cow G

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

文章操作

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

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

The Lazy Cow G

平面上有若干点，要求在平面上任意地选出一个位置，使得到该点曼哈顿距离不超过 kk 的点的数量最多。
首先题目要求的是曼哈顿距离。如果把对于一个位置曼哈顿距离不超过 kk 的位置都标记出来，会发现是一个正方形旋转了 45∘45^\circ。而对于这个图形，正方形是容易处理的，而旋转 45∘45^\circ 不好操作，可以考虑将曼哈顿距离转换成切比雪夫距离，此处略微讲讲两距离及其转换。
曼哈顿距离：∣xi−xj∣+∣yi−yj∣|x_i-x_j|+|y_i-y_j|。
切比雪夫距离：max⁡{∣xi−xj∣,∣yi−yj∣}\max\{|x_i-x_j|, |y_i-y_j|\}。
可以发现，切比雪夫距离不超过 kk 的图形就是一个边与 xx 轴或 yy 轴分别平行的一个正方形。
而对于曼哈顿距离，∣xi−xj∣+∣yi−yj∣=max⁡{xi−xj,xj−xi}+max⁡{yi−yj,yj−yi}=max⁡{xi−xj+yi−yj,xi−xj+yj−yi,xj−xi+yi−yj,xj−xi+yj−yi}=max⁡{(xi+yi)−(xj+yj),(xi−yi)−(xj−yj),(xj−yj)−(xi−yi),(xj+yj)−(xi+yi)}=max⁡{∣(xi+yi)−(xj+yj)∣,∣(xi−yi)−(xj−yj)∣}|x_i-x_j|+|y_i-y_j|=\max\{x_i-x_j, x_j-x_i\}+\max\{y_i-y_j, y_j-y_i\}=\max\{x_i-x_j+y_i-y_j, x_i-x_j+y_j-y_i, x_j-x_i+y_i-y_j, x_j-x_i+y_j-y_i\}=\max\{(x_i+y_i)-(x_j+y_j), (x_i-y_i)-(x_j-y_j), (x_j-y_j)-(x_i-y_i), (x_j+y_j)-(x_i+y_i)\}=\max\{|(x_i+y_i)-(x_j+y_j)|,|(x_i-y_i)-(x_j-y_j)|\}，则令 xi′=xi+yi,yi′=xi−yix'_i=x_i+y_i, y'_i=x_i-y_i，则上式等于 max⁡{∣xi′−xj′∣,∣yi′−yj′∣}\max\{|x'_i-x'_j|, |y'_i-y'_j|\}。这样就完成了曼哈顿距离与切比雪夫距离的转换。
实际操作时，只需要先转换坐标，再按切比雪夫距离的求法做即可。
转换后，所求变为在平面上一个 2k×2k2k\times2k 的矩形最多能覆盖的点数，这个用扫描线解决即可。
Code
CPP
#include <iostream>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <bitset>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define fst first
#define scd second
#define db double
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector <int>
#define pii pair <int, int>
#define sz(x) ((int)x.size())
#define ms(f, x) memset(f, x, sizeof(f))
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
#define R(i, j, k) for (int i=(j); i>=(k); --i)
#define ACN(i, H_u) for (int i=H_u; i; i=E[i].nxt)
using namespace std;
template <typename INT> void rd(INT &res) {
	res=0; bool f=false; char ch=getchar();
	while (ch<'0'||ch>'9') f|=ch=='-', ch=getchar();
	while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
	res=(f?-res:res);
}
template <typename INT, typename...Args>
void rd(INT &x, Args &...y) { rd(x), rd(y...); }
//dfs
const int inf=0x3f3f3f3f;
const int maxn=1e5;
const int N=maxn+10;
int n, kv, d[N], dcnt;
//wmr
#define ls (p<<1)
#define rs (p<<1|1)
struct SegmentTree { int l, r; ll ma, add; } t[N<<2];
void pushdown(int p) {
	t[ls].ma+=t[p].add;
	t[rs].ma+=t[p].add;
	t[ls].add+=t[p].add;
	t[rs].add+=t[p].add;
	t[p].add=0;
}
void pushup(int p) { t[p].ma=max(t[ls].ma, t[rs].ma); }
void build(int p, int l, int r) {
	t[p]={l, r, 0, 0};
	if (l==r) return;
	int mid=l+r>>1;
	build(ls, l, mid); build(rs, mid+1, r);
}
void update(int p, int l, int r, int k) {
	if (l<=t[p].l&&t[p].r<=r) return t[p].ma+=k, t[p].add+=k, void();
	int mid=t[p].l+t[p].r>>1; pushdown(p);
	if (l<=mid) update(ls, l, r, k);
	if (mid<r) update(rs, l, r, k);
	pushup(p);
}
ll query(int p, int l, int r) {
	if (l<=t[p].l&&t[p].r<=r) return t[p].ma;
	int mid=t[p].l+t[p].r>>1; pushdown(p); ll res=0;
	if (l<=mid) res=max(res, query(ls, l, r));
	if (mid<r) res=max(res, query(rs, l, r));
	return res;
}
struct node {
	int x, y, v;
	bool operator < (const node &k) const { return x<=k.x||x==k.x&&y<k.y; }
} a[N];
//incra

//lottle
signed main() {
//	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	rd(n, kv); kv<<=1;
	L(i, 1, n) {
		int v, x, y; rd(v, x, y);
		a[i].x=x+y, a[i].y=x-y, a[i].v=v; d[i]=a[i].y;
	}
	sort(a+1, a+n+1); sort(d+1, d+n+1); dcnt=unique(d+1, d+n+1)-d-1;
	L(i, 1, n) a[i].y=lower_bound(d+1, d+dcnt+1, a[i].y)-d;
	a[n+1].x=inf; int lst=0, cur=0; ll ans=0;
	build(1, 1, dcnt);
	L(i, 1, n) if (a[i].x!=a[i+1].x) {
		while (cur<n&&a[cur+1].x-a[i].x<=kv) ++cur, update(1, lower_bound(d+1, d+dcnt+1, d[a[cur].y]-kv)-d, a[cur].y, a[cur].v);
		ans=max(ans, t[1].ma);
		L(j, lst+1, i) update(1, lower_bound(d+1, d+dcnt+1, d[a[j].y]-kv)-d, a[j].y, -a[j].v);
		lst=i;
	}
	printf("%lld\n", ans);
	return 0;
}
/*
input
4 3
7 8 6
3 0 0
4 6 0
1 4 2
output
8
*/

评论

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

正在加载评论...