9557.最有节目效果的一集

Time Limit: 3s Memory Limit: 512MB

小 E 和小 L 是某项赛事的狂热粉丝，一直以这个赛事为闲聊话题之一。

某项赛事有 $3 \times n$ 个战队参加，小组赛阶段这些队伍被均分分为 $3$ 个组。同一个小组的所有队伍打单循环赛（即每两个队伍之间都会打一场），不同小组的队伍之间不会比赛。每个战队有 $5$ 个选手。该比赛不会有平局。

有一个关于这项赛事的论坛。大家会在论坛发帖讨论队伍之间的战况。但是有的帖子可能是无效消息。

你经常好奇某个队伍目前在小组的排名，你会根据这个论坛已知的有效消息，计算目前的小组排名。

小组排名的计算方式是：

  1. 按胜场从多到少排序。

  2. 胜场数相同，按净胜分之和从大到小排序（净胜分 = 总得分 - 总失分）。

  3. 净胜分相同按队伍名的字典序从小到大排序。

你已知战队分组情况和每个战队的成员名字（保证战队名、成员名字互不相同）。

有三种操作：

  1. 新增一条论坛消息:

    格式为: a fan of A: The score of our game against Team B is a-b.，其中 A 是选手名或队伍名，B 是队伍名。 A 是选手名的时候，表示该选手所在的队伍战胜或输给了 B 队伍。"a-b"是两队的比分，其中 b 表示 B 队的得分。

    消息分为有效消息和无效消息：

    • 当该消息提到的 A、B 两队不在一个小组时，该消息为无效消息。
    • 当该消息与消息时间早于它的有效消息讨论的是同一场比赛时（“A对战B” 和 “B对战A”是同一场比赛），该消息为无效消息。

    不符合以上两条且没有被管理员标记为无效消息的消息是有效消息

  2. 管理员标记无效消息：

    管理员标记论坛的第 x 条消息为无效消息（注意管理员操作不计入“消息数”），保证 x 不大于论坛已经存在的消息数。

    注意：

    1. 管理员的标记只代表这条消息是无效消息，不代表这个比分是无效的。可能有效消息的比分和这条一样。
    2. 原本被认为是有效消息的 x 被管理员标记为无效消息后，与 x 讨论同一场比赛且未被管理员标记为无效消息的最早的一条消息会变为有效消息。如果不存在，则说明这两组的比分未知。
    3. x 可能本身就是无效消息。管理员可能重复标记。

  3. 查询队伍 A 在小组内的排名。

    根据已知有效消息，计算目前的各队伍得分，根据计算结果得到目前队伍 A 在小组内的排名。

Input Format(From the terminal/stdin)

本题有多组测试数据。第一行一个正整数 $T$，表示数据组数，接下来输入每组测试数据。

对于每组测试数据：

  • 第一行输入两个正整数 $n,k$，表示有 $3n$ 个战队数量，三种操作一共有 $k$ 条。
  • 接下来 $3n$ 行，每行 $6$ 个字符串和 $1$ 个正整数，第一个字符串表示战队名称，接下来 $5$ 个字符串表示战队所有队员的名字，接下来一个正整数表示战队所在的小组编号。
  • 接下来 k 行，每行第一个正整数为 op。
    • op=1 时，接下来为一句话 a fan of A: The score of our game against Team B is a-b.，含义见题目描述。
    • op=2 时，接下来为一个正整数 x，表示管理员标记论坛的第 x 条消息为无效消息。
    • op=3 时，接下来为一个正整数 x，表示查询战队 x 目前在小组内的排名。

Output Format(To the terminal/stdout)

对于每组测试数据的每个 op=3 的操作，输出一行一个整数表示组内排名。

Sample Input

Copy 
2
3 5
T1 P1_1 P1_2 P1_3 P1_4 P1_5 2
T2 P2_1 P2_2 P2_3 P2_4 P2_5 1
T3 P3_1 P3_2 P3_3 P3_4 P3_5 1
T4 P4_1 P4_2 P4_3 P4_4 P4_5 2
T5 P5_1 P5_2 P5_3 P5_4 P5_5 2
T6 P6_1 P6_2 P6_3 P6_4 P6_5 3
T7 P7_1 P7_2 P7_3 P7_4 P7_5 1
T8 P8_1 P8_2 P8_3 P8_4 P8_5 3
T9 P9_1 P9_2 P9_3 P9_4 P9_5 3
1 a fan of P4_1: The score of our game against Team T6 is 3-6.
1 a fan of T5: The score of our game against Team T1 is 4-5.
1 a fan of T5: The score of our game against Team T6 is 7-2.
2 3
3 8
3 3
T1 P1_1 P1_2 P1_3 P1_4 P1_5 1
T2 P2_1 P2_2 P2_3 P2_4 P2_5 1
T3 P3_1 P3_2 P3_3 P3_4 P3_5 1
T4 P4_1 P4_2 P4_3 P4_4 P4_5 2
T5 P5_1 P5_2 P5_3 P5_4 P5_5 3
T6 P6_1 P6_2 P6_3 P6_4 P6_5 2
T7 P7_1 P7_2 P7_3 P7_4 P7_5 3
T8 P8_1 P8_2 P8_3 P8_4 P8_5 2
T9 P9_1 P9_2 P9_3 P9_4 P9_5 3
1 a fan of P2_1: The score of our game against Team T1 is 7-2.
1 a fan of P8_1: The score of our game against Team T1 is 7-2.
3 2 \n
 · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
 · ·   ·  ·     ·   ·     ·  ·   ·    ·       ·    ·  ·  ·    \n
 · ·   ·  ·   ·   ·     ·  ·   ·    ·       ·    ·  ·  ·    \n
 · ·   ·  ·   ·   ·     ·  ·   ·    ·       ·    ·  ·  ·    \n
 · \n
 · \n
 · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
  ·    ·    ·    ·    ·    · \n
 · ·   ·  ·     ·   ·     ·  ·   ·    ·       ·    ·  ·  ·    \n
 · ·   ·  ·     ·   ·     ·  ·   ·    ·       ·    ·  ·  ·    \n
 · \n

Sample Output

Copy 
2
1 \n
 \n

Hints

对于所有数据，保证：

  • $T\leq 11, 1\leq n\leq 10^3，1\leq k\leq 10^5$。
  • 在 op=1 的情况中 $a+b =9, a\geq 0, b\geq 0$。
  • 在 op=2 的情况中 x 不大于论坛已经存在的消息数。
  • 在 op=3 的情况中 $x<=3\times n$。

保证队伍名称和选手名称长度不超过 $50$ 个字符。

请注意 op=1 时，句法将严格按照a fan of A: The score of our game against Team B is a-b.输入。

Source: 2025“钉耙编程”中国大学生算法设计暑期联赛（8）, HDU, 8073

Submit

请先 登录
 Submit
题解(0)
© 2025 FAQs