P3701 「伪模板」主席树

    • 373通过
    • 731提交
  • 题目提供者 朝田诗乃
  • 评测方式 云端评测
  • 标签 图的建立,建图 字符串 最大流 网络流 邻接表 洛谷原创 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目背景

    byx和手气君都非常都非常喜欢种树。有一天,他们得到了两颗奇怪的树种,于是各自取了一颗回家种树,并约定几年后比一比谁种出来的树更加牛x。

    题目描述

    很快,这棵树就开花结果了。byx和手气君惊讶的发现,这是一棵主席树,树上长满了主席和主席的朋友们。这棵树上一共有五种人,主席(J),记者(HK),高人(W),女王(E)和膜法师(YYY)。他们发现,他们的主席树上的人数相同,都为N。

    研究发现,这五种人的输赢如上图所示(一样的人不能PK),箭头指向输的人。至于为什么,留给同学们自己思考。

    比赛如期进行。

    byx和手气君要进行M场比赛,每一场比赛他们会选出树上的两个人来比较看谁更牛x。

    第i个人寿命为Lifei秒,每次比完赛他们就会-1s。当他们生命为0s时他们就不能再比赛了。

    同时,当J的寿命为0时,同一棵树上的YYY可以为他+1s。每个YYY只能给.每个J续一次。

    那么问题来了

    现在给定N,M(1≤N≤100,1≤M≤1000),A和B每一个人所属种类(J,HK,W,YYY或E)以及每一个人的生命,生命不超过50.请你算算A最多能够赢得多少场比赛呢。

    数据保证每一场一定都有人用。两个人之间只能比一场。

    输入输出格式

    输入格式:

    第一行包含两个数N,M,含义看上面。

    第二行N个字串(J,HK,W,YYY或E),表示byx的人所属种类,用空格隔开。

    第三行N个字串(J,HK,W,YYY或E),表示手气君的人所属种类,用空格隔开。

    第四行N个数,表示byx的人的生命。

    第五行N个数,表示手气君的人的生命。

    输出格式:

    一个数,byx能赢的场次

    输入输出样例

    输入样例#1: 复制
    3 3
    J W YYY
    J HK E
    2 2 2
    2 2 2
    
    输出样例#1: 复制
    3
    

    说明

    第一场主席赢记者,第二场高人赢女王,第三场膜法师赢记者。

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