QOJ.ac

QOJ

Total points: 100 Output Only

# 4553. 工厂

统计

这是一道提交答案题

跳蚤国作为一个发展中国家,生产力始终比发达国家跳晚国差一大截,因此发展生产力一直是跳蚤国第一重要的事。

近日,跳蚤国王在视察跳蚤国首都的X工厂时,发现这里的机器效率低下,而且污染严重,以至于跳蚤国首都几乎每天都是漫天雾霾……

X工厂是用来检验各地运来的产品的质量的。在X工厂的每个车间中,有若干个节点。每个节点有一台机器,这台机器对产品进行一些处理后,将其送给下一个节点。

跳蚤国王回忆起几个月前造计算机的经历,想到了一个绝佳的主意:使用高效、清洁的生物资源!于是在每个节点上,机器被换成了跳蚤。

具体来说:

  • 对于X工厂的每个车间,我们可以将所有节点从 $1$ 开始编号。
  • 对于每个产品,都有一个只由可见字符(即ASCII码在[32,126]区间内的字符)构成的字符串,作为其标识串

在一开始的时候,产品被送到了第 $1$ 个节点上,然后这些节点需要检查该产品的标识串,最终接受(Accept)或拒绝(Reject)该产品。

  • 对于不同的车间,需要接受的产品的标识串集合是不同的。
  • 对于某个节点上的跳蚤,有transnext两个属性。其中trans为一个大小为$128$的整数数组,next为一个整数。

当一个产品被送到这个节点上时,该产品的标识串的第一个字符将被移除,设其ASCII码为$x$, 则该产品在下一秒会被送到编号为trans[x]的节点上。 如果该产品的标识串已经是空串,则该产品下一秒会被送到编号为next的节点上。

蛐蛐国王对此表示十分支持,他派来了一些蛐蛐,来增加X工厂的处理能力。也就是说,一个节点上的跳蚤可以被替换成蛐蛐。

  • 每只蛐蛐有xnext两个整数属性。其中x的范围是[0,127]。
  • 当一个产品被送到这个蛐蛐节点上时,该产品的标识串的最后会被添加一个ASCII码为x的字符,然后该产品下一秒会被送到编号为next的节点上。

另外,对于任意一只跳蚤的transnext,以及对于任意一只蛐蛐的next,其值可以等于0或者-1,其中0表示下一秒接受该产品,-1表示下一秒拒绝该产品。

由于跳蚤国资源的限制,一个车间最多能有300个节点。在处理一个产品的时候,最多只能花费 $10^6$ 秒的时间。

跳蚤国王发现自己没有足够的能力来管理这么多跳蚤和蛐蛐,于是找到了参加清华集训的你。请你对X工厂的每个车间,确定需要使用的节点数 $n$,以及每个节点使用的跳蚤或蛐蛐的属性。每个车间作为一个任务,要求如下:

任务1(5分)

接受所有以1结尾的01串作为标识串的产品。 如"111"是以1结尾的01串,而"110"和"233"都不是。 保证每个产品中,标识串的长度 $L$ 满足 $1 \le L \le 100$。

任务2(13分)

接受所有包含子串

aaaaaaaaaaaabaaaaaabaaaaaaaaaaaaaabaaabaaabaaaaaaaaaabaaaaaaaaabaabaaaaaaaaaaaaabaaaaaaaaaaaaaaaaaaaorz

的串作为标识串的产品。 这个子串在该试题目录下的task2_string.txt中也存有一份。 保证每个产品中,标识串的长度 $L$ 满足 $1 \le L \le 500000$。

任务3(9分)

接受所有匹配的括号串作为标识串的产品。 匹配的括号串可以这么定义:

  • 空串是匹配的括号串
  • 如果S是匹配的括号串,则(S)是匹配的括号串
  • 如果X和Y都是匹配的括号串,则XY是匹配的括号串

如"(())()"是匹配的括号串,而"(()"不是。 一个等价的上下文无关文法为:

S -> SS | (S) | ε

保证每个产品中,标识串的长度 $L$ 满足 $1 \le L \le 100$。

任务4(12分)

接受所有匹配的括号串作为标识串的产品。 匹配的括号串的定义同任务3。 保证每个产品中,标识串的长度 $L$ 满足 $1 \le L \le 900000$。

任务5(6分)

接受所有从左到右看作为二进制数为3的倍数的01串作为标识串的产品。 如 $(10010)_2 = (18)_{10}$,所以一个标识串为"10010"的产品是可以接受的。 保证每个产品中,标识串的长度 $L$ 满足 $1 \le L \le 100$。

任务6(15分)

接受所有fib串作为标识串的产品。 fib串可以这么定义:

  • 我们记f[1] = "a"f[2] = "b"
  • 对于$i > 2$,我们定义f[i] = f[i - 1] + f[i - 2],其中+表示字符串的连接
  • f[3] = "ba"f[4] = "bab"
  • 那么,一个串 $s$ 是fib串,当且仅当存在一个正整数 $i$ ,使得 $s$ 等于f[i]

如"bab"是一个fib串,而"baa"不是。 保证每个产品中,标识串的长度 $L$ 满足 $1 \le L \le 400$。

任务7(8分)

接受所有fib串作为标识串的产品。 fib串的定义同任务6。 保证每个产品中,标识串的长度 $L$ 满足 $1 \le L \le 200000$。

任务8(14分)

接受所有表达式作为标识串的产品。 表达式可以这么定义:

  • 先引入另外一个定义:
  • 任何一个项都是一个表达式
  • "0"和"1"是项
  • 如果X是一个表达式,则(X)是一个项
  • 如果X和Y都是项,则X*Y是项
  • 如果X和Y都是表达式,则X+Y是表达式

如"(1+0)*1+0+(1)"是一个表达式,而"(1+1"不是。 一个等价的上下文无关文法为:

S -> S + T | T
T -> T * F | F
F -> 0 | 1 | (S)

保证每个产品中,标识串的长度 $L$ 满足 $1 \le L \le 1000$。

任务9(7分)

接受所有表达式作为标识串的产品。 表达式的定义同任务8。 保证每个产品中,标识串的长度 $L$ 满足 $1 \le L \le 100000$。

任务10(11分)

接受所有跳蚤语言的串作为标识串的产品。

  • 跳蚤语言为一种只有语句和控制结构的语言。
  • 为方便起见,跳蚤语言只由三种字符构成:'i'、'e'和'a'。
  • 其中'a'表示语句,'i'表示if,'e'表示else。
  • 一个跳蚤语言的串,可以是一个语句,或一个控制结构。
  • 语句即为"a",控制结构为"iAeB",或者是"iA",其中A可以是语句或控制结构,B也可以是语句或控制结构。
  • 对于一个'e',它总是会跟最近的一个'i'进行匹配。

如"iiaea"是一个跳蚤语言的串,因为它的后缀"iaea"作为一个控制结构整体,跟第一个"i"构成了一个"iA"型的控制结构。 如"iaeaea"就不是一个跳蚤语言的串,因为它最后一个"ea"找不到跟它匹配的"i"了。 如"iiaeaea"是一个跳蚤语言的串,并且第一个"ea"跟第二个"i"相匹配,第二个"ea"跟第一个"i"相匹配。

一个等价的上下文无关文法为:

S -> iSeS | iS | a
其中e跟最近的i相匹配,即iSeS的优先级比iS要高。

保证每个产品中,标识串的长度 $L$ 满足 $1 \le L \le 100$。

输入格式

所有输入数据 factory1.in ~ factory10.in 分别对应10个任务。 每组输入数据仅包含一个整数,表示需要解决的任务编号。

输出格式

输出文件为 1.out ~ 10.out,分别对应相应的输入文件。 对于每组输入数据,你需要输出你使用的各个节点。 具体来说,第一行输出一个整数$n$,表示你使用了编号为$1 \sim n$的节点。 接下来$n$行,按编号从小到大的顺序每行描述一个节点。 首先输出一个整数表示该节点的类型,其中跳蚤为1,蛐蛐为2。 对于跳蚤节点,先输出128个整数表示trans[0] ~ trans[127],再输出一个整数next。 对于蛐蛐节点,输出两个整数xnext。 要求trans[i]next都在[-1,$n$]范围内,其中-1和0的意义见题目描述。 要求x在[0,127]范围内。 同一行中相邻两个整数用一个空格隔开。

在输出文件的最后,你可以添加任意内容,这不会影响你的得分。 我们建议你在此处写一些有意义的内容(如该任务的构造方法),以便于我们在考后进行统计分析。

评分方式

这道题没有部分分

我们提供了10个评分文件factory1.ans ~ factory10.ans,分别对应每个任务。

在每个评分文件中,第一行是一个整数$m$,表示有$m$组测试数据。接下来$2m$行,每两行表示一组测试数据,其中第一行为一个字符串,表示该测试数据的标识串,第二行一个字符串,为"Accept"(接受)或"Reject"(拒绝),表示该测试数据的答案。

本题中,我们对每个任务单独评分,每个任务的分值见题目描述。

如果你的输出格式不合法或者参数不符合题目约定,则得0分。

否则,按照以下规则来评分:

  • 首先测评器会从相应的评分文件中读取该任务的测试数据,并将每组数据代入你的输出。
  • 如果在代入某一组数据时,你处理该产品的时间超过了$10^6$秒,则得0分。
  • 如果在代入某一组数据时,你的输出与相应的答案不一样,则得0分。
  • 否则该任务得满分。

如何测试你的输出

在终端中先切换到该试题的目录下:(windows用户请使用cmd)

cd factory

我们提供checker这个工具来测试你的输出文件是否是可接受的。使用这个工具的方法是,先编译checker.cpp,假设编译后的文件名为checker,则在终端中运行

./checker <task_id>

其中task_id为任务的编号,例如

./checker 3

将测试3.out是否可以接受。(windows用户请使用checker 3) 在你调用这个程序之后,checker会根据你给出的输出文件给出测试结果。 另外,你可以直接不加参数运行checker,来测试这道题的所有输出文件。

我们还提供了一些其他的小工具,如用来运行/调试你的输出文件的工具,详细说明见该试题目录下的readme.txt。


或者逐个上传: