Hướng dẫn giải của Bedao Regular Contest 02 - 8ROOKS
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.
Tác giả:
Subtask 1:
Nếu biểu diễn cách xếp cờ bằng ~1~ chuỗi có ~8~ ký tự như trong đề thì với mọi cách xếp cờ thỏa mãn chuỗi này luôn là ~1~ hoán vị của các số từ ~1 → 8~.
Sinh mọi hoán vị của các số từ ~1 → 8~ rồi đếm số thao tác ít nhất để xếp bàn cờ thành ~1~ trong ~8!~ hoán vị
Độ phức tạp: ~O(8! \times 8 \times q)~.
Subtask 2:
- k = 1
Gọi ~cnt_i~ là số con xe nằm ở hàng ~i~.
Mỗi lượt di chuyển của một con xe tương ứng với chuyển từ ~cnt_i~ sang ~cnt_{i-1}~ hoặc ~cnt_i~ sang ~cnt_{i+1}~ đúng ~1~ đơn vị ( Chú ý nếu ~i=1~ thì chuyển qua trái sẽ là chuyển tới ~cnt_8~, tương tự ~i=8~ chuyển qua phải sẽ là ~cnt_1~ )
Xem các quân xe là cục đá, lúc này, bài toán trở thành cho một vòng tròn có độ dài ~8~, ô thứ ~i~ có ~cnt_i~ cục đá. Mỗi lần có thể chọn ~i~ bất kì, chuyển ~1~ cục đá qua trái hoặc phải của ~i~ trên vòng tròn. Tính số bước ít nhất để ~cnt_i = 1 (1 \leq i \leq 8)~
Giả sử, bài toán ở trên một dãy chứ không phải vòng tròn. Ta sẽ có thuật tham lam như sau:
Nhận xét: để ~cnt_1 = 1~, thì nếu ~cnt_1 = 0~, thì ~cnt_1~ chỉ có thể nhận đá ở những ô bên phải. Nếu ~cnt_1 > 1~ thì phải chuyển đi ~cnt_1 - 1~ cục đá đang ở ô này qua các ô sau.
Từ nhận xét trên, ta duyệt ~i~ từ ~1~ đến ~8~:
- Ta lưu biến ~num~ là tượng trưng cho số đá đang ở ~i~ cần di chuyển. Nếu ~num < 0~ nghĩa là cần chuyển từ phải sang, ngược lại là cần chuyển từ trái sang. Gọi ~ans~ là kết quả, ta có:
~num = num + cnt_i - 1~
~ans = ans + |num|~
Đó là thực hiện trên dãy, còn trên vòng tròn thì sao ?
Với những bài thao tác trên vòng tròn, ta sẽ nghĩ tới việc cắt vòng tròn ra và thực hiện trên một dãy. Ta sẽ duyệt ~i~ từ ~1~ đến ~8~ thể hiện cho mình sẽ không được chuyển qua trái ở thằng ~i~. Và bài toán lại trở thành bài trên dãy, ta sẽ tính và lấy min kết quả.
Độ phức tạp: ~O(Q \times 8^2)~
Subtask 3:
Sử dụng quy hoạch động trạng thái:
Vì bàn cờ tương đối nhỏ, chúng ta có thể sử dụng bitmask để biểu diễn các quân xe, nếu dòng ~i~ có quân xe thì bit thứ ~i = 1~, ngược lại nếu dòng i trống thì bit thứ ~i = 0~.
Gọi ~dp[n][mask]~ là số thao tác tối thiểu để xếp lại ~n~ cột đầu tiên của bàn cờ sao cho:
- Không quân xe nào cùng dòng trong ~n~ cột đầu tiên.
- bitmask biểu diễn ~n~ cột đầu tiên = mask.
Dễ thấy ~n~ bằng số bit bật của mask nên trong thực tế chúng ta có thể vứt chiều này đi, đáp án sau cùng là ~dp[2^8-1]~. Thuật này chạy trong khoảng ≈ ~1024~ phép tính.
Ta tiến hành loại bỏ trường hợp thừa: vì số query lên tới ~1000000~, nếu sử dụng dp bitmask cho mọi query thì không thể đảm bảo chương trình chạy trong ~1~ giây.
- Nhận xét: ~2~ chuỗi biểu diễn bàn cờ mà là hoán vị của nhau thì đáp án luôn giống nhau (ví dụ : ~12121212~ và ~22112211~, ~12345672~ và ~12234567~,...).
- Do mọi chuỗi đều có thể xếp thành một chuỗi không giảm (ví dụ : ~12121212~ thành ~11112222~, ~12345672~ thành ~12234567~,...) nên ta chỉ xét các chuỗi không giảm khác nhau, bằng công thức chia kẹo ta biết có khoảng ~6500~ chuỗi như thế.
Vậy từ các nhận xét trên ta có thể:
- Duy trì ~1~ map ( STL của C++ ) để lưu kết quả của các truy vấn cũ.
- Với mỗi truy vấn, xếp lại chuỗi thành một chuỗi không giảm, gọi chuỗi này là ~S~.
- Nếu ~S~ chưa từng xuất hiện trong map ta chạy dp bitmask rồi nhét kết quả vào map theo dạng key = ~S~ và value = ~dp[2^8-1]~, thao tác này phải chạy tối đa ~6500~ lần.
- Nếu ~S~ đã từng xuất hiện, ta lấy value kết quả tương ứng với key = ~S~ trong thời gian tối đa là ~\log_2{(6500)}~.
Độ phức tạp: ~O(6500 \times 1024 + \log_2{(6500)} \times q)~.
Sử dụng tham lam:
- k ~\leq~ ~10^9~
Xét các ô từ ~0~ đến ~7~
Nhận thấy từ phần tử ~i~ thì ta sẽ đi được tới ~(i + k) \% 8~, ~(i + 2 * k) \% 8~, ~\dots~, cho tới khi quay lại ô ~i~.
Ta sẽ tách các dãy như trên ra thành một số dãy độc lập với nhau. Và mỗi dãy làm thuật giống với với subtask 2: k = 1.
Lưu ý:
- Để tăng tốc độ xử lý, vì mọi chuỗi có ~8~ ký tự trong khoảng từ ~1 → 8~, bạn nên chuyển chúng về dạng int trước khi lưu vào map.
- Bài toán có thể AC hoàn toàn bằng tham lam, quy hoạch động, BFS và meet in the middle.
Code mẫu
#include <bits/stdc++.h> using namespace std; #define fo(i, a, b) for(int i = a; i <= b; i++) #define _fo(i, a, b) for(int i = a; i >= b; i--) #define foa(i, a) for (auto &i : a) #define sz(a) ((int) a.size()) #define all(a) begin(a), end(a) #define fi first #define se second #define pb(x) push_back(x) #define mk(x, y) make_pair(x, y) typedef long long ll; typedef pair<ll, ll> pll; typedef vector<ll> vl; typedef pair<int, int> pii; typedef vector<int> vi; const int MAX = (1<<10); const int LOG = 20; const int MOD = 1e9+7; const ll INF = 1e7+5; int q, k; int cnt[9], a[9]; int lg[MAX], bcnt[MAX], dist[9], f[MAX]; map<int, int> result; void precompute() { fo(i, 2, MAX-1) lg[i] = lg[i/2]+1; fo(i, 1, MAX-1) bcnt[i] = bcnt[i^(i&-i)]+1; int pt = 0, cnt = 0; fill(dist, dist+8, 100); while(dist[pt] == 100) { dist[pt] = cnt; pt = (pt+k) % 8; cnt++; } } int solve() { int goal = (1<<8)-1; fo(i, 1, goal) { f[i] = 100; int temp = i; while(temp > 0) { int curr = temp&-temp, d = abs(lg[curr]-a[bcnt[i]]); f[i] = min(f[i], f[i^curr]+min(dist[d], dist[8-d])); temp -= curr; } } return f[goal]; } int get(int val) { while(val > 0) { cnt[val % 10]++; val /= 10; } int nval = 0, p = 0; fo(i, 1, 8) { while(cnt[i] > 0) { p++; a[p] = i; nval = nval*10+i; cnt[i]--; } } if(result.count(nval)) return result[nval]; int temp = solve(); if(temp == 100) temp = -1; result.insert(mk(nval, temp)); return temp; } int main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin >> q >> k; precompute(); while(q--) { int val; cin >> val; cout << get(val) << "\n"; } }
Bình luận