磁軌移動序列 題解｜APCS 2023 年 6 月中高級 第 3 題

前置知識

這題的核心推導（一段指令只要記三個數）下面會從頭講；要先會的是這幾件事，同一個主題兩邊都有的，對照著讀會更快上手：

簡潔題意

指針一開始在位置 \(10\)。指令 Txx 把指針移到位置 \(xx\)（兩位數，\(10 \sim 99\)），移動距離是兩個位置的差的絕對值；Lx...E 把中間的指令依序執行 \(x\) 次（\(1 \sim 9\)），可以巢狀，每個 loop 裡至少有一個 T。輸入字串以 T10 開頭、長度不超過 \(10^5\)，求總移動距離（保證不超過 \(2^{60}\)）。

依正確通過的測試資料筆數給分，其中：

  • 子題組 1（\(10\) 分）：沒有 loop，長度不超過 \(50\)。
  • 子題組 2（\(30\) 分）：長度不超過 \(10^4\)，loop 全部展開後的 T 指令數不超過 \(3 \times 10^4\)。
  • 子題組 3（\(60\) 分）：無額外限制。

先拿下 10 分：沒有 loop

字串每三個字元就是一個 Txx：第 \(i\) 個字元是 T、後面兩個字元是兩位數。記住目前位置 cur，每讀到一個目標就把距離加進去、再把 cur 搬過去。

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

int main() {
    string s;
    cin >> s;
    int cur = 10;                            // 指針目前的位置
    long long total = 0;
    for (int i = 0; i < (int)s.size(); i += 3) {        // 每個 Txx 占三個字元
        int target = (s[i + 1] - '0') * 10 + (s[i + 2] - '0');
        total += abs(cur - target);
        cur = target;
    }
    cout << total << endl;
    return 0;
}

再拿 30 分：照字面把 loop 跑出來

子題組 2 保證展開後的 T 不超過 \(3 \times 10^4\) 個，那就真的把 loop 跑出來。先用堆疊做一次「括弧配對」：由左到右掃，遇到 L 把位置推進堆疊，遇到 E 就彈出最上面的 L——這一對就配好了，記在 matchE[]。然後寫一個遞迴函式 run(l, r) 執行 \(s[l..r]\) 這一段：碰到 T 就移動；碰到 L，把它到配對的 E 之間那一段用 run 跑 \(x\) 次，再跳到 E 後面繼續。

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

const int MAX_LEN = 100000;
string s;
int matchE[MAX_LEN];             // matchE[i] = 位置 i 的 L 所配對的 E 在哪
int cur = 10;                    // 指針目前的位置
long long total = 0;

void run(int l, int r) {         // 執行 s[l..r] 這一段指令
    int i = l;
    while (i <= r) {
        if (s[i] == 'T') {
            int target = (s[i + 1] - '0') * 10 + (s[i + 2] - '0');
            total += abs(cur - target);
            cur = target;
            i += 3;
        } else {                                     // s[i] == 'L'
            int times = s[i + 1] - '0';
            for (int t = 0; t < times; t++) run(i + 2, matchE[i] - 1);   // 迴圈內容真的跑 times 次
            i = matchE[i] + 1;                       // 跳到 E 的下一個字元
        }
    }
}

int main() {
    cin >> s;
    stack<int> opened;                               // 括號配對：找出每個 L 的 E
    for (int i = 0; i < (int)s.size(); i++) {
        if (s[i] == 'L') {
            opened.push(i);
        } else if (s[i] == 'E') {
            matchE[opened.top()] = i;
            opened.pop();
        }
    }
    run(0, (int)s.size() - 1);
    cout << total << endl;
    return 0;
}

這份程式沒有 loop 時就是上一節的程式，所以子題組 1、2 的 \(40\) 分穩穩到手。它的問題是巢狀：L9 裡面再包 L9，每多一層就多九倍，九層就是 \(9^9 \approx 3.9 \times 10^8\) 次移動；本站子題組 3 有三筆這種測資，這份程式跑不完（超時）。要拿滿分，不能真的把 loop 跑出來。

從 40 分到 100 分：一段指令只要記三個數

想想「loop 的內容跑 \(x\) 次」到底多走了什麼。內容跑一次，指針從內容的第一個目標一路走到最後一個目標，中間走的距離是固定的；跑第二次時，指針要先從上一輪停的位置回到內容的第一個目標，再走一次同樣的路。所以一段指令對外面來說，只有三個數有意義（圖 1）：

  • first：這段的第一個目標（外面進來要先走到這裡）。
  • last：這段跑完停在哪裡。
  • inner：這段內部走的總距離。
圖 1：範例 2 外層 loop 的內容壓成 (15, 23, 22)，重複兩次 = 2 × 22 + 1 × 8 = 52，再接上前後的 T10、T44 得 78

兩個規則就能把任何指令串算完：

  • 把兩段接起來（\(a\) 後面接 \(b\)）：first 是 \(a\) 的、last 是 \(b\) 的，inner 多一段從 \(a\) 的終點走到 \(b\) 的起點：\(a.\mathrm{inner} + |a.\mathrm{last} - b.\mathrm{first}| + b.\mathrm{inner}\)。
  • 一段重複 \(x\) 次：first、last 都不變，inner 變成 \(x \times \mathrm{inner} + (x - 1) \times |\mathrm{last} - \mathrm{first}|\)——每一輪都走一次內部距離，相鄰兩輪之間還要從 last 回到 first，共 \(x - 1\) 次。

一個 Txx 自己就是一段：first = last = xx、inner = 0。接下來只要由左到右掃字串，用堆疊記「每一層 loop 目前累積的摘要」：碰到 T 就接到最上層；碰到 L 推一個空的新層；碰到 E 把最上層拿出來、重複 \(x\) 次、接回上一層。最外層一開始放 (10, 10, 0)——指針本來就在 \(10\)，當成已經有一個 T10——掃完後最外層的 inner 就是答案。

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

struct Summary {
    bool empty;                  // 這段裡還沒有任何 T
    int first, last;             // 這段的第一個目標、最後停的位置
    long long inner;             // 這段內部走的距離
};

Summary join(Summary a, Summary b) {        // 把 b 接在 a 後面
    if (a.empty) return b;
    Summary c;
    c.empty = false;
    c.first = a.first;
    c.last = b.last;
    c.inner = a.inner + abs(a.last - b.first) + b.inner;   // 多走一段：a 的終點到 b 的起點
    return c;
}

Summary repeat(Summary a, int times) {      // 把一段重複 times 次
    a.inner = a.inner * times + (long long)(times - 1) * abs(a.last - a.first);
    return a;                               // first、last 都不變
}

int main() {
    string s;
    cin >> s;
    stack<Summary> seg;          // 每一層 loop 目前累積的摘要
    stack<int> times;            // 每一層 loop 要重複幾次
    seg.push({false, 10, 10, 0});            // 最外層：指針一開始就在 10，當成已經有一個 T10
    times.push(1);
    for (int i = 0; i < (int)s.size();) {
        if (s[i] == 'T') {
            int x = (s[i + 1] - '0') * 10 + (s[i + 2] - '0');
            seg.top() = join(seg.top(), {false, x, x, 0});
            i += 3;
        } else if (s[i] == 'L') {
            seg.push({true, 0, 0, 0});       // 新的一層，還是空的
            times.push(s[i + 1] - '0');
            i += 2;
        } else {                             // 'E'：這一層結束，整段重複後接回上一層
            Summary body = repeat(seg.top(), times.top());
            seg.pop();
            times.pop();
            seg.top() = join(seg.top(), body);
            i += 1;
        }
    }
    cout << seg.top().inner << endl;
    return 0;
}

每個字元只看一次，每一層的摘要只進出堆疊一次，\(O(|s|)\)。inner 用 long long：每一層算出來的 inner 都是最後答案的一部分，題目保證答案不超過 \(2^{60}\)，所以中間值也不會超過，long long 夠用。

測過再交：範例的 loop 都是「直接寫 T」開頭

範例 2 的兩個 loop，內容都是以直接寫在那一層的 T 開頭、也以 T 結尾。沒蓋到的：只跑一次的 L1、整個內容只有一個位置（相鄰兩輪之間不用走）、內容以另一個 loop 開頭（first 要從內層拿）、原地不動的 T，以及真的不能展開的深層巢狀。

輸入 正確輸出 這一筆在測什麼
T10L1T20E 10 L1：跑一次就是沒有 loop，\(x - 1 = 0\)
T10L3T20E 10 內容只有一個位置：三輪之間 last 和 first 都是 \(20\)，一步都不用走
T10L2T20T10E 40 兩輪之間要從 \(10\) 回到 \(20\)：\(2 \times 10 + 1 \times 10\)，再加上一開始的 \(10 \to 20\)
T10T30L2L2T20ET50E 120 loop 內容以內層 loop 開頭：外層的 first 是內層給的 \(20\)，不是後面那個 T50
T10T10T10 0 原地不動：距離 \(0\)，不是負數也不會當掉
用程式造：T10 接 \(15\) 層 L9、裡面 T99T10、再 \(15\) 個 E 36648621512847522 展開是 \(9^{15} \times 2\) 個 T，照字面跑不完；答案約 \(3.7 \times 10^{16}\)，驗 long long

六筆都親眼看過正確，這題就穩了。

常犯錯誤
  • 真的把 loop 跑出來（\(40\) 分版硬交）：兩個範例都過，子題組 3 有三筆超時——九層 L9 要跑 \(9^9\) 次。
  • 重複 \(x\) 次只把 inner 乘 \(x\)，忘了相鄰兩輪之間要從 last 回到 first：範例 2 印 70（少了 \(8\)）；自測表第 3 列印 30。
  • first、last 只看直接寫在這一層的 T，沒把內層 loop 的算進來：兩個範例都過、計分測資掛 \(4\) 筆；自測表第 4 列印 80。
  • loop 只執行一次（忘了乘次數）：範例 2 印 48。
  • 對 \(10^9 + 7\) 取餘數：題目要的是精確值——兩個範例都過，答案超過 \(10^9 + 7\) 的兩筆掛掉。
  • 距離用 int：同樣那兩筆溢位；自測表第 6 列印 583528610。