Feng003

算法课课程作业

codeforces(2) DP(3) 图论(2) 基础数据结构(2) 字符串(1) 数据结构课程(1) 概率期望(1) 题解(6)

/ 注册

全部文章 / 算法课课程作业（共4篇）

最大连续乘积子数组

给定一个长度为N的浮点数数组a。请找出其中乘积最大的子数组。例如，给定数组{-2.5, 4, 0, 3, 0.5, 8, -1}，则取出的最大乘积子数组为{3, 0.5, 8}。也就是说，在上述数组中，3 , 0.5和8这三个数是连续的，而且乘积是最大的。思路：设计状态代表以结尾的子数组中，乘积...

DP

2020-05-22

0 583

各大排序模板

快速排序 int a[N];//待排序数组 inline void swap(int& x, int& y) { int tmp = x; x = y; y = tmp; } void quick_sort(int l, int r) { if (l...

排序算法

2020-04-19

0 447

平衡树之splay

　　Splay这个名字在我很早的时候就听说过了，是寒假的时候在lyd的蓝书上学平衡树章节的时候，他在那一章节的最后强力推荐的一种平衡树。"Splay(伸展树)灵活多变，应用广泛，能够很方便地支持各种动态的区间操作，是用于解决复杂问题的一个重要的高级数据结构。"(原话)。当时就使...

平衡树 Splay

2020-04-16

0 571

找区间第k大（小）的数

问题：给定n个整数，如何用最快的方法求出第k大的数？　　我们当然可以对这n个整数排序然后直接输出第k大的数，时间复杂度为O(nlog n)。　　但是实际上我们可以用基于快速排序所用到的思想，在每一层递归中，随机选取一个数为基准值，把比它大的数交换到左半段，把其余的数和基准值自身一起作为右半段。在这...

区间第ｋ大

2020-04-01

0 873