自动搬运

查看原文

来自洛谷，原作者为

	KingPowers 重开了

搬运于2025-08-24 23:18:03，当前版本为作者最后更新于2025-06-13 15:51:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

直接的想法是考虑二分，每次把当前矩形横着切成两半，尝试问出来终点实在上半部分还是下半部分，然后递归过去，这样每次能把问题规模减半。考虑如何判断终点是否在一个矩形区域内，发现只需要把矩形的边界和边界外的一圈问出来（如果某个方向的边界就是整个网格图的边界则不用处理），根据方向统计一下进出这个矩形的次数即可。

于是就有了这么一个策略，设 $solve(l,r)$ 表示当前已经确定了终点在第 $[l,r]$ 行内，每次把当前位置移动到 $mid$ 行然后把第 $mid,mid+1$ 行全部经过一遍，然后就可以按照上面的策略判断上半或下半矩形是否合法了。这样看上去总共需要走 $O(n\log n)$ 步，但是发现每层二分的步数都在 $4n$ 步左右，常数太大了所以无法通过。

发现上面的策略步数太大的原因是我们每次都横着切而且要扫两行，所以有个优化方向是考虑同时加入竖切操作，这样每层要扫的格子数量就会不断缩减。具体来说设 $solve(l_1,r_1,l_2,r_2)$ 表示当前已经确定终点在第 $[l_1,r_1]$ 行，$[l_2,r_2]$ 列这个范围内，然后考虑类似网格图分治那样，每次选行列里长度较大的那个方向劈成两半，然后同样是在劈开的折线附近两行/两列内走一下，继续用上面的方法判断终点在哪一侧子矩形递归过去即可。为了减小常数，可以每次先令当前点移动到整个矩形范围内的中心。

提交上去发现可以通过，稍微分析一下发现上面的策略步数其实应该是 $O(n)$ 的，画一下就发现每次折线的长度至多递归两层后就会减半，所以一个比较松的上界大概是 $T(n)=8n+T(n/2)=16n$ 左右，实际上并不太满。

给一个比较简短的代码实现，小细节是判定一个矩形的时候如果矩形包含了起点进入次数要加 $1$。

#include<bits/stdc++.h>
//#define int long long
#define For(i, a, b) for(int i = (a); i <= (b); i++)
#define Rof(i, a, b) for(int i = (a); i >= (b); i--)
using namespace std;
template<typename T> void cmax(T &x, T y){x = x < y ? y : x;}
template<typename T> void cmin(T &x, T y){x = x > y ? y : x;}
const int N = 5005;
int n, len, nx, ny;
char cur, a[N][N];
bool valid(){return nx >= 1 && nx <= len && ny >= 1 && ny <= len;}
char moveU(){nx--; cout << "^" << endl; char c; cin >> c; return a[nx][ny] = cur = c;}
char moveD(){nx++; cout << "v" << endl; char c; cin >> c; return a[nx][ny] = cur = c;}
char moveL(){ny--; cout << "<" << endl; char c; cin >> c; return a[nx][ny] = cur = c;}
char moveR(){ny++; cout << ">" << endl; char c; cin >> c; return a[nx][ny] = cur = c;}
void move(int tx, int ty){
	while(nx > tx) if(moveU() == 'G') return;
	while(nx < tx) if(moveD() == 'G') return;
	while(ny > ty) if(moveL() == 'G') return;
	while(ny < ty) if(moveR() == 'G') return;
}
bool check(int l1, int r1, int l2, int r2){
	int cnt = 0;
	if(l1 <= n + 1 && n + 1 <= r1 && l2 <= n + 1 && n + 1 <= r2) cnt++;
	For(i, l1, r1){
		cnt += a[i][l2 - 1] == '>'; cnt += a[i][r2 + 1] == '<';
		cnt -= a[i][r2] == '>'; cnt -= a[i][l2] == '<';
	}
	For(i, l2, r2){
		cnt += a[r1 + 1][i] == '^'; cnt += a[l1 - 1][i] == 'v';
		cnt -= a[r1][i] == 'v'; cnt -= a[l1][i] == '^';
	}
	return cnt;
}
void solve(int l1, int r1, int l2, int r2){
	int mid1 = (l1 + r1) >> 1, mid2 = (l2 + r2) >> 1;
	move(mid1, mid2); if(cur == 'G') return;
	if(r1 - l1 >= r2 - l2){
		For(i, mid2 + 1, r2) if(moveR() == 'G') return;
		if(moveD() == 'G') return;
		Rof(i, r2 - 1, l2) if(moveL() == 'G') return;
		if(moveU() == 'G') return;
		For(i, l2 + 1, mid2) if(moveR() == 'G') return;
		if(check(l1, mid1, l2, r2)) solve(l1, mid1, l2, r2);
		else solve(mid1 + 1, r1, l2, r2);
	}
	else{
		For(i, mid1 + 1, r1) if(moveD() == 'G') return;
		if(moveR() == 'G') return;
		Rof(i, r1 - 1, l1) if(moveU() == 'G') return;
		if(moveL() == 'G') return;
		For(i, l1 + 1, mid1) if(moveD() == 'G') return;
		if(check(l1, r1, l2, mid2)) solve(l1, r1, l2, mid2);
		else solve(l1, r1, mid2 + 1, r2);
	}
}
signed main(){
	cin.tie(0)->sync_with_stdio(0);
	cin >> n; nx = n + 1, ny = n + 1; len = 2 * n + 1;
	a[nx][ny] = '^'; solve(1, len, 1, len);
	return 0;
}