P3825 [NOI2017]游戏

    • 351通过
    • 1.2K提交
  • 题目提供者 deluxurous
  • 评测方式 云端评测
  • 标签 2-SAT 后缀数组,SA 强连通分量,缩点 拓扑排序 NOI系列 2017 O2优化 Special Judge 高性能
  • 难度 NOI/NOI+/CTSC
  • 时空限制 1000ms / 262MB

题解

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

    推荐的相关题目 显示

    题目背景

    狂野飙车是小 L 最喜欢的游戏。与其他业余玩家不同的是,小 L 在玩游戏之余,还精于研究游戏的设计,因此他有着与众不同的游戏策略。

    题目描述

    小 L 计划进行 $n$ 场游戏,每场游戏使用一张地图,小 L 会选择一辆车在该地图上完成游戏。

    小 L 的赛车有三辆,分别用大写字母ABC表示。地图一共有四种,分别用小写字母xabc表示。其中,赛车A不适合在地图a上使用,赛车B不适合在地图b上使用,赛车C不适合在地图c上使用,而地图x则适合所有赛车参加。适合所有赛车参加的地图并不多见,最多只会有d张。

    $n$ 场游戏的地图可以用一个小写字母组成的字符串描述。例如:S=xaabxcbc表示小 L 计划进行 $8$ 场游戏,其中第 $1$ 场和第 $5$ 场的地图类型是x,适合所有赛车,第 $2$ 场和第 $3$ 场的地图是a,不适合赛车A,第 $4$ 场和第 $7$ 场的地图是b,不适合赛车B,第 $6$ 场和第 $8$ 场的地图是c,不适合赛车C

    小 L 对游戏有一些特殊的要求,这些要求可以用四元组 $(i, h_i, j, h_j)$ 来描述,表示若在第 $i$ 场使用型号为 $h_i$ 的车子,则第 $j$ 场游戏要使用型号为 $h_j$ 的车子。

    你能帮小 L 选择每场游戏使用的赛车吗?如果有多种方案,输出任意一种方案。如果无解,输出 “-1’’(不含双引号)。

    输入输出格式

    输入格式:

    输入第一行包含两个非负整数 $n, d$ 。

    输入第二行为一个字符串 $S$ 。 $n, d, S$ 的含义见题目描述,其中 $S$ 包含 $n$ 个字符,且其中恰好 $d$ 个为小写字母 $x$ 。

    输入第三行为一个正整数 $m$ ,表示有 $m$ 条用车规则。接下来 $m$ 行,每行包含一个四元组 $i, h_i, j, h_j$ ,其中 $i, j$ 为整数, $h_i, h_j$ 为字符abc,含义见题目描述。

    输出格式:

    输出一行。

    若无解输出 “-1’’(不含双引号)。

    若有解,则包含一个长度为 $n$ 的仅包含大写字母ABC的字符串,表示小 L 在这 $n$ 场游戏中如何安排赛车的使用。如果存在多组解,输出其中任意一组即可。

    输入输出样例

    输入样例#1: 复制
    3 1
    xcc
    1
    1 A 2 B
    输出样例#1: 复制
    ABA
    输入样例#2: 复制
    100 8
    bbccxabbcxaabbabcaaxbxaaccbcxcccbaccbccbbacaabcbcabxccbbabccabcabbacbbbbabccaabcaaacbabcacxabaxcabbb
    200
    61 B 14 A
    34 B 76 B
    17 B 13 A
    5 C 2 C
    90 A 73 C
    6 B 72 C
    21 A 1 C
    54 B 96 B
    2 C 44 B
    7 A 32 B
    71 A 83 C
    65 A 21 A
    32 B 45 B
    18 B 34 B
    51 A 13 A
    89 C 63 B
    26 B 22 C
    38 B 94 C
    86 C 95 C
    95 C 76 B
    67 B 100 A
    99 A 40 A
    35 A 53 B
    47 B 41 A
    36 B 69 A
    75 B 52 B
    90 A 7 A
    96 B 59 A
    92 C 98 C
    23 B 80 B
    13 A 48 A
    54 B 2 C
    93 C 39 A
    96 B 87 A
    66 A 15 C
    38 B 16 A
    54 B 41 A
    67 B 40 A
    45 B 66 A
    32 B 80 B
    34 B 59 A
    31 B 75 B
    65 A 78 C
    34 B 56 C
    28 B 8 A
    87 A 40 A
    56 C 40 A
    93 C 100 A
    31 B 41 A
    39 A 48 A
    55 C 28 B
    64 C 60 B
    69 A 82 C
    99 A 13 A
    47 B 30 B
    45 B 33 A
    88 A 75 B
    59 A 4 B
    53 B 44 B
    11 B 80 B
    52 B 50 C
    71 A 7 A
    41 A 63 B
    58 A 23 B
    55 C 96 B
    71 A 9 A
    24 B 34 B
    68 B 92 C
    15 C 18 B
    56 C 14 A
    98 C 39 A
    27 A 56 C
    95 C 31 B
    100 A 57 C
    62 C 51 A
    6 B 32 B
    9 A 99 A
    46 C 66 A
    21 A 1 C
    14 A 91 C
    61 B 37 A
    76 B 81 B
    80 B 43 B
    98 C 87 A
    56 C 49 A
    39 A 5 C
    88 A 65 A
    60 B 34 B
    95 C 11 B
    90 A 56 C
    61 B 48 A
    87 A 21 A
    46 C 84 A
    87 A 18 B
    36 B 52 B
    61 B 97 B
    40 A 36 B
    77 C 71 A
    78 C 26 B
    57 C 85 C
    75 B 95 C
    41 A 14 A
    59 A 1 C
    47 B 5 C
    11 B 88 A
    60 B 24 B
    35 A 98 C
    44 B 32 B
    2 C 69 A
    33 A 62 C
    65 A 72 C
    97 B 93 C
    94 C 27 A
    19 C 51 A
    63 B 45 B
    97 B 4 B
    10 A 8 A
    4 B 56 C
    12 C 66 A
    95 C 72 C
    41 A 30 B
    69 A 85 C
    13 A 2 C
    18 B 14 A
    71 A 3 B
    75 B 87 A
    26 B 24 B
    80 B 20 B
    2 C 50 C
    70 A 64 C
    46 C 18 B
    67 B 55 C
    25 B 22 C
    62 C 37 A
    40 A 56 C
    60 B 80 B
    37 A 28 B
    16 A 50 C
    82 C 34 B
    15 C 4 B
    88 A 42 B
    90 A 13 A
    17 B 21 A
    32 B 18 B
    22 C 53 B
    81 B 67 B
    71 A 48 A
    73 C 47 B
    21 A 34 B
    83 C 60 B
    40 A 78 C
    22 C 7 A
    79 C 55 C
    40 A 46 C
    58 A 79 C
    87 A 99 A
    92 C 55 C
    20 B 75 B
    72 C 41 A
    28 B 52 B
    60 B 50 C
    51 A 32 B
    96 B 24 B
    18 B 31 B
    83 C 59 A
    24 B 74 A
    88 A 97 B
    81 B 67 B
    51 A 72 C
    64 C 8 A
    51 A 50 C
    7 A 42 B
    4 B 78 C
    68 B 27 A
    70 A 95 C
    30 B 29 C
    96 B 81 B
    13 A 44 B
    4 B 82 C
    74 A 38 B
    92 C 49 A
    12 C 79 C
    46 C 44 B
    97 B 96 B
    15 C 60 B
    56 C 65 A
    61 B 14 A
    58 A 16 A
    43 B 26 B
    42 B 12 C
    72 C 24 B
    41 A 68 B
    4 B 5 C
    63 B 59 A
    86 C 88 A
    48 A 77 C
    36 B 59 A
    7 A 33 A
    2 C 56 C
    81 B 69 A
    
    输出样例#2: 复制
    CABABCCABBCBCABAACBCCBCCAACBCBAACCBAAABCCCACCAACACCBAAAACCBACAABCCCACCCABCAABBAACBBACBCBBBCBABBACACA
    

    说明

    【样例1解释】

    小 L 计划进行 $3$ 场游戏,其中第 $1$ 场的地图类型是x,适合所有赛车,第 $2$ 场和第 $3$ 场的地图是c,不适合赛车C

    小 L 希望:若第 $1$ 场游戏使用赛车A,则第 $2$ 场游戏使用赛车B。那么为这 $3$ 场游戏分别安排赛车ABA可以满足所有条件。若依次为 $3$ 场游戏安排赛车为BBBBAA时,也可以满足所有条件,也被视为正确答案。但依次安排赛车为AABABC时,因为不能满足所有条件,所以不被视为正确答案。

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