Блог пользователя fsb4000

Автор fsb4000, 13 лет назад, По-русски

Решил начать решать задачи с архива. Отсортировал по количеству решивших. Дошел до задачи 81A - Плагин. Попытался решить ее сначала в лоб за n^2, не прошло по времени. Перестроил решение, чтобы убирать повторы за один проход, получил сложность n, но все равно получаю TL. Где нужно еще убыстрить решение, чтобы код стал проходить тесты? Так как решивших эту задачу достаточно много, то думаю в моем решении не придется подправлять слишком много... Но мне ничего в голову не идет... :(
(Смотрел http://mirror.codeforces.com/search?query=%D0%AF%D0%BD%D0%B4%D0%B5%D0%BA%D1%81 , но ничего не нашел)
Код:(посылка 854500)

  1. using System;
  2. using System.Collections.Generic;

  3. namespace YA2011_1_A
  4. {
  5.     class Program
  6.     {
  7.         static void Main(string[] args)
  8.         {
  9.             string s = Console.ReadLine();          
  10.             Stack<char> s1 = new Stack<char>();

  11.             for (int i = 0; i < s.Length; i++)
  12.             {
  13.                 if (s1.Count > 0 && s1.Peek() == s[i])
  14.                 {
  15.                     s1.Pop();
  16.                 }
  17.                 else
  18.                 {
  19.                     s1.Push(s[i]);
  20.                 }
  21.             }
  22.             string a = "";
  23.             while (s1.Count > 0)
  24.             {
  25.                 a += s1.Pop();
  26.             }
  27.             string a1 = "";
  28.             for (int i = 0; i < a.Length; i++)
  29.             {
  30.                 a1 += a[a.Length - 1 - i];
  31.             }
  32.             Console.WriteLine(a1);
  33.          
  34.             Console.ReadLine();
  35.         }
  36.     }
  37. }
Update. Кстати, почему код вставился так криво?(Больше переводов строки, чем я писал) У меня в редакторе темы отображается нормально : http://saveimg.ru/show-image.php?id=82e30ef7f3fe6dc62113a4a5633248e9


  • Проголосовать: нравится
  • -11
  • Проголосовать: не нравится

13 лет назад, # |
Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

Как это "в лоб" за n^2? В лоб здесь как раз за n...

Хоть и не знаю особенностей С#, но подозреваю что Ваша программулина тормозит не в основном цикле работы (если он правильно работает), а там где вы строку лепите из стека (ваша конструкция работает за n^2). Используйте что-то типа СтрингБуффер/СтрингБилдер.

(ессно для "лепки" a1 это тоже справедливо, если справедливо для a)

Вот здесь по-моему об этом...

13 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

Цитата: "....... там где вы строку лепите из стека (ваша конструкция работает за n^2). "
     Да вроде за n...:
1. Записываем из стека элементы в строку - n
2. Реверсируем порядок и записываем в новую строку, т.к. string - константный тип. Тоже n.
 Хотя попробую StringBuilder... мало ли...
А по поводу лишних переводов строки в отображении кода в блоге не знаешь ничего?

Update. Исправил тип на StringBuilder, и получил AC. посылка 854679
Чудеса однако.



  • 13 лет назад, # ^ |
      Проголосовать: нравится +1 Проголосовать: не нравится

    Чево чудеса-то? Езык знать надо.

    Строки в C#, как и в джаве, неизменяемые.

    Оператор s += smth на самом деле создаст новую строку, и присвоит ссылку на нее переменной s. То бишь работает это за O(N). А стрингбилдер специально создан для подобных манипуляций со строками, в нем все работает быстро.

  • 13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится
    Да вроде за n

    Просто потестируйте на досуге скорость работы такой конкатенации:
    String s = "";
    for (int i = 0; i < 100000; i++) {
        s += i;
    } // for

    Вы убедитесь что она действительно квадратичная - очевидно сама операция s += i; выполняется за O(s.length()), как и в java...
13 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится
Кроме СтрингБилдера, стек можно на массиве сделать, тоже увеличит скорость.