题解：P12784 [ICPC 2024 Yokohama R] Beyond the Former Explorer

· · 题解

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

于是就有了这么一个策略，设 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;
}