| 1 Хавлявкин Тимофей Сергеевич, 28 февраля 2026 г. 11:39:20 |
| там s.size()-1
|
|
|
| 2 Хавлявкин Тимофей Сергеевич, 28 февраля 2026 г. 11:38:14 |
| #include<iostream> #include<algorithm> #include <map> #include<vector> #include <string> using namespace std; int a[100000+8]; int sum=0,l=0; main() { int n,k; cin >> n>>k; string s; cin >> s; for(int i=0;i<=s.size();i++) { a[i]=-1; } a[0]=0; for(int i=0;i<n;i++) { if(a[i]>-1) { int y[27]; for(int j=0;j<27;j++) { y[j]=0; } for(int j=min(n,i+k);j>i;j--) { if(y[s[j]-'A']==0) {y[s[j]-'A']++; if(a[j]==-1) { if(s[i]!=s[j]) { a[j]=a[i]+1; } else { a[j]=a[i]; } } else { if(s[i]!=s[j]) { a[j]=min(a[i]+1,a[j]); } else { a[j]=min(a[i],a[j]); } } } } } } cout <<a[s.si
|
|
|
| 3 Довлетмурадов Шохрат Довлетмурадович, 18 декабря 2024 г. 11:29:51 |
| Что 21м
|
|
|
| 4 Кемалов Нуры, 25 августа 2021 г. 22:04:17 |
| Задача хороша тем что ее можно решить нескольким способом а проходит не всеми..
|
|
|
| 5 Нуриев Амир Равилевич, 23 января 2021 г. 21:40:40 |
| Есть решение за O(n), не зависящее от размера алфавита.
|
|
|
| 6 Зинов Вадим, 05 августа 2020 г. 22:39:35 |
| Боюсь напугать любителей ДО, но асимптотика - O(N*алфавит), где алфавит - количество различных букв во входящих данных.
|
|
|
| 7 Даурен, 21 мая 2020 г. 17:35:13 |
| Дерево отрезков получил TL Написал set и все работает
|
|
|
| 8 Якина Ангелина Ивановна, 27 июня 2019 г. 15:46:50 |
| Эта задача, по-моему, даже легче, чем "Компьютерная игра" :)
|
|
|
| 9 Драганов Александр Андреевич, 04 января 2018 г. 21:28:55 |
Можно решить за О(N), но я решил за О(N * log(n)), так как я ленивый.
0.3 секунды.
|
|
|
| 10 Линар Хилажев, 13 июля 2017 г. 10:25:26 |
| Решал O(n*k) с некоторой оптимизацией.
|
|
|
| 11 Харальд Синезубый, 19 февраля 2017 г. 18:47:32 |
| Не нужно тут дерево отрезков использовать
|
|
|
| 12 Юсупов Темиржан Нурланович, 06 сентября 2016 г. 13:01:24 |
| Дерево отрезков тащит :D
|
|
|
| 13 Юсупов Темиржан Нурланович, 05 сентября 2016 г. 12:47:35 |
| Ребята, не пишите за квадрат, уже пофиксили)
|
|
|
| 14 Каракотов Ахмат Асланович, 10 января 2016 г. 23:51:43 |
| Писать дерево отрезков там, где простенькая динамика на 300 символов, это извращение
|
|
|
| 15 Скаковский Юрий Евгеньевич, 29 сентября 2015 г. 15:12:20 |
| За линию так и не понял, как. segment_tree, ACCEPTED, nlogn :)
|
|
|
| 16 Прогер, 27 июня 2015 г. 0:01:33 |
WHAT????
Один break и вместо TL21 AC 0.17с
|
|
|
| 17 Луффи, 17 июня 2015 г. 11:17:43 |
| Подсказка TLE 21 : Break
|
|
|
| 18 Удовин Иван Анатольевич, 20 мая 2015 г. 18:38:00 |
| Интересная задача. Интересность ее заключается в том, что входные данные имеют особые ограничания (кол-во букв алфавита). Решение естественно с такими ограничениями O(26*N) = O(N)
|
|
|
| 19 Гриня, 19 мая 2015 г. 16:20:42 |
| Квадрат заходит, печально..
|
|
|
| 20 Петров Владимир Алексеевич, 19 мая 2015 г. 15:34:58 |
| Без проблем зашло O(N*log k), правда с константой равной 26? при желании можно ещё больше уменьшить асимптотику. Так что задача не сложная, если даже до O(N) не догадаться.
|
|
|
