CF754C Vladik and chat 题解

Trista_ · 2023-11-20 20:10:23 · 题解

洛谷 CF754C 题解

题目传送门

题目算法

模拟

题目思路

题目给出了一段聊天记录，但是里面有若干聊天记录的发布者缺失，要求我们复原出缺失的发布者，并输出完整的聊天记录，如果无解输出 impossible 。

现在已知：

• 一条消息的发送者不可能在他的消息里出现自己的名字。

• 一个人不会连续发两条消息。

所以我们可以通过：

• 查看该条消息里出现的人名。

• 查看上一条消息或者下一条消息的发布者。

从而帮助我们推断出这条消息的发布者。

我们构建 ImpossibleName 数组来存放下一条消息不可能的发布者，所以我们要将每一条消息的发布者存入此数组（因为一个人不会连续发两条消息）。

我们构建 PossibleName 数组来存放该条消息可能的发布者：

1. PossibleName 初始状态为所有人（因为一开始所有人都可能是这条消息的发布者）。

2. 查看这条消息里出现的人名，并把他们从 PossibleName 里面删除。

3. 把 ImpossibleName 里面的元素（即这一条消息不可能的发布者）从 PossibleName 里面删除。

4. 如果已知下一条消息的发布者，就把下一条消息的发布者从 PossibleName 里面删除（因为一个人不会连续发两条消息）。

5. 如果最后 PossibleName 里面只剩下一个元素（即这条消息只有一个可能的发布者，即这条消息可能的发布者唯一），就说明这条消息的发布者就是 PossibleName 里面的那个元素；如果最后 PossibleName 里面剩下的元素个数不为一（即这条消息没有可能的发布者或者有多个可能的发布者，即这条消息可能的发布者不唯一），就无解。