全部评论 3

  • P3952 [NOIP 2017 Senior] Time Complexity

    题目背景

    NOIP 2017 Senior D1T2.

    题目描述

    Xiao Ming is learning a new programming language, A++. After just learning loop statements, he excitedly wrote many programs and gave the time complexity he calculated for each. His programming teacher does not want to check them one by one, so here is your chance! Please write a program to judge whether the time complexity Xiao Ming gave for each program is correct.

    The loop structure in A++ is as follows:

    F i x y
        loop body
    E
    

    Here, F i x y means creating a new variable ii (the variable ii must not have the same name as any existing variable that has not been destroyed) and initializing it to xx. Then compare ii with yy: if ii is less than or equal to yy, enter the loop; otherwise, do not enter. After each loop, ii is updated to i+1i+1. Once ii becomes greater than yy, the loop terminates.

    xx and yy can be positive integers (the relation between xx and yy is not fixed) or the variable nn. The variable nn represents the problem size; in time complexity analysis, nn must be kept as a variable and not treated as a constant. It is much larger than 100100.

    E indicates the end of the loop body. When the loop body ends, the variables created by this loop are destroyed.

    Note: For convenience, this problem uses the uppercase letter O\operatorname O to denote the concept of Θ\Theta in the usual sense when describing complexity.

    输入格式

    The first line of input contains a positive integer tt, meaning there are tt (t10t \le 10) programs whose time complexity needs to be checked. For each program, we only need to extract the F i x y and E lines to compute the time complexity. Note: Loop structures can be nested.

    For each program, the first line contains a positive integer LL and a string. LL is the number of lines in the program, and the string denotes the program’s claimed complexity. O(1) means constant complexity, and O(n^w) means the co

    5天前 来自 福建

    0
  • 做大模拟真的是找虐

    1周前 来自 浙江

    0
  • 1周前 来自 广东

    0
    • userId_undefined
      wcqk
      回复
      cjdst

      存模拟有时间再做

      1周前 来自 湖北

      0
    • userId_undefined
      wcqk
      回复
      cjdst

      发灌水了捏

      1周前 来自 湖北

      0
    • userId_undefined
      cjdst
      回复
      wcqk

      不是,你为啥要做模拟啊吓哭了

      1周前 来自 广东

      0

热门讨论