[CCPC 2024 哈尔滨站] 在哈尔滨指路 的题解

记住只在没有思路时使用题解，不要从它复制粘贴代码。请尊重题目和题解的作者。
在解题之前提交题解的代码会导致封禁。

作者： admin

概述

本题要求将一组按绝对方位（东南西北）描述的路径指令，转换为哈尔滨人习惯的相对方位指令（直走、左转、右转）。核心解法是保持第一步为直走，之后每一步根据当前朝向与下一目标方向的相对关系输出左转或右转，再接一次直走。

分析
核心观察

相邻两条绝对指令的方向既不相同也不相反，因此从当前方向转向下一方向时，只可能是左转或右转，不会出现掉头。初始面向即第一条指令的方向，后续每次转向角度为 90 度。

思路

设当前朝向为 cur，下一个目标方向为 nxt。判断 nxt 相对于 cur 是左转还是右转。按顺时针方向排列方位顺序为 N → E → S → W → N。若 nxt 在顺时针顺序中位于 cur 的下一个，则为右转；若位于前一个，则为左转。

具体判断：

  • 若 (cur == 'N' && nxt == 'E') 或 (cur == 'E' && nxt == 'S') 或 (cur == 'S' && nxt == 'W') 或 (cur == 'W' && nxt == 'N')，则输出 R（右转）；
  • 否则输出 L（左转）。

每条指令（除第一条外）先输出转向命令，再输出直走命令，直走距离为对应绝对指令中的路口数。总指令数为 2n-1：第一条直走，之后每组（转向 + 直走）共 2(n-1) 条。

具体示例

输入样例：

  • 第一条 S 2：初始面向 S，输出 Z 2。
  • 第二条 E 1：当前朝向 S，目标 E，顺时针 S→W→N→E，E 是 S 的前一个（逆时针），所以左转，输出 L，然后直走 Z 1。 最终输出： 
    3 S
Z 2
L
Z 1
算法步骤
  1. 读取测试组数 T。
  2. 对每组数据：
    • 读取指令条数 n。
    • 读取第一条指令的方向 f 和距离 d。
    • 输出 2 * n - 1 和 f。
    • 输出直走命令 Z d。
    • 循环 n-1 次处理剩余指令：
      • 读取当前指令的方向 f 和距离 d（此时 f 是目标方向，前一条方向为 last）。
      • 判断转向：若 (last, f) 属于右转关系，输出 R，否则输出 L。
      • 输出直走命令 Z d。
      • 更新 last = f。
复杂度分析
  • 时间：O(\sum n)，每组处理 n 条指令。
  • 空间：O(1)。
实现注意事项
  • 相邻指令保证方向不相同且不相反，因此转向非左即右，无需处理掉头。
  • 输出指令中，L 和 R 不能相邻，但本转换中每个转向后必接直走，因此满足。
  • 每条直走距离 y 范围 1 到 100，而原距离 x \le 10，但输出可放大？题目要求输出任意方案均可，且 y 范围放宽至 100，但按原距离直接输出是合法的，因为原来的路口数不变。
  • 使用 cin/cout 并关闭同步以提高效率。
源代码
#include <iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        char dir;
        int dist;
        cin >> dir >> dist;

        cout << 2 * n - 1 << ' ' << dir << '\n';
        cout << "Z " << dist << '\n';

        char last = dir;
        for (int i = 1; i < n; ++i) {
            cin >> dir >> dist;
            char turn;
            if ((last == 'N' && dir == 'E') ||
                (last == 'E' && dir == 'S') ||
                (last == 'S' && dir == 'W') ||
                (last == 'W' && dir == 'N')) {
                turn = 'R';
            } else {
                turn = 'L';
            }
            cout << turn << '\n';
            cout << "Z " << dist << '\n';
            last = dir;
        }
    }
    return 0;
}

import sys

def solve():
    data = sys.stdin.read().strip().split()
    it = iter(data)
    T = int(next(it))
    out_lines = []
    for _ in range(T):
        n = int(next(it))
        dir = next(it)
        dist = int(next(it))
        out_lines.append(f"{2 * n - 1} {dir}")
        out_lines.append(f"Z {dist}")
        last = dir
        for _ in range(n - 1):
            dir = next(it)
            dist = int(next(it))
            if ((last == 'N' and dir == 'E') or
                (last == 'E' and dir == 'S') or
                (last == 'S' and dir == 'W') or
                (last == 'W' and dir == 'N')):
                turn = 'R'
            else:
                turn = 'L'
            out_lines.append(turn)
            out_lines.append(f"Z {dist}")
            last = dir
    sys.stdout.write("\n".join(out_lines))

if __name__ == "__main__":
    solve()

评论

目前没有评论。