新手求高人指点今晚ABC F
  • 板块学术版
  • 楼主封禁用户
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/5/11 22:02
  • 上次更新2024/5/12 09:29:48
查看原帖
新手求高人指点今晚ABC F
639563
封禁用户楼主2024/5/11 22:02
// Problem: F - Tile Distance
// Contest: AtCoder - AtCoder Beginner Contest 353
// URL: https://atcoder.jp/contests/abc353/tasks/abc353_f
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define ll long long

bool large(ll bx, ll by) {
	return (bx + by) & 1;
}

// X-1,X+1,Y-1,Y+1

ll s_to_l(ll x, ll y, ll sz, int dir) {
	x %= sz, y %= sz;
	if (dir == 0) {
		return x + 1;
	} else if (dir == 1) {
		return sz - x;
	} else if (dir == 2) {
		return y + 1;
	} else {
		return sz - y;
	}
}

ll dis_l(ll bx1, ll by1, ll bx2, ll by2, ll sz) {
	if (sz == 1) {
		return abs(bx1 - bx2) + abs(by1 - by2);
	} else if (sz == 2) {
		ll ans = min(abs(bx1 - bx2), abs(by1 - by2)) * 2;
		ans += (max(abs(bx1 - bx2), abs(by1 - by2)) - min(abs(bx1 - bx2), abs(by1 - by2))) / 2 * 3;
		return ans;
	}
	return max(abs(bx1 - bx2), abs(by1 - by2)) * 2;
}

ll dx[] = {-1, 1, 0, 0};
ll dy[] = {0, 0, -1, 1};

int main() {
	ll sz;
	scanf("%lld", &sz);
	ll sx, sy, tx, ty;
	scanf("%lld %lld", &sx, &sy);
	scanf("%lld %lld", &tx, &ty);
	ll bsx = sx / sz, bsy = sy / sz, btx = tx / sz, bty = ty / sz;
	// Case 1: L vs L
	// Case 2: L vs S
	// Case 3: S vs S
	// Case 4: same L
	// Case 5: same S
	if (bsx == btx && bsy == bty) {
		// Case 4/5
		if (large(bsx, bsy)) {
			// Case 4
			cerr << 4;
			puts("0");
		} else {
			// Case 5
			cerr << 5;
			printf("%lld", abs(sx - tx) + abs(sy - ty));
		}
	} else {
		// Case 1/2/3
		if (large(bsx, bsy) && large(btx, bty)) {
			// Case 1
			cerr << 1;
			printf("%lld", dis_l(bsx, bsy, btx, bty, sz));
		} else if (!large(bsx, bsy) && !large(btx, bty)) {
			// Case 3
			cerr << 3;
			ll ans = 0x3f3f3f3f3f3f3f3fll;
			for (int i = 0; i < 4; i++) {
				for (int j = 0; j < 4; j++) {
					ans = min(ans, s_to_l(sx, sy, sz, i) + s_to_l(sx, sy, sz, j) + dis_l(bsx + dx[i], bsy + dy[i], btx + dx[j], bty + dy[j], sz));
				}
			}
			printf("%lld", ans);
		} else {
			// Case 2
			cerr << 2;
			if (!large(bsx, bsy)) {
				swap(bsx, btx);
				swap(bsy, bty);
				swap(sx, tx);
				swap(sy, ty);
			}
			ll ans = 0x3f3f3f3f3f3f3f3fll;
			for (int i = 0; i < 4; i++) {
				ans = min(ans, s_to_l(tx, ty, sz, i) + dis_l(bsx, bsy, btx + dx[i], bty + dy[i], sz));
			}
			printf("%lld", ans);
		}
	}
}

大致思路就是分成五类,第一类从L到L,第二类从L到S,第三类从S到S,第四类同在一个L内,第五类不需要经过L

2024/5/11 22:02
加载中...