R考场（第二期）活动结果&&你对XP区考场的看法

RyanBern

应大家的要求，已经做出了附加题的答案，可以参考一下。
@繁星千羽
@zaiy2863
我想说的是附加题的代码都好短啊有木有，实际上也不是特别难呢~

RUBY 代码复制

#=============================================================================
# A题思路：
#-----------------------------------------------------------------------------
# 其实可以使用下面的方法进行。
# output = 0
# for x1 in 0..10
#   for x2 in 0..10
#     for x3 in 0..10
#       for x4 in 0..10
#         for x5 in 0..10
#           for x6 in 0..10
#             for x7 in 0..10
#               for x8 in 0..10
#                 for x9 in 0..10
#                   for x10 in 0..10
#                     if x1+x2+x3+x4+x5+x6+x7+x8+x9+x10 == m
#                       output += 1
#                     end
#                   end
#                 end
#               end
#             end
#           end
#         end
#       end
#     end
#   end
# end
# p output
#-----------------------------------------------------------------------------
# 只写了10支箭的时候，作死向穷举已经把人累得要死了。
# 所以大家不要学习这样的行为。
#-----------------------------------------------------------------------------
# 真·A题思路：
#-----------------------------------------------------------------------------
# 考虑20支箭中最后一箭的成绩，有可能是0到10中间的任何一个。如果这支箭的成绩被
# 确定下来之后，那么我们只需要考虑19支箭所达到的成绩的方式了。
# 所以，仔细想想，下面的关系是成立的。
# 如果用F(n,m)表示用n支箭共射中m环的组合数量，那么应该有：
# F(n,m) = F(n-1,m) + F(n-1,m-1) + ... + F(n-1, m-10)
# 这个就是我们的递推公式，有了它我们就可以写我们的程序了。
# 下面是一个递归算法，如果大家不熟悉递归算法的话，可以改成DP算法，不过那样的
# 话貌似比较浪费内存。
#=============================================================================
module Teijal_Ex1
  def self.solve(n,m)
    if n * 10 < m || m < 0
      return 0
    end
    if m == 0
      return 1
    end
    output = 0
    for i in 0..10
      output += self.solve(n-1, m-i)
    end
    return output
  end
end
 
#=============================================================================
# B题思路：
#-----------------------------------------------------------------------------
# 对于第一只飞来的乌鸦，Te'ijal有两种选择：射击它或者放过它。但是不知道那种选
# 择会带来更好的结果。因此，她必须在两种方法直接进行比较。
# 如果用F(arr)表示当乌鸦的高度分别为arr时（arr是一个数组），Te'ijal最多能击中
# 乌鸦数目。
# 那么应该有：
# F(arr) = [F(arr.shift), 1 + F(arr')].max
# 其中arr.shift表示arr去掉arr[0]之后的数组。（这是放过第一只乌鸦的情况）
# arr'表示去掉arr[0]以及小于它的数字所生成的新数组。（这是射击第一只乌鸦的情况）
#=============================================================================
module Teijal_Ex2
  def self.solve(arr)
    if arr.empty?
      return 0
    end
    a0 = arr.shift
    arr_cpy = arr.reject{|i| i < a0}
    return [self.solve(arr), 1 + self.solve(arr_cpy)].max
  end
end

#=============================================================================


# A题思路：


#-----------------------------------------------------------------------------


# 其实可以使用下面的方法进行。


# output = 0


# for x1 in 0..10


#   for x2 in 0..10


#     for x3 in 0..10


#       for x4 in 0..10


#         for x5 in 0..10


#           for x6 in 0..10


#             for x7 in 0..10


#               for x8 in 0..10


#                 for x9 in 0..10


#                   for x10 in 0..10


#                     if x1+x2+x3+x4+x5+x6+x7+x8+x9+x10 == m


#                       output += 1


#                     end


#                   end


#                 end


#               end


#             end


#           end


#         end


#       end


#     end


#   end


# end


# p output


#-----------------------------------------------------------------------------


# 只写了10支箭的时候，作死向穷举已经把人累得要死了。


# 所以大家不要学习这样的行为。


#-----------------------------------------------------------------------------


# 真·A题思路：


#-----------------------------------------------------------------------------


# 考虑20支箭中最后一箭的成绩，有可能是0到10中间的任何一个。如果这支箭的成绩被


# 确定下来之后，那么我们只需要考虑19支箭所达到的成绩的方式了。


# 所以，仔细想想，下面的关系是成立的。


# 如果用F(n,m)表示用n支箭共射中m环的组合数量，那么应该有：


# F(n,m) = F(n-1,m) + F(n-1,m-1) + ... + F(n-1, m-10)


# 这个就是我们的递推公式，有了它我们就可以写我们的程序了。


# 下面是一个递归算法，如果大家不熟悉递归算法的话，可以改成DP算法，不过那样的


# 话貌似比较浪费内存。


#=============================================================================


module Teijal_Ex1


  def self.solve(n,m)


    if n * 10 < m || m < 0


      return 0


    end


    if m == 0


      return 1


    end


    output = 0


    for i in 0..10


      output += self.solve(n-1, m-i)


    end


    return output


  end


end


 


#=============================================================================


# B题思路：


#-----------------------------------------------------------------------------


# 对于第一只飞来的乌鸦，Te'ijal有两种选择：射击它或者放过它。但是不知道那种选


# 择会带来更好的结果。因此，她必须在两种方法直接进行比较。


# 如果用F(arr)表示当乌鸦的高度分别为arr时（arr是一个数组），Te'ijal最多能击中


# 乌鸦数目。


# 那么应该有：


# F(arr) = [F(arr.shift), 1 + F(arr')].max


# 其中arr.shift表示arr去掉arr[0]之后的数组。（这是放过第一只乌鸦的情况）


# arr'表示去掉arr[0]以及小于它的数字所生成的新数组。（这是射击第一只乌鸦的情况）


#=============================================================================


module Teijal_Ex2


  def self.solve(arr)


    if arr.empty?


      return 0


    end


    a0 = arr.shift


    arr_cpy = arr.reject{|i| i < a0}


    return [self.solve(arr), 1 + self.solve(arr_cpy)].max


  end


end

无脑之人

诶 又有算法题么 快拿来做做【泥垢
不过好⑨没看算法可能要跪了【

---

啊 原来LS就是答案
话说怎么都是动规题啊【