Codeforces Round #421 (Div. 2)

A. Mister B and Book Reading

Mister B once received a gift: it was a book about aliens, which he started read immediately. This book had c pages.

At first day Mister B read v0 pages, but after that he started to speed up. Every day, starting from the second, he read a pages more than on the previous day (at first day he read v0 pages, at second — v0 + a pages, at third — v0 + 2a pages, and so on). But Mister B is just a human, so he physically wasn’t able to read more than v1 pages per day.

Also, to refresh his memory, every day, starting from the second, Mister B had to reread last l pages he read on the previous day. Mister B finished the book when he read the last page for the first time.

Help Mister B to calculate how many days he needed to finish the book.

第一天看v0页,每天比前一天多a页但不会超过v1页,每天会往前看最后l页,问c页的书几天能看完.

模拟题:

B. Mister B and Angle in Polygon

On one quiet day all of sudden Mister B decided to draw angle a on his field. Aliens have already visited his field and left many different geometric figures on it. One of the figures is regular convex n-gon (regular convex polygon with n sides).

That’s why Mister B decided to use this polygon. Now Mister B must find three distinct vertices v1, v2, v3 such that the angle 角V1V2V3(where v2 is the vertex of the angle, and v1 and v3 lie on its sides) is as close as possible to a. In other words, the value |角V1V2V3 – a| should be minimum possible.

If there are many optimal solutions, Mister B should be satisfied with any of them.

从一个正n多边形上选择三个点,V1V2V3组成的角度离a最近。

由于同弧所对圆周角相等,所以V1=1,V2=2,找最长的V1V3即可。

D. Mister B and PR Shifts

Some time ago Mister B detected a strange signal from the space, which he started to study.

After some transformation the signal turned out to be a permutation p of length n or its cyclic shift. For the further investigation Mister B need some basis, that’s why he decided to choose cyclic shift of this permutation which has the minimum possible deviation.

Let’s define the deviation of a permutation p as \(\sum_{i=1}^{n}|{p[i]-i}|\).

Find a cyclic shift of permutation p with minimum possible deviation. If there are multiple solutions, print any of them.

Let’s denote id k (0 ≤ k < n) of a cyclic shift of permutation p as the number of right shifts needed to reach this shift, for example:

k = 0: shift p1, p2, … pn,
k = 1: shift pn, p1, … pn - 1,
…,
k = n - 1: shift p2, p3, … pn, p1.

n个数,从1-n乱序,可以将其向后移动p位,求秩序值最小到时候是第几次。

记录下每个数是在目标位置(a[i] – i ==0)的左边还是右边,存下所有在目标左边的数。
cur[i]记录距离目标位置为i的数字的个数。
L记录开始在左边的个数,R记录开始在右边的个数。

然后模拟右移,对于第i次右移,左边的有L = L-cur[i-1], 右边的有R = R+cur[i-1],即当次位移刚好有cur[i-1]个数原本在目标位置左跑到了目标右。

特判最后一个数跑到第一个。L+1,R-1;

Codeforces Round #420 (Div. 2)

题目链接:http://codeforces.com/contest/821

A Okabe and Future Gadget Laboratory

Okabe needs to renovate the Future Gadget Laboratory after he tried doing some crazy experiments! The lab is represented as an n by n square grid of integers. A good lab is defined as a lab in which every number not equal to 1 can be expressed as the sum of a number in the same row and a number in the same column. In other words, for every x, y such that 1 ≤ x, y ≤ n and ax, y ≠ 1, there should exist two indices s and t so that ax, y = ax, s + at, y, where ai, j denotes the integer in i-th row and j-th column.
Help Okabe determine whether a given lab is good!

n * n的网格里(n <= 50),考虑每个不等于1的位置,在该行与该列上是否分别存在一个数,使得它们的和等于该位置的值,如果都存在输出“Yes”, 否则输出“No”。暴力枚举即可。

B Okabe and Banana Trees

Okabe needs bananas for one of his experiments for some strange reason. So he decides to go to the forest and cut banana trees.

Consider the point (x, y) in the 2D plane such that x and y are integers and 0 ≤ x, y. There is a tree in such a point, and it has x + y bananas. There are no trees nor bananas in other points. Now, Okabe draws a line with equation \(y=-\frac{x}{m}+b\). Okabe can select a single rectangle with axis aligned sides with all points on or under the line and cut all the trees in all points that are inside or on the border of this rectangle and take their bananas. Okabe’s rectangle can be degenerate; that is, it can be a line segment or even a point.

Help Okabe and find the maximum number of bananas he can get if he chooses the rectangle wisely.

Okabe is sure that the answer does not exceed 1018. You can trust him.

样例1
直接看样例1的图,m和b带入公式得到这样一条直线,图上每一个整点的值等于横纵坐标之和,在直线下方与坐标轴正半轴构成一个矩形,问这个矩形包含的值最大等于多少(只考虑整点,包含边界)。
直线与坐标轴交于(bm,0),(0,b)两点,确定右上角的点的位置就确定了整个矩形,然后等差数列求和,就得到了矩形的值,三分或者直接暴力可以得到最大值。

C Okabe and Boxes

Okabe and Super Hacker Daru are stacking and removing boxes. There are n boxes numbered from 1 to n. Initially there are no boxes on the stack.

Okabe, being a control freak, gives Daru 2n commands: n of which are to add a box to the top of the stack, and n of which are to remove a box from the top of the stack and throw it in the trash. Okabe wants Daru to throw away the boxes in the order from 1 to n. Of course, this means that it might be impossible for Daru to perform some of Okabe’s remove commands, because the required box is not on the top of the stack.

That’s why Daru can decide to wait until Okabe looks away and then reorder the boxes in the stack in any way he wants. He can do it at any point of time between Okabe’s commands, but he can’t add or remove boxes while he does it.

Tell Daru the minimum number of times he needs to reorder the boxes so that he can successfully complete all of Okabe’s commands. It is guaranteed that every box is added before it is required to be removed.

模拟进栈出栈,出栈顺序必须递增。

D Okabe and City

Okabe likes to be able to walk through his city on a path lit by street lamps. That way, he doesn’t get beaten up by schoolchildren.

Okabe’s city is represented by a 2D grid of cells. Rows are numbered from 1 to n from top to bottom, and columns are numbered 1 to m from left to right. Exactly k cells in the city are lit by a street lamp. It’s guaranteed that the top-left cell is lit.

Okabe starts his walk from the top-left cell, and wants to reach the bottom-right cell. Of course, Okabe will only walk on lit cells, and he can only move to adjacent cells in the up, down, left, and right directions. However, Okabe can also temporarily light all the cells in any single row or column at a time if he pays 1 coin, allowing him to walk through some cells not lit initially.

Note that Okabe can only light a single row or column at a time, and has to pay a coin every time he lights a new row or column. To change the row or column that is temporarily lit, he must stand at a cell that is lit initially. Also, once he removes his temporary light from a row or column, all cells in that row/column not initially lit are now not lit.

Help Okabe find the minimum number of coins he needs to pay to complete his walk!

bfs搜索题,从左上角到右下角,必须走在有灯的格子里,如果要去的格子没有灯,可以暂时照亮任意一行或者一列,但必须之前站在原来就是有灯的格子里,同时花费为1,问是否能到达目的地,如果能输出最小花费,否则输出-1。
分析下来有以下几点:

  • 每次bfs都是在原始就是有灯的点之间移动(除了终点)
  • 一行或者一列最多被照亮一次
  • 当前点,与下一次可以到达的点的横坐标或纵坐标距离小于等于2

E Okabe and El Psy Kongroo

Okabe likes to take walks but knows that spies from the Organization could be anywhere; that’s why he wants to know how many different walks he can take in his city safely. Okabe’s city can be represented as all points (x, y) such that x and y are non-negative. Okabe starts at the origin (point (0, 0)), and needs to reach the point (k, 0). If Okabe is currently at the point (x, y), in one step he can go to (x + 1, y + 1), (x + 1, y), or (x + 1, y - 1).

Additionally, there are n horizontal line segments, the i-th of which goes from x = ai to x = bi inclusive, and is at y = ci. It is guaranteed that a1 = 0, an ≤ k ≤ bn, and ai = bi - 1 for 2 ≤ i ≤ n. The i-th line segment forces Okabe to walk with y-value in the range 0 ≤ y ≤ ci when his x value satisfies ai ≤ x ≤ bi, or else he might be spied on. This also means he is required to be under two line segments when one segment ends and another begins.

Okabe now wants to know how many walks there are from the origin to the point (k, 0) satisfying these conditions, modulo 10^9 + 7.
从(0,0) 到(k,0),每个点可以到达右上,右,右下这三个点,但必须在c下方,0上方(包括0边界),问最终到达(k,0)有多少种方案。

dp,因为ci是一条与x轴平行的线段,所以从ai到ai+1的每一次的贡献都是一样的,可以用矩阵加速,c最多为15,所以不会超时

AtCoder Regular Contest 076

题目链接:http://arc076.contest.atcoder.jp/assignments

C – Reconciled?

Snuke has N dogs and M monkeys. He wants them to line up in a row.

As a Japanese saying goes, these dogs and monkeys are on bad terms. (“ken’en no naka”, literally “the relationship of dogs and monkeys”, means a relationship of mutual hatred.) Snuke is trying to reconsile them, by arranging the animals so that there are neither two adjacent dogs nor two adjacent monkeys.

How many such arrangements there are? Find the count modulo 109+7 (since animals cannot understand numbers larger than that). Here, dogs and monkeys are both distinguishable. Also, two arrangements that result from reversing each other are distinguished.

n只狗和m只猫排列,同种动物不能相邻出现,问有多少种排列方式(模1e9+7)
n和m相等时答案2 × n!× m!
n和m相差1时n! × m!
否则为0

D – Built?

There are N towns on a plane. The i-th town is located at the coordinates (xi,yi). There may be more than one town at the same coordinates.

You can build a road between two towns at coordinates (a,b) and (c,d) for a cost of min(|a−c|,|b−d|) yen (the currency of Japan). It is not possible to build other types of roads.

Your objective is to build roads so that it will be possible to travel between every pair of towns by traversing roads. At least how much money is necessary to achieve this?

求最小生成树的权值和,任意两点的权值为min(|x1-x2|,|y1-y2|),按横坐标和纵坐标分别排序然后kruskal+并查集

E – Connected?

Snuke is playing a puzzle game. In this game, you are given a rectangular board of dimensions R×C, filled with numbers. Each integer i from 1 through N is written twice, at the coordinates (xi,1,yi,1) and (xi,2,yi,2).

The objective is to draw a curve connecting the pair of points where the same integer is written, for every integer from 1 through N. Here, the curves may not go outside the board or cross each other.

Determine whether this is possible.

R × C的网格里有N 种数,每种数出现两次,给出它们在网格里的坐标,问是否能够使得所有相同的数相互连通,并且不会有交叉或者穿过其他边

顺时针考虑两次都出现在边界上的点,假设存在两点i,j如果出现顺序是i,j,i,j则不能满足要求,如果是i,j,j,i 或 i,i,j,j则满足,可以用栈来实现

F – Exhausted?

There are M chairs arranged in a line. The coordinate of the i-th chair (1≤i≤M) is i.

N people of the Takahashi clan played too much games, and they are all suffering from backaches. They need to sit in chairs and rest, but they are particular about which chairs they sit in. Specifically, the i-th person wishes to sit in a chair whose coordinate is not greater than Li, or not less than Ri. Naturally, only one person can sit in the same chair.

It may not be possible for all of them to sit in their favorite chairs, if nothing is done. Aoki, who cares for the health of the people of the Takahashi clan, decides to provide additional chairs so that all of them can sit in chairs at their favorite positions.

Additional chairs can be placed at arbitrary real coordinates. Find the minimum required number of additional chairs.

N 个人,M把椅子,每个人都要有椅子坐,第i个人不能坐[Li+1,Ri-1]里的椅子,最少要添多少椅子

贪心,先按左端点(L)排序,尽量先往左边垒,如果左边垒不下就垒右边,在已经垒好的集合里换一个右端点(R)最小的,最终还没有垒的全放在右端点。

Ubuntu下用gdb调试

安装cgdb

以a+b Problem为例。
1.调出控制台

2.生成执行文件

3.进入gdb

4.设置断点

5.运行

6.其他命令

九大基础排序算法

基础排序算法分析与总结

插入类排序

直接插入排序

算法思想
(1)将第i个记录插入到前面i-1个已经排序好的记录中
(2)插入过程为依次比较后移,直到找到比第i个记录小的数为止,插入。

算法实例
待排序列{48,62,35,77,55,14,35,98}
A){48} 62 35 77 55 14 35 98
B){48 62} 35 77 55 14 35 98
C){35 48 62} 77 55 14 35 98
D){35 48 62 77} 55 14 35 98
E){35 48 55 62 77} 14 35 98
F){14 35 48 55 62 77} 35 98
G){14 35 35 48 55 62 77} 98
H){14 35 35 48 55 62 77 98}
以下是用插入排序对30个元素的数组进行排序的动画:

对序列{6, 5, 3, 1, 8, 7, 2, 4}进行插入排序的实现过程如下

直接插入排序动画图:

算法实现

算法分析
1.空间复杂度:O(1)
2.平均时间复杂度:O(n²)
最差情况:反序,需要移动n*(n-1)/2个元素 ,运行时间为O(n^2)。
最好情况:正序,不需要移动元素,运行时间为O(n).
3.稳定的排序算法
4.该排序与选择排序的区别是:选中已经排好序列的后一个数来进行插入操作,没有从未排序数中选择的过程
5.该排序与折半插入排序的区别:减少比较次数,直接插入排序为挨个比较,折半插入排序为二分比较,效率更高

折半插入排序

算法思想
与直接插入排序类似,只是通过二分查找找到需要插入的位置,直接插入,而非一个一个比较查找
算法实例

A){48} 62 35 77 55 14 35 98
B){48 62} 35 77 55 14 35 98
C){35 48 62} 77 55 14 35 98
D){35 48 62 77} 55 14 35 98
E){35 48 55 62 77} 14 35 98
F){14 35 48 55 62 77} 35 98
G){14 35 35 48 55 62 77} 98
H){14 35 35 48 55 62 77 98}
算法实现

算法分析
1.空间复杂度:O(1)
2.平均时间复杂度:O(n²)
3.折半插入排序是一种稳定的排序算法
4.折半插入排序并没有改变时间复杂度,而是把比较次数的数量级降到了O(nlogn)
5.当n较大时 折半插入排序的比较次数要比直接插入排序的最差情况要好很多 但比其最好情况要差

希尔排序

算法思想
希尔排序法(缩小增量法) 属于插入类排序,是将整个无序列分割成若干小的子序列分别进行插入排序的方法。
把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至1时,整个文件恰被分成一组,算法便终止
希尔排序是基于插入排序的以下两点性质而提出改进方法的:
(1)插入排序在对几乎已经排好序的数据操作时,效率高,即可以达到线性排序的效率。
(2)但插入排序一般来说是低效的,因为插入排序每次只能将数据移动一位。
算法实例
假设有这样一组数[13 14 94 33 82 25 59 94 65 23 45 27 73 25 39 10],如果我们以步长为5开始进行排序,我们可以通过将这列表放在有5列的表中来更好地描述算法,
这样他们就应该看起来是这样:
13 14 94 33 82
25 59 94 65 23
45 27 73 25 39
10
然后我们对每列进行排序:
10 14 73 25 23
13 27 94 33 39
25 59 94 65 82
45
将上述四行数字,依序接在一起时我们得到:[10 14 73 25 23 13 27 94 33 39 25 59 94 65 82 45].这时10已经移至正确位置了,然后再以3为步长进行排序:
10 14 73
25 23 13
27 94 33
39 25 59
94 65 82
45
排序之后变为:
10 14 13
25 23 33
27 25 59
39 65 73
45 94 82
94
最后以1步长进行排序(此时就是简单的插入排序了)。
希尔排序动画图:

算法实现

算法分析
1.空间复杂度:O(1)
2.时间复杂度:平均 O(n^1.5)或O(n^1.3)
       最好 O(n)
       最坏 O(n^2)
3.希尔排序是一种不稳定的排序算法
4.希尔排序对于中等规模(n≤1000)的序列具有较高的效率,而且希尔排序算法简单,容易执行,因此很多排序应用程序都选用了希尔排序
5.关于增量d的取法,最初Shell提出取d=n[n/2]–下取整,再取d=d=n[n/2],直到d=1为止。
该思路的缺点是,奇数位置的元素在最后一步才会与偶数位置的元素进行比较,使得希尔排序效率降低
后来Knuth提出d=[n/3]+1
本文代码采用的是d=n[n/2]的增量取法

交换类排序

冒泡排序

算法思想
冒泡排序通过重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来,直到没有再需要交换的元素为止(对n个项目需要O(n^2)的比较次数)
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。
1.比较相邻的元素。如果第一个比第二个大,就交换他们两个。
2.对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
3.针对所有的元素重复以上的步骤,除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
算法实例
对序列{6, 5, 3, 1, 8, 7, 2, 4}进行冒泡排序的实现过程如下

冒泡排序动画如下:

算法实现

算法分析
1.空间复杂度:O(1)
2.时间复杂度: 平均O (n²)
最好O(n)
3.冒泡排序是一种稳定的排序算法
4.冒泡两层for循环外层表示进行n-1趟排序 内层表示每趟要进行n-i次比较
5.冒泡排序的改进:
思路:增加一个标识位 当某一趟冒泡排序没有进行元素交换 即元素已经有序时 冒泡结束
核心部分改为以下即可:

快速排序

算法思想
快速排序(Quicksort)是对冒泡排序的一种改进,又称划分交换排序(partition-exchange sort。
快速排序使用分治法(Divide and conquer)策略来把一个序列(list)分为两个子序列(sub-lists)
1.从数列中挑出一个元素,称为”基准”(pivot)
2.重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。在这个分区结束之后,该基准就处于数列
的中间位置。这个称为分区(partition)操作。
3.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序
算法实例

算法实现

算法分析
1.平均空间复杂度:O(logn)
2.平均时间复杂度:O(nlogn)
最差:O(n²)
最好:O(nlogn)
3.快排是一种不稳定的排序算法
4.当数据趋近于无序时 快排的时间复杂度最优
当数据趋近于有序有 快排就会退化为一般的排序算法 时间复杂度退化为O(n²)
5.快排使用了递推 因此需要栈的辅助 空间复杂度较别的算法略高
6.优化(一)
枢轴的选取十分重要 选取的枢轴越接近中间值 算法的效率越高
正常算法的枢轴选取为数组的首元素
因此具体优化可以:每次选取避免选取到最值 可采用取平均值的方法求得尽可能靠中间的值
7.优化二(二)
获取枢轴的一般步骤为:
(1)确定枢轴
(2)从最高位开始找到第一个小于枢轴的数 与枢轴交换
(3)从最低位开始找到第一个大于枢轴的数 与枢轴交换
(4)直到high=low停止 实现枢轴的坐标均小于它 右边均大于它
针对两次交换操作 可以做如下优化:

如上优化可以避免进行两次交换操作
哪怕使用空间复杂度为1的位运算来交换两个数也会额外增加代码书写难度

选择类排序

简单选择排序

算法思想
每趟在n-i+1个记录中选取最小的关键字作为有序列中的第i个记录
算法实例
待排序列{4862357755143598
A)1462 35 77 55 48 35 98
B)14 3562 77 55 48 35 98
C)14 35 3577 55 48 62 98
D)14 35 35 4855 77 62 98
E)14 35 35 48 5577 62 98
F)14 35 35 48 55 6277 98
G)14 35 35 48 55 62 7798
H)14 35 35 48 55 62 77 98
选择排序的比较过程如下:

动画效果如下:

算法实现

算法分析
1.空间复杂度:O(1)
2.时间复杂度:O(n²)
3.简单选择排序是不稳定的排序算法

树形选择排序

算法思想
又成锦标赛排序
基本思想是先把待排序的n个记录的关键字两两比较 取出最小者 然后在[n/2]个较小者中 采用同样的方法进行比较 直至选出最小的关键字为止
这一过程可以用一颗满二叉树来表示 不满时的结点用正无穷来填补
重复以上操作 直到所有的关键字全被取出为止
算法实例

算法分析
1.时间复杂度为:O(n*logn)

堆排序

算法思想
堆是一种数据结构,最好的理解堆的方式就是把堆看成一棵完全二叉树,这个完全二叉树满足任何一个非叶节点的值,都不大于(或不小于)其左右孩子节点的值。
若父亲大孩子小,则这样的堆叫做大根堆;若父亲小孩子大,这样的堆叫做小根堆。根据堆的定义,其根节点的值是最大(或最小),因此将一个无序序列调整为一个堆,
就可以找出这个序列的最大(或最小)值,然后将找出的这个值交换到序列的最后(或最前),这样有序序列元素增加1个,无序序列中元素减少1个,对新的无序序列重
复这样的操作,就实现了序列排序。堆排序中最关键的操作是将序列调整为堆,整个排序的过程就是通过不断调整使得不符合堆定义的完全二叉树变为符合堆定义的完全
二叉树的过程。
堆排序执行过程(大根堆):
(1)从无序序列所确定的完全二叉树的第一个非叶子节点开始,从右至左,从下至上,对每个节点进行调整,最终将得到一个大根堆。
将当前节点(a)的值与其孩子节点进行比较,如果存在大于a值的孩子节点,则从中选出最大的一个与a交换。
当a来到下一层的时候重复上述过程,直到a的孩子节点值都小于a的值为止。
(2)将当前无序序列中第一个元素,在树中是根节点(a)与无序序列中最后一个元素(b)交换。a进入有序序列,到达最终位置,
无序序列中元素减少1个,有序序列中元素增加1个,此时只有节点b可能不满足堆的定义,对其进行调整。
算法实例
初始化动画如下:

堆排序动画如下:

算法实现

算法分析
1.空间复杂度:O(1)
2.时间复杂度为:O(nlogn)
最差时间复杂度:O(nlogn)
3.堆排序是一种不稳定的排序算法
4.由于堆排序的最差时间复杂度依然为O(nlogn) 这是堆排序最大的优点
5.它并不适用于n个数较小的情况 对于n较大的文件非常有效 如从1000000个记录中选出前10个最小的 这种情况用堆排序最好
6.堆中定义的三种操作
(1)创建大根堆(Build_Max_Heap):将堆所有数据重新排序
(2)大根堆调整(Max_Heapify):将堆的节点作调整,使得子节点永远小于父节点
(3)堆排序(HeapSort):移除位在第一个数据的根节点,并做大根堆调整的递归运算
7.由于堆排序运用了子节点与父节点的关系 所以数组最好从a[1]开始存储数据 方便运算
8.堆的存储:

归并排序

算法思想
其核心就是“两两归并”,首先将原始序列看成每个只含有单独1个元素的子序列,两两归并,形成若干有序二元组,则第一趟归并排序结束,再将这个序列看成若干个
二元组子序列,继续两两归并,形成若干有序四元组,则第二趟归并排序结束,以此类推,最后只有两个子序列,再进行一次归并,即完成整个归并排序。
若将两个有序表合并成一个有序表,称为二路归并。
算法实例


归并排序动画如下:

算法实现

算法分析
1.空间复杂度:O(n)
2.时间复杂度为:O(nlogn)
3.归并排序是一种稳定的排序算法
4.归并排序运用了二分递归的方法实现两两排序 把两个子表合成一个总表的方法类似于单链表的合并操作
5.参加网上测试样例:对于5万个随机数 归并排序几乎不需要时间 对于20万个随机数 仅耗时62ms 而快排需要78ms

三大线性时间排序算法

计数排序

算法思想
计数排序用到一个额外的计数数组C,根据数组C来将原数组A中的元素排到正确的位置。
计数数组C用来统计比数组中每个数字小的数有多少个 例如有个17个小于x的元素 那么C[x]=17 x可直接放在第18个位置
1.统计数组A中每个值A[i]出现的次数,存入C[A[i]]
2.从前向后,使数组C中的每个值等于其与前一项相加,这样数组C[A[i]]就代表了数组A中小于等于A[i]的元素个数
3.反向填充目标数组B:将数组元素A[i]放在数组B的第C[A[i]]项(即B[C[A[i]] – 1]),每放一个元素就将C[A[i]]递减
算法实例
下图给出了对{4, 1, 3, 4, 3}进行计数排序的简单演示过程

再给出一个实现图解:

算法实现

算法分析
1.空间复杂度:O(n+k)
2.时间复杂度:O(n+k)–k为数据的范围
平均时间复杂度:O(n+k)
最差时间复杂度:O(n+k)
3.计数排序是一种稳定的排序算法
4.如果在面试中有面试官要求你写一个O(n)时间复杂度的排序算法,你千万不要立刻说:这不可能!虽然前面基于比较的排序的下限是O(nlogn)。
但是确实也有线性时间复杂度的排序,只不过有前提条件,就是待排序的数要满足一定的范围的整数,而且计数排序需要比较多的辅助空间。
其基本思想是,用待排序的数作为计数数组的下标,统计每个数字的个数。然后依次输出即可得到有序序列。
5.计数排序的时间复杂度和空间复杂度取决于数组A的数据范围(等于A中元素的最大值与最小值的差加上1),因此对于数据范围很大的数组,计数排序需要大量时间
和内存 所以计数排序并不适用与数据范围很大的数组
6.计数排序经常用作基数排序算法的一个子过程,其稳定性对于基数排序的正确性来说非常关键
7.计数排序不是比较排序,排序的速度快于任何比较排序算法

桶排序

算法思想
工作原理是将数组分解到有限数量的桶里,每个桶再分别进行排序。桶内排序有可能使用其他排序算法或是以递归的方式继续使用桶排序
1.在数组中查找数值的最大值和最小值;
2.初始化一个数组当作空桶,长度为 (MaxValue – MinValue + 1)。
3.遍历被排序数组,并把数值逐个放入对应的桶中。
4.对每个不是空的桶进行排序。
5.从不是空的桶里把数值再放回原来的数组中。
算法实例
下图给出了对{29, 25, 3, 49, 9, 37, 21, 43}进行桶排序的简单演示过程


算法实现

算法分析
1.空间复杂度:O(k×n)
2.时间复杂度:O(n+k) (k=N(logN-logM)–N为待排数据 M为桶的数量)
平均时间复杂度:O(n+k)
最差时间复杂度:O(n²)
3.桶排序是一种稳定的排序算法
4.当要被排序的数组中的数值是均匀分布时 桶排序的运行时间为线性时间O(n)。桶排序不是比较排序,它不受O(nlogn)下界的影响
5.在桶排序中找到正确的映射函数f(k)是关键 他可以把N个数据尽可能平均的分配到M个桶中
其作用就相当于快排中的划分 希尔排序中的子序列 归并排序中的子问题 已经把大量数据分割成了基本有序的数据块
例如上述图解的映射函数为f(k)=k/10
6.每个桶中可以根据情况使用各种排序函数 本文使用的是快排 也可以使用计数排序 堆排等等
7.桶排序算是计数排序的一种改进和推广 但是网上有许多资料把计数排序和桶排序混为一谈 其实桶排序要比计数排序复杂许多
8.代码中的结构体模拟了vector的作用 算出最大值-最小值后使用指针p动态分配空间 使得空间消耗最优

基数排序

算法思想
基数排序又是一种和前面排序方式不同的排序方式 基数排序不需要进行记录关键字之间的比较 基数排序是一种借助多关键字排序思想对单逻辑关键字进行排序的方法
所谓的多关键字排序就是有多个优先级不同的关键字 比如说成绩的排序 如果两个人总分相同 则语文高的排在前面 语文成绩也相同则数学高的排在前面
如果对数字进行排序 那么个位、十位、百位就是不同优先级的关键字 如果要进行升序排序 那么个位、十位、百位优先级一次增加
基数排序是通过多次的收分配和收集来实现的 关键字优先级低的先进行分配和收集
原理是将整数值按相同的有效位进行分组,然后在有效位区间内进行排序
1.获得值的最右侧的最小的位。
2.根据该位的值将数组内的元素值进行分组,但仍然保持元素的顺序。(以此来保持算法稳定性)
3.重复上述分组过程,直到所有的位都已被处理。
算法实例
下图给出了对{ 329, 457, 657, 839, 436, 720, 355 }进行基数排序的简单演示过程

再给出链式基数排序的实现过程


数排序中可以选择采用
最低有效位基数排序(LSD Radix Sort:Least Significant Digit Radix Sort)或最高有效位基数排序(MSD Radix Sort:Most Significant Digit Radix Sort)
LSD 的排序方式由值的最低位也就是最右边开始,而 MSD 则相反 由值的最高位也就是最左边开始

但由于MSD比LDS复杂 所以一般采用从低位开始排序的算法
例如,如下这个无序的数列需要排序:
  170, 45, 75, 90, 802, 2, 24, 66
使用 LSD 方式从最低位开始(个位)排序的结果是:
  170, 90, 802, 2, 24, 45, 75, 66
再继续从下一位(十位)继续排序的结果是:
  802, 2, 24, 45, 66, 170, 75, 90
再继续从下一位(百位)继续排序的结果是:
  2, 24, 45, 66, 75, 90, 170, 802
算法实现

算法分析
1.空间复杂度:O(d×n)
2.时间复杂度:O(d×n)
3.基数排序是一种稳定的排序算法
4.基数排序的时间复杂度是O(ndn),其中n是排序元素个数,dn是数字位数。这个时间复杂度不一定优于O(nlogn),dn的大小取决于数字位的选择(比如比特位数)
和待排序数据所属数据类型的全集的大小;dn决定了进行多少轮处理,而n是每轮处理的操作数目。
5.由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序并不是只能用于整数排序
 如果考虑和比较排序进行对照 基数排序的形式复杂度虽然不一定更小 但由于不进行比较 因此其基本操作的代价较小 而且如果适当的选择基数
 dn一般不大于logn 所以基数排序一般要快过基于比较的排序 比如快速排序
6.基数排序类似于桶排序的思想 把数字按照位数放到10个桶中 每个桶中可以使用计数排序 因为在数据量较小时计数排序具有较高的效率
7.由于分块(桶)的数量是确定 所以可以使用vector来动态在每个桶中存放数字 即较少了内存消耗也减少了书写难度

总结

1.稳定性
指待排序的序列中有两个或两个以上相同的项,在排序前和排序后看这些相同项的相对位置有没有发生变化,如果没有发生变化,即该排序方法是稳定的,
如果发生变化,则说该排序方法是不稳定的。
2.在是三种排序算法中
稳定:直接插入排序 折半插入排序 冒泡排序 归并排序 基数排序 计数排序 桶排序
不稳定:希尔排序 快速排序 简单选择排序 堆排序
即除了“快些(希)选堆”以外 其余都是稳定的排序算法
3.经过一趟排序能够保证一个元素到达最终位置的是冒泡排序快速排序简单选择排序堆排序
4.元素比较次数和原始序列无关的是简单选择排序折半插入排序
5.排序趟数和原始序列有关的是交换类排序冒泡排序 快速排序)。
6.快速排序归并排序堆排序的平均时间为O(nlogn) 希尔排序复杂度为O(n^1.3)或O(n^1.5)。
7.对于选择排序 给定含n个元素的输入序列 任何比较排序在最坏情况下都需要Ω(nlogn)次比较来进行排序。
归并排序堆排序在最坏情况下达到上界O(nlogn) 它们都是渐进最优的排序算法 快速排序在平均情况下达到上界 O(nlogn)。
而三种线性时间排序算法基数排序 计数排序 桶排序)将突破O(nlogn)的下界 以线性时间运行
8.三种线性时间排序算法是非比较排序 在特定条件下速度快过所有比较排序
9.没有最优的排序算法 根据数据的特性以及大小选择合适的排序算法才是关键
10.最后总结下几种较优排序算法的实用情况:
选择排序

直接插入排序:在数据基本有序时有较高的性能
 希尔排序: 在中等数据量规模(n < 1000)具有较高的效率 但不稳定
 快排排序: 在数据量较大且数据趋于无序时具有较高效率 但不稳定且过多递归容易爆内存
 堆排序: 适用于数据量非常大的情况 最差时间复杂度依然为O(n×logn) 这是堆排序最大的优点 但不稳定
 归并排序:和前三种排序算法不同的是归并排序是一种稳定的排序算法 且综合性能很强 在要求稳定性时优先使用归并排序
非选择排序
 计数排序: 适用于数据范围较小的情况 线性时间O(n)运行 稳定 但耗空间较大
 桶排序: 适用于数据是均匀分布的情况 线性时间O(n)运行 稳定 但映射函数的选择对性能的影响巨大
 基数排序:线性时间O(n)运行 稳定 但数据的位数过大时不宜使用

Codeforces Round #419 (Div. 2)

题目链接:http://codeforces.com/contest/816

A Karen and Morning

It is currently hh:mm, given in a 24-hour format. As you know, Karen loves palindromes, and she believes that it is good luck to wake up when the time is a palindrome.

What is the minimum number of minutes she should sleep, such that, when she wakes up, the time is a palindrome?

Remember that a palindrome is a string that reads the same forwards and backwards. For instance, 05:39 is not a palindrome, because 05:39 backwards is 93:50. On the other hand, 05:50 is a palindrome, because 05:50 backwards is 05:50.

过几分钟回文。

B Karen and Coffee

Karen, a coffee aficionado, wants to know the optimal temperature for brewing the perfect cup of coffee. Indeed, she has spent some time reading several recipe books, including the universally acclaimed “The Art of the Covfefe”.

She knows n coffee recipes. The i-th recipe suggests that coffee should be brewed between li and ri degrees, inclusive, to achieve the optimal taste.

Karen thinks that a temperature is admissible if at least k recipes recommend it.

Karen has a rather fickle mind, and so she asks q questions. In each question, given that she only wants to prepare coffee with a temperature between a and b, inclusive, can you tell her how many admissible integer temperatures fall within the range?

n个菜单,每个菜单在[l,r]区间是好的。
统计[L,R]区间 菜单是好的的个数 >=k 的点。
对于[l,r]
presum[l]++
presum[r+1]–
然后求前缀和的时候就相当于presum[l..r]++了
前缀和统计+树状数组。

C Karen and Game

The game is played as follows. In each level, you have a grid with n rows and m columns. Each cell originally contains the number 0.

One move consists of choosing one row or column, and adding 1 to all of the cells in that row or column.

To win the level, after all the moves, the number in the cell at the i-th row and j-th column should be equal to gi, j.

Karen is stuck on one level, and wants to know a way to beat this level using the minimum number of moves. Please, help her with this

类似消消乐吧。
直接贪心消除。
注意最小这个条件。
于是需要选择先消列还是行。
先消效益高的,就是数值小的那一个。

D Karen and Test

There are n integers written on a row. Karen must alternately add and subtract each pair of adjacent integers, and write down the sums or differences on the next row. She must repeat this process on the values on the next row, and so on, until only one integer remains. The first operation should be addition.

Note that, if she ended the previous row by adding the integers, she should start the next row by subtracting, and vice versa.

The teachers will simply look at the last integer, and then if it is correct, Karen gets a perfect score, otherwise, she gets a zero for the test.

Karen has studied well for this test, but she is scared that she might make a mistake somewhere and it will cause her final answer to be wrong. If the process is followed, what number can she expect to be written on the last row?

Since this number can be quite large, output only the non-negative remainder after dividing it by 1e9 + 7.

考虑最简版本每个ai对最终式子的贡献,可以令ai的系数为1,其余为0,类似0,0,0…1…0,0,0,同时暂且不考虑减法,可以得出每个ai的贡献为\(C_{n-1}^{k-1} \),然后通过下面这个过程,可以看出最终的式子,是两个奇偶序列和(最简版本),相加或做差得到的,n mod 4 = 2时相加,n mod 4 = 0时做差。(如果n是奇数,那么先暴力进行第一次变换使得n成为偶数)

E Karen and Supermarket

On the way home, Karen decided to stop by the supermarket to buy some groceries.

She needs to buy a lot of goods, but since she is a student her budget is still quite limited. In fact, she can only spend up to b dollars.

The supermarket sells n goods. The i-th good can be bought for ci dollars. Of course, each good can only be bought once.

Lately, the supermarket has been trying to increase its business. Karen, being a loyal customer, was given n coupons. If Karen purchases the i-th good, she can use the i-th coupon to decrease its price by di. Of course, a coupon cannot be used without buying the corresponding good.

There is, however, a constraint with the coupons. For all i ≥ 2, in order to use the i-th coupon, Karen must also use the xi-th coupon (which may mean using even more coupons to satisfy the requirement for that coupon).

Karen wants to know the following. What is the maximum number of goods she can buy, without exceeding her budget b?

超市里有n种商品,第i件物品价格为ci,除了第一件物品以外,每个物品都有优惠劵,可以优惠di,但是第i件物品能使用优惠劵的前提是第xi (1 <= xi < i) 件物品已经用优惠券买过。每件物品只能买一次,问在不超过预算b的情况下,最多能买多少件不同的物品。

先将问题转化一下,逐个求出买j(1 < j <= n)件物品的最小价值,然后根据b就可以确定最多的件数。然后就是树上的做背包的动态规划问题,类似的题目参考Black Nodes in Subgraphs