P7204 题解

ikunTLE · 2024-06-11 16:23:22 · 题解

题目传送门

思路

由于删除特定的字符之后再多删也可以，发现答案具有单调性，故用二分实现。本题中的 N\le10^5，在 check 函数中调用肯定会超时，需要用前缀和预处理。

在 check 函数中，不外乎几种操作：询问每一种单词的数量，删除一些字母，判断字母是否重复。这些操作都可以用树状数组维护。

具体实现

1. 读入，对于每个字母出现的次数用前缀和维护。

2. 二分答案：对于每一次使用的 check 函数，枚举所有的字母。