公园重建 - المسألة

Note: Currently the partial scoring for this problem is not working.

怪物城有一个大型公园，该公园由若干个景点以及连接这些景点所在地点的单向道路组成，共有 $v$ 个景点，编号为 $1,2,\cdots,v$，这些景点包含了 $n$ 个入口和 $1$ 个出口，编号 $1,2,\cdots,n$ 的景点为入口，编号为 $v$ 的景点为出口。公园内一共有 $e$ 条道路，第 $i$ 条道路的起点为景点 $a_i$，终点为景点 $b_i$。

每个景点 $i$ 都有一个标志 $s_i$，这个标志是 &、| 两者之一。类似地，每条道路 $i$ 也有一个标志 $t_i$，这个标志是 &、|、~、<、> 五者之一。如果 $t_i$ 不等于 ~，那么道路 $i$ 还有一个权值 $l_i$。

每天，有 $n$ 只怪物组成一波进入公园。第 $i$ 天，初始生命值分别为 $h_{i,1},h_{i,2},\cdots,h_{i,n}$ 的 $n$ 只怪物在同一时刻分别进入 $n$ 个入口 $1,2,\cdots,n$，然后这些怪物将在公园内闯荡。在每一分钟内，每只怪物将会分身成 $k$ 个生命值和分身前相同的怪物（$k$ 为以该怪物所在景点为起点的道路数），分别朝着 $k$ 条以该怪物所在景点为起点的道路前进。

一只怪物通过一条道路恰好需要 $1$ 分钟。生命值为 $h$ 的怪物通过道路 $i$ 之后生命值将变化为 $h'$，下表给出了变化关系。

$t_i=$	$h'=$	说明
`&`	$h\ \mathrm{AND}\ l_i$	将 $h$ 和 $l_i$ 在二进制下做按位与运算的结果
`\|`	$h\ \mathrm{OR}\ l_i$	将 $h$ 和 $l_i$ 在二进制下做按位或运算的结果
`~`	$\mathrm{NOT}\ h$	将 $h$ 在二进制下按位 $0,1$ 取反的结果
`<`	$h\ \mathrm{SHL}\ l_i$	将 $h$ 在二进制下低位补 $l_i$ 个 $0$，舍弃最高 $l_i$ 位的结果
`>`	$h\ \mathrm{SHR}\ l_i$	将 $h$ 在二进制下高位补 $l_i$ 个 $0$，舍弃最低 $l_i$ 位的结果

表格中 $\mathrm{AND},\mathrm{OR},\mathrm{NOT},\mathrm{SHL},\mathrm{SHR}$ 分别对应了按位与、按位或、按位取反、按位左移、按位右移五种位运算。其中 $h,l_i$ 和 $h'$ 都是 $32$ 位无符号整数。对于 $\mathrm{AND},\mathrm{OR}$ 运算，满足 $0\le l_i < 2^{32}$。对于 $\mathrm{SHL},\mathrm{SHR}$ 运算，满足 $0\le l_i < 32$。

当生命值为 $h_1,h_2,\cdots,h_c$ 的多只怪物在同一景点 $i$ 相遇时，它们会合体成一只怪物，其生命值 $h'$ 等于 $h_1,h_2,\cdots,h_c$ 做 $s_i$ 运算的结果，即：若 $s_i$ 为 &，则合体后的怪物生命值 $h'=h_1\ \mathrm{AND}\ h_2\ \mathrm{AND}\ \cdots\ \mathrm{AND}\ h_c$；若 $s_i$ 为 |，则合体后的怪物生命值 $h'=h_1\ \mathrm{OR}\ h_2\ \mathrm{OR}\ \cdots\ \mathrm{OR}\ h_c$。之后，如果该怪物位于公园的出口，那么它就会离开公园。每一波怪物中，第一只离开公园的怪物被称为 Winner。所有怪物初始生命值和 Winner 离开公园时的生命值都会被记录下来。

一只怪物死亡当且仅当以下几种情况之一（死亡后的怪物永远不会行动或参与合体）：

1、没有一条道路以该怪物所在景点为起点，且该怪物不在出口。

2、该怪物的生命值为 $0$。这意味着怪物可能在道路上死亡或者在合体后瞬间死亡。

3、从所有怪物进入公园到当前时刻超过了 $k$ 分钟，其中 $k$ 为怪物的寿命。

你可以认为第 $i+1$ 天时，在第 $i$ 天进入的怪物均离开公园或死亡。

然而，$m$ 天之后，一场天灾将这个公园严重破坏了。不过，怪物城希望根据这 $m$ 天的记录重建这个公园，但这件事有些困难，于是他找到了你来帮忙——当然，只要你设计出任意一种能满足 $m$ 天的所有记录的方案就行了。

输入格式

所有输入数据 rebuild1.in ~ rebuild10.in 见数据下载。

输入第 $1$ 行包含 $3$ 个整数 $n,m,k$，分别表示每天进入的怪物个数、天数以及怪物的寿命。

第 $2$ 行至第 $2m+1$ 行为 $m$ 天的记录。其中，第 $2i$ 行包含 $n$ 个整数 $h_{i,1},h_{i,2},\cdots,h_{i,n}$，表示第 $i$ 天的 $n$ 只怪物进入公园时的初始生命值，第 $2i+1$ 行包含 $1$ 个整数 $w_i$，表示第 $i$ 天怪物的 Winner 离开公园时的生命值。数据保证每天均存在 Winner。

输出格式

针对给定的 $10$ 个输入文件 rebuild1.in ~ rebuild10.in，你需要分别提交你的输出文件 rebuild1.out ~ rebuild10.out。

输出第 $1$ 行包含 $2$ 个整数 $v,e$，分别表示景点数和道路数，$n < v\le 100$，$0\le e\le 500$。

第 $2$ 行包含 $1$ 个长度为 $v$ 的字符串 $s$，其中第 $i$ 个字符 $s_i$ 为 &、| 之一，表示第 $i$ 个景点的标志。

第 $3$ 行至第 $e+2$ 行，每行描述一条道路。其中，第 $i+2$ 行四个数或字符 $a_i,b_i,t_i,l_i$，分别表示第 $i$ 条道路的起点、终点、标志和权值。$1\le a_i,b_i\le v$，标志为 &、|、~、<、> 之一，特别地，当 $t_i$ 为 ~ 时，$l_i$ 并不会输入。允许两景点间连有多条道路，也允许存在起点和终点相同的道路。

输出任意一种满足要求的方案即可。数据保证存在这样的方案。

样例输入

样例输出

4 4
||&&
1 3 | 0
2 3 ~
2 4 & 12
3 4 < 1

样例说明

样例输出为一种可能的公园重建方案。以第 $1$ 天的怪物为例：

一开始，有 $2$ 只怪物，分别位于景点 $1,2$，生命值分别为 $11,1$。

第 $1$ 分钟，景点 $1$ 的怪物沿道路进入景点 $3$，其生命值变为 $11\ \mathrm{OR}\ 0=11$；景点 $2$ 的怪物分身成 $2$ 只怪物，一只沿道路进入景点 $3$，其生命值变为 $\mathrm{NOT}\ 1=4294967294$，另一只沿道路进入景点 $4$，其生命值变为 $1\ \mathrm{AND}\ 12=0$，因此该分身在进入景点前死亡。之后，位于景点 $3$ 的 $2$ 只怪物合体成 $1$ 只生命值为 $11\ \mathrm{AND}\ 4294967294=10$ 的怪物。此时仅景点 $3$ 有 $1$ 只怪物。

第 $2$ 分钟，景点 $3$ 的怪物沿道路进入景点 $4$，其生命值变为 $10\ \mathrm{SHL}\ 1=20$。景点 $4$ 为出口，所以接下来该怪物将离开公园，成为 Winner。

因此，该组怪物的 Winner 生命值为 $20$。

子任务及部分分

我们提供了 $10$ 个评分文件 rebuild1.ans ~ rebuild10.ans。每个评分文件共 $10$ 行，第 $i$ 行一个评分参数 $a_i$，具体意义将在下面给出。

每个测试点单独评分。对于每个测试点，如果选手的输出格式不合法，则得 $0$ 分。如果输出合法，但 $m$ 条记录中只有部分记录被满足，则你还可能获得部分分。

在你的方案中，若满足的记录条数为 $x_{user}$，你的分数将会由下表给出：

得分	条件	得分	条件
$10$	$x_{user}\ge a_{10}$	$5$	$x_{user}\le a_5$
$9$	$x_{user}\ge a_9$	$4$	$x_{user}\ge a_4$
$8$	$x_{user}\ge a_8$	$3$	$x_{user}\ge a_3$
$7$	$x_{user}\ge a_7$	$2$	$x_{user}\ge a_2$
$6$	$x_{user}\ge a_6$	$1$	$x_{user}\ge a_1$

若不符合表中所有条件，得 $0$ 分；若符合表中的多个条件，则取分数最高的。

如何测试你的输出

在终端中先切换到该试题的目录下：（windows用户请使用cmd）（假设你把输入输出文件、checker 什么的都放在了 rebuild 这个文件夹下）

cd rebuild

我们提供checker这个工具来测试你的输出文件是否是可接受的。使用这个工具的方法是，在终端中运行

./checker_linux64 <case_no>

其中 case_no 是测试数据的编号。例如

./checker_linux64 3

将测试 rebuild3.out 是否可以接受。（windows用户请使用 checker_win32 3）（什么你是windows 64位？放心吧可以运行win32应用程序的。）

当然我们有对应的 linux 32 位版本：checker_linux32。如果 linux 用户发现无法运行程序，请尝试执行 chmod +x checker_linux64 或 chmod +x checker_linux32 后重试。

在你调用这个程序后，checker 将根据你给出的输出文件给出测试的结果。

请不要随便更改in文件，防止checker出现不可预知的错误。

另外，你还可以在终端中使用命令

./checker_linux64 –w <case_no>

以将测试点 <case_no> 中每天怪物行进过程中的位置和生命值输出到文件 report.log 中。注意文件 report.log 可能很大，极端情况下文件大小约为 $150\texttt{MB}$。

QOJ.ac

QOJ

#10355. 公园重建