竟然会超时，WHY?

Question

题目：http://acm.timus.ru/problem.aspx?space=1&num=1209
这样写会超时？有些搞不明白了。。
大伙看看是什么原因？
也顺便说说有没有什么更好更快的方法。。using System;namespace ConsoleApplication1
{
    class Program
    {
        static void Main(string[] args)
        {
            int count = int.Parse(Console.ReadLine());
            long[] num = new long[count];
            for(int i=0;i<count;i++)
                num[i] = long.Parse(Console.ReadLine());
            string result = string.Empty;
            DateTime dt1 = DateTime.Now;
            foreach (long n in num)
                result += ZeroOrOne(n) + " ";
            Console.Write(result.Trim());
        }        static int ZeroOrOne(long number)
        {
            double d = Math.Sqrt((number<<1) - 1.75) + 0.5;
            if (d - (long)d == 0) return 1;
            return 0;
        }    }
}

Answer 1

忘了说下题目：
有一无穷位的数：110100100010000100000.......
求第n位是1还是0？（n<2^31)

Answer 2

好玩的题目，有空了试试1, 10, 100, 1000...
Time Limit: 1.0 second
Memory Limit: 16 MBLet's consider an infinite sequence of digits constructed of ascending powers of 10 written one after another. Here is the beginning of the sequence: 110100100010000… You are to find out what digit is located at the definite position of the sequence.
Input
There is the only positive integer number N in the first line, N < 65536. The i-th of N left lines contains the positive integer Ki — the number of position in the sequence. It's given that Ki < 231.
Output
You are to output N digits 0 or 1 separated with a space. More precisely, the i-th digit of output is to be equal to the Ki-th digit of described above sequence. 

Answer 3

哪个地方超时？            for(int i=0;i<count;i++)
                num[i] = long.Parse(Console.ReadLine());
这里就很费时间的
其余不清楚

Answer 4

这样就OK了：（LZ可能是字符串操作太费时了）using System;class Program
{
  static void Main()
  {
    int count = int.Parse(Console.ReadLine());
    long[] num = new long[count];
    for(int i=0; i < count; i++)
    {
      num[i] = long.Parse(Console.ReadLine());
    }
    foreach (long n in num)
    {
      Console.Write(ZeroOrOne(n));
      Console.Write(" ");
    }
  }  static int ZeroOrOne(long number)
  {
    double d = Math.Sqrt((number<<1) - 1.75) + 0.5;
    return d == (long)d ? 1 : 0;
  }
}

Answer 5

这样更简单，没有必要开一个数组保存输入，边输入边输出就可以了：using System;class Program
{
  static void Main()
  {
    int count = int.Parse(Console.ReadLine());
    for(int i = 0; i < count; i++)
    {
      Console.Write(ZeroOrOne(long.Parse(Console.ReadLine())));
      Console.Write(" ");
    }
  }  static int ZeroOrOne(long number)
  {
    double d = Math.Sqrt((number<<1) - 1.75) + 0.5;
    return d == (long)d ? 1 : 0;
  }
}

Answer 6

没有必要用 long，用 uint 就够了：using System;class Program
{
  static void Main()
  {
    int count = int.Parse(Console.ReadLine());
    for(int i = 0; i < count; i++)
    {
      Console.Write(ZeroOrOne(uint.Parse(Console.ReadLine())));
      Console.Write(" ");
    }
  }  static int ZeroOrOne(uint number)
  {
    double d = Math.Sqrt((number<<1) - 1.75) + 0.5;
    return d == (uint)d ? 1 : 0;
  }
}

Answer 7

不是输入费时，应该是字符串操作（字符串相加）费时：            foreach (long n in num)
                result += ZeroOrOne(n) + " ";

Answer 8

如果不想要最后一个空格，加上 if (i < count - 1) 就好了：using System;class Program
{
  static void Main()
  {
    int count = int.Parse(Console.ReadLine());
    for(int i = 0; i < count; i++)
    {
      Console.Write(ZeroOrOne(uint.Parse(Console.ReadLine())));
      if (i < count - 1) Console.Write(" ");
    }
  }  static int ZeroOrOne(uint number)
  {
    double d = Math.Sqrt((number<<1) - 1.75) + 0.5;
    return d == (uint)d ? 1 : 0;
  }
}

Answer 9

为了节省时间，并且不要最后一个空格，这样也行（避免在循环里面if）：using System;class Program
{
  static void Main()
  {
    int count = int.Parse(Console.ReadLine());
    for(int i = 0; i < count - 1; i++)
    {
      Console.Write(ZeroOrOne(uint.Parse(Console.ReadLine())));
      Console.Write(" ");
    }
    Console.Write(ZeroOrOne(uint.Parse(Console.ReadLine())));
  }  static int ZeroOrOne(uint number)
  {
    double d = Math.Sqrt((number<<1) - 1.75) + 0.5;
    return d == (uint)d ? 1 : 0;
  }
}

Answer 10

兄台，有时间的话帮忙看下这题。自己感觉没有问题，结果却是：Wrong answer！
http://acm.timus.ru/problem.aspx?space=1&num=1201    class Program
    {
        static void Main(string[] args)
        {
            string[] ss = Console.ReadLine().Split();
            PrintCal(new DateTime(int.Parse(ss[2]), int.Parse(ss[1]), int.Parse(ss[0])));
            PrintCal(new DateTime(2009, 3, 31));
        }        static void PrintCal(DateTime dt)
        {
            DateTime startDay = dt.AddDays(dt.Day * -1 + 1);
            int index = 0;
            switch (startDay.DayOfWeek)
            {
                case DayOfWeek.Monday: index = 0; break;
                case DayOfWeek.Tuesday: index = -1; break;
                case DayOfWeek.Wednesday: index = -2; break;
                case DayOfWeek.Thursday: index = -3; break;
                case DayOfWeek.Friday: index = -4; break;
                case DayOfWeek.Saturday: index = -5; break;
                case DayOfWeek.Sunday: index = -6; break;
            }
            for (int i = 0; i < 7; i++)
            {
                switch (i)
                {
                    case 0: Console.Write("mon"); break;
                    case 1: Console.Write("tue"); break;
                    case 2: Console.Write("wed"); break;
                    case 3: Console.Write("thu"); break;
                    case 4: Console.Write("fri"); break;
                    case 5: Console.Write("sat"); break;
                    case 6: Console.Write("sun"); break;
                }
                for (DateTime day = startDay.AddDays(index+i); day < startDay.AddMonths(1); day = day.AddDays(7))
                {
                    if (day.CompareTo(dt) == 0)
                    {
                        if (day.CompareTo(startDay.AddDays(7 + index)) >= 0) Console.Write(".");
                        Console.Write(".[" + day.Day.ToString().PadLeft(2, '.') + "]");
                    }
                    else if (day.CompareTo(dt.AddDays(7)) == 0) Console.Write(".." + day.Day.ToString().PadLeft(2, '.'));
                    else
                    {
                        if (day.CompareTo(startDay) < 0) Console.Write("....");
                        else if (day.CompareTo(startDay.AddDays(7 + index)) < 0) Console.Write(".." + day.Day.ToString().PadLeft(2, '.'));
                        else Console.Write("..." + day.Day.ToString().PadLeft(2, '.'));
                    }
                }
                Console.WriteLine();
            }
        }
}//难道是最后多输出了Console.WriteLine();？？

Answer 11

PrintCal(new DateTime(2009, 3, 31));
这句复制多了，调试时用的。

Answer 12

(for a reading convenience spaces in output example are replaced with dots, real output should contain spaces instead)实际输出时不要出现点，用空格代替。这样就OK了：
   using System;   class Program
    {
        static void Main(string[] args)
        {
            string[] ss = Console.ReadLine().Split();
            PrintCal(new DateTime(int.Parse(ss[2]), int.Parse(ss[1]), int.Parse(ss[0])));
            // PrintCal(new DateTime(2009, 3, 31));
        }        static void PrintCal(DateTime dt)
        {
            DateTime startDay = dt.AddDays(dt.Day * -1 + 1);
            int index = 0;
            switch (startDay.DayOfWeek)
            {
                case DayOfWeek.Monday: index = 0; break;
                case DayOfWeek.Tuesday: index = -1; break;
                case DayOfWeek.Wednesday: index = -2; break;
                case DayOfWeek.Thursday: index = -3; break;
                case DayOfWeek.Friday: index = -4; break;
                case DayOfWeek.Saturday: index = -5; break;
                case DayOfWeek.Sunday: index = -6; break;
            }
            for (int i = 0; i < 7; i++)
            {
                switch (i)
                {
                    case 0: Console.Write("mon"); break;
                    case 1: Console.Write("tue"); break;
                    case 2: Console.Write("wed"); break;
                    case 3: Console.Write("thu"); break;
                    case 4: Console.Write("fri"); break;
                    case 5: Console.Write("sat"); break;
                    case 6: Console.Write("sun"); break;
                }
                for (DateTime day = startDay.AddDays(index+i); day < startDay.AddMonths(1); day = day.AddDays(7))
                {
                    if (day.CompareTo(dt) == 0)
                    {
                        if (day.CompareTo(startDay.AddDays(7 + index)) >= 0) Console.Write(" ");
                        Console.Write(" [" + day.Day.ToString().PadLeft(2, ' ') + "]");
                    }
                    else if (day.CompareTo(dt.AddDays(7)) == 0) Console.Write("  " + day.Day.ToString().PadLeft(2, ' '));
                    else
                    {
                        if (day.CompareTo(startDay) < 0) Console.Write("    ");
                        else if (day.CompareTo(startDay.AddDays(7 + index)) < 0) Console.Write("  " + day.Day.ToString().PadLeft(2, ' '));
                        else Console.Write("   " + day.Day.ToString().PadLeft(2, ' '));
                    }
                }
                Console.WriteLine();
            }
        }
      }

Answer 13

注意下面这两行可以代替你程序中的两个 switch：            int index = -(((int)startDay.DayOfWeek + 6) % 7);                Console.Write(new string[]{"mon","tue","wed","thu","fri","sat","sun"}[i]);   using System;   class Program
    {
        static void Main(string[] args)
        {
            string[] ss = Console.ReadLine().Split();
            PrintCal(new DateTime(int.Parse(ss[2]), int.Parse(ss[1]), int.Parse(ss[0])));
            // PrintCal(new DateTime(2009, 3, 31));
        }        static void PrintCal(DateTime dt)
        {
            DateTime startDay = dt.AddDays(dt.Day * -1 + 1);
            int index = -(((int)startDay.DayOfWeek + 6) % 7);
            for (int i = 0; i < 7; i++)
            {
                Console.Write(new string[]{"mon","tue","wed","thu","fri","sat","sun"}[i]);
                for (DateTime day = startDay.AddDays(index+i); day < startDay.AddMonths(1); day = day.AddDays(7))
                {
                    if (day.CompareTo(dt) == 0)
                    {
                        if (day.CompareTo(startDay.AddDays(7 + index)) >= 0) Console.Write(" ");
                        Console.Write(" [" + day.Day.ToString().PadLeft(2, ' ') + "]");
                    }
                    else if (day.CompareTo(dt.AddDays(7)) == 0) Console.Write("  " + day.Day.ToString().PadLeft(2, ' '));
                    else
                    {
                        if (day.CompareTo(startDay) < 0) Console.Write("    ");
                        else if (day.CompareTo(startDay.AddDays(7 + index)) < 0) Console.Write("  " + day.Day.ToString().PadLeft(2, ' '));
                        else Console.Write("   " + day.Day.ToString().PadLeft(2, ' '));
                    }
                }
                Console.WriteLine();
            }
        }
      }

Answer 14

Good！写的时候就觉得那两个switch很碍眼。

Answer 15

顺便说一下，1001题的解答如下：using System;
using System.Globalization;
using System.Text.RegularExpressions;// http://acm.timus.ru/problem.aspx?space=1&num=1001
class Acm1001
{
  static void Main()
  {
    string[] nums = Regex.Split(Console.In.ReadToEnd().Trim(), @"\s+");
    for (int i = nums.Length - 1; i >= 0; i--)
    {
      Console.WriteLine(Math.Sqrt(ulong.Parse(nums[i])).ToString("F4", CultureInfo.InvariantCulture));
    }
  }
}
请参见：http://www.cnblogs.com/skyivben/archive/2008/06/07/1215740.html更多请见：http://www.cnblogs.com/skyivben/archive/2008/12/08/1350510.html

Answer 16

1001,我试着用foreach逐字符来取数，结果爆掉了。。呵呵。。

Answer 17

1001题分析输入时也可以不用正则，效率应该比用正则好些：using System;
using System.Globalization;public class ReverseRoot
{
  private static void Main()
  {
    NumberFormatInfo nfi = NumberFormatInfo.InvariantInfo;
    string[] input = Console.In.ReadToEnd().Split(
      new char[] {' ', '\t', '\n', '\r'}, StringSplitOptions.RemoveEmptyEntries);
    for (int i = input.Length - 1; i >= 0; i--)
    {
      double root = Math.Sqrt(double.Parse(input[i], nfi));
      Console.WriteLine(string.Format(nfi, "{0:F4}", root));
    }
  }
}

Answer 18

重构了一下26楼的程序：using System;namespace Skyiv.Ben.Timus
{
  // http://acm.timus.ru/problem.aspx?space=1&num=1201
  sealed class T1201
  {
    static void Main()
    {
      var ss = Console.ReadLine().Split();
      var dt = new DateTime(int.Parse(ss[2]), int.Parse(ss[1]), int.Parse(ss[0]));
      var d0 = dt.AddDays(1 - dt.Day);
      var k = -(((int)d0.DayOfWeek + 6) % 7);
      string[] weeks = {"mon", "tue", "wed", "thu", "fri", "sat", "sun"};
      for (var i = 0; i < weeks.Length; i++)
      {
        Console.Write(weeks[i]);
        for (var d = d0.AddDays(k + i); d < d0.AddMonths(1); d = d.AddDays(7))
          Console.Write((d < d0) ? "    " : ((d != dt) ?
            (((d >= d0.AddDays(k + 7) && d != dt.AddDays(7)) ? " " : "") + "{0,4}") :
            (((d >= d0.AddDays(k + 7))? " " : "") + " [{0,2}]")), d.Day);
        Console.WriteLine();
      }
    }
  }
}

Answer 19

33楼的程序中：          Console.Write((d < d0) ? "    " : ((d != dt) ?
            (((d >= d0.AddDays(k + 7) && d != dt.AddDays(7)) ? " " : "") + "{0,4}") :
            (((d >= d0.AddDays(k + 7))? " " : "") + " [{0,2}]")), d.Day);可改为：Console.Write((d < d0) ? "     " : ((d != dt) ? "{0,4} " : " [{0,2}]"), d.Day);请参见： http://www.cnblogs.com/skyivben/archive/2009/03/12/1410028.html