Конкатенація Насера#12479

Конкатенація Насера (Розбір)

Автор задачі:	Mohammad Nasser (MOAGEZA)
Підготував:	Mohammad Nasser (MOAGEZA)
Відредагував:	Hasan Saleh (MathModel)

Розв'язок

Загальна ідея: Нам потрібно знайти максимальну довжину однорідного підрядка (що складається з однакових символів) серед усіх можливих порядків розташування чотирьох рядків.

Оскільки існує лише $4! = 24$ 4! = 24 можливих перестановки, ми можемо перебрати їх усі.

Для кожної перестановки:

Конкатенуємо чотири рядки у відповідному порядку.
Знаходимо найдовший неперервний підрядок з однакових символів.
Відстежуємо максимум серед усіх перестановок.

Щоб знайти найдовший однорідний підрядок у рядку:

Проходимо по рядку.
Рахуємо послідовні однакові символи.
Оновлюємо максимум при зміні символу.

Ключове спостереження полягає в тому, що при наявності лише 4 рядків і невеликих обмеженнях метод грубої сили є достатньо ефективним.

Розв'язок працює за час $O (4! \cdot n)$ \mathcal{O}(4! \cdot n) на один тест, що спрощується до $O (n)$ , оскільки $4! = 24$ 4! = 24 є константою.

#include <bits/stdc++.h>
using namespace std;

void solve() {
    int n;
    cin >> n;
    vector<string> v(4);
    
    for (int i = 0; i < 4; i++) {
        cin >> v[i];
    }
    
    int ans = 0;
    sort(v.begin(), v.end());
    
    do {
        string temp = "";
        for (int i = 0; i < 4; i++) {
            temp += v[i];
        }
        
        int cnt = 1;
        for (int i = 1; i < temp.size(); i++) {
            if (temp[i] == temp[i - 1]) {
                cnt++;
            } else {
                ans = max(ans, cnt);
                cnt = 1;
            }
        }
        ans = max(ans, cnt);
        
    } while (next_permutation(v.begin(), v.end()));
    
    cout << ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
        cout << '\n';
    }
    return 0;
}