P8303 [CoE R4 C] 网格 题解

· · 题解

直接模拟即可。

分析

我们注意到这样一件事情，对于一张网格图来说，确定两个邻角到每个点的曼哈顿距离就可以确定整张图的结构。

规定网格图规模为 l \times c ， (i,j) 代表第 i 行第 j 列。

例如，设图的左上角为 a ，左下角为 b ，则对于点 p 来说，很显然有

p : (\frac{1}{2}(dis(a,p) - dis(b,p) + dis(a,b) + 2),\frac{1}{2}(dis(a,p) + dis(b,p) - dis(a,b) + 2))

我们构造两条路径：

1.从左上角 a 一直向下走，至 p 点所在行，再向右走，至 p 点所在列。

2.从右下角 b 一直向上走，至 p 点所在行，再向右走，至 p 点所在列。

可以发现，两条路径的长度分别为 dis(a,p),dis(b,p) 。

首先，无论 p 点的坐标在哪个位置，两条路径必然恰好覆盖全了一整列，并且从第一列至 p 所在列走了两次，进而可求得 p 点的 y 坐标，又由于 p 点到 a,b 的距离确定，相减就能得出 x 坐标。

现在问题就转化成了在 3 次询问内找出网格图的两个邻角。

我们先询问 1 号点，这时候，距离 1 号点最远的点一定在角上，可以采用反证法，若其不是一个角，则可继续向远离 1 的位置找点，找到的角必然更远。这时候，我们知道了一个角，询问这个角，便一定能找出这个角的对角（距离其最远的点）。钦定找到的角为 x ，对角为 y ，则有 l + c = dis(x,y) - 2 ，又已知 l \times c = n ，则能确定出 l,c 。

并且，我们确定了 l,c ，只需要知道一个点和 x 的距离，就能确定其与 y 的距离。

现在，我们根据已知条件，求出点 1 的坐标。

设：

sum_1 = \sum_{i = 1}^{ n } { [dis(x,i) + dis(1,i) = dis(x,1)] } sum_2 = \sum_{i = 1}^{ n } { [dis(y,i) + dis(1,i) = dis(y,1)] }

不妨设 x 为左上角， y 为右下角。

我们观察到，满足 sum_1 求和号内条件的点必然在以左上角为 x ，右下角为 1 的矩形中，满足 sum_2 求和号内条件的点必然在以 1 为左上角， y 为右下角的矩形中。也就意味着，设点 1 的坐标为 (i,j) ，则 sum_1 = i \times j,sum_2 = (r - i + 1) \times (c - j + 1) ，又由于我们知道 1 与左上角的距离，便可以求得坐标。

不妨设 l \leq c ，我们从网格图的左上向右下画一条线，注意到，当 1 在线的下侧时，右上角比左下角距离更远。所有距离 x 为 c - 1 的点必然在从右上角开始，坐标每次变化 (1,-1) 得到的，那么，其他距离 x 为 c - 1 的点就一定比右上角近，因此，不可能存在一个点使得 1 到这个点的距离与 1 到右上角的距离相等，因此可以确定右下角，左上角同理。

注意到 l = c 时无法判断是左上角还是右下角，不过此时是对称的，没有影响。

另外，我们观察到，有很多情况需要特判。

定义一个点的度数为与其距离为 1 的节点的个数。

首先，只有一个点的时候直接判。

然后，我们发现，若点 1 的度数为 1 ，则必然是一个 1 \times n 的网格，直接输出即可。

同理，若点 1 的度数为 2 ，则询问其中一个与点 1 相邻的点 q ，若 q 度数为 1 ，则是 1 \times n ，若其度数为 3 ，则将 1 看做找到的角， q 看做最开始询问的 1 ，正常计算即可。若 q 度数为 2 ，询问距离其最远的点 s ，若 s 度数为 1 ，则是 1 \times n 的情况，否则表明 1,q 是一个 2 \times \frac{n}{2} 的网格的两个邻角。

以上是我花 10 块钱买了官方题解的原因。

AC 代码

#include<iostream>
#include<cstdio>
#include<utility>
#include<vector>
#include<algorithm>
#define MAXN 100005
#define fi first
#define se second

using namespace std;

int n,a1[MAXN],a2[MAXN],a3[MAXN];

void Ask(int * a,int x){
    cout << x << endl;
    for(int i=1;i<=n;i++) cin >> a[i];
}

int X,Y,Z,l,c,x_1,y_1;

inline int dis_1(int x) { return a1[x]; }
inline int dis_X(int x) { return a2[x]; }
inline int dis_Y(int x) { return l+c-2-a2[x]; }
inline int dis_Z(int x) { return a3[x]; }
inline int Abs(int x) { return x>0?x:-x; }

inline int get_d(int * a){
    int ret=0;
    for(int i=1;i<=n;i++) ret+=(a[i]==1);
    return ret;
}

void solve_1(){
    vector <int> a(n,0);
    a[0]=1;
    for(int i=1;i<=n;i++) a[a1[i]]=i;
    cout << 0 << endl;
    cout << 1 << ' ' << n << endl;
    for(int i=0;i<n;i++) cout << a[i] << ' ';
    cout << endl;
}

void get_ans(int pos_1){
    for(int i=1;i<=n;i++) if(a2[i]>=a2[Y]) Y=i;
    int sum_lc=dis_X(Y)+2;
    for(int i=1;i<=n;i++){
        if((!(n%i))&&i+n/i==sum_lc){
            l=i; c=n/i; break;
        }
    }
    int t1=0,t2=0;
    for(int i=1;i<=n;i++){
        if(dis_1(i)+dis_X(i)==dis_X(pos_1)) t1++;
        if(dis_1(i)+dis_Y(i)==dis_Y(pos_1)) t2++;
    }
    for(int i=1;i<=l;i++){
        for(int j=1;j<=c;j++){
            if(i+j==dis_1(X)+2&&i*j==t1&&(l-i+1)*(c-j+1)==t2){
                x_1=i,y_1=j;
                break;
            }
        }
    }
    vector <int> ld,ru;
    for(int i=1;i<=n;i++){
        if(dis_X(i)==l-1&&dis_1(i)==Abs(l-x_1)+Abs(y_1-1)){
            ld.push_back(i);
        }
        if(dis_X(i)==c-1&&dis_1(i)==Abs(1-x_1)+Abs(c-y_1)){
            ru.push_back(i);
        }
    }
    vector < vector <int> > a(l,vector <int> (c,0));
    if(Z){
        if(dis_X(Z)==l-1){
            for(int i=1,tx,ty;i<=n;i++){
                ty=(dis_Z(i)+dis_X(i)-dis_X(Z)+2)/2;
                tx=dis_X(i)-ty+2;
                a[tx-1][ty-1]=i;
            }
            cout << 0 << endl;
            cout << l << ' ' << c << endl;
            for(int i=0;i<l;i++){
                for(int j=0;j<c;j++){
                    cout << a[i][j] << ' ';
                }
                cout << endl;
            }
        }
        else{
            for(int i=1,tx,ty;i<=n;i++){
                tx=(dis_Z(i)+dis_X(i)-dis_X(Z)+2)/2;
                ty=dis_X(i)-tx+2;
                a[tx-1][ty-1]=i;
            }
            cout << 0 << endl;
            cout << l << ' ' << c << endl;
            for(int i=0;i<l;i++){
                for(int j=0;j<c;j++){
                    cout << a[i][j] << ' ';
                }
                cout << endl;
            }
        }
        return;
    }
    if(ld.size()==1){
        Ask(a3,ld[0]),Z=ld[0];
        for(int i=1,tx,ty;i<=n;i++){
            ty=(dis_Z(i)+dis_X(i)-dis_X(Z)+2)/2;
            tx=dis_X(i)-ty+2;
            a[tx-1][ty-1]=i;
        }
        cout << 0 << endl;
        cout << l << ' ' << c << endl;
        for(int i=0;i<l;i++){
            for(int j=0;j<c;j++){
                cout << a[i][j] << ' ';
            }
            cout << endl;
        }
    }
    else{
        Ask(a3,ru[0]),Z=ru[0];
        for(int i=1,tx,ty;i<=n;i++){
            tx=(dis_Z(i)+dis_X(i)-dis_X(Z)+2)/2;
            ty=dis_X(i)-tx+2;
            a[tx-1][ty-1]=i;
        }
        cout << 0 << endl;
        cout << l << ' ' << c << endl;
        for(int i=0;i<l;i++){
            for(int j=0;j<c;j++){
                cout << a[i][j] << ' ';
            }
            cout << endl;
        }
    }
}

void solve_2(){
    int p;
    for(int i=1;i<=n;i++){
        if(a1[i]==1) { p=i; Ask(a2,p); break; }
    }
    if(get_d(a2)>=3){
        swap(a2,a1); X=1;
        get_ans(p);
    }
    else if(get_d(a2)==1){
        vector <int> a(n,0);
        a[0]=p;
        for(int i=1;i<=n;i++) a[a2[i]]=i;
        cout << 0 << endl;
        cout << 1 << ' ' << n << endl;
        for(int i=0;i<n;i++) cout << a[i] << ' ';
        cout << endl;
    }
    else{
        for(int i=1;i<=n;i++) if(a2[i]>=a2[Z]) Z=i;
        Ask(a3,Z);
        if(get_d(a3)==1){
            vector <int> a(n,0);
            a[0]=Z;
            for(int i=1;i<=n;i++) a[a3[i]]=i;
            cout << 0 << endl;
            cout << 1 << ' ' << n << endl;
            for(int i=0;i<n;i++) cout << a[i] << ' ';
            cout << endl;
        }
        else{
            swap(a1,a2);
            get_ans(p);
        }
    }
}

void solve(){
    X=Y=Z=l=c=x_1=y_1=0;
    cin >> n;
    Ask(a1,1);
    if(get_d(a1)==0){
        cout << 0 << endl;
        cout << 1 << ' ' << 1 << endl;
        cout << 1 << endl;
        return;
    }
    if(get_d(a1)==1) return solve_1();
    if(get_d(a1)==2) return solve_2();
    for(int i=1;i<=n;i++) if(a1[i]>=a1[X]) X=i;
    Ask(a2,X);
    get_ans(1);
}

int main(){
    int T; cin >> T;
    while(T--) solve();
    return 0;
}