【题解】CF1179B Tolik and His Uncle 题解

· · 题解

题意

给定一个矩阵的边长 n 和 m，要求以不同的向量到达矩阵中的每一个格子，并输出到达各自的顺序。
以不同的向量，简单理解就是将当前格子和要去往的格子连线，使得整个过程中所有直线两两斜率不相同。

思路

不太好直接构造，也不可能用类似搜索的做法（1\leq n \times m \leq 10^6）。
本题最大的障碍是，如果按心情随便走，很有可能在走到某一个点时发现剩下的点都必须用到相同的向量才可到达，那我们不妨考虑一种有规律的方法。
首先，考虑如果 n=1：
显然，横坐标都是 0，纵坐标：1,m,2,m-1,3,m-2,\ldots。
这里可以给我们一些启发：在这个过程中，向量时绝对不会重复的。

（图丑见谅）
图中蓝色向右走，红色向左走。可以发现，每一条水平的蓝红色线段两两不相等。
那我们把这种方法扩展，对于 n 行的矩阵，第一次在第 1 行和第 n 行之间跳，第二次在第 2 行和第 n-1 行之间跳，相当于横坐标是水平对称的。
而纵坐标则竖直对称。以下图帮助理解（图中数字代表到达顺序）：

其实可以发现，每两行之间的跳跃不会出现向量相同的情况，当移动距离相同时，一定会有上下或左右方向相反。
而扩展到另两行时，上下移动的距离又不相同，所以一定不会出现向量相同的情况。

Code

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

int n,m;

int main(){
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n/2;i++)
        for(int j=1;j<=m;j++)
            printf("%d %d\n%d %d\n",i,j,n-i+1,m-j+1);
    if(n%2==1){
        int x=(n/2)+1;
        for(int i=1;i<=m/2;i++) printf("%d %d\n%d %d\n",x,i,x,m-i+1);
        if(m%2==1) printf("%d %d\n",x,(m/2)+1);
    }
    return 0;
}

完结撒花！