Послідовність Замка та Ключа#12236
Увійти

Послідовність Замка та Ключа (Розбір)

Автор задачі:

Imran AKKI

Підготовлено:

Imran AKKI

Редаговано:

Hasan Saleh (MathModel)

Розв'язок Нам потрібні два однакові кінці та попарно різних символів строго між ними. Еквівалентно: знайти l < r з s_l=s_r так, щоб підрядок s[l+1;r-1]=s_{l+1}s_{l+2}...s_{r-1} містив принаймні різних літер, і серед усіх таких пар повернути ту, де r-l+1 мінімальне.

Зафіксуємо лівий кінець та символ c = s_l. Якщо рухати вправо, то кількість різних літер всередині (l,r) не зменшується при русі . Ця монотонність дозволяє використати двійковий пошук для найменшого значення , яке задовольняє вимогу різних символів для кожного .

Можна рахувати кількість входжень деякої літери за допомогою використовуючи префіксні частоти для 26 літер англійського алфавіту як , тоді для кожної літери , яка зустрічається щонайменше двічі:

  1. Для кожного індексу появи (ліва поява) виконати двійковий пошук серед наступних появ \text{pos}[c][\text{mid}] для найменшого , такого що підрядок s[i+1;r-1] містить різних літер.

  2. Використати для підрахунку різних літер у цьому підрядку; зупинитися, щойно знайдено .

  3. Відстежувати мінімальну довжину підрядка r- i + 1 та відповідні кінці.

// Автор: Imran AKKI (imranakki)
#include <bits/stdc++.h>
#define ll long long
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define lp(i, a, n) for (ll i = a; i < n; i++)
#define MAXN 1000005
#define MOD (ll)(1e9 + 7)
using namespace std;

void solve()
{
    ll n, k; cin >> n >> k;
    string s; cin >> s;

    // індексація з 1!
    vector<vector<ll>> pre(26, vector<ll>(n + 2, 0));
    for(ll d = 0; d < 26; d++) {
        for(ll i = 0; i < n; i++) {
            pre[d][i + 1] = pre[d][i] + ((s[i] - 'a') == d);
        }
    }

    vector<ll> pos[26];
    for(ll i = 0; i < n; i++){
        pos[s[i] - 'a'].push_back(i);
    }

    auto can = [&](ll i, ll l) {
        // i та l --- 0-індексовані
        if(l - i < k + 1) return false;
        ll distinct = 0;
        for(ll d = 0; d < 26; d++) {
            if(pre[d][l] - pre[d][i + 1] > 0) {
                distinct++;
                if(distinct >= k){
                    return true;
                }
            }
        }
        return false;
    };
    ll bestLen = INT_MAX;
    ll bestI = -1, bestJ = -1;
    for(ll c = 0; c < 26; c++) {
        auto &P = pos[c];
        ll m = P.size();
        if(m < 2) continue;

        for(ll x = 0; x < m - 1; x++) {
            ll i = P[x];
            ll l = x + 1, r = m - 1;
            ll best = -1;
            while(l <= r) {
                ll mid = (l + r) >> 1;
                if(can(i, P[mid])) {
                    best = mid;
                    r = mid - 1;
                }else {
                    l = mid + 1;
                }
            }
            if(best != -1  && can(i, P[best]) && P[best] - i + 1 < bestLen) {
                bestLen = min(bestLen, P[best] - i + 1);
                bestI = i;
                bestJ = P[best];
            }
        }
    }

    if(bestI != -1) {
        cout << "YES\n";
        cout << bestI + 1 << " " << bestJ + 1 << "\n";
    } else {
        cout << "NO\n";
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll t; cin >> t;
    while(t--) solve();
    return 0;
}
C++

Складність: \mathcal{O}(n \cdot 26 \cdot \log n)