Hướng dẫn giải của Chuỗi hạt bồ đề
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.
Lời giải này đang bị ẩn cho đến khi bạn chọn mở ra.
Chúng tôi khuyên bạn nên tự thử giải bài trước. Việc mở lời giải có thể làm lộ mất ý tưởng chính trước khi bạn có cơ hội tự giải.
Bạn phải đăng nhập để mở lời giải này.
Đăng nhậpTác giả: ,
Editorial for ptit009: Chuỗi hạt bồ đề
Hiểu bài toán
Bài toán yêu cầu tìm số bước tối thiểu để biến đổi n chuỗi hạt thành một chuỗi giống hệt nhau bằng cách thực hiện thao tác 'dời hạt từ đầu về cuối' (cyclic shift). Mỗi bước dời, ký tự đầu tiên được chuyển xuống cuối chuỗi. Nếu không thể biến đổi tất cả chuỗi về cùng một chuỗi, output là -1.
Ví dụ: "ryuu" có thể trở thành "yuur" sau 1 bước (dời 'r' xuống cuối).
Giả sử chuỗi đích là S. Với mỗi chuỗi Ai ban đầu, có thể có nhiều cách dời để được S. Nếu ta chọn S là một trong các chuỗi ban đầu, số bước để biến đổi chuỗi Aj thành S là số lần dời cần thiết để đưa Aj về S. Số bước này tương ứng với độ lệch chu kỳ (cyclic shift offset) giữa Aj và S.
Đề bài yêu cầu chọn một chuỗi đích (không nhất thiết phải là chuỗi ban đầu, nhưng kết quả sẽ là tối ưu nếu chọn một trong các chuỗi ban đầu làm đích) sao cho tổng số bước biến đổi của các chuỗi còn lại về nó là nhỏ nhất.
Các cách tiếp cận
Cách Brute Force (Duyệt chuỗi đích)
#include <stdio.h>
#include <string.h>
#include <limits.h>
int main() {
int n;
scanf("%d", &n);
char s[55][55];
for (int i = 0; i < n; i++) {
scanf("%s", s[i]);
}
int len = strlen(s[0]);
int min_total = INT_MAX;
int possible = 0;
// Duyệt từng chuỗi làm chuỗi đích
for (int i = 0; i < n; i++) {
int current_total = 0;
int ok = 1;
for (int j = 0; j < n; j++) {
if (i == j) continue;
// Tạo chuỗi kép để kiểm tra cyclic shift
char double_s[110];
strcpy(double_s, s[j]);
strcat(double_s, s[j]);
// Tìm vị trí của chuỗi đích trong chuỗi kép
char *ptr = strstr(double_s, s[i]);
if (ptr == NULL) {
ok = 0;
break;
}
int shift = (int)(ptr - double_s);
// Chỉ chấp nhận nếu shift < len (để tránh lấy kết quả từ phần thứ hai của chuỗi kép không cần thiết)
// và phải khớp đúng độ dài len
if (shift >= len || strncmp(ptr, s[i], len) != 0) {
ok = 0;
break;
}
current_total += shift;
}
if (ok) {
possible = 1;
if (current_total < min_total) {
min_total = current_total;
}
}
}
if (!possible) printf("-1");
else printf("%d", min_total);
return 0;
}
- Time Complexity: O(n^2 * L^2)
- Space Complexity: O(L)
Phương pháp này giả định rằng chuỗi đích cuối cùng phải là một trong các chuỗi ban đầu (điều này luôn đúng để tối thiểu hóa số bước).
- Duyệt qua từng chuỗi
s[i]trong danh sách để thử làm chuỗi đích. - Với mỗi chuỗi đích
s[i], tính tổng số bước cần thiết để biến đổi tất cả các chuỗi khács[j]vềs[i]. - Để biến đổi
s[j]thànhs[i], ta cần tìm số lần dời (shift) cần thiết. Ta ghéps[j]với chính nó thành một chuỗi képtmp. - Nếu
s[i]xuất hiện trongtmp, vị trí xuất hiện chính là số bước dời. - Nếu có bất kỳ chuỗi
s[j]nào không thể biến đổi thànhs[i], thìs[i]không thể là chuỗi đích chung. - Cập nhật tổng số bước nhỏ nhất.
Cách Optimized Brute Force
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <limits.h>
int calculate_shift(const char *src, const char *dest, int len) {
char buffer[102];
strcpy(buffer, src);
strcat(buffer, src);
for (int k = 0; k < len; k++) {
if (strncmp(buffer + k, dest, len) == 0) {
return k;
}
}
return -1;
}
int main() {
int n;
scanf("%d", &n);
char s[55][55];
for (int i = 0; i < n; i++) scanf("%s", s[i]);
int len = strlen(s[0]);
int min_total = INT_MAX;
int possible = 0;
// Kiểm tra tính tương đồng trước (tùy chọn nhưng cần thiết cho logic)
// Đảm bảo tất cả chuỗi đều thuộc cùng một chu kỳ
// Logic kiểm tra trong vòng lặp dưới đã đủ
for (int i = 0; i < n; i++) {
int total = 0;
int ok = 1;
for (int j = 0; j < n; j++) {
if (i == j) continue;
int shift = calculate_shift(s[j], s[i], len);
if (shift == -1) {
ok = 0;
break;
}
total += shift;
}
if (ok) {
possible = 1;
if (total < min_total) min_total = total;
}
}
if (!possible) printf("-1");
else printf("%d", min_total);
return 0;
}
- Time Complexity: O(n^2 * L)
- Space Complexity: O(L)
Đây là phiên bản tối ưu hơn của Brute Force. Thay vì dùng strstr (tùy thuộc thư viện, có thể chậm), ta tự viết vòng lặp so sánh thủ công.
- Tạo chuỗi kép
src + src. - Duyệt
ktừ 0 đếnlen-1để kiểm tra xemdestcó nằm bắt đầu từ vị tríkcủa chuỗi kép không. - Nếu khớp, trả về
k. - Nếu duyệt hết mà không tìm thấy, trả về -1.
Cách này đảm bảo độ phức tạp ổn định O(n^2 * L).
Cách Direct Calculation (Most Optimal)
#include <stdio.h>
#include <string.h>
#include <limits.h>
int n;
char s[55][55];
int len;
// Kiểm tra xem các chuỗi có thể biến đổi về nhau không
int check_compatibility() {
char temp[110];
// Lấy chuỗi đầu tiên làm tham chiếu
strcpy(temp, s[0]);
strcat(temp, s[0]);
for (int i = 1; i < n; i++) {
if (strstr(temp, s[i]) == NULL) return 0;
}
return 1;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) scanf("%s", s[i]);
len = strlen(s[0]);
// Bước 1: Kiểm tra tính khả thi
if (!check_compatibility()) {
printf("-1");
return 0;
}
int min_total = INT_MAX;
// Bước 2: Duyệt qua tất cả các vị trí shift có thể của chuỗi đầu tiên làm chuỗi đích
// Thay vì chỉ chọn 1 trong n chuỗi, ta xét tất cả các biến thể cyclic shift của chuỗi đầu tiên
// (hoặc đơn giản là duyệt tất cả chuỗi ban đầu cũng đủ, nhưng duyệt all shifts đảm bảo tìm đúng min)
// Thực tế, chỉ cần duyệt các chuỗi ban đầu là đủ vì độ ưu tiên.
for (int i = 0; i < n; i++) {
int current_sum = 0;
for (int j = 0; j < n; j++) {
if (i == j) continue;
// Tính offset giữa s[j] và s[i]
// Tạo s[j] + s[j]
char temp_concat[110];
strcpy(temp_concat, s[j]);
strcat(temp_concat, s[j]);
// Tìm s[i] trong s[j]+s[j]
// Chỉ cần tìm vị trí đầu tiên (< len)
int offset = -1;
for (int k = 0; k < len; k++) {
if (strncmp(temp_concat + k, s[i], len) == 0) {
offset = k;
break;
}
}
current_sum += offset;
}
if (current_sum < min_total) min_total = current_sum;
}
printf("%d", min_total);
return 0;
}
- Time Complexity: O(n^2 * L)
- Space Complexity: O(L)
Đây là phương pháp trực tiếp và tối ưu nhất.
Kiểm tra tính khả thi: Kiểm tra xem tất cả các chuỗi có phải là các cyclic shift của nhau không. Có thể làm bằng cách ghép chuỗi đầu tiên với chính nó và kiểm tra xem các chuỗi khác có nằm trong đó không. Nếu có chuỗi không khớp, in -1.
Tìm số bước tối thiểu:
- Giả sử chuỗi đích là
s[i](một trong các chuỗi ban đầu). - Với mỗi chuỗi
s[j], số bước để biến đổis[j]vềs[i]là độ lệch chu kỳ giữa chúng. - Để tính độ lệch, ta ghép
s[j]vớis[j]thànhtmp. Nếus[i]nằm trongtmptại vị trík, thìs[j]cầnkbước dời để thànhs[i]. - Tong số bước để biến đổi tất cả về
s[i]là tổng cácknày. - Ta lặp qua tất cả
s[i]để tìm tổng nhỏ nhất.
- Giả sử chuỗi đích là
Lưu ý: Bài này có thể tối ưu hơn bằng cách chuẩn hóa chuỗi, nhưng với n, L <= 50, cách này hoàn toàn đủ nhanh.
Phân tích độ phức tạp
| Cách tiếp cận | Time | Space | Tên |
|---|---|---|---|
| 1 | O(n^2 * L^2) | O(L) | Brute Force (Duyệt chuỗi đích) |
| 2 | O(n^2 * L) | O(L) | Optimized Brute Force |
| 3 | O(n^2 * L) | O(L) | Direct Calculation (Most Optimal) |
Bài học kinh nghiệm
- Thao tác 'dời đầu về cuối' tạo thành nhóm xoay chu kỳ (cyclic group). Hai chuỗi có thể biến đổi cho nhau iff chúng có cùng ký tự và là các xoay của nhau.
- Chuỗi đích tối ưu để tối thiểu hóa tổng số bước luôn là một trong các chuỗi ban đầu.
- Để tính số bước dời giữa chuỗi A và chuỗi B, ta ghép A với chính nó (A+A) và tìm B trong chuỗi ghép đó. Vị trí tìm thấy chính là số bước.
Lỗi thường gặp
- Quên kiểm tra xem các chuỗi có thực sự biến đổi được cho nhau không. Nếu chỉ đơn giản tìm offset mà không kiểm tra, có thể bỏ qua trường hợp không tìm thấy (offset = -1).
- Lỗi truy cập mảng khi sử dụng
strcatvào mảng chưa đủ kích thước (cần ít nhất2*L+1) - Sai lệch khi đếm số bước (ví dụ: dời 1 lần để từ 'ab' thành 'ba', offset tìm được là 1, đúng).
Bình luận