ABC350B Dentist Aoki
题目分析
- 初始时，编号为 $1$ 到 $N$ 的洞中各有一颗牙齿，总计 $N$ 颗牙齿；
- 每次治疗操作针对一个洞：
- 如果该洞中有牙齿，则移除牙齿（该洞变空）；
- 如果该洞为空，则长出一颗牙齿；
- 需要根据 $Q$ 次操作后，计算剩余牙齿的数量。
解题思路
- 使用一个长度为 $N$ 的布尔数组
vis 来表示每个洞是否有牙齿；
- 初始化时，所有洞都有牙齿，即所有元素为
0；用 $0$ 来充当有牙齿。
- 遍历治疗操作序列 $T_i$：
- 若
vis[T[i]] 是 0，置为 1（移除牙齿）；
- 否则置为
0（长出牙齿）；
- 最后统计
vis 中为 0 的个数，即剩余牙齿数量。
实现步骤
- 读入 $N, Q$；
- 定义大小为 $1005$ 的布尔数组
vis，设置为全局变量，这样默认均为 $0$；
- 读取 $Q$ 个治疗洞编号 $T_i$；
- 对每个 $T_i$，切换
vis[T[i]] 的状态；
- 遍历
vis 统计为 0 的数量；
- 输出该数量。
复杂度分析
- 时间复杂度：$O(N + Q)$，初始化和遍历操作均为线性；
- 空间复杂度：$O(N)$，用于存储每个洞的状态。
总结
- 利用布尔状态表示洞的牙齿是否存在；
- 每次操作直接切换对应状态；
- 最终统计
0 的数量即为剩余牙齿数。