Решил начать решать задачи с архива. Отсортировал по количеству решивших. Дошел до задачи 81A - Плагин. Попытался решить ее сначала в лоб за n^2, не прошло по времени. Перестроил решение, чтобы убирать повторы за один проход, получил сложность n, но все равно получаю TL. Где нужно еще убыстрить решение, чтобы код стал проходить тесты? Так как решивших эту задачу достаточно много, то думаю в моем решении не придется подправлять слишком много... Но мне ничего в голову не идет... :(
(Смотрел http://codeforces.net/search?query=%D0%AF%D0%BD%D0%B4%D0%B5%D0%BA%D1%81 , но ничего не нашел)
Код:(посылка 854500)
Update. Кстати, почему код вставился так криво?(Больше переводов строки, чем я писал) У меня в редакторе темы отображается нормально : http://saveimg.ru/show-image.php?id=82e30ef7f3fe6dc62113a4a5633248e9
- using System;
- using System.Collections.Generic;
- namespace YA2011_1_A
- {
- class Program
- {
- static void Main(string[] args)
- {
- string s = Console.ReadLine();
- Stack<char> s1 = new Stack<char>();
- for (int i = 0; i < s.Length; i++)
- {
- if (s1.Count > 0 && s1.Peek() == s[i])
- {
- s1.Pop();
- }
- else
- {
- s1.Push(s[i]);
- }
- }
- string a = "";
- while (s1.Count > 0)
- {
- a += s1.Pop();
- }
- string a1 = "";
- for (int i = 0; i < a.Length; i++)
- {
- a1 += a[a.Length - 1 - i];
- }
- Console.WriteLine(a1);
- Console.ReadLine();
- }
- }
- }
Как это "в лоб" за n^2? В лоб здесь как раз за n...
Хоть и не знаю особенностей С#, но подозреваю что Ваша программулина тормозит не в основном цикле работы (если он правильно работает), а там где вы строку лепите из стека (ваша конструкция работает за n^2). Используйте что-то типа СтрингБуффер/СтрингБилдер.
(ессно для "лепки" a1 это тоже справедливо, если справедливо для a)
Вот здесь по-моему об этом...
Цитата: "....... там где вы строку лепите из стека (ваша конструкция работает за n^2). "
Да вроде за n...:
1. Записываем из стека элементы в строку - n
2. Реверсируем порядок и записываем в новую строку, т.к. string - константный тип. Тоже n.
Хотя попробую StringBuilder... мало ли...
А по поводу лишних переводов строки в отображении кода в блоге не знаешь ничего?
Update. Исправил тип на StringBuilder, и получил AC. посылка 854679
Чудеса однако.
Чево чудеса-то? Езык знать надо.
Строки в C#, как и в джаве, неизменяемые.
Оператор s += smth на самом деле создаст новую строку, и присвоит ссылку на нее переменной s. То бишь работает это за O(N). А стрингбилдер специально создан для подобных манипуляций со строками, в нем все работает быстро.
Просто потестируйте на досуге скорость работы такой конкатенации:
String s = "";
for (int i = 0; i < 100000; i++) {
s += i;
} // for
Вы убедитесь что она действительно квадратичная - очевидно сама операция s += i; выполняется за O(s.length()), как и в java...
;-)