Решение задачи Общие префиксы с Codeforces

С пояснением   Просмотров: 1222

Длина самого длинного общего префикса двух строк s=s1s2…sn и t=t1t2…tm определяется как наибольшее целое число k (0≤k≤min(n,m)) такое, что s1s2…sk равняется t1t2…tk.

У Коалы Коа изначально есть n+1 строка s1,s2,…,sn+1.

Для каждого i (1≤i≤n) она вычислила ai — длину самого длинного общего префикса si и si+1.

Несколько дней спустя Коа нашла эти числа, но не могла вспомнить строки.

Поэтому Коа хотела бы найти какие-нибудь строки s1,s2,…,sn+1, которые дали бы числа a1,a2,…,an. Можете ли вы ей помочь?

Если ответов несколько, выведите любой. Можно показать, что для данных ограничений ответ всегда существует.

Код 

#include <bits/stdc++.h>

using namespace std;
void solve(){
    int n, mx = 0;
    cin >> n;
    vector<int> a(n);
    for(int i = 0; i < n; ++i){
        cin >> a[i];
        mx = max(mx, a[i]);
    }
    string s = "";
    if(mx)
        s.insert(0, mx, 'a');
    else
        s = "a";
    cout << s << endl;
    for(int i = 0; i < a.size(); ++i){
        if(s[a[i]] == 'a')
            s[a[i]] = 'b';
        else
            s[a[i]] = 'a';
        cout << s << endl;
    }
}
int main()
{
    int t;
    cin >> t;
    while(t--){
        solve();
    }

    return 0;
}

         

Администратор Photo Автор: Администратор


Пояснение к задаче

4
1 2 4 2
aaaa
abaa
abbb
abbb
abaa


Комментарии

Чтобы написать комментарии вам нужно войти в систему или зарегистрироваться



info@mycod.net   Карта сайта   Правообладателям
Заявка на расчет
×

или напишите нам прямо сейчас:

Написать в MAX
Написать в Telegram
Написать в WhatsApp