Hướng dẫn giải của [2526 KSCUM TT2] Câu 4: DAOTT
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
Dãy ban đầu là ~1, 2, \dots, n~. Mỗi lượt gồm hai phép đảo đoạn ~[u, v]~ rồi ~[l, r]~, lặp đúng ~k~ lượt. Mỗi lượt là cùng một hoán vị cố định của các vị trí.
Sub 1: Mô phỏng — ~O(k \cdot n)~, dùng khi ~k \le 10^3~
Thực hiện đúng ~k~ lần hai phép đảo bằng hàm reverse. Nếu chỉ nộp sub này: đúng 8/20 test.
Sub 2: Lũy thừa hoán vị bằng chu trình — ~O(n)~
Thực hiện một lượt trên dãy ~1..n~ để được hoán vị ~p~ (vị trí ~i~ nhận giá trị từ vị trí ~p_i~). Lặp ~k~ lần tương ứng đi ~k~ bước theo ~p~. Tách ~p~ thành các chu trình; trong chu trình độ dài ~m~, mỗi phần tử chỉ cần đi ~k \bmod m~ bước. Chú ý ~k~ lên tới ~10^9~ nên dùng ~long long~ khi lấy phần dư. Nếu chỉ nộp sub này: đúng 20/20 test.
Chương trình hoàn chỉnh
Main đọc ~n, k, u, v, l, r~ từ file DAOTT.INP; nếu ~k \le 10^3~ gọi sub1, ngược lại gọi sub2. Khi đi thi nên viết như vậy: sub sau có sai hoặc chưa kịp làm thì vẫn ăn điểm sub trước.
#include <bits/stdc++.h>
using namespace std;
int n, u, v, l, r;
long long k;
// Sub 1: mô phỏng trực tiếp k lần — O(k * n), dùng khi k <= 1000
void sub1() {
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) a[i] = i;
for (long long t = 0; t < k; t++) {
reverse(a.begin() + u, a.begin() + v + 1);
reverse(a.begin() + l, a.begin() + r + 1);
}
for (int i = 1; i <= n; i++) printf("%d\n", a[i]);
}
// Sub 2: một lượt (2 thao tác) là một hoán vị p; lặp k lần = lũy thừa hoán vị.
// Tách thành các chu trình, mỗi phần tử đi k mod (độ dài chu trình) bước. O(n)
void sub2() {
vector<int> a(n + 1);
for (int i = 1; i <= n; i++) a[i] = i;
reverse(a.begin() + u, a.begin() + v + 1);
reverse(a.begin() + l, a.begin() + r + 1);
// a[i] = phần tử đứng ở vị trí i sau một lượt: vị trí i nhận giá trị ban đầu a[i]
// Sau mỗi lượt, giá trị ở vị trí i của dãy mới = giá trị ở vị trí a[i] của dãy cũ
vector<int> res(n + 1), vis(n + 1, 0);
for (int i = 1; i <= n; i++) if (!vis[i]) {
vector<int> cyc;
for (int j = i; !vis[j]; j = a[j]) { vis[j] = 1; cyc.push_back(j); }
int m = cyc.size();
for (int t = 0; t < m; t++) res[cyc[t]] = cyc[(t + k) % m];
}
for (int i = 1; i <= n; i++) printf("%d\n", res[i]);
}
int main() {
freopen("DAOTT.INP", "r", stdin);
freopen("DAOTT.OUT", "w", stdout);
scanf("%d %lld %d %d %d %d", &n, &k, &u, &v, &l, &r);
if (k <= 1000) sub1();
else sub2();
return 0;
}
Bình luận