信友赛(伪)题解—核酸检测

发布于 2020-05-18  42 次阅读


题面描述

新型冠状病毒疫情爆发!某城市内大量疑似患者被集中到各个隔离点,初期确诊非常困难,专家团队需要依次到这些隔离点去现场指导,为疑似患者进行核酸检测。城市共有 n(n+1)个隔离点,它们形成了 n 行 (n+1)列的方阵。我们用 (r,c)表示位于从上到下第 r 行、从左到右第c列的隔离点。例如,左上角的坐标是 (1,1),右下角的坐标是(n,n+1)。该城市的交通结构比较特殊,任意两个 对角方向相邻 隔离点之间有一条 双向通路 。此外,在方阵的边界处有一条 顺时针 运行的 单向 地铁环线。下图是一个n=5的城市示意图:

GhLigP.jpg

专家可以从任意一个隔离点出发,之后你可以沿着道路或乘坐地铁前往其他隔离点。走过一条道路、乘坐一段地铁都需要111单位时间。在隔离点处进行核酸检测所需的时间忽略不计。专家迫切想要知道 最少 需要多少时间才能完成所有隔离点的核酸检测。请求出最少需要的时间,以及一条路线。

输入描述

输入共一行,包含一个整数 n (2≤n≤100),表示隔离点方阵的行数。

输出描述

第一行输出一个整数,表示花费的时间 T。

接下来包含 T+1行。这部分的第i行包含两个整数xi,yi,用一个空格隔开,表示你构造出的路线经过的第iii 个隔离点坐标是(xi,yi)。

如果存在多种可行的方案,请输出 任意 一种可行的方案。

样例输入样例输入

2

样例输出

5
1 1
1 2
1 3
2 3
2 2
2 1

限制及约定

本题采用子任务形式评测。

子任务编号特殊限制分值
111n=2n = 2n=2777
222n=3n = 3n=3151515
333n≤5n \le 5n≤5292929
444n≤10n \le 10n≤10212121
555n≤100n \le 100n≤100282828

对于所有数据,满足 2≤n≤100。

1.日常吐槽:第一眼看到的时候着实震惊,这就是学军信友赛入门难度的题目吗,i了i了,第一个想法是图论,然后马上pass掉了,在之后是广搜,然后屈服于100ms的淫威之下。

2.地铁上和某梁巨佬聊了下,他想法是整一个数学方法O(1)求解,我当时猜是可能有唯一路径方法适用(大概就是交叉型走,最后走出好多×的样子),实验了一下是不行的,然后地铁就到站了

2.1.总之来看看这道题的例子,众所周知,样例总能让同学们无法找到规律,很好,样例就是绕着地铁线走了一波,真是十分发人深省的样例呢

2.2然后记住,这道题的意思类似于一笔画,走完整个图上的所有点,那么最短时间一定是n*(n-1)(还有打表的7分别忘了),用连续的交叉走是不行的,以为会重复点。

3.回去拿题目的图片试了一下,整出这么个东西:

我jio的就很行,但是自测的WA又直接给我一斤鸭梨。

4.很好,没考虑n为奇数的情况,怎么办。

5.答案很简单,把图翻转就行,翻转九十度就是奇数的,两种情况分情况模拟就好

6.程序就不放了,毕竟莫名在梁某的OJ上全是WA(QAQ)

2020.5.25更新:官方题解放一放好了,不过别抄就行

#include <cstdio>
#include <algorithm>
using namespace std;
int n, m; 
void Print(int x, int y) 
{ 
if (n < m) printf("%d %d\n", x + 1, y + 1); 
else  printf("%d %d\n", m - y, x + 1);  } 
int main(void) 
{ 
scanf("%d", &n); 
m = n + 1; 
printf("%d\n", n * m - 1); 
if (n & 1) { swap(n, m); } 
for (int y = 0; y < m - 1; y += 2) 
{ 
for (int x = 0; x < n; x += 2) { Print(x, y); Print(x + 1, y + 1); }
for (int x = n - 2; x >= 0; x -= 2) { Print(x + 1, y); Print(x, y + 1); } } for (int x = 0; x < n; ++x) { Print(x, m - 1); } 
return 0; 
}

花开花败总归尘。 阴阳化生,清浊自分。