ZeroJudge 解題筆記：f164. 萬球同心移位之章

作者：王一哲
日期：2025年10月2日


ZeroJudge 題目連結：f164. 萬球同心移位之章

解題想法

這題絕對不要真的用鏈結串列解題，因為要找到鏈結串列中指定的值只能從頭開始依序往下找，一定會超時。用兩個陣列儲存每一個節點的左、右節點編號，移動節點時只要修改對應的節點編號即可。

Python 程式碼

最後一筆測資記憶體爆掉。

n, m, q = map(int, input().split())  # n 顆球，m 次操作，q 次查詢
pre = [(i-1+n)%n for i in range(n)]  # 每顆球的前一顆球
nxt = [(i+1)%n for i in range(n)]  # 每顆球的後一顆球
for _ in range(m):  # 執行 m 次
    d, a, b = input().split()  # 方向 d，a 球移到 b 球旁邊
    if a == b: continue  # 如果 a 等於 b，不移動
    a = int(a); b = int(b)  # 轉成整數
    nxt[pre[a]] = nxt[a]  # a 原來左側的球接到 a 原來右側的球
    pre[nxt[a]] = pre[a]  # a 原來右側的球接到 a 原來左側的球
    if d == 'R':  # 逆向
        le = pre[b]  # 暫存 b 原來左側的球
        nxt[le] = a  # b 原來左側的球接到 a
        pre[b] = a  # b 的左側接到 a
        pre[a] = le  # a 左側接到 le
        nxt[a] = b  # a 右側接到 b
    else:  # 順向
        ri = nxt[b]  # 暫存 b 原來右側的球
        pre[ri] = a  # b 原來右側的球接到 a
        nxt[b] = a  # b 的右側接到 a
        pre[a] = b  # a 的左側接到 b
        nxt[a] = ri  # a 的右側接到 ri
arr = tuple(map(int, input().split()))
for a in arr[:-1]: print(pre[a], nxt[a], end=" ")
print(pre[arr[-1]], nxt[arr[-1]])

C++ 程式碼

使用時間約為 6 ms，記憶體約為 3.9 kB，通過測試。

#include <cstdio>
using namespace std;

int main() {
    int n, m, q; scanf("%d %d %d", &n, &m, &q);  // n 顆球，m 次操作，q 次查詢
    int pre[n], nxt[n];  // 每顆球的前、後的球
    for(int i=0; i<n; i++) {
        pre[i] = (i-1+n)%n;
        nxt[i] = (i+1)%n;
    }
    for(int i=0; i<m; i++) {  // 執行 m 次
        char d; int a, b;  // 方向 d，a 球移到 b 球旁邊
        scanf(" %c %d %d", &d, &a, &b);  // %c 前面有要空格，才能忽略前一行的 \n
        if (a == b) continue;  // 如果 a 等於 b，不移動
        nxt[pre[a]] = nxt[a];  // a 原來左側的球接到 a 原來右側的球
        pre[nxt[a]] = pre[a];  // a 原來右側的球接到 a 原來左側的球
        if (d == 'R') {  // 逆向
            int le = pre[b];  // 暫存 b 原來左側的球
            nxt[le] = a;  // b 原來左側的球接到 a
            pre[b] = a;  // b 的左側接到 a
            pre[a] = le;  // a 左側接到 le
            nxt[a] = b;  // a 右側接到 b
        } else {  // 順向
            int ri = nxt[b];  // 暫存 b 原來右側的球
            pre[ri] = a;  // b 原來右側的球接到 a
            nxt[b] = a;  // b 的右側接到 a
            pre[a] = b;  // a 的左側接到 b
            nxt[a] = ri;  // a 的右側接到 ri
        }
    }
    int c;
    for(int i=0; i<q-1; i++) {
        scanf("%d", &c);
        printf("%d %d ", pre[c], nxt[c]);
    }
    scanf("%d", &c);
    printf("%d %d\n", pre[c], nxt[c]);
    return 0;
}