bzoj 2761: [JLOI2011]不重复数字 map

这真的是JL省选题么。std map基本使用的考察。

bzoj 4198: [Noi2015]荷马史诗 优先队列 哈夫曼编码

大概颓了两天之后心情好了点。QwQ。写了一发题。。

讲道理喝维他柠檬茶来消愁,感觉,好贵,冰红茶只有一半价格的说。。233

大概哈夫曼编码随便搞一下就好了,很简单。

2进制的哈夫曼是二叉树,那你就k叉树好了。

唯一注意一下的就是,常见的二进制喊夫曼树是你有多少个元素都可以把树[……]

Read more

省选模板-数据结构-pb_ds可并堆

UOJ #10. 【UTR #1】pyx的难题

首先这题二分答案然后用优先队列暴力判一判是90分。

然后大概需要O(松)的卡常技巧。

后来发现,二分答案其实不需要,我们可以先假装特殊的这题不存在,看看发生在tx -> T这段时间内会有那些题。显然只有这些题是 与特殊题有关系的,暴力瞎搞一下就好了。。这题代码好不好写。参照了下别人[……]

Read more

bzoj 4010: [HNOI2015]菜肴制作 拓扑排序 优先队列

我们考虑,字典序最小的方案不对的。但是倒序字典序最大的方案一定是对的。因为靠后的位置尽可能的被劣质的菜品占据了。所以我们加反边,然后拓扑排序即可。

bzoj 1208: [HNOI2004]宠物收养所 set

set搞一搞就好了,忘记取模了,然后调了半天。mdzz。一个set存x,一个存-x。这样子可以用low_bound()来访问前驱和后继了。感觉就是注意别写乱了,就好了。

codeforces 401div2 b Game of Credit Cards

就是一道类似田忌赛马的题。如何能让自己输的局最少,如何能让对方输的局最多。其实排个序扫一下就好了。然而为了偷懒用set直接查前驱和后继,然后因为重复元素GG掉了。换了multiset就好了。如果想让自己输的最少,就对于队手的每个元素用自己的lower_bound对战。如果想让队手输的最多,就用自己的[……]

Read more

1588: [HNOI2002]营业额统计 set

我们只要有办法快速查找之前第一个>=的数,和第一个<=的数就行了。那么我们可以建立两个set,一个正常,一个为负值。这样子就可查询<=的情况了。

[LNWC2016]过河 贪心 优先队列

题目描述

(N+1)个平行于y轴的河岸排成一排,每两个河岸之间夹着一条河,所以一共有N条河。第i条河的宽度为wi在第i条河中行进的速度为vi。河岸的宽度忽略不计。令X=Σwi现在要(0,0)出发,渡过这N条河,到达(X,Y)(Y是一个给定的整数)。在渡河时,必须从一个整点走到另一个整点[……]

Read more

STLmap 学习笔记

最近尝试通过迭代器反向遍历map,然后就鬼畜了,发现自己map还有一些细节不太了解,所以来写篇博客。

MAP是什么?

MAP提供一对一的下标访问。

举一个简单的例子,加入你有用数组记录一些东西,个数很少,但是下标可能会非常大,比如10^15,所以我们此时使用传统数组是不合适的,我们[……]

Read more