这是一道提交答案题

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

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

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

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

具体来说：

• 对于X工厂的每个车间，我们可以将所有节点从 $1$ 开始编号。
• 对于每个产品，都有一个只由可见字符（即ASCII码在[32,126]区间内的字符）构成的字符串，作为其标识串。 在一开始的时候，产品被送到了第 $1$ 个节点上，然后这些节点需要检查该产品的标识串，最终接受(Accept)或拒绝(Reject)该产品。

• 对于不同的车间，需要接受的产品的标识串集合是不同的。

• 对于某个节点上的跳蚤，有trans和next两个属性。其中trans为一个大小为$128$的整数数组，next为一个整数。 当一个产品被送到这个节点上时，该产品的标识串的第一个字符将被移除，设其ASCII码为$x$， 则该产品在下一秒会被送到编号为trans[x]的节点上。 如果该产品的标识串已经是空串，则该产品下一秒会被送到编号为next的节点上。

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

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

另外，对于任意一只跳蚤的trans或next，以及对于任意一只蛐蛐的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。 对于蛐蛐节点，输出两个整数x和next。 要求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。

注意：最终评测时，使用的评分文件factory1.ans ~ factory10.ans可能跟下发的不同。使用下发的评分文件测试的得分仅供参考。

下载

相关文件下载