题目描述 聪聪研究发现,荒岛野人总是过着群居的生活,但是,并不是整个荒岛上的所有野人都属于同一个部落,野人们总是拉帮结派形成属于自己的部落,不同的部落之间则经常发生争斗。只是,...
快速排序
洛谷 P2376 [USACO09OCT]津贴Allowance 题解【贪心】【快速排序】
贪心大毒瘤。。。 Description As a reward for record milk production, Farmer John has decided to start paying Bessie the cow a small weekly allowance. FJ has a set of c...
凸包学习笔记【计算几何】【凸包】
求凸包就是求一个最小周长凸多边形,使得所求点集都被包含在这个凸多边形里。 为什么是凸多边形?根据三角形不等式,如果有一个满足包含所有点的凹多边形,一定存在额外的一条边使得多边形的边...
NOIP模拟题 大奖赛 题解【双向搜索】【二分答案】【快速排序】
这是一道双向搜索(折半搜索)的经典题目改编。 题目描述 Lancelot市最近要举办大奖赛啦!住在市里的市民都十分兴奋,Morgan也不例外。他查了一下比赛的信息,发现比赛一共有N场,并...
NOIP模拟题 秘密信息 题解【字符串】【快速排序】【贪心】
这个题主要是手玩找规律吧(不过最近怎么老看到手玩这个名词 题目描述 Irene想用一下的方法加密一条信息(这是她从密码学书上自学来的): 假定这条信息可以用一个字符串S表示,其...
Codeforces 994B Knights of a Polygonal Table (#488 Div 2 B)题解【堆】【快速排序】【贪心】
算是第一次打CF…… 思维量不算大,做法比较巧妙,而且k≤10,就很好做了。 Description Unlike Knights of a Round Table, Knights of a Polygonal Table depriv...
洛谷 P1158 NOIP2010普及组 导弹拦截 题解【枚举】【前缀最大值】【快速排序】
我估计CCF也经历了11年的韬光养晦。。。 题目描述 经过11年的韬光养晦,某国研发出了一种新的导弹拦截系统,凡是与它的距离不超过其工作半径的导弹都能够被它成功拦截。当工作半径为0时...
洛谷 P2345 奶牛集会 题解【暴力】【树状数组】【逆序对】【排序】
当时考试看到这个题感觉暴力挺多分的,结果暴力一打并开O2就A了???数据略水。。。 题目背景 MooFest, 2004 Open 题目描述 约翰的\(N\)头奶牛每年都会参加“哞哞大会”。哞哞大会是奶牛界的盛事。集会上的...
求逆序对的方法【逆序对】【树状数组】【归并排序】
题面可见洛谷P1908逆序对 逆序对,最朴素的做法就是$ O(N^2)$的了,枚举每个数对,逆序则sum++。 不过主流做法是归并排序,也可以用树状数组(线段树)来做。 ...
关于各种排序方法的见解
众所周知,排序是一种基础算法。新手在入门时几乎都会接触到这类问题,这些问题可以练习对基础语言的掌握能力,如对数组的处理。 排序常见的有冒泡、桶、归并、快排(甚至可以利用优先队列或者是红-黑树...