• Black Box(堆)

    Black Box(堆)

    BlackBox对问题的分析设计过程题目要求实现一个支持插入序列和在第$i$次查询序列第$i$小的数的算法,经过思考得到如下算法:可以考虑直接用动态开节点的线段树或者BST来进行在线查询若将序列分成前$i$小和其他,可以通过两个堆实现单次操作在$O(\logn)$的时间内的在线查询和修改若使用时间倒流方法,将插入和删除离线从后向前处理,可以只使用两个栈实现上述操作程序中用到的数据机构和算法综合考虑到实现难度和时间空间复杂...

    02017年10月29日35,算法
  • JLOI2015 解题报告

    JLOI2015 解题报告

    JLOI2015真的不愧是NOI出题组出的,题目难度够吊。不过每一道都是结论题和乱搞题真的很不好玩。。。T1:[JLOI2015]有意义的字符串首先贴下popoqqq的blog吧感性的认识就是感觉到部分分是个斐波那契数列的通项公式然后考虑是否能把该式子化成递推式然后矩阵乘法算了。。感觉是超级恶心的一道题了,还得用快速乘法。。。T2:[JLOI2015]城池攻占首先这道题我们先考虑暴力,也就是每个点向父亲跑,我们考虑能否一起做,...