P3727 曼哈顿计划E

    • 13通过
    • 152提交
  • 题目提供者will7101 管理员
  • 标签 分治 枚举,暴力 深度优先搜索,DFS 点分治 洛谷原创 高性能
  • 难度 省选/NOI-
  • 时空限制 1s / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 推荐的相关题目

    题目背景

    1942年6月,美国开始实施利用核裂变反应来研制原子弹的计划,亦称曼哈顿计划。后来两颗原子弹在广岛和长崎爆炸,世界见证了核武器的威力,并在它的威胁下颤抖不已。2200年,dedsec组织利用美国军方的网络安全漏洞渗入了美国的和武器系统,并密谋使用隐藏在曼哈顿的核武器储备毁灭世界。然而dedsec的一名成员Badboy17反对这一计划,她把这一计划告知了艾登。为了拯救他的家人,避免地球变为废土,艾登不得不再次发挥他的黑客能力拯救世界。

    题目描述

    艾登尝试黑入dedsec的系统并取得控制权,然而dedsec有所反应并予以反击。

    • dedsec的网络可以看做是一个n个点n-1条边的连通图(一棵树),每个节点有一个稳定值

    • 艾登可以选择网络中上的一条链,并对那一条链上的节点进行破解(把这一条链从树上拆下来)

    • 假设这一条链长度为m,现在你会得到m个节点

    • 然后艾登要和dedsec开始攻防战,双方轮流行动,每次可以从任意一个稳定值大于0的节点里依照计算规则进行一些操作,操作后,稳定值不能小于0,否则计算机会爆炸,最后不能进行操作的一方算作失败

    • 由于dedsec占据了防守的地理优势,dedsec先进行操作

    • 艾登虽然精于黑客技术,但他的手机没电了。现在他把这个消息告诉了你,希望你帮他拯救世界,所以你需要写一个程序,来帮你判断是否存在一种方式,艾登可以取胜。当然,dedsec的防守可能完美无缺,艾登根本无法取胜,你只好跑到shelter里去当试验品。

    输入输出格式

    输入格式:

    • 输入包含多组测试数据,输入第一行包含一个整数T,表示数据组数

    • 对于每组测试数据

    • 第1行1个整数n,表示有n个点

    • 第2~n行,每行两个整数u,v,表示网络中有一条边连接u,v

    • 第n+1行n个整数w,第wi表示i号节点的稳定值

    • 第n+2行一个整数k,描述操作的规则

    • 如果k==1,你可以减少任意正整数的稳定值

    • 如果k==2,接下来一行一个正整数s,表示双方每次可以减少s的非负整数幂的稳定值

    • 如果k==3,接下来一行一个正整数s,表示双方每次可以减少大于等于s的稳定值

    • 如果k==4,表示双方每次可以减少任意正整数的稳定值,或者把一个稳定值数量大于等于2的节点分裂成两个,分开后的两个节点的稳定值之和等于原来的节点(比如7分成3+4)

    • 如果k==5,双方都不能进行操作

    输出格式:

    • 对于每一组测试数据,输出一行

    • 如果存在一种方式,你可以获胜,输出"Mutalisk ride face how to lose?"

    • 如果不存在一种方式可以取胜,输出"The commentary cannot go on!"

    • 不包含双引号

    输入输出样例

    输入样例#1: 复制
    1
    3
    1 2
    2 3
    1 2 3
    1
    输出样例#1: 复制
    Mutalisk ride face how to lose?
    输入样例#2: 复制
    1
    3
    1 2
    2 3
    1 2 4
    1
    输出样例#2: 复制
    The commentary cannot go on!

    说明

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