#PQJ1972x10355. QOJ 1972_10355
QOJ 1972_10355
标题: 公园重建 - Problem - QOJ.ac
#10355. 公园重建
The problem was used in the following contests:
Note: Currently the partial scoring for this problem is not working.
怪物城有一个大型公园,该公园由若干个景点以及连接这些景点所在地点的单向道路组成,共有 v 个景点,编号为 1,2,⋯,v,这些景点包含了 n 个入口和 1 个出口,编号 1,2,⋯,n 的景点为入口,编号为 v 的景点为出口。公园内一共有 e 条道路,第 i 条道路的起点为景点 ai,终点为景点 bi。
每个景点 i 都有一个标志 si,这个标志是 &、| 两者之一。类似地,每条道路 i 也有一个标志 ti,这个标志是 &、|、~、<、> 五者之一。如果 ti 不等于 ~,那么道路 i 还有一个权值 li。
每天,有 n 只怪物组成一波进入公园。第 i 天,初始生命值分别为 hi,1,hi,2,⋯,hi,n 的 n 只怪物在同一时刻分别进入 n 个入口 1,2,⋯,n,然后这些怪物将在公园内闯荡。在每一分钟内,每只怪物将会分身成 k 个生命值和分身前相同的怪物(k 为以该怪物所在景点为起点的道路数),分别朝着 k 条以该怪物所在景点为起点的道路前进。
一只怪物通过一条道路恰好需要 1 分钟。生命值为 h 的怪物通过道路 i 之后生命值将变化为 h′,下表给出了变化关系。
ti= h′= 说明 & h AND li 将 h 和 li 在二进制下做按位与运算的结果 | h OR li 将 h 和 li 在二进制下做按位或运算的结果 ~ NOT h 将 h 在二进制下按位 0,1 取反的结果 < h SHL li 将 h 在二进制下低位补 li 个 0,舍弃最高 li 位的结果 > h SHR li 将 h 在二进制下高位补 li 个 0,舍弃最低 li 位的结果
表格中 AND,OR,NOT,SHL,SHR 分别对应了按位与、按位或、按位取反、按位左移、按位右移五种位运算。其中 h,li 和 h′ 都是 32 位无符号整数。对于 AND,OR 运算,满足 0≤li<232。对于 SHL,SHR 运算,满足 0≤li<32。
当生命值为 h1,h2,⋯,hc 的多只怪物在同一景点 i 相遇时,它们会合体成一只怪物,其生命值 h′ 等于 h1,h2,⋯,hc 做 si 运算的结果,即:若 si 为 &,则合体后的怪物生命值 h′=h1 AND h2 AND ⋯ AND hc;若 si 为 |,则合体后的怪物生命值 h′=h1 OR h2 OR ⋯ OR hc。之后,如果该怪物位于公园的出口,那么它就会离开公园。每一波怪物中,第一只离开公园的怪物被称为 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 个整数 hi,1,hi,2,⋯,hi,n,表示第 i 天的 n 只怪物进入公园时的初始生命值,第 2i+1 行包含 1 个整数 wi,表示第 i 天怪物的 Winner 离开公园时的生命值。数据保证每天均存在 Winner。
输出格式
针对给定的 10 个输入文件 rebuild1.in ~ rebuild10.in,你需要分别提交你的输出文件 rebuild1.out ~ rebuild10.out。
输出第 1 行包含 2 个整数 v,e,分别表示景点数和道路数,n<v≤100,0≤e≤500。
第 2 行包含 1 个长度为 v 的字符串 s,其中第 i 个字符 si 为 &、| 之一,表示第 i 个景点的标志。
第 3 行至第 e+2 行,每行描述一条道路。其中,第 i+2 行四个数或字符 ai,bi,ti,li,分别表示第 i 条道路的起点、终点、标志和权值。1≤ai,bi≤v,标志为 &、|、~、<、> 之一,特别地,当 ti 为 ~ 时,li 并不会输入。允许两景点间连有多条道路,也允许存在起点和终点相同的道路。
输出任意一种满足要求的方案即可。数据保证存在这样的方案。
样例输入
2 4 2
11 1
20
11 2
18
11 3
16
18 12
12
样例输出
4 4
||&&
1 3 | 0
2 3 ~
2 4 & 12
3 4 < 1
样例说明
样例输出为一种可能的公园重建方案。以第 1 天的怪物为例:
一开始,有 2 只怪物,分别位于景点 1,2,生命值分别为 11,1。
第 1 分钟,景点 1 的怪物沿道路进入景点 3,其生命值变为 11 OR 0=11;景点 2 的怪物分身成 2 只怪物,一只沿道路进入景点 3,其生命值变为 NOT 1=4294967294,另一只沿道路进入景点 4,其生命值变为 1 AND 12=0,因此该分身在进入景点前死亡。之后,位于景点 3 的 2 只怪物合体成 1 只生命值为 11 AND 4294967294=10 的怪物。此时仅景点 3 有 1 只怪物。
第 2 分钟,景点 3 的怪物沿道路进入景点 4,其生命值变为 10 SHL 1=20。景点 4 为出口,所以接下来该怪物将离开公园,成为 Winner。
因此,该组怪物的 Winner 生命值为 20。
子任务及部分分
我们提供了 10 个评分文件 rebuild1.ans ~ rebuild10.ans。每个评分文件共 10 行,第 i 行一个评分参数 ai,具体意义将在下面给出。
每个测试点单独评分。对于每个测试点,如果选手的输出格式不合法,则得 0 分。如果输出合法,但 m 条记录中只有部分记录被满足,则你还可能获得部分分。
在你的方案中,若满足的记录条数为 xuser,你的分数将会由下表给出:
得分 条件 得分 条件 10 xuser≥a10 5 xuser≤a5 9 xuser≥a9 4 xuser≥a4 8 xuser≥a8 3 xuser≥a3 7 xuser≥a7 2 xuser≥a2 6 xuser≥a6 1 xuser≥a1
若不符合表中所有条件,得 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 可能很大,极端情况下文件大小约为 150MB。