原文哦 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 看见没有 01Trie 的，赶紧来交一篇。 题意简述 笔和笔盖分别有两个属性 xxx 和 yyy，yyy 相同的笔和笔盖可以组成配对，xxx 和 yyy 都相同的笔和笔盖可以组成优秀的配对。问最多有几个配对，几个优秀的配对。 思路 配对很简单，开两个桶，把不同东西的 yyy 分别统计一下，答案就是 ∑min⁡(b1(i),b2(i))\sum\min(b_1(i),b_2(i))∑min(b1 (i),b2 (i))。 优秀的配对虽然也可以开桶，但是如果数据范围再大一点就会爆空间。发现桶的大部分空间都被浪费，这个时候我们就可以用到 map 了。然而 map 常数略大，更好的选择是动态开点的字典树。对于每一个物品，我们把它的两个属性压进一个 int，然后扔进一个 01Trie，就能优美地统计优秀的配对了。 实现 动态开点字典树可以用数组模拟。