Codeforces815D题解
题意:
- 给定N张卡牌,每张卡牌有三个属性$a_i,b_i,c_i$。
- 现在给出三个数$p,q,r$,分别表示三个属性的上限。问有多少种不同的卡牌,能压制给定的$n$张卡牌(只要三个属性有两个的值严格大于另一卡牌即可)。其中属性值一定是正整数。
题解:
- 首先肯定要按某一维排序,我们不妨排序$c_i$。
- 从大到小枚举$c$,我们发现每次的答案都是一个类似于阶梯的图。然后(好吧我也不知道)似乎先算出最后的所有的卡牌都加入后的阶梯图,统计$a,b$维的前缀和,然后每个$c$应该分类讨论一下就可以了。
- 时间复杂度$O(nlogn+p+q+r)$。
代码:
1 |
|