题解 [email protected]洛谷 | [email protected] 【Valera and Tubes 】

upd(2020.10.5):修复一个手贱错误。

题意:一个 m×nm\times n 的网格图,每次连一条线,要求这条线:

  • 至少包含两个点。
  • 必须连续:也就是说,每一步可以继续向前画,也可以向左或向右转弯 90°90\degree
  • 不与以前画过的线重复。

构造一种包含 kk 条线的画法,把整个图覆盖。


显然构造题。

一种容易想到的方法是:我们使前 k1k-1 条线每条经过两个点,最后一条线将剩余所有点连接。为了方便描述,我们以 5×55\times 5 的网格图为例,对其进行编号:

假设 k=4k=4,则四条线段分别经过如下点:

  • Line1:(1,2)\operatorname{Line}1:(1,2)
  • Line2:(3,4)\operatorname{Line}2:(3,4)
  • Line3:(5,6)\operatorname{Line}3:(5,6)
  • Line4:(7,8,,25)\operatorname{Line}4:(7,8,\cdots,25)

基础思路有了,问题转化为如何根据点的编号求出其坐标。发现对于奇数行,编号正序;偶数行为倒序。我们根据这一特点对编号的行数进行分类,经过一定的数学推导,就可以得到行数和列数了。

pair<int, int> calcPos(int x) {
	int div = (x - 1) / n + 1, pos = (x - 1) % n + 1;
	if(div & 1) return make_pair(div, pos);
	return make_pair(div, n-pos+1);
}

然后根据上面说过的思路,计算出所有线的情况,输出即可。


代码:

//By: [email protected]_er(122461)
#include <bits/stdc++.h>
using namespace std;

int n, m, k;
pair<int, int> calcPos(int x) {
	int div = (x - 1) / n + 1, pos = (x - 1) % n + 1;
	if(div & 1) return make_pair(div, pos);
	return make_pair(div, n-pos+1);
}

int main() {
	scanf("%d%d%d", &m, &n, &k);
	for(int i=1;i<k;i++) {
		printf("2 ");
		pair<int, int> _;
		_ = calcPos((i<<1)-1);
		printf("%d %d ", _.first, _.second);
		_ = calcPos(i<<1);
		printf("%d %d\n", _.first, _.second);
	}
	printf("%d ", n*m-((k-1)<<1));
	for(int i=(k<<1)-1;i<=n*m;i++) {
		pair<int, int> _;
		_ = calcPos(i);
		printf("%d %d ", _.first, _.second);
	}
	puts("");
	return 0;
}