P2892 [NOI2007]追捕盗贼

    • 19通过
    • 196提交
  • 题目提供者 chen_zhe Aya
  • 评测方式 云端评测
  • 标签 NOI系列 2007 O2优化 Special Judge 提交答案 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目背景

    spj来源:loj-Robin。已获得授权。

    https://www.luogu.org/paste/dxytr6gc

    附spj,一些修改部分未按照代码规范,请各位谅解。

    题目描述

    魔法国度 Magic Land 里最近出现了一个大盗 Frank,他在 Magic Land 四处作案,专门窃取政府机关的机密文件(因而有人怀疑 Frank 是敌国派来的间谍)。

    为了捉住 Frank,Magic Land 的安全局重拳出击!

    Magic Land 由 N 个城市组成,并且这 N 个城市又由恰好 N-1 条公路彼此连接起来,使得任意两个城市间都可以通过若干条公路互达。从数据结构的角度我们也可以说,这 N 个城市和 N-1 条公路形成了一棵树。

    例如,下图就是 Magic Land 的一个可能格局(4 个城市用数字编号,3 条公路用字母编号):

    大盗 Frank 能够在公路上以任意速度移动。

    比方说,对于上图给出的格局,在 0.00001 秒钟内(或者任意短的一段时间内),Frank 就可以从城市 1 经过城市 2 到达城市 4,中间经过了两条公路。

    想要生擒 Frank 困难重重,所以安全局派出了经验丰富的警探,这些警探具有非凡的追捕才能:

    1. 只要有警探和 Frank 同处一个城市,那么就能够立刻察觉到Frank,并且将其逮捕。

    2. 虽然 Frank 可以在公路上以任意快的速度移动,但是如果有警探和 Frank 在同一条公路上相遇,那么警探也可以立刻察觉到 Frank 并将其逮捕。

    安全局完全不知道 Frank 躲在哪个城市,或者正在哪条公路上移动,所以需要制定一个周密的抓捕计划,计划由若干 步骤组成。在每一步中,可以做如下几件事中的一个:

    1. 在某个城市空降一位警探。警探可以直接从指挥部空降到 Magic Land 的任意一个城市里。此操作记为“L x”,表示在编号为 x 的城市里空降一位警探。耗时 1 秒。

    2. 把留在某个城市里的一位警探直接召回指挥部。以备在以后的步骤中再度空降到某个城市里。此操作记为“B x”。表示把编号为 x 的城市里的一位警探召回指挥部。耗时 1 秒。

    3. 让待在城市 x 的一位警探沿着公路移动到城市 y,此操作记为“M x y”。耗时 1 秒。当然,前提是城市 x 和城市 y 之间有公路。如果在警探移动的过程中,大盗 Frank 也在同一条公路上,那么警探就抓捕到了Frank。

    现在,由你来制定一套追捕计划,也就是给出若干个步骤,需要保证:无论大盗 Frank 一开始躲在哪儿,也无论 Frank 在整个过程中如何狡猾地移动(Frank大盗可能会窃取到追捕行动的计划书,所以他一定会想尽办法逃避),他一定会被缉拿归案。

    希望参与的警探越少越好,因为经验丰富的警探毕竟不多。

    例如对于前面所给的那个图示格局,一个可行的计划如下:

    1. L 2 在城市 2 空降一位警探。注意这一步完成之后,城市 2 里不会有 Frank,否则他将被捉住。

    2. L 2 再在城市 2 空降一位警探。

    3. M 2 1 让城市 2 的一位警探移动到城市 1。注意城市 2 里还留有另一位警探。这一步完成之后,城市 1 里不会有 Frank,公路 A 上也不会有 Frank。也就是说,假如 Frank 还没有被逮捕,那么他只能是在城市 3 或城市 4 里,或者公路 B 或公路 C 上。

    4. B 1 召回城市 1 的一位警探。注意虽然召回了这位警探,但是由于我们始终留了一位警探在城市 2 把守,所以 Frank 仍然不可能跑到城市 1 或者是公路 A 上。

    5. L 3 在城市 3 空降一位警探。注意这一步可以空降在此之前被召回的那位警探。这一步完成之后,城市 3 里不会有 Frank,否则他会被捉住。

    6. M 3 2 让城市 3 里的一位警探移动到城市 2。这一步完成之后,如果 Frank 还没有被捉住,那他只能是在公路 C 上或者城市 4 里。注意这一步之后,城市 2 里有两位警探。

    7. M 2 4 让城市 2 里的一位警探移动到城市 4。这一步完成之后,Frank 一定会被捉住,除非他根本就没来 Magic Land。

    这个计划总共需要 2 位警探的参与。可以证明:如果自始至终只有 1 名或者更少的警探参与,则 Frank 就会逍遥法外。

    你的任务很简单:对于一个输入的 Magic Land 的格局,计算 S,也就是为了追捕 Frank 至少需要投入多少位警探,并且给出相应的追捕计划步骤。

    输入输出格式

    输入格式:

    输入文件给出了 Magic Land 的格局。

    第一行一个整数 N,代表有 N 个城市,城市的编号是 1~N。

    接下来 N-1 行,每行有两个用空格分开的整数 x i ,y i ,代表城市 x i ,y i之间有公路相连。保证 1≤x i ,y i ≤N

    输出格式:

    向输出文件输出你所给出的追捕计划。

    第一行请输出一个整数 S,代表追捕计划需要多少位警探。

    第二行请输出一个整数 T,代表追捕计划总共有多少步。

    接下来请输出 T 行,依次描述了追捕计划的每一步。每行必须是以下三种形式之一:

    ”L x”,其中 L 是大写字母,接着是一个空格,再接着是整数 x,代表在城市 x 空降一位警探。你必须保证 1≤x≤N。

    “B x”,其中 B 是大写字母,接着是一个空格,再接着是整数 x,代表召回城市 x 的一位警探。你必须保证 1≤x≤N,且你的计划执行到这一步之前,城市 x 里面确实至少有一位警探。

    “M x y”,其中 M 是大写字母,接着是一个空格,再接着是整数 x,再跟一个空格,最后一个是整数 y。代表让城市 x 的一位警探沿着公路移动到城市 y。你必须保证 1≤x, y≤N,且你的计划执行到这一步之前,城市 x 里面确实至少有一位警探,且城市 x, y 之前确实有公路。

    必须保证输出的 S 确实等于追捕计划中所需要的警探数目。

    输入输出样例

    输入样例#1: 复制
    4
    1 2
    3 2
    2 4
    输出样例#1: 复制
    2
    7
    L 2
    L 2
    M 2 1
    B 1
    L 3
    M 3 2
    M 2 4

    说明

    对于任何一个测试点:

    如果输出的追捕计划不合法,或者整个追捕计划的步骤数 T 超过了 20000,或者追捕计划结束之后,不能保证捉住 Frank,则不能得分。

    否则,用你输出的 S 和我们已知的标准答案 S * 相比较:
    1. 若 S<S * ,则得到 120%的分。
    2. 若 S=S * ,则得到 100%的分。
    3. 若 S * <S≤S * +2,则得到 60%的分。
    4. 若 S * +2<S≤S * +4,则得到 40%的分。
    5. 若 S * +4<S≤S * +8,则得到 20%的分。
    6. 若 S>S * +8,则得到 10%的分。

    输入保证描述了一棵连通的 N 结点树,1≤N≤1 000。

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。