Black Box(堆)

Black Box

对问题的分析设计过程

题目要求实现一个支持插入序列和在第$i$次查询序列第$i$小的数的算法,经过思考得到如下算法:

  1. 可以考虑直接用动态开节点的线段树或者BST来进行在线查询
  2. 若将序列分成前$i$小和其他,可以通过两个堆实现单次操作在$O(\log n)$的时间内的在线查询和修改
  3. 若使用时间倒流方法,将插入和删除离线从后向前处理,可以只使用两个栈实现上述操作

程序中用到的数据机构和算法

综合考虑到实现难度和时间空间复杂度,考虑用第二种方法实现。通过维护一个大根堆存储前i小的元素以及一个小根堆存储其他元素。对操作有如下实现方法:

  • 添加元素$x$
    • 元素$x$小于第$i$个元素:将元素$x$插入大根堆中,并将大根堆堆顶元素插入小根堆中。
    • 元素$x$大于第$i$个元素:将元素$x$插入小根堆中。
  • 查询输出大根堆堆顶元素,将小根堆堆顶元素插入大根堆中

程序的运行情况

提交一次即通过,提交情况如下:

在实习过程中得到的经验和体会

  1. 使用STL库将会大大减少代码复杂度
  2. 注意初始化问题

Code:

 

JLOI2015 解题报告

JLOI2015 真的不愧是NOI出题组出的,题目难度够吊。不过每一道都是结论题和乱搞题真的很不好玩。。。

T1:[JLOI2015]有意义的字符串

首先贴下popoqqq的blog

感性的认识就是感觉到部分分是个斐波那契数列的通项公式然后考虑是否能把该式子化成递推式然后矩阵乘法算了。。感觉是超级恶心的一道题了,还得用快速乘法。。。

T2:[JLOI2015]城池攻占

首先这道题我们先考虑暴力,也就是每个点向父亲跑,我们考虑能否一起做,可以发现在同一个点的骑士可以用一个堆维护一起跳(因为没有改变优先级的操作)然后再用懒标记维护,我们可以直接用一个可合并堆来维护就可以啦

当然这道题用线段树,倍增都是可行的,就是空间比较拙计罢了,需要用一些奇奇怪怪的方法来干

CODE:

T3:[JLOI2015]装备购买

首先这个其实是求一个代价最小的最大线性无关集合(不会去线性代数把),线性无关集合也就是指在该集合中没有一个向量能由该集合的其他向量组成

所以该集合其实就是一组基,那么我们可以每次用高斯消元判断当前的向量是否能由其他向量组成,如果不行的话就加入答案了

求代价最小就排个序即可

CODE:

T4:[JLOI2015]骗我呢

这道题比较奇葩啦

首先我们考虑每一行,可以发现是单调递减的,并且肯定只缺了一个格,所以我们设f[i][j]为第i行缺j的方案数

可得f[i][j]=sigma(f[i-1][k]) k<=j+1

也就是f[i][j]=f[i][j-1]+f[i-1][j+1]

发现这个形式长得很像组合数,也可想求组合数那样看成求路径数。

我们把第i行向右平移i位,那么这个图就变成这样了

也就是把求这样子的路径方案数。

我们考虑先记下组合数那样的矩形图,再如何去掉左下和右上的点

很明显我们可以将终点按y=-x-1那条线镜面反射即可。

右上角也相似,但可能出现:左上->右下的情况,所以我们还要再去掉这种情况

这样推下去

CODE:

T5:[JLOI2015]管道连接

这是一个叫斯坦纳树的东西= =,以前知道但没写过,今天终于写了一次了

首先我们可以记f[i][j]为点的联通状态为i,经过点j的距离最小值,那么有两种状态转移

i的转移f[i][j]=max(f[k][j]+f[i^k][j])k为i的子集

j的转移:我们先求出i的转移,然后一边spfa即可

这样可以证明是正确的

这样我们就求出了一组点的答案,那么多组点我们可以用一个dp来合并答案

写起来还是挺舒服的,很多东西都能用这个东西解决,插头dp啊什么的

CODE:

T6:[JLOI2015]战争调度
这道题还是挺不错的,jloi考了好多要让你算空间的题- –

记f[i][j][k]为第i个节点祖先状态为j有k个儿子选择战争的最小答案,那么我们考虑一下这样的状态数以及转移复杂度

第i层的节点祖先状态有2^i儿子数有2^n-i一共有2^n个状态,所以总状态数为4^n

每个节点的转移是O(k)的,总的时间复杂度就是n*4^n,可以解决本题

这个主要还是得考你对时间和空间复杂度的分析= =

CODE:

好啦总结一下这套题吧= =

首先我觉得出得太noi化了没有省选的感觉,但又没有noi那么难,有种四不像的感觉

很多题目的想法都很值得学习,而且题解的ppt上的总结写得非常好

总的来说还是值得一刷的