【XP提问区活动】R考场活动结果

RyanBern · 发表于 2014-7-21 17:09:44

加入我们，或者，欢迎回来。

您需要登录才可以下载或查看，没有帐号？注册会员

x

本帖最后由 RyanBern 于 2014-7-21 23:07 编辑

R考场的阅卷已经完成，成绩也已经公布。

这次的活动参与者为10人（比M考场少了一半呢，桑心），根据设定，将取前两名发放额外好人卡+1，下面的表格是得分情况，顺序按照交卷顺序。

姓名	第一大题得分	第二大题得分	第三大题得分	附加题得分	获得奖励
@丰聪耳神子	30+15+15+30+40	50+50+93	0(未做)	0(未做)	323EXP
@myownroc	30+15+15+20+55	50+30+100	75+75+95	98(2)	658EXP+2好人卡
@恐惧剑刃	30+15+15+25+50	50+40+30	75+75+90	50(1)	545EXP
@kuerlulu	0(未做)	0(未做)	75+40+100	50(1)	265EXP
@satgo1546	30+15+15+25+60	50+50+100	75+75+90	0(未做)	585EXP
@芯☆淡茹水	27+15+15+30+57	50+45+100	75+75+100	50(1)	639EXP+1好人卡
@无脑之人	0(未做)	0(未做)	0(未做)	100(2)	100EXP+1好人卡
@冰水金刚	30+15+15+25+58	50+50+100	65+75+60	50(3)	593EXP
@atom0520	25+15+15+30+58	50+50+100	75+75+100	0(1)	593EXP
@无忧谷主幻	30+15+15+30+55	50+50+90	75+60+100	0(未做)	570EXP

根据规则，前两名追加好人卡1张，他们分别是myownroc 和芯☆淡茹水。当然参加的人都很努力，在这里谢谢大家了。
注：附加题后面的括号中代表选做的题目号。具体的扣分细则我点评到R考场原帖里面了，有疑问就尽情找我吧。

接下来RB君就很不要脸地对这次考试题进行胡扯了。

首先是先进行一下自我批评。这次出的考卷，题目有的就出的不是特别好。
1.5那个画阴影的题，描述得一点也不清楚，后来在版主双子人的指导下，更改了题干，但是还是不清楚。交上来的答卷的绘画方式跟我想的不太一样。不过satgo1546做得最接近，当然，这个题目大家看到我给出的分数都很高，也算是给大家的补偿吧。
关于3.2题技能消耗物品，依旧没有说清楚。现在想想，这个技能只能是主角技能，敌人是无法使用的。可如果按照参考答案的标准，敌人使用这个技能也会消耗主角的物品。因此这个题目应该加上说明：这是一个主角技能，敌人不可使用。
最后三个附加题，本人是慎重选出的三个难度和复杂度依次增加的题目，可是还是很多考生没有做。是我下手太狠了么？

然后说一下出现的问题：
1.4题那个秒杀敌人的设置，不要考虑脚本了。因为第一大题是数据库操作题，这就提示你仅仅利用数据库即可完成。正确的方法是附加【战斗不能】状态即可。刚开始判卷的时候大家都做对了，可是后面的答卷却不是这样。
2.2题说“调查4次获得2个物品”，这里应该理解为空格四次后就拿到了物品，而不是空格五次。这个我想多数人应该像前一种方式理解吧。
2.3题，水晶小游戏题。这我认为是个比较好的题目。因为大家的做法每个人都不一样。如果用事件的话，比较麻烦，但是也可做到。用脚本的话可以减小编者的工作量，但是需要思考一番。在这里用脚本的话，要注意开关改变的问题。很多人都这样写：

if $game_self_switches[[1,7,'A']] == true
$game_self_switches[[1,7,'A']] = false
else
$game_self_switches[[1,7,'A']] = true
end

复制代码

说实话用事件的可以这样，但是用脚本的话就没必要这样了吧。（虽然我也是这么写的，打脸）

$game_self_switches[[1,7,'A']] = !$game_self_switches[[1,7,'A']]

复制代码

这样一行就可以了，有一个考生就是这样写的，很好。
3.2题，特技消耗物品的话只需要连一个公共事件就可以了，没必要再动脚本了。
3.3题，图片标题，做出来的都很好，但是有的有小BUG。
另外，大家不要把外挂脚本放上去，我想做个3.1题也没必要放上去FUKI脚本吧，仅仅就是加个正则表达式gsub而已吧，考虑到这是第一次，我就不管了，就这样吧。

最后的最后，放上参考答案和大家期待的（what?）附加题脚本，希望高手能够不吝赐教：

R考场.rar (250.4 KB, 下载次数: 121)

附加题原题及参考源码：

=begin
下面是附加题，多少和算法有点关系，大家可以选择作答。
一共有三道题目，答题的时候可以任选一道作答。三个题目的难度不同，因此各自的满分
也不一样，请慎重选择。
注意，只允许选择一道题作答，如果多答，则按照题号最小的题目进行评判，不考虑其他
的题目。因此回答之前要注明所选题号。
=end
#=============================================================================
# 附加题1（猴王问题）：本小题满分50分
#-----------------------------------------------------------------------------
# 现在考虑 n 只猴子围成一圈，编号 ID 为1,2,3,...,n，顺序为逆时针。现在从ID为1的
# 猴子开始报数 1 ，按照逆时针顺序，下面的猴子报数2,3,4,...，现在指定一
# 个数 m，每当有猴子报出数 m 时，它就被淘汰，而它的下一个猴子（仍是按照逆时针
# 次序）继续从 1 开始报数，如此反复。当最后剩下一只猴子时，这只猴子就被选中当做
# 猴群的猴王。问题：请写出一个算法，在给定猴子数目 n 和指定的正整数 m 的条件下
# 求出最后剩下的猴子（猴王）的ID。
#=============================================================================
#=============================================================================
# 本题思路：考虑到猴子们围成一圈，因此可以设计成“循环链表”的模式。定义出猴子
# 类 Monkey，这个类的属性只有两个，一个是猴子的 ID，另一个是它的下一只猴子。
# 为了处理问题方便，还定义出“猴子队列”类 Monkey_Queue。制作队列完毕后，开始
# 循环，逐个剔出被淘汰的猴子。直到队列的长度为1即可。
#=============================================================================
module Ex1
N = 6
M = 1
class Monkey
attr_reader :id # 猴子 ID
attr_accessor :next_monkey # 下一只猴子
def initialize(id)
@id = id
@next_monkey = nil
end
end
class Monkey_Queue
attr_reader :size # 当前队列长度
attr_reader :data # 保存着所有猴子的信息，注意，是所有，而不是当前队列中的
attr_accessor :current # 当前被操作的猴子
def initialize(num)
@size = num
@data = Array.new(num){|i| Monkey.new(i+1)}
@data.each_with_index{|monkey, i| monkey.next_monkey = @data[(i+1) % @data.size]}
@current= @data[0]
end
#-------------------------------------------------------------------------
# 删除一个猴子
#-------------------------------------------------------------------------
def delete(monkey)
# 确保队列长度超过1
return if @size == 1
# 找到前驱结点
pre = @data.find{|member| member.next_monkey == monkey}
# 重新设置次序（下面那个设置为nil的必要）
@current= pre.next_monkey = monkey.next_monkey
monkey.next_monkey = nil
# 队列长度-1
@size -= 1
end
end
#---------------------------------------------------------------------------
# 主函数
#---------------------------------------------------------------------------
def self.solve
# 生成 N 个猴子的环列
queue = Monkey_Queue.new(N)
# 循环，直到剩下一只猴子为止
until queue.size == 1
# 找到下一只被淘汰的猴子
(M-1).times do
queue.current = queue.current.next_monkey
end
# 剔除
queue.delete(queue.current)
end
# 显示结果
p queue.current.id
end
end
#=============================================================================
# 附加题2（括号匹配问题）：本小题满分100分
#-----------------------------------------------------------------------------
# 这是一个很经典的问题，写脚本的同学都知道，括号'()'在脚本中起到了很关键的作用
# ，比如说改变运算顺序，包含方法参数等等。但是，有些书写错误的括号不能通过编译
# 会发生 Syntax Error，比如说(1 + 2)) + 3，它就多了一个右括号。现在的问题是，
# 给定一个字符串，能否确定其中所有不能匹配的括号的位置？
# 为了使得问题更加简单，我们假定字符串中出现的括号只有圆括号'()'一种，方括号
# 和花括号等其他类别的括号不作考虑。当然，除了括号以外，其它字符（比方说字母
# 、数字、空格）会出现在表达式中。请设计一个算法，为其中所有不能匹配的括号作
# 出特殊标记，如果一个左括号没有对应的右括号，则在相应位置输出'，如果一个右
# 括号没有对应的左括号，则在相应位置输出'?'。
# 例（两边的引号代表字符串，不算内容）：
# Input1: "())"
# Output1:" ?"
# Input2: "))(()((((xy))))"
# Output2:"??$ "
#=============================================================================
#=============================================================================
# 本题思路：考虑现实中我们从左到右的阅读顺序，这里的括号匹配也是同样的道理。
# 在这里我们只考虑括号的出现时机。从左到右阅读时，如果发现了一个左括号，那么
# 我们一定要找到与之对应的右括号。如果一开始就发现了个右括号，那么这个括号肯定
# 是有问题的。如果我们读到左括号，继续向右搜寻，读到了一个右括号，那么这两个
# 括号就会自然配对，从而消去这两个括号，不作考虑。如果仍然读到左括号，那么我们
# 就把手头已有的这个括号放弃，暂不考虑，而去为最近的一个左括号寻找右括号。
# 因此我们可以定义一个栈模型，从左到右依次处理每个字符，处理方式如下：
# 1.读到一个左括号，入栈。
# 2.读到一个右括号，观察栈顶部是不是左括号，如果是，则把左括号弹出栈。如果不是
# 则将此右括号入栈。
# 3.读到其他字符，跳过。
# 这样一来，处理完毕后，栈中剩下的所有字符就是无法进行配对的字符，全部弹出，然
# 后按照索引做标记即可（索引可能需要进行预处理）。
#=============================================================================
module Ex2
INPUT = "))(()((((xy))))"
class Char_With_Index
attr_accessor :char # 字符内容
attr_accessor :index # 索引
def initialize(char, index)
@char= char
@index = index
end
end
def self.solve
# 预处理，实际上就是为每个字符标上索引，以便于查找
input = Array.new(INPUT.size){|i| Char_With_Index.new(INPUT[i], i)}
# 初始化栈
stack = []
# 循环，直到所有字符都被处理到
until input.empty?
# 拿出一个字符
ch = input.shift
# 如果是左括号
if ch.char.chr == "("
# 入栈
stack.push(ch)
end
# 如果是右括号
if ch.char.chr == ")"
# 栈为空或者栈顶不是左括号
if stack.empty? || stack[-1].char.chr != "("
# 入栈
stack.push(ch)
else
# 栈顶元素（一定是左括号）出栈
stack.pop
end
end
end
# 输出结果
output = " " * INPUT.size
# 替换
stack.each do |ch|
ch.char.chr == "(" ? output[ch.index] = "$" : output[ch.index] = "?"
end
p output
end
end
#=============================================================================
# 附加题3（DNA序列比对问题）：本小题满分150分
#-----------------------------------------------------------------------------
# DNA序列分析现在的应用价值比较大，有了它就可以为生物的同源性提供有力的证据。
# 这里的DNA序列比对，特指给定两串基因X和Y，我们来比较它们的相似性。但是由于
# 时间久远，两段DNA可能不完全相同，因此我们要设计一个匹配方式，来将这两个DNA
# 进行配对。
# 其中，我们考虑下面两种配对方式
# 这里，设基因X：AGCCT
# 设基因Y：ACCG
#（1）字母——字母：即两个字母相互匹配
#（2）字母——空位：如果X和Y不等长，那么则要在短的那个基因处插入空格，插入的
# 空格位置可以任意，但是基因Y的相对次序不可以变。注，也可以在基因X的地方
# 插入空格，但是也不可以改变基因X的相对次序，若这样做，基因Y就必须插入更
# 多的空格。
# 例（下划线_代表空位）：
# 基因X：AGCCT
# 基因Y：A_CCG
# 另外一种可能的配对方式为：
# 基因X：AGCC_T
# 基因Y：A_CCG_
# 注：此时Y的最后一位要用空位补齐。
# 自然，对于一组基因X和Y，配对的方式多种多样，现在我们利用一个打分原则对所有
# 的配对方式进行评价，现在这个评价方式如下：
#（1）如果字母和字母进行配对，进行配对的两个字母相同，分数+1
# 进行配对的两个字母不同，分数-1
#（2）如果字母和空位进行配对，无论怎么匹配，分数均-1
# 例如，上面两个例子的配对方式：
# 基因X：AGCCT
# 基因Y：A_CCG
# 五个位置分数为+1,-1,+1,+1,-1，总分为1分
# 另一种匹配方式：
# 基因X：AGCC_T
# 基因Y：A_CCG_
# 六个位置分数为+1,-1,+1,+1,-1,-1,总分为0分
# 显然前一种配对方式要好于后一个。
# 那么，我们的问题自然是，在给定基因X和基因Y，并且在这个打分原则的条件下，
# 找出得分最高的匹配方式。
# 在这里，基因X：ATGCCTGA
# 基因Y：AGCTAA
#=============================================================================
#=============================================================================
# 本题思路：配对的方式多种多样，通过计算（利用斯特林公式）我们可以大概估计出
# 需要列出的配对方式大概是指数量级。因此穷举定然会十分麻烦。因此我们考虑动态
# 规划算法。在这里列出一个二维表格F（可以看作二维数组），其中F[i][j]就表示序
# 列 X 的前 i 个和序列 Y 的前 j 个进行匹配，所能达到的最高得分。因此假设序列
# X和Y的长度分别为m和n，那么F[m][n]就是我们要求的最高得分。
# 那么如何计算F[m][n]？这就要用到递推式子。
# 假设我们要求F[i][j]，那么我们应该怎么看呢？
# 我们看匹配的最后一位（注意，匹配结束后，X和Y可以看作是等长的，不足的位置已
# 经用空格替代了），它无非有三种情况：
# （1）序列X的最后一位真正的字母和序列Y添加的空格配对
# （2）序列X添加的空格和序列Y的左后一位真正的字母配对
# （3）序列X和序列Y的最后一位真正的字母配对
# 注意不存在空格和空格配对的情况，因为可以同时删去空格，这样做毫无意义。
# 我们很容易能找到下面的递推关系：
# 情况（1）：F[i][j] = F[i-1][j] - 1
# 情况（2）：F[i][j] = F[i][j-1] - 1
# 情况（3）：F[i][j] = F[i-1][j-1] + d(i,j)
# 其中，d(i,j) = 1 when X[i-1] = Y[j-1]
# d(i,j) = -1 when X[i-1] != Y[j-1]
# 注意，这里d(i,j)只与i和j有关，而与F无关，这点是非常重要的。
# 因此我们得到重要的递推公式如下：
# F[i][j] = [F[i-1][j] - 1,F[i][j-1] - 1, F[i-1][j-1] + d(i,j)].max
# 初始值的话很容易算，这里就不说了。
# 当然，要想知道具体匹配方式的话，还需要进行回溯，这是个细节问题，懂的人应该会
# 处理的。
#=============================================================================
module Ex3
X = "ATGCCTGA"
Y = "AGCTAA"
def self.solve
# 建立最优值表格
value_table = Table.new(X.size+1, Y.size+1)
# 建立回溯表格
# 其中，第三个分量表示沿着X和Y的位移量，可以为-1或0
# 例如trace_table[i,j,0] = -1,trace_table[i,j,1] = 0表示F[i][j]在
# F[i-1][j] - 1处达到最大值
trace_table = Table.new(X.size+1, Y.size+1, 2)
# 初始化
(0..X.size).each do |i|
value_table[i,0] = -i
trace_table[i,0,0] = -1
trace_table[i,0,1] = 0
end
(0..Y.size).each do |j|
value_table[0,j] = -j
trace_table[0,j,0] = 0
trace_table[0,j,1] = -1
end
# 迭代
(1..X.size).each do |i|
(1..Y.size).each do |j|
dij = X[i-1] == Y[j-1] ? 1 : -1
val1 = value_table[i-1,j] - 1
val2 = value_table[i,j-1] - 1
val3 = value_table[i-1,j-1] + dij
if val1 >= val2 && val1 >= val3
value_table[i,j] = val1
trace_table[i,j,0] = -1
trace_table[i,j,1] = 0
end
if val2 >= val1 && val2 >= val3
value_table[i,j] = val2
trace_table[i,j,0] = 0
trace_table[i,j,1] = -1
end
if val3 >= val1 && val3 >= val2
value_table[i,j] = val3
trace_table[i,j,0] = -1
trace_table[i,j,1] = -1
end
end
end
# 回溯
i = X.size
j = Y.size
result_x = ""
result_y = ""
until i == 0 && j == 0
cx = trace_table[i,j,0]
cy = trace_table[i,j,1]
if cx == -1
result_x = X[i-1].chr + result_x
else
result_x = "_" + result_x
end
if cy == -1
result_y = Y[j-1].chr + result_y
else
result_y = "_" + result_y
end
i += cx
j += cy
end
p value_table[X.size,Y.size],result_x,result_y
end
end

复制代码

机械守护者 · 发表于 2014-7-21 17:13:51

支持

myownroc · 发表于 2014-7-21 17:18:50

附加题第二题思路怎么那么奇怪啊...
以下是本人的,感觉更好(?):
从左往右检索右括号,每发现一个右括号就调头检索左括号,匹配则替换掉,没有匹配则给当前右括号做标记...
检索一次之后,所有与右括号匹配得上的左括号,剩余的必然是不能匹配的左括号...

另外,给M考场加个链接呗

satgo1546 · 发表于 2014-7-21 17:30:47

1.4秒杀敌人我是根本不会做（战斗渣
3.3我没看懂题目的意思，因为默认脚本中存档禁止时也可以被选中，且看得出来是选中的。

无忧谷主幻 · 发表于 2014-7-21 17:44:48

本帖最后由无忧谷主幻于 2014-7-21 22:57 编辑

我想做个3.1题也没必要放上去FUKI脚本吧，仅仅就是加个正则表达式gsub而已吧

貌似说的是我？其实我是懒得找了，才把现在游戏中用的对话框脚本放上去的

关于水晶小游戏这个题的确很有趣，当初想了一大堆变量，后来才发觉根本就是在画蛇添足，明明只用几个开关就能解决了。
PS：我以为不发光的水晶就是不亮的

不会做附加题的我注定与好人卡无缘了

羁绊的守望者 · 发表于 2014-7-21 17:48:31

本帖最后由羁绊的守望者于 2014-7-21 18:02 编辑

话说附加题第一题是约瑟夫问题吧？还有第二题是不是用数组模拟栈？

@RyanBern
扫了一眼答案后：第二题用栈，遇见（就压栈，遇见）就和上一个元素一起出栈？
话说要不要介绍一下栈？

kuerlulu · 发表于 2014-7-21 18:10:47

# 递归公式 (约瑟夫斯问题)
def mk(n, m)
n == 1 ? 0 : (mk(n-1, m) + m) % n
end

复制代码

↑比如说约瑟夫斯问题, 上面这个方法得到结果后还要+1才是"第几"
~~话说BZ介绍一下栈吧, 一定能骗走很多膝盖的【咦~~

芯☆淡茹水 · 发表于 2014-7-21 18:19:12

本人纯属捧场，混XP提问区，看到活动，哪有不插一脚的道理，也没什么可以说的。<=一开始就该闭嘴。

你最珍贵 · 发表于 2014-7-21 19:47:32

今天才刚刚看到这个考场，就已经结束了……

无脑之人 · 发表于 2014-7-21 20:18:49

啊哈第三题果然是动规么= =不过实在是懒得想了
第一题真心去一趟C语言吧都能看见满地约瑟夫环
附加题还是留一道算法题吧，这样咱还是有东西可以做的【泥垢【要是不会做就喜闻乐见了

帐号		自动登录	找回密码
密码			注册会员

[胡扯] 【XP提问区活动】R考场活动结果

加入我们，或者，欢迎回来。

点评

点评

点评

点评

点评

评分

点评

点评

点评

点评

开拓者

贵宾

剧作品鉴家

极短25参与

极短24参与

极短23参与

极短22参与

极短21参与