Hướng dẫn cho Số đối xứng (TS10 LQĐ, Đà Nẵng 2021)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: BaoJiaoPisu

\(\color{#008b8b}{\text{Thuật toán chuẩn}}\)

  • Ý tưởng: Một số palidrome khi đi từ vị trí chính giữa qua hai bên thì cũng sẽ tạo ra được những số palindrome.

Từ đó ta có cách tiếp cận rằng xét ở vị trí i, ta đi về hai bên của \(i\) cho đến khi nào hai phần tử hai bên không còn bằng nhau

Lúc đó nếu tiếp tục đi qua cũng sẽ không thể tạo được số palindrome mà có trung tâm là \(i\)

Xét đến độ phức tạp cao nhất có thể xảy ra là \(2 * 2 * (n / 2) * (n / 2 + 1) / 2 = O(n * (n + 2) / 2)\)

  • Chú ý 1 : Bỏ qua các số 0 vô nghĩa

  • Chú ý 2 : Nếu có nhiều số có cùng độ dài, ta ưu tiên số có thứ tự từ điển cao hơn

\(\color{green}{\text{Code tham khảo }}\):

C++
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define pf push_front
#define popb pop_back
#define popf pop_front
#define ins insert
#define pq priority_queue
#define minele min_element
#define maxele max_element
#define lb lower_bound //first pos >= val
#define ub upper_bound // first pos > val
#define cnt_bit __builtin_popcount
#define debug(...) " [" << #__VA_ARGS__ ": " << (__VA_ARGS__) << "] "
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;


int d4x[4] = {1, 0, -1, 0}; int d4y[4] = {0, 1, 0, -1};
int d8x[8] = {0, 1, 1, 1, 0, -1, -1, -1};
int d8y[8] = {1, 1, 0, -1, -1, -1, 0, 1};

const ll oo = 1e18;
const ll maxN = 1e6;

/* Author : Le Ngoc Bao Anh, 10A5, LQD High School for Gifted Student */

void maximize(int &a, int b) {
    a = max(a, b);
}

void minimize(int &a, int b) {
    a = min(a, b);
}

void solve() {
    string s; cin >> s;
    struct T {
        int L, R;
    };
    vector<T> good;
    int n = s.size(), len = 0;
    for(int i = 0; i < n; i++) {
        for(int j = 1; i - j >= 0, i + j < n; j++) {
            if(s[i - j] == s[i + j]) {
                if(s[i - j] != '0') {
                    if(len < (2 * j + 1)) {
                        len = 2 * j + 1;
                        good.clear();
                        good.pb({i - j, i + j});
                    } else {
                        if(len == 2 * j + 1) {
                            good.pb({i - j, i + j});
                        }
                    }
                }
            } else break;
        }

        for(int j = 1; i - j >= 0, i + j - 1 < n; j++) {
            if(s[i - j] == s[i + j - 1]) {
                if(s[i - j] != '0') {
                    if(len < (2 * j)) {
                        len = 2 * j;
                        good.clear();
                        good.pb({i - j, i + j - 1});
                    } else {
                        if(len == 2 * j) {
                            good.pb({i - j, i + j - 1});
                        }
                    }
                }
            } else break;
        }
    }

    if(!len) {
        cout << 1 << endl << 0;
        return;
    }
    cout << len << endl;
    string ans = "";
    for(int i = 0; i < len; i++) ans += '0';
    for(int i = 0; i < good.size(); i++) {
        int L = good[i].L, R = good[i].R;
        string curr = "";
        for(int j = L; j <= R; j++) curr += s[j];
        if(ans < curr) ans = curr;
    }

    cout << ans;
}

int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("intput.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
    #else 
    //online
    #endif

    int tc = 1, ddd = 0;
    // cin >> tc;
    while(tc--) {
        //ddd++;
        //cout << "Case #" << ddd << ": ";
        solve();
    }
}

Bình luận

Không có bình luận nào.