Hướng dẫn giải của [200 đề thầy Đức] Bài 134: Di chuyển Robot
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Hướng dẫn giải
Cho chuỗi $s$ gồm các ký tự L, R, U, D. Ta được bỏ đi một số ký tự và sắp xếp lại các ký tự còn lại, sao cho robot xuất phát từ $(0, 0)$, đi theo chuỗi, và quay về $(0, 0)$ mà không đi qua điểm nào khác (trừ điểm xuất phát) quá một lần. Cần tìm độ dài lớn nhất và một chuỗi đạt được.
Gọi $L, R, U, D$ là số lần xuất hiện của mỗi ký tự. Một đường đi khép kín không lặp cần có số L bằng số R và số U bằng số D trong chuỗi con được chọn.
- Nếu chỉ dùng được một trục (ngang hoặc dọc): đi tới lui trên một đường thẳng sẽ quay lại điểm cũ, nên chỉ dùng được đúng một cặp, ví dụ
RLhoặcUD, độ dài $2$. - Nếu dùng cả hai trục: đi theo hình chữ nhật $R^a U^b L^a D^b$ với $a = \min(L, R)$ và $b = \min(U, D)$ là các điểm trên biên hình chữ nhật, không trùng nhau. Độ dài là $2a + 2b$.
Sub 1: Vét cạn — ~O(\min(L,R) \cdot \min(U,D))~, dùng khi độ dài ~\le 1000~
Thử mọi cặp $(a', b')$ với $0 \le a' \le \min(L, R)$ và $0 \le b' \le \min(U, D)$, tính độ dài của chuỗi xây được từ cặp đó (theo hai trường hợp ở trên), và lấy cặp cho độ dài lớn nhất.
Kết quả chấm riêng sub này: đúng 21/21 test.
Sub 2: Công thức — ~O(|s|)~
Vì độ dài $2a' + 2b'$ tăng khi $a'$ và $b'$ tăng (khi cả hai đều dương), nên dùng luôn $a = \min(L, R)$ và $b = \min(U, D)$. Đếm bốn loại ký tự rồi xây chuỗi trực tiếp.
Bẫy cần chú ý: khi một trong hai trục bằng $0$, không được lấy $a$ hoặc $b$ lớn, mà chỉ lấy đúng một cặp $RL$ hoặc $UD$ (độ dài $2$). Khi cả hai trục đều bằng $0$, đáp án là chuỗi rỗng với độ dài $0$.
Kết quả chấm riêng sub này: đúng 21/21 test.
Chương trình hoàn chỉnh
Chương trình đọc $q$, rồi với mỗi truy vấn đếm bốn loại ký tự. Nếu độ dài $|s| \le 1000$ thì gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub1 vẫn ăn điểm các test nhỏ nếu sub2 chưa làm kịp.
#include <bits/stdc++.h>
using namespace std;
string s;
int cntL, cntR, cntU, cntD;
// Xây chuỗi hướng dẫn từ số cặp ngang a (L và R) và số cặp dọc b (U và D)
// Nếu có cả hai: đi hình chữ nhật R^a U^b L^a D^b, không đi qua điểm nào hai lần
// Nếu chỉ có một loại: chỉ dùng được một cặp (RL hoặc UD) vì đi tới lui sẽ quay lại điểm cũ
string build(int a, int b) {
if (a > 0 && b > 0) return string(a, 'R') + string(b, 'U') + string(a, 'L') + string(b, 'D');
if (a > 0) return "RL";
if (b > 0) return "UD";
return "";
}
// Độ dài của chuỗi xây từ (a, b)
int lenOf(int a, int b) {
if (a > 0 && b > 0) return 2 * a + 2 * b;
if (a > 0 || b > 0) return 2;
return 0;
}
// Sub 1: vét cạn — thử mọi cặp (a', b') với 0 <= a' <= min(L, R), 0 <= b' <= min(U, D),
// lấy cặp cho chuỗi dài nhất. Dùng khi độ dài s <= 1000
void sub1() {
int A = min(cntL, cntR), B = min(cntU, cntD);
int bestLen = -1, bestA = 0, bestB = 0;
for (int a = 0; a <= A; a++)
for (int b = 0; b <= B; b++)
if (lenOf(a, b) > bestLen) { bestLen = lenOf(a, b); bestA = a; bestB = b; }
string res = build(bestA, bestB);
cout << res.size() << "\n" << res << "\n";
}
// Sub 2: công thức — dùng tối đa số cặp có thể: a = min(L, R), b = min(U, D).
// Khi cả hai đều dương thì 2a + 2b là lớn nhất. Dùng cho mọi độ dài
void sub2() {
string res = build(min(cntL, cntR), min(cntU, cntD));
cout << res.size() << "\n" << res << "\n";
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int q;
cin >> q;
while (q--) {
cin >> s;
cntL = cntR = cntU = cntD = 0;
for (char ch : s) {
if (ch == 'L') cntL++;
else if (ch == 'R') cntR++;
else if (ch == 'U') cntU++;
else if (ch == 'D') cntD++;
}
if (s.size() <= 1000) sub1(); // độ dài nhỏ: vét cạn cho chắc
else sub2(); // độ dài lớn: dùng công thức
}
return 0;
}
Bình luận