acgo题库
  • 首页
  • 题库
  • 题单
  • 竞赛
  • 讨论
  • 排行
  • 团队
  • 备赛专区

    竞赛

    • CSP-J/S
    • 蓝桥杯

    考级

    • GESP
    • CPA
    • 电子学会考级
登录
注册
题目详情题解(1)讨论(0)提交记录(2)
  • 自搬

    原文哦 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 看见没有 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,就能优美地统计优秀的配对了。 实现 动态开点字典树可以用数组模拟。

    userId_undefined

    暑 假 神(开学祭

    3阅读
    0回复
    0点赞
首页