fsb4000's blog

By fsb4000, 13 years ago, In Russian

Решил начать решать задачи с архива. Отсортировал по количеству решивших. Дошел до задачи 81A - Плагин. Попытался решить ее сначала в лоб за n^2, не прошло по времени. Перестроил решение, чтобы убирать повторы за один проход, получил сложность n, но все равно получаю TL. Где нужно еще убыстрить решение, чтобы код стал проходить тесты? Так как решивших эту задачу достаточно много, то думаю в моем решении не придется подправлять слишком много... Но мне ничего в голову не идет... :(
(Смотрел http://codeforces.net/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


  • Vote: I like it
  • -11
  • Vote: I do not like it