Codeforces 321A Ciel and Robot：枚舉最後一步判斷可達性

問題描述

機器人從 (0,0) 出發，按指令串 s（U/D/L/R）循環移動。給定目標點 (a,b)，問是否能到達。

解法：枚舉前綴步數

設完整指令串位移為 (dx, dy)。機器人走 k 輪完整指令加前 i 步（0≤i<|s|）到達 (a,b)。即：

a = k*dx + pre_x[i], b = k*dy + pre_y[i]，其中 pre_x[i], pre_y[i] 為前 i 步位移。

枚舉 i，解關於 k 的方程：

• 若 dx=0，要求 a == pre_x[i]，且 (b - pre_y[i]) % dy == 0 且商 k ≥ 0。
• 若 dy=0 同理。
• 否則要求 (a - pre_x[i]) % dx == 0，(b - pre_y[i]) % dy == 0，且兩商相等且 ≥ 0。

代碼

bool work() {
    for(int i=0;i= 0) return true;
        } else {
            if(lx % x[n]) continue;
            ll kx = lx / x[n];
            if(kx < 0) continue;
            if(y[n]==0) { if(ly) continue; else return true; }
            if(ly % y[n]) continue;
            if(ly / y[n] == kx) return true;
        }
    }
    return false;
}

關鍵點

• 預計算前綴位移 x[i], y[i]（x[0]=y[0]=0）。
• 整除與非負判斷嚴格（C++ 負數取模行為注意，題目數據非負或可調整）。
• 枚舉 i=0..n-1 即「最後一步」為第 i 步（0 表示剛好走完整數輪）。