状态区分类问题

· · 个人记录

见过几次，但还是不太会，这里小记一下。

标题是我随便起的，可能不太恰当。

有一个比较经典的模型：有 n 种不同的状态，可以进行 m 次某种询问，询问的结果对应一个状态的集合，要求设计某种策略能够保证将 n 种状态两两区分开。

给定 m，求最大的 n。

这种题如果直接构造策略一般很难行得通，只有从更加本质的角度分析。

可以考虑求出 m 次询问能够获得的最多的本质不同结果个数。

一般对于这类题而言，这个数即为答案，可以通过构造证明其正确性。值得一提的是，这里是对着结果构造，而不是直接对着题目漫无目的地猜策略，因此可以说这会容易许多，并且更不容易出错。

我并没有见过上面这个过程无法解决的这类问题，如果哪天真的遇到了，随便猜点看起来对的东西就可以跑路了