ACM

Atcoder - 3N Numbers(优先队列)

Atcoder - 3N Numbers(优先队列)
题意:给出3N个点,删除其中N个点,将剩下的2N个数分成两份,求前面部分的和减去后面部分的和的最大值。题解:设前面部分为Na,后面部分为Nb,要使Na-Nb最大。我们可以先假设这删除的N个全都是从N+1到3N中删除的。那么Na最大的就是前面N个的和,我们用最小优先队列来维护这N个的值,然后把接下来的第N+1个数push 进去,删除其中最小的这样就得到了在前N+1个中删除一个的前面的最大值了,依次类... 继续阅读 »
ACM

CDOJ - 1334 郭大侠与Rabi-Ribi(stl、贪心)

CDOJ - 1334 郭大侠与Rabi-Ribi(stl、贪心)
开始一直想的是直接安时间-价值排序,然后从时间最少的开始for循环一遍找兔子,如果时间不够用则进入下一个时间段找兔子,然后就wa啊,后来想想有点不对,万一时间少的地方有比时间大的地方的兔子呢,所以这个地方要用一个优先队列来维护,和bzoj上面建筑抢修那个题一毛一样啊。地址:http://acm.uestc.edu.cn/#/problem/show/1334代码:StatusAcceptedTim... 继续阅读 »
ACM

CDOJ - 1339 郭大侠与线上游戏 (STL)

CDOJ - 1339 郭大侠与线上游戏 (STL)
很有意思啊,把set分成l、r两部分来用,由于中位数是k/2+1的位置,保证中位数始终在r这边就可以,在而且set还有rbegin的函数。平衡l、r两个set集合就行,辅以一个队列用来删除数用。地址:http://acm.uestc.edu.cn/#/problem/show/1339代码:StatusAcceptedTime917msMemory12004kBLength1831LangC++#... 继续阅读 »
ACM

AtCoder 074 D - 3N Numbers(STL,优先队列)

AtCoder 074 D - 3N Numbers(STL,优先队列)
题目的意思是,给你一个长为3N的序列,从中删除N个序列,将剩下的2N个序列平分后用前面的区间和减去后面的区间和,求最大的区间差。竟然考的是优先队列,真的是尴尬,还有输出要是%lld或者是cout。我的想法就是至少要在n-2n后面切开这段序列,然后前面一段排序后删除最小数,后面一段排序后删除最大数,一直排序肯定不行,所以用优先队列优化,开始还打算手写链表来着。。。代码:#include &... 继续阅读 »
ACM

HDU 1247 - Hat’s Words(字典树,map)

HDU 1247 - Hat’s Words(字典树,map)
题目的意思就是给你一些字符串,然后从字符串里面找这样的字符串输出:1、这个字符串在给出的列表里面2、这个字符串由其中其他两个字符串组成。一看就是字典树,建树,然后拆分字符串遍历,搜索就行。然后,这个题map也可以做,代码量减少一倍,时间增加一倍。代码:自建字典树:StatusAcceptedTime62msMemory8240kBLength1167LangC++#include <... 继续阅读 »
ACM

CodeForces 696A Lorenzo Von Matterhorn(STL)

CodeForces 696A Lorenzo Von Matterhorn(STL)
看着挺像线段树的,不是吗?但是不是,这是个STL中map的应用。开始看数据,只有q个命令,u、v的数据也不算很大,有没有什么办法可以把命令存起来就好了。像python中字典那样,后来发现C++中的map,好东西啊。说下思路,因为要计算u->v的权值之和,我们可以把权值放在v中,由于题目中给定的u、v特性,我们可以从最后一个v开始倒回来每次除以2,然后把权值加起来就好了,注意输入的区间大小值。... 继续阅读 »
ACM

C++ STL之map的使用

C++ STL之map的使用
C++里面的map真是个好东西,就像python中的字典一样。比如python中的:dict = {} dict['hello'] = 'world'在C++中就是:map<char, char> dict; dict["hello"] = "... 继续阅读 »