Giải Bài Tập Chu Ký Hoán Vị - Codeforces Round 797 (Div. 3) F
Đối với các bài toán liên quan đến hoán vị, việc phân tích chu kỳ (cycle) của hoán vị là một hướng tiếp cận hiệu quả. Trong bài toán này, chúng ta có thể hình dung việc biến đổi chuỗi ký tự như một quá trình di chuyển trên đồ thị, nơi mỗi vị trí sẽ quay về vị trí ban đầu sau một số bước nhất định.
Để giải quyết bài toán này, chúng ta có thể sử dụng cấu trúc dữ liệu danh sách liên kết để mô phỏng quá trình di chuyển, đồng thời đếm số bước cần thiết để mỗi vị trí quay về vị trí ban đầu. Kết quả cuối cùng sẽ là bội số chung nhỏ nhất (LCM) của tất cả các bước này.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 200 + 10, MOD = 1e9 + 7;
int permutation[MAXN];
bool visited[MAXN];
vector<int> cycle;
void dfs(int current) {
if (visited[current]) return;
visited[current] = true;
cycle.push_back(current);
dfs(permutation[current]);
}
void solve() {
int n;
string s;
cin >> n >> s;
s = " " + s;
for (int i = 1; i <= n; i++) {
cin >> permutation[i];
visited[i] = false;
}
int result = 1;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
cycle.clear();
dfs(i);
list<char> original, current;
for (auto idx : cycle) {
original.push_back(s[idx]);
}
current = original;
current.push_back(current.front());
current.pop_front();
int steps = 1;
while (original != current) {
current.push_back(current.front());
current.pop_front();
steps++;
}
result = result * steps / __gcd(result, steps);
}
}
cout << result << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test_cases = 1;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}
Tìm Căn Bậc Hai Của Hoán Vị - Educational Codeforces Round 4, E
Bài toán này yêu cầu chúng ta tìm một hoán vị B sao cho B² = A (A là hoán vị cho trước). Giải pháp dựa trên việc phân tích hoán vị thành các chu kỳ và xử lý riêng biệt từng loại chu kỳ (độ dài chẵn và lẻ).
Đối với các chu kỳ có độ dài chẵn, chúng ta ghép từng cặp chu kỳ lại. Đối với các chu kỳ có độ dài lẻ, chúng ta thực hiện một phép biến đổi đặc biệt để tạo ra chu kỳ mới.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e6 + 10, MOD = 1e9 + 7;
int answer[MAXN], permutation[MAXN], visited[MAXN], n;
vector<int> current_cycle;
vector<vector<int>> cycles_by_size[MAXN];
void update_result(vector<int> cycle) {
for (int i = 1; i < cycle.size(); i++) {
answer[cycle[i-1]] = cycle[i];
}
answer[cycle.back()] = cycle[0];
}
void dfs(int node) {
if (visited[node]) return;
visited[node] = 1;
current_cycle.push_back(node);
dfs(permutation[node]);
}
void solve() {
cin >> n;
for (int i = 1; i <= n; i++) {
answer[i] = i;
cin >> permutation[i];
}
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
current_cycle.clear();
dfs(i);
cycles_by_size[current_cycle.size()].push_back(current_cycle);
}
}
for (int size = 1; size <= n; size++) {
if (size % 2 == 0 && cycles_by_size[size].size() % 2 == 1) {
cout << "-1\n";
return;
}
}
for (int size = 1; size <= n; size++) {
if (size % 2 == 1) {
for (auto cycle : cycles_by_size[size]) {
vector<int> new_cycle(cycle.size());
int index = 0;
for (auto node : cycle) {
new_cycle[index % cycle.size()] = node;
index += 2;
}
update_result(new_cycle);
}
} else {
for (int i = 0; i < cycles_by_size[size].size(); i += 2) {
vector<int> cycle1 = cycles_by_size[size][i];
vector<int> cycle2 = cycles_by_size[size][i+1];
vector<int> merged_cycle;
for (int j = 0; j < cycle1.size(); j++) {
merged_cycle.push_back(cycle1[j]);
merged_cycle.push_back(cycle2[j]);
}
update_result(merged_cycle);
}
}
}
for (int i = 1; i <= n; i++) {
cout << answer[i] << " ";
}
cout << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test_cases = 1;
// cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}
Bài Tốnh Hai Băng Màu Sắc - Codeforces Round 789 (Div. 2) E
Bài toán này liên quan đến việc tính toán tổng khoảng cách tuyệt đối tối thiểu khi sắp xếp hai dãy màu sắc. Chúng ta có thể sử dụng kỹ thuật phân tích chu kỳ để giải quyết bài toán này một cách hiệu quả.
Đầu tiên, chúng ta xây dựng đồ thị ánh xạ từ dãy này sang dãy kia. Sau đó, chúng ta phân tích đồ thị này thành các chu kỳ. Với mỗi chu kỳ, chúng ta tính toán khoảng cách tối ưu bằng cách sắp xếp các giá trị một cách xen kẽ giữa giá trị lớn nhất và nhỏ nhất còn lại.
#include <bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int, int> pii;
const int MAXN = 1e5 + 10, MOD = 1e9 + 7;
int sequence_a[MAXN], sequence_b[MAXN], mapping[MAXN];
bool visited[MAXN];
vector<int> cycle;
void dfs(int current) {
if (visited[current]) return;
visited[current] = true;
cycle.push_back(current);
dfs(mapping[current]);
}
int calculate_distance() {
if (cycle.size() == 1) return 0;
vector<int> values;
int min_val = 1, max_val = n;
for (int i = 0; i < cycle.size() - cycle.size() % 2; i++) {
if (i % 2 == 0) {
values.push_back(max_val--);
} else {
values.push_back(min_val++);
}
}
int total_distance = 0;
for (int i = 1; i < values.size(); i++) {
total_distance += abs(values[i] - values[i-1]);
}
total_distance += abs(values.back() - values[0]);
return total_distance;
}
void solve() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
visited[i] = false;
}
for (int i = 1; i <= n; i++) {
cin >> sequence_a[i];
}
for (int i = 1; i <= n; i++) {
cin >> sequence_b[i];
mapping[sequence_a[i]] = sequence_b[i];
}
int total_distance = 0;
for (int i = 1; i <= n; i++) {
if (!visited[i]) {
cycle.clear();
dfs(i);
total_distance += calculate_distance();
}
}
cout << total_distance << '\n';
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int test_cases = 1;
cin >> test_cases;
while (test_cases--) {
solve();
}
return 0;
}