Hướng dẫn giải của Bedao Regular Contest 04 - ACCIO


Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
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ả: bedao

Gọi hai chữ cái xuất hiện trong hai xâu đã cho lần lượt là AB.

Dễ thấy độ dài hai xâu phải bằng nhau và số lần xuất hiện của A trong hai xâu đã cho phải bằng nhau. Nếu không đáp án sẽ là ~-1~.

Gọi các vị trí xuất hiện của A trong xâu ~s~ là ~x_1, x_2, \ldots, x_k~ và trong xâu ~t~ là ~y_1, y_2, \ldots, y_k~.

Đáp án của bài toán là ~\sum\limits_{i = 1}^{k} |x_i - y_i|~.

Dễ thấy đây là đáp án bé nhất có thể (không có bước nào thừa - đổi chỗ hai kí tự A). Ta có thể tạo dãy các bước di chuyển như sau để đạt đáp án tối ưu:

  • Nếu tồn tại ~i~ sao cho ~x_i > y_i~: Gọi ~p~ là giá trị bé nhất sao cho ~x_p > y_p~. Ta sẽ sử dụng ~x_q - y_q~ bước để di chuyển cho chúng đúng vị trí.
  • Nếu không: Gọi ~q~ là giá trị lớn nhất sao cho ~x_q < y_q~. Ta sẽ sử dụng ~y_q - x_q~ bước để di chuyển cho chúng đúng vị trí.

Code mẫu

/*#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2,fma")*/

#include <bits/stdc++.h>

#define for1(i,a,b) for (int i = a; i <= b; i++)
#define for2(i,a,b) for (int i = a; i >= b; i--)
#define int long long

#define sz(a) (int)a.size()
#define pii pair<int,int>
#define pb push_back

/*
__builtin_popcountll(x) : Number of 1-bit
__builtin_ctzll(x) : Number of trailing 0
*/

const long double PI = 3.1415926535897932384626433832795;
const int INF = 1000000000000000000;
const int MOD = 1000000007;
const int MOD2 = 1000000009;
const long double EPS = 1e-6;

using namespace std;

string s, t;
map<char, int> mp;
vector<int> v1, v2;
int res;

signed main() {

    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    // freopen("cf.inp", "r", stdin);
    // freopen("cf.out", "w", stdout);

    cin >> s >> t;

    for (auto f : s) mp[f]++;
    for (auto f : t) mp[f]--;

    for (auto p : mp) if (p.second != 0) {
        cout << -1;
        return 0;
    }

    if (sz(s) != sz(t)) {
        cout << -1;
        return 0;
    }

    for1(i,0,sz(s) - 1) if (s[i] == s[0]) v1.push_back(i);
    for1(i,0,sz(t) - 1) if (t[i] == s[0]) v2.push_back(i);

    for1(i,0,sz(v1) - 1) res += abs(v1[i] - v2[i]);
    cout << res;

}

Bình luận

Hãy đọc nội quy trước khi bình luận.


Không có bình luận tại thời điểm này.