题解：P14440 [JOISC 2013] 山岳救援队 / Mountain Rescue Team

· · 题解

坐标。

Description

交互题。

给定 R、C、R_s、C_s、X，交互库会隐藏一个 R\times C 的正整数网格，保证其满足以下条件：

  • 没有两个位置上的数相等。
  • 值域为 [1,10^9]。
  • 对于任意两个相邻网格，与 (R_s,C_s) 曼哈顿距离较远的网格的数更小。

你可以进行询问：给出 r、c，然后得知网格上 (r,c) 位置的值。

在 1000 次询问内，找到值恰好为 X 的那个位置。

Solution

把网格上所有 \ge X 的位置标记上，这个东西的边界在四个象限都是一条折线，围成了一个神秘图形。

不难发现 X 一定位于这个神秘图形的边缘，所以我们二分出四个方向的边界，拿一个指针扫过去，一路询问边缘上的所有值，最后找 X 在哪就行了。

Code

:::success[代码]

#include<bits/stdc++.h>
#define inf 0x3f3f3f3f
#define infll 0x3f3f3f3f3f3f3f3fll
using namespace std;

// -------- grader.h ------------
// #include "grader.h"
int Measure(int RM, int CM);
void Pinpoint(int RP, int CP);
// ------------------------------

int find_first(int l,int r,auto check){
    while(l<r){
        int mid=(l+r)>>1;
        if(check(mid)) r=mid;
        else l=mid+1;
    }
    return l;
}

int find_last(int l,int r,auto check){
    while(l<r){
        int mid=(l+r+1)>>1;
        if(check(mid)) l=mid;
        else r=mid-1;
    }
    return l;
}

int mp[210][210];
int query(int x,int y){
    if(mp[x][y]) return mp[x][y];
    return mp[x][y]=Measure(x,y);
}

void solve(int n,int m,int px,int py,int h){
    int lbound,rbound,tbound,bbound;

    lbound=find_first(1,py,[&](int pos){return query(px,pos)>=h;});
    rbound=find_last(py,m,[&](int pos){return query(px,pos)>=h;});
    tbound=find_first(1,px,[&](int pos){return query(pos,py)>=h;});
    bbound=find_last(px,n,[&](int pos){return query(pos,py)>=h;});

    // tbound -> lbound
    for(int nowx=tbound,nowy=py;nowy>=lbound;nowy--) while(nowx<=px&&query(nowx,nowy)<h) nowx++;

    // tbound -> rbound
    for(int nowx=tbound,nowy=py;nowy<=rbound;nowy++) while(nowx<=px&&query(nowx,nowy)<h) nowx++;

    // bbound -> lbound
    for(int nowx=bbound,nowy=py;nowy>=lbound;nowy--) while(nowx>=px&&query(nowx,nowy)<h) nowx--;

    // bbound -> rbound
    for(int nowx=bbound,nowy=py;nowy<=rbound;nowy++) while(nowx>=px&&query(nowx,nowy)<h) nowx--;

    for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) if(mp[i][j]==h) Pinpoint(i,j);
    Pinpoint(0,0);
}

void Rescue(int R,int C,int RS,int CS,int X){solve(R,C,RS,CS,X);}

:::