第一章 二分查找
二分查找函数
①写一个函数BinarySearch,在包含size个元素的、从小到大排序的int数组a里查找元素p,如果找到,则返回元素下标,如果找不到,则返回-1。要求时间复杂度$O\left(\log n \right)$
1 | int BinarySearch(int a[],int size,int p) |
②写一个函数LowerBound,在包含size个元素的、从小到大排序的int数组a里查找比给定整数p小的,下标最大的元素,找到则返回其下标,找不到则返回-1。
1 | int LowerBound(int a[],int size,int p) |
二分法求方程的根
求下面方程的一个根:$f(x)=x^3-5x^2+10x-80=0$,若求出的根是a,则要求$|f(a)|<=10^{-6}$
1 | /* |
整数和
输入n(n<=100,000)个整数,找出其中的两个数,它们之和等于整数m(假定肯定有解)。体重所有整数都能用int表示。
解法1
用两重循环,枚举所有的取数方法,复杂度是$O\left(n^2\right)$
1 | for(int i=0;i<n-1;i++) |
$100,1000^2=100亿$,在各种OJ伤提交或参加各种程序设计竞赛,这种复杂度都会超时!
解法2
1)将数组排序,复杂度是$O\left(n\log n\right)$
2)对数组中的每个元素a[i],在数组中二分查找m-a[i],看能否找到。
复杂度$\log n$,最坏要查找n-2,所以查找这部分的复杂度也是$O\left(n\log n\right)$。
这种解法总的复杂度是$O\left(n \log n\right)$。
解法3
1)将数组排序,复杂度是$O\left(n \log n\right)$
2)查找的时候,设置两个变量i和j,i初值是0,j初值是n-1.
看a[i]+a[j],如果大于m,就让j减1,如果小于m,就让i加1,直至a[i]+a[j]=m。
这种解法总的复杂度是$O\left(n \log n\right)$。
Aggressive cows
描述
Farmer John has built a new long barn, with N (2 <= N <= 100,000) stalls. The stalls are located along a straight line at positions x1,…,xN (0 <= xi <= 1,000,000,000).
His C (2 <= C <= N) cows don’t like this barn layout and become aggressive towards each other once put into a stall. To prevent the cows from hurting each other, FJ want to assign the cows to the stalls, such that the minimum distance between any two of them is as large as possible. What is the largest minimum distance?
输入
Line 1: Two space-separated integers: N and C
Lines 2..N+1: Line i+1 contains an integer stall location, xi
输出
Line 1: One integer: the largest minimum distance
样例输入
5 3
1
2
8
4
9
样例输出
3
程序
1 | /* |
第二章 动态规划之背包专题
概述
0-1背包问题
一个背包总容量为V,现在有N个物品,第i个 物品体积为weight[i],价值为value[i],现在往背包里面装东西,怎么装能使背包的内物品价值最大?
状态转移方程
取或不取第i件物品,j表示当前剩余容量
d[i][j]=max(d[i-1][j],d[i-1][j-w[i]]+v[i]) (j>w[i]才有第二项)
伪代码如下:
1 | for i=1..N |
这里已经是空间优化的结果
求第i行j列的元素,按照状态转移方程可知,必须用到其上一行正上方的元素和该元素左侧的一个元素
①行分析
那么按照行从小到大的顺序进行,当前行各元素计算完成则其上一行元素失去作用,不再参与计算,
故可以将下一行的各元素的计算结果保存到上一行,已达到空间优化的目的。
②列分析
由于当前元素的计算需要其正上方及其左边的某个元素,那么,
如果从左到右进行枚举,当前元素的计算结果保存到其正上方元素,则进行右边的其他元素时
可能会用到这个已经被保存计算结果的元素,所以不可以。
如果从右到左进行枚举,当前元素的计算结果保存到其正上方元素,对当行左边其他元素的计算不产生任何影响,故达到了空间优化的目的。
综上:采用从上到下,从右到左的顺序进行枚举。
完全背包问题
一个背包总容量为V,现在有N种物品,第i个 物品体积为weight[i],价值为value[i],每个物品都有无限多件,现在往背包里面装东西,怎么装能使背包的内物品价值最大?
状态转移方程
i表示选第i种物品,j表示剩余空间
d[i][j]=max\left(d[i-1][j],d[i-1][j-k×w[i]]+k×v[i]\right) (j>k×w[i]才有第二项,0<=k×w[i]<=V)
伪代码如下:
1 | for i=1..N |
同样采用空间优化的思路:
在d[i][j]与d[i-1][j]以及d[i-1][j]左边k个元素比较的过程中,取最大值,
由于i、w[i]在k循环中为定量,考虑j和k是变量,进行逆序循环k:
1 | for i=1..N |
那么在j增加的情况下,递推公式可以简化:
1 | 假设j_1,...,j_4都恰好整除w[i]: |
综上,完全背包在当前j剩余空间最优结果可以由前者递推实现,也就是说j增大的过程中,较大的j的k个取法的最优结果是由上一个较小的j的k个取法最优结果和i当前不取时两者取最优。
二者区别
前者物品有限件,后者物品无限件
完全背包问题和01背包问题唯一不同的是j是从1到M。01背包问题是在前一个子问题(i-1种物品)的基础上来解决当前问题(i种物品),向i-1种物品时的背包添加第i种物品;而完全背包问题是在解决当前问题(i种物品),向i种物品时的背包添加第i种物品。
从矩阵来看,
0-1背包
第二层循环必须逆序进行,因为当前f[i][j]需要用到f[i-1][j]和f[i-1][j-w[i]],即前一个i-1件商品的结果,并且不重复
完全背包
第二层循环必须顺序进行,因为当前f[i][j]表示取第i件,这第i件可以和前i-1件重复
分析优化后的伪代码
你会发现,这个伪代码与01背包的伪代码只有v的循环次序不同而已。为什么这样一改就可行呢?
首先想想为什么01背包中要按照v=V..0的逆序来循环。这是因为要保证第i次循环中的状态f[v]是由状态f[v-c]递推而来。换句话说,这正是为了保证每件物品只选一次,保证在考虑“选入第i件物品”这件策略时,依据的是一个没有已经选入第i件物品的子结果f[v-c]。
而当前完全背包的特点恰是每种物品可选无限件,所以在考虑“加选一件第i种物品”这种策略时,却正需要一个可能已选入第i种物品的子结果f[v-c],所以就可以并且必须采用v=0..V的顺序循环。这就是这个简单的程序为何成立的道理。
多重背包
与完全背包类似,不同的是,多重背包每种物品的个数有限,假设为m_i,那么可以转化成0-1背包求解
d[i][j]=max(d[i-1][j],d[i-1][j-k×w[i]]+k×v[i]) (j>k×w[i]才有第二项,0<=k<=m_i)
二进制优化
这m个同种物品可以用二进制表示,因为每个整数m都可以用二进制表示,那么
比如说$10=2^0+2^1+2^2+3$
那么也就是把同一件物品10件拆成1,2,4,3份,每一份看成新的一种物品,那么就是0-1背包问题,
这里每新的一种都有取或不取,或句话说,也就是这些新的堆可以在取或不取中组成10以内的各个数,也就是说
如果10件商品最优为取7件,那么1+2+4或者4+3,虽然会有重复,但是也在计算内。
再言之,如果单纯将同种物品的每一件看成不同的,那么无奈枚举的情况太多,时间复杂度太高,这种二进制的优化能在很大程度上减少枚举的数量。
参考
背包九讲
神奇的口袋
描述
有一个神奇的口袋,总的容积是40,用这个口袋可以变出一些物品,这些物品的总体积必须是40。John现在有n个想要得到的物品,每个物品的体积分别是a1,a2……an。John可以从这些物品中选择一些,如果选出的物体的总体积是40,那么利用这个神奇的口袋,John就可以得到这些物品。现在的问题是,John有多少种不同的选择物品的方式。
输入
输入的第一行是正整数n (1 <= n <= 20),表示不同的物品的数目。接下来的n行,每行有一个1到40之间的正整数,分别给出a1,a2……an的值。
输出
输出不同的选择物品的方式的数目。
样例输入
3
20
20
20
样例输出
3
程序
1 | /* |
1 | /* |
Charm Bracelet
描述
Bessie has gone to the mall’s jewelry store and spies a charm bracelet. Of course, she’d like to fill it with the best charms possible from the N(1 ≤ N≤ 3,402) available charms. Each charm iin the supplied list has a weight Wi(1 ≤ Wi≤ 400), a ‘desirability’ factor Di(1 ≤ Di≤ 100), and can be used at most once. Bessie can only support a charm bracelet whose weight is no more than M(1 ≤ M≤ 12,880).
Given that weight limit as a constraint and a list of the charms with their weights and desirability rating, deduce the maximum possible sum of ratings.
输入
Line 1: Two space-separated integers: N and M
Lines 2..N+1: Line i+1 describes charm i with two space-separated integers: Wi and Di
输出
Line 1: A single integer that is the greatest sum of charm desirabilities that can be achieved given the weight constraints
样例输入
4 6
1 4
2 6
3 12
2 7
样例输出
23
程序
1 | /* |
1 | /* |
HDOJ 1114 Piggy-Bank
Problem Description
Before ACM can do anything, a budget must be prepared and the necessary financial support obtained. The main income for this action comes from Irreversibly Bound Money (IBM). The idea behind is simple. Whenever some ACM member has any small money, he takes all the coins and throws them into a piggy-bank. You know that this process is irreversible, the coins cannot be removed without breaking the pig. After a sufficiently long time, there should be enough cash in the piggy-bank to pay everything that needs to be paid.
But there is a big problem with piggy-banks. It is not possible to determine how much money is inside. So we might break the pig into pieces only to find out that there is not enough money. Clearly, we want to avoid this unpleasant situation. The only possibility is to weigh the piggy-bank and try to guess how many coins are inside. Assume that we are able to determine the weight of the pig exactly and that we know the weights of all coins of a given currency. Then there is some minimum amount of money in the piggy-bank that we can guarantee. Your task is to find out this worst case and determine the minimum amount of cash inside the piggy-bank. We need your help. No more prematurely broken pigs!
Input
The input consists of T test cases. The number of them (T) is given on the first line of the input file. Each test case begins with a line containing two integers E and F. They indicate the weight of an empty pig and of the pig filled with coins. Both weights are given in grams. No pig will weigh more than 10 kg, that means 1 <= E <= F <= 10000. On the second line of each test case, there is an integer number N (1 <= N <= 500) that gives the number of various coins used in the given currency. Following this are exactly N lines, each specifying one coin type. These lines contain two integers each, Pand W (1 <= P <= 50000, 1 <= W <=10000). P is the value of the coin in monetary units, W is it’s weight in grams.
Output
Print exactly one line of output for each test case. The line must contain the sentence “The minimum amount of money in the piggy-bank is X.” where X is the minimum amount of money that can be achieved using coins with the given total weight. If the weight cannot be reached exactly, print a line “This is impossible.”.
Sample Input
3
10 110
2
1 1
30 50
10 110
2
1 1
50 30
1 6
2
10 3
20 4
Sample Output
The minimum amount of money in the piggy-bank is 60.
The minimum amount of money in the piggy-bank is 100.
This is impossible.
Procedure
1 | /* |
HDOJ 1203 I NEED A OFFER!
Problem Description
Speakless很早就想出国,现在他已经考完了所有需要的考试,准备了所有要准备的材料,于是,便需要去申请学校了。要申请国外的任何大学,你都要交纳一定的申请费用,这可是很惊人的。Speakless没有多少钱,总共只攒了n万美元。他将在m个学校中选择若干的(当然要在他的经济承受范围内)。每个学校都有不同的申请费用a(万美元),并且Speakless估计了他得到这个学校offer的可能性b。不同学校之间是否得到offer不会互相影响。“I NEED A OFFER”,他大叫一声。帮帮这个可怜的人吧,帮助他计算一下,他可以收到至少一份offer的最大概率。(如果Speakless选择了多个学校,得到任意一个学校的offer都可以)。
Input
输入有若干组数据,每组数据的第一行有两个正整数n,m(0<=n<=10000,0<=m<=10000)
后面的m行,每行都有两个数据ai(整型),bi(实型)分别表示第i个学校的申请费用和可能拿到offer的概率。
输入的最后有两个0。
Output
每组数据都对应一个输出,表示Speakless可能得到至少一份offer的最大概率。用百分数表示,精确到小数点后一位。
Sample Input
10 3
4 0.1
4 0.2
5 0.3
0 0
Sample Output
44.0%
Hint
You should use printf(“%%”) to print a ‘%’.
Procedure
1 | /* |
HDOJ 1171 Big Event in HDU
Problem Description
Nowadays, we all know that Computer College is the biggest department in HDU. But, maybe you don’t know that Computer College had ever been split into Computer College and Software College in 2002.
The splitting is absolutely a big event in HDU! At the same time, it is a trouble thing too. All facilities must go halves. First, all facilities are assessed, and two facilities are thought to be same if they have the same value. It is assumed that there is N (0<N<1000) kinds of facilities (different value, different kinds).
Input
Input contains multiple test cases. Each test case starts with a number N (0 < N <= 50 – the total number of different facilities). The next N lines contain an integer V (0<V<=50 –value of facility) and an integer M (0<M<=100 –corresponding number of the facilities) each. You can assume that all V are different.
A test case starting with a negative integer terminates input and this test case is not to be processed.
Output
For each case, print one line containing two integers A and B which denote the value of Computer College and Software College will get respectively. A and B should be as equal as possible. At the same time, you should guarantee that A is not less than B.
Sample Input
2
10 1
20 1
3
10 1
20 2
30 1
-1
Sample Output
20 10
40 40
Procedure
1 | /* |
HDOJ 1059 Dividing
Problem Description
Marsha and Bill own a collection of marbles. They want to split the collection among themselves so that both receive an equal share of the marbles. This would be easy if all the marbles had the same value, because then they could just split the collection in half. But unfortunately, some of the marbles are larger, or more beautiful than others. So, Marsha and Bill start by assigning a value, a natural number between one and six, to each marble. Now they want to divide the marbles so that each of them gets the same total value.
Unfortunately, they realize that it might be impossible to divide the marbles in this way (even if the total value of all marbles is even). For example, if there are one marble of value 1, one of value 3 and two of value 4, then they cannot be split into sets of equal value. So, they ask you to write a program that checks whether there is a fair partition of the marbles.
Input
Each line in the input describes one collection of marbles to be divided. The lines consist of six non-negative integers n1, n2, …, n6, where ni is the number of marbles of value i. So, the example from above would be described by the input-line 1 0 1 2 0 0. The maximum total number of marbles will be 20000.
The last line of the input file will be 0 0 0 0 0 0; do not process this line.
Output
For each colletcion, output Collection #k:, where k is the number of the test case, and then either Can be divided. or Can’t be divided..
Output a blank line after each test case.
Sample Input
1 0 1 2 0 0
1 0 0 0 1 1
0 0 0 0 0 0
Sample Output
Collection #1:
Can’t be divided.
Collection #2:
Can be divided.
Procedure
1 | /* |
第三章 子集生成算法
增量构造法
每次只选择一个元素进入集合,同时规定集合A中所有元素的编号从小到大排列,不会出现重复输出。
程序的关键在于cur的处理上,很巧妙。
总体思路明了,程序设计上需要多加理解:
①每个元素遍历一次
②打印子集
③剩余元素遍历一次
④打印子集
⑤…
总的来说,就是取完当个元素(顺序取),剩余元素重复之前顺序取的步骤,直至所有遍历次数达到数组大小n
和取或不取当个元素相当,但是巧妙地控制了输出。(难想!我还是喜欢位向量的排列组合思维!🌝)
程序演示结果:
5
0
0 1
0 1 2
0 1 2 3
0 1 2 3 4
0 1 2 4
0 1 3
0 1 3 4
0 1 4
0 2
0 2 3
0 2 3 4
0 2 4
0 3
0 3 4
0 4
1
1 2
1 2 3
1 2 3 4
1 2 4
1 3
1 3 4
1 4
2
2 3
2 3 4
2 4
3
3 4
4
1 |
|
位向量法
每种元素都有取或不取两种情况,故递归,当所有元素都判断了一遍就输出。
1 |
|
二进制法
1、A&B、A|B和A^B分别对应集合的交、并和对称差
2、如果是n那就一般都是0~n-1的子集,而且对应的二进制位是从右往左
其中从右往左第i位(从0开始编号)表示元素i是否在集合中(1表示在,0表示不在)
s={0,1,…,n-1}中n个1,对应十进制2^n-1
那么全集为(1<<n)-1
1 |
|
第四章 双向广度优先搜索(DBFS)
概述
DBFS算法是对BFS算法的一种扩展
①BFS算法从起始节点以广度优先的顺序不断扩展,直到遇到目标节点。
②DBFS算法从两个方向以广度优先的顺序同时扩展,一个是从起始节点开始扩展,另一个从目标节点扩展,直到一个扩展队列中出现另外一个队列中已经扩展的节点,也就是相当于两个扩展方向出现了交点,那么可以认为我们找到了一条路径。
比较
①DBFS算法相对于BFS算法来说,由于采用了双向扩展的方式,搜索树的宽度得到了明显的减少,所以在算法的时间复杂度和空间复杂度上都有较大的优势!
②假设一个节点能扩展出n个节点,单向搜索要m层能找到答案,那么扩展出来的节点数目就是:$\frac{\left(1-n^m\right)}{\left(1-n\right)}$
③双向广搜,同样是一共扩展m层,假定两边各扩展出m/2层,则总节点数目$2\cdot\frac{\left(1-n^{\frac{m}{2}}\right)}{\left(1-n\right)}$
DBFS框架
1.双向广搜函数
1 | void Dbfs() |
2.扩展函数
1 | int expand(i)//其中i为队列的编号,0或1 |
Eight
Problem Description
The 15-puzzle has been around for over 100 years; even if you don’t know it by that name, you’ve seen it. It is constructed with 15 sliding tiles, each with a number from 1 to 15 on it, and all packed into a 4 by 4 frame with one tile missing. Let’s call the missing tile ‘x’; the object of the puzzle is to arrange the tiles so that they are ordered as:
1 | 1 2 3 4 |
where the only legal operation is to exchange ‘x’ with one of the tiles with which it shares an edge. As an example, the following sequence of moves solves a slightly scrambled puzzle:
1 | 1 2 3 4 1 2 3 4 1 2 3 4 1 2 3 4 |
The letters in the previous row indicate which neighbor of the ‘x’ tile is swapped with the ‘x’ tile at each step; legal values are ‘r’,’l’,’u’ and ‘d’, for right, left, up, and down, respectively.
Not all puzzles can be solved; in 1870, a man named Sam Loyd was famous for distributing an unsolvable version of the puzzle, and
frustrating many people. In fact, all you have to do to make a regular puzzle into an unsolvable one is to swap two tiles (not counting the missing ‘x’ tile, of course).
In this problem, you will write a program for solving the less well-known 8-puzzle, composed of tiles on a three by three
arrangement.
Input
You will receive, several descriptions of configuration of the 8 puzzle. One description is just a list of the tiles in their initial positions, with the rows listed from top to bottom, and the tiles listed from left to right within a row, where the tiles are represented by numbers 1 to 8, plus ‘x’. For example, this puzzle
1 2 3
x 4 6
7 5 8
is described by this list:
1 2 3 x 4 6 7 5 8
Output
You will print to standard output either the word “unsolvable”, if the puzzle has no solution, or a string consisting entirely of the letters ‘r’, ‘l’, ‘u’ and ‘d’ that describes a series of moves that produce a solution. The string should include no spaces and start at the beginning of the line. Do not print a blank line between cases.
Sample Input
2 3 4 1 5 x 7 6 8
Sample Output
ullddrurdllurdruldr
Procedure
最近懒,不想看新算法,所以来仔细研究研究这道题….偶都尅~
方案一
每个状态用一个字符串存储,要9个字节,太浪费!
方案二
①每个状态对应于一个9位数,则该9位数最大为876543210,小于$2^{31}$,则int就能表示一个状态。
②判重需要一个标志位序列,每个状态对应于标志位序列中的1位,标志位为0表示该状态尚未扩展,为1则说明已经扩展过了
③标志位序列可以用字符数组a存放。a的每个元素存放8个状态的标志位。最多需要876543210位,因此a数组需要876543210/8+1个元素,即109,567,902字节
④如果某个状态对应于x,则其标志位就是a[x/8]的第x%8位
⑤空间要求还是太大!
方案三
①状态数目义工只有9!个,即$362880_{\left(10\right)}$个,怎么会需要$876543210_{\left(9\right)}$即$381367044_{\left(10\right)}$个标志位呢?
②如果某个状态对应于数x,则其标志位就是a[x/8]的第x%8位
③因为有浪费!例如,$666666666_{\left(9\right)}$根本不对应于任何状态!
方案四
①把每个状态都看做0-8的一个排列,以此排列在全部排列中的位置作为其序号。状态用其排列序号来表示
②012345678是第0个排列,876543210是第9!-1个
③状态总数即排列总数:9!=362880比特即可。
④如果某个状态的序号是x,则其标志位就是a[x/8]的第x%8位
⑤在进行状态间转移,即一个状态通过某个移动变化到另一个状态时,需要先把int形式的状态(排列序号),转变成字符串形式的状态,然后在字符串形式的状态上进行移动,得到字符串形式的新状态,再把新状态转换成int形式(排列序号)
⑥需要编写给定排列(字符串型是)求序号的函数
⑦需要编写给定序号,求该序号的排列(字符串型是)的函数
给定排列求序号
整数1,2,…,k的一个排列
$a_1,a_2,a_3,…,a_k$
求其序号
基本思想:算出有多少个排列比给定排列小。
先算1到$a_1-1$放在第1位,会有多少个排列:$\left(a_1-1\right)\cdot\left(\left(k-1\right)!\right)$
再算$a_1$不变,1到$a_2-1$放在第2位(左边出现过的不能再用),会有多少个排列:$\left(a_2-1\right)\cdot\left(\left(k-2\right)!\right)$
再算$a_1,a_2$不变,1到$a_3-1$放在第3位,会有多少个排列
…全加起来。时间复杂度:$O\left(n^2\right)$
给定序号n求排列
1234的排列的第9号
第一位假定是1,共有3!种,没有到达9,所以第一位至少是2
第一位是2,一共能数到3!+3!>=9,所以第一位是2
第二位是1,21??,一共能数到3!+2!=8<9,所以第二位至少是3
第二位是3,23??,一共能数到3!+2!+2!>=9,因此第二位是3
第三位是1,一共能数到3!+2!+1=9,所以第三位是1,第四位是4
答案2314
时间复杂度:$O\left(n^2\right)$
八数码问题有解性的判定
①八数码问题的一个状态实际上是08的一个排列,对于任意给定的初始状态和目标,不一定有解,即从初始状态不一定能到达目标状态。因为排列有奇排列和偶排列两类,从奇排列不能转化成偶排列或相反。8的随机排列,用F(X)(X!=0)表示数字X前面比它小的数(不包括0)的个数,全部数字的F(X)之和为Y=∑(F(X)),如果Y为奇数则称该排列是奇排列,如果Y为偶数则称该排列是偶排列。
②如果一个数字0
871526340排列的Y=0+0+0+1+1+3+2+3=10,10是偶数,所以是偶排列
871625340排列的Y=0+0+0+1+1+2+2+3=9,9是奇数,所以是奇排列
因此,可以在运行程序前检查初始状态和目标状态的奇偶性是否相同,相同则问题可解,应当能搜索到路径,否则无解。
证明:移动0的位置,不改变排列的奇偶性
$a_1,a_2,a_3,a_4,a_5,a_6,a_7,a_8,a_9$
0向上移动
$a_1,0,a_3,a_4,a_2,a_5,a_6,a_7,a_8,a_9$
0的位置无非上下左右,
①左右移动时,由于0不参与计算,所以奇偶性不变
②上下移动时,由于变化仅2位,那么假设连续4位为ABC0,变化后为0BCA
这4位之后的序列F(X)不变,那么不妨设这4位序列后的F(X)之和为$Y_{Later}$
这4位之前的序列F(X)不变,那么不妨设这4位之前的序列的F(X)之和为$Y_{Before}$
仅在这4位的序列F(X)改变,那么不妨设这4位的序列的F(X)之和为$Y_{Mid}$
所以$Y=Y_{Before}+Y_{Mid}+Y_{Later}$
那么可知
$F(A)=F_0(A)+(A>B)+(A>C)$
$F(B)=F_0(B)-(B>A)$
$F(C)=F_0(C)-(C>A)$
$(F_0(*)表示变化前,其他同理)$
$Y_{Mid}$
$=F(A)+F(B)+F(A)$
$=F_0(A)+(A>B)+(A>C)$
$+F_0(B)-(B>A)$
$+F_0(C)-(C>A)$
$=F_0(A)+F_0(B)+F_0(C)$
$+(A>B)-(B>A)$
$+(A>C)-(C>A)$
$=F_0(A)+F_0(B)+F_0(C)$或$=F_0(A)+F_0(B)+F_0(C)±2$
$=Y_{Mid0}$或$=Y_{Mid0}±2$
$∴Y=Y_0或Y=Y_0±2$
$∴排列的奇偶性不变!$
证毕!
1 | //八数码问题 单向广搜 用set判重 |
1 | //八数码 双向广搜 |
迷宫问题(DBFS版)
描述
定义一个二维数组,它表示一个迷宫,其中的1表示墙壁,0表示可以走的路,只能横着走或竖着走,不能斜着走,要求编程序找出从左上角到右下角的最短路线。
输入
一个5 × 5的二维数组,表示一个迷宫。数据保证有唯一解。
输出
左上角到右下角的最短路径,格式如样例所示。
样例输入
0 1 0 0 0
0 1 0 1 0
0 0 0 0 0
0 1 1 1 0
0 0 0 1 0
样例输出
(0, 0)
(1, 0)
(2, 0)
(2, 1)
(2, 2)
(2, 3)
(2, 4)
(3, 4)
(4, 4)
程序
1 | /* |
Jack and Jill
Description
Ever since the incident on the hill, Jack and Jill dislike each other and wish to remain as distant as possible. Jack and Jill must attend school each day; Jack attends a boys’ school while Jill attends a girls’ school. Both schools start at the same time. You have been retained by their lawyers to arrange routes and a schedule that Jack and Jill will adhere to so as to maximize the closest straight-line distance between them at any time during their trip to school.
Jack and Jill live in a town laid out as an n by n square grid (n <= 30). It takes 1 minute to walk from one location to an adjacent location. In maximizing the distance between Jack and Jill you need consider only the distance between the locations they visit (i.e. you need not consider any intermediate points on the path they take from grid location to grid location). Some locations are impassable due to being occupied by rivers, buildings, etc. Jack must start at his house and walk continuously until he gets to school. Jill must start at her house at the same time as Jack and walk continuously until she arrives at her school. Jack’s house and school are impassable to Jill while Jill’s house and school are impassable to Jack. Other grid locations that are impassable to both Jack and Jill are given in the input.
Input
Input will consist of several test cases. Each test case will consist of n, followed by n lines with n characters representing a map of the town. In the map, Jack’s house is represented by ‘H’, Jack’s school is represented by ‘S’, Jill’s house is represented by ‘h’, Jill’s school is represented by ‘s’, impassable locations are represented by ‘*‘, and all other locations are represented by ‘.’ You may assume the normal cartographic convention that North is at the top of the page and West is to the left. A line containing 0 follows the last case.
Output
For each input case you should give three lines of output containing:
the closest that Jack and Jill come during the schedule (to 2 decimal places)
Jack’s route
Jill’s route.
Each route is a sequence of directions that Jack or Jill should follow for each minute from the start time until arriving at school. Each direction is one of ‘N’, ‘S’, ‘E’, or ‘W’. If several pairs of routes are possible, any one will do. You may assume there is at least one solution. Leave a blank line between the output for successive cases.
Sample Input
1 | 10 |
Sample Out
6.71
WWWSSSSSSSEEE
NEEENNNNNWWW
Procedure
1 | /* |
第五章 素数筛选法
素数筛选函数
当一个数不算大的时候,可以用普通的求素数的方法去求,但是如果一个数过大的话,就像让求1-十亿之间素数的个数,普通方法就不行了,这事就需要用到素数筛选法,他的时间复杂度是O(n),尽管不算很好,但是,也算是目前为止比较快的一种方法了,它是以空间换取时间,现在的计算机,空间有的是,但是时间是非常珍贵的。效率问题特别重要。他的原理就是标记,防止重复判断,这样提高了效率。就像2是素数,所有是2的倍数的肯定都不是素数,这时候标记上,接着判断3是素数,所有是3的倍数的都肯定不是素数,这时就要标记上,以此下去,执行到根下(总数),这样就会得到一个素数表,所有没有被标记的都是素数,下面是具体的代码实现,代码里面有注释。写的很清楚。
1 |
|
素数判断函数
1 | Status Is_prime(x) |
Calling Extraterrestrial Intelligence Again
描述
A message from humans to extraterrestrial intelligence was sent through the Arecibo radio telescope in Puerto Rico on the afternoon of Saturday November 16, 1974. The message consisted of 1679 bits and was meant to be translated to a rectangular picture with 23 x 73 pixels. Since both 23 and 73 are prime numbers, 23 x 73 is the unique possible size of the translated rectangular picture each edge of which is longer than 1 pixel. Of course, there was no guarantee that the receivers would try to translate the message to a rectangular picture. Even if they would, they might put the pixels into the rectangle incorrectly. The senders of the Arecibo message were optimistic.
We are planning a similar project. Your task in the project is to find the most suitable width and height of the translated rectangular picture. The term “most suitable” is defined as follows. An integer m greater than 4 is given. A positive fraction a/b less than or equal to 1 is also given. The area of the picture should not be greater than m. Both of the width and the height of the translated picture should be prime numbers. The ratio of the width to the height should not be less than a/b nor greater than 1. You should maximize the area of the picture under these constraints.
In other words, you will receive an integer m and a fraction a/b. It holds that m > 4 and 0 < a/b <= 1. You should find the pair of prime numbers p, q such that pq <= m and a/b <= p/q <= 1, and furthermore, the product pq takes the maximum value among such pairs of two prime numbers. You should report p and q as the “most suitable” width and height of the translated picture.
输入
The input is a sequence of at most 2000 triplets of positive integers, delimited by a space character in between. Each line contains a single triplet. The sequence is followed by a triplet of zeros, 0 0 0, which indicates the end of the input and should not be treated as data to be processed.
The integers of each input triplet are the integer m, the numerator a, and the denominator b described above, in this order. You may assume 4 < m <= 100000 and 1 <= a <= b <= 1000.
输出
The output is a sequence of pairs of positive integers. The i-th output pair corresponds to the i-th input triplet. The integers of each output pair are the width p and the height q described above, in this order.
Each output line contains a single pair. A space character is put between the integers as a delimiter. No other characters should appear in the output.
样例输入
5 1 2
99999 999 999
1680 5 16
1970 1 1
2002 4 11
0 0 0
样例输出
2 2
313 313
23 73
43 43
37 53
程序
1 | /* |
第六章 博弈论及其算法实现
何为博弈论
那就是若有多个人进行博弈,假设他们都足够聪明(能力已经相当于计算机了),在他们都没有失误并采取最优策略后,一定有一个人胜出,在知道初状态及规则的情况下,求解最终必胜的初状态(即何人胜出)的一类问题的理论及方法。
理论铺垫
1、定义P-position和N-position
其中P代表Previous,N代表Next。直观的说,上一次move的人有必败策略的局面是P-position,也就是“先手必败”(奇异局势),现在轮到move的人有必胜策略的局面是N-position,也就是“先手可保证必胜”(非奇异局势)。
(1).无法进行任何移动的局面(也就是terminal position)是P-position;
(2).可以移动到P-position的局面是N-position;
(3).所有移动都导致N-position的局面是P-position。
2、P/N状态有如下性质
(1)、若面临末状态者为获胜则末状态为胜态否则末状态为必败态。
(2)、一个局面是胜态的充要条件是该局面进行某种决策后会成为必败态。
(3)、一个局面是必败态的充要条件是该局面无论进行何种决策均会成为胜态
公平组合博弈(ICG)
1.定义
(1)只有两人参与。
(2)游戏局面的状态集合是有限。
(3)对于同一个局面,两个游戏者的可操作集合完全相同
(4)游戏者轮流进行游戏。
(5)当无法进行操作时游戏结束,此时不能进行操作的一方算输。
(6)无论游戏如何进行,总可以在有限步数之内结束。
2.模型
给定一个有向无环图和一个起始顶点上的一枚棋子,两名选手交替的将这枚棋子沿有向边进行移动,无法移动者判负。这个游戏可以认为是所有公平组合游戏的抽象模型。其实,任何一个ICG都可以通过把每个局势看成一个顶点,对每个局势和它的子局势连一条有向边来抽象成这个“有向图游戏”。
3.解决思路
现在,假定我们给出两个游戏G1 和 G2甚至多个游戏。如果我们只知道单个游戏的P-状态和N-状态我们能够正确地玩好游戏和G1 + G2吗?答案是否定的。不难看出两个P-状态的和总是P-状态,P-状态和N-状态的和总是N-状态。但是两个N-状态的和既可能是P-状态也可能是N-状态。因此,只知道单个游戏的P-状态和N-状态是不够的。
为了了解到几个状态叠加后是N还是P状态,我们需首先了解Sprague-Grudy函数。
4.Sprague-Grudy定理
令N = {0, 1, 2, 3, …} 为自然数的集合。Sprague-Grundy 函数给游戏中的每个状态分配了一个自然数。结点v的Grundy值等于没有在v的后继的Grundy值中出现的最小自然数.
形式上:给定一个有限子集 S ⊂ N,令mex S为没有出现在S中的最小自然数。定义的mex(minimal excludant)运算,这是施加于一个集合的运算,表示最小的不属于这个集合的非负整数。例如mex{0,1,2,4}=3、mex{2,3,5}=0、mex{}=0。
对于一个给定的有向无环图,定义关于图的每个顶点的Sprague-Garundy函数g如下:g(x)=mex{ g(y) | y是x的后继 }。
5.Sprague-Grudy函数性质
(1)所有的终结点所对应的顶点,其SG值为0,因为它的后继集合是空集——所有终结点是必败点(P点)。
(2)对于一个SG(x)=0的顶点x,它的所有后继y都满足g(y)!=0——无论如何操作,从必败点(P点)都只能进入必胜点(N点)//对手走完又能把N留给我们。
(3)对于一个SG(x)!=0的顶点,必定存在一个后继点y满足g(y)=0——从任何必胜点(N点)操作,至少有一种方法可以进入必败点(P点)
//就是那种我们要走的方法。
综上:必须判断先手是否为P状态,如果是,则必败,如果不是则必赢,因为按照上述性质,先手N状态必然可以移动到P状态使后者必输。
巴什博奕(Bash Game)
1.QUESTION
只有一堆n个物品,两个人轮流从这堆物品中取物,规定每次至少取一个,最多取m个。最后取光者得胜。
2.分析
游戏中为两人取一堆,干脆扩展到取n堆,由于取物数量有限制,因此正好是综合内第一个情况。
求SG值总能发现SG值为该值%(m+1) 后的结果,因此不加证明就能给出每一堆%(m+1)后再抑或一遍就为答案,下面是一堆贪心算法原理:
显然,如果n=m+1,那么由于一次最多只能取m个,所以,无论先取者拿走多少个,后取者都能够一次拿走剩余的物品,后者取胜。因此我们发现了如何取胜的法则:如果n=(m+1)r+s,(r为任意自然数,s≤m),那么先取者要拿走s个物品,如果后取者拿走k(≤m)个,那么先取者再拿走m+1-k个,结果剩下(m+1)(r-1)个,以后保持这样的取法,那么先取者肯定获胜。总之,要保持给对手留下(m+1)的倍数,就能最后获胜。
即,若n=k×(m+1),则后取着胜,反之,存在先取者获胜的取法。n%(m+1)==0. 先取者必败,即此时为P状态。
多堆类似。
3.算法实现
1 | bool Bash_Game(int n,int m) //先手是否有必赢策略 |
尼姆博弈(Nimm Game)
1.简单情况
有3堆各若干个物品,两个人轮流从某一堆取任意多的物品,规定每次至少取一个,最后取光者获胜胜。
这是nim博弈最简单的情况,我们用(a,b,c)表示某种局势,首先(0,0,0)显然是奇异局势,无论谁面对奇异局势,都必然失败。第二种奇异局势是(0,n,n),只要与对手拿走一样多的物品,最后都将导致(0,0,0)。仔细分析一下,(1,2,3)也是奇异局势,无论对手如何拿,接下来都可以变为(0,n,n)的情形。
那么怎么才能判断一个局势是否为奇异局势呢?答案就是抑或运算。这也算是公平组合博弈的一个原理之一,由于是尼姆博弈的基础于是放到此部分。
2.异或运算对尼姆博弈的处理以及原理
对于P/N状态,有以下三个定义:(即前面理论铺垫的三个定义)
(1)无法进行任何移动的局面(也就是terminal position)是P-position;
(2)可以移动到P-position的局面是N-position;
(3)所有移动都导致N-position的局面是P-position。
假设各堆石子数为$a_1,a_2,a_3,…,a_n$,首先P状态对应$a_1;xor;a_2;xor;a_3;xor;…;xor;a_n = 0$,N状态对应$a_1;xor;a_2;xor;a_3;xor;…;xor;a_n !=0 $;
对于(1),无法操作的局面对应$a_i$全为0的情况,抑或为0,得证。
对于(2),对于任何$a_1;xor;a_2;xor;a_3;xor;…;xor;a_n!=0$的情况,如果能够转移成P-position,则必存在一个数$a_i$使得$a_1;xor;a_2;xor;a_3;xor;…;xor;a_n=0$,证明如下:
将$a_i$减少为$a_i’$($a_i’\lt a_i$,因为$a_i$只能减小不能增加),令$A=a_1;xor;a_2;xor;a_3;xor;…;xor;a_{i-1};xor;a_{i+1};xor;a_n$,则$a_i’;xor;A=0$,
$又∵A;xor;a_i=X>0$,
$∴a_i’;xor;A=a_i’;xor;a_i;xor;a_i;xor;A=X;xor;a_i;xor;a_i’=0$
$∴a_i’=X;xor;a_i$
$又∵a_i’\lt a_i$
$∴X;xor;a_i\lt a_i$
故满足此式的$a_i$必能转移成P-position,
进一步,如果X与$a_i$最高位同时为1,那么必定满足上式,而由于X>0,且X由其他各元素异或得到,必定存在奇数个与X最高位同为1的$a_i$
证毕。
对于(3),证明P状态转移后必定不为P状态,也就能证明(3)了。
对于$a_1;xor;a_2;xor;a_3;xor;…;xor;a_i;xor;…;xor;a_n=0$的P状态 将其中$a_i$取走一堆,即减去一个数字变为$a_i’$,仍为P状态,即$a_1;xor;a_2;xor;a_3;xor;…;xor;a_i’;xor;…;xor;a_n=0=a_1;xor;a_2;xor;a_3;xor;…;xor;a_i;xor;…;xor;a_n$,由于抑或运算满足削去率,所以得到最后结果为$a_i’=a_i$,所以P状态不可能经过任何转移使得其仍未P状态,(3)成立。
因此nim简单博弈中,把3堆石子数量抑或一遍,判断是否为零就能得出是否为必胜态。
推广到n堆,原理相似。
3.算法实现
1 | bool Nimm_Game(int a[],int size) //判断先手是否有必赢策略 |
ICG,NIM博弈及 SG函数综合
对于能化为n堆取石子的问题,若取石子的数量是有限制的(给出n个能取得石子数量),因此先求出每堆数量的SG值(也就是单个游戏对应的状态),再进行抑或,得出的答案按是否为0判断是否为必胜或者必败态。
而对于一次取后会变为多状态的问题,由于按照最优策略最后一定有一个人胜出,所以取后各个状态得出的结果是一致的,只需要把该次取后的所有状态抑或一遍,得出的答案就是取前状态,可递归计算。
威佐夫博弈(Wythoff Game)
1.QUESTION
有两堆各若干个物品,两个人轮流从某一堆或同时从两堆中取同样多的物品,规定每次至少取一个,多者不限,最后取光者得胜。
2.分析
这种情况下是颇为复杂的。我们用$(a_k,b_k)(a_k ≤ b_k ,k=0,1,2,…,n)$表示两堆物品的数量并称其为局势,如果甲面对(0,0),那么甲已经输了,这种局势我们称为奇异局势。前几个奇异局势是:(0,0)、(1,2)、(3,5)、(4,7)、(6,10)、(8,13)、(9,15)、(11,18)、(12,20)。
可以看出,$a_0=b_0=0,a_k$是未在前面出现过的最小自然数,而$b_k=a_k + k$,奇异局势有
如下三条性质:
a.任何自然数都包含在一个且仅有一个奇异局势中
由于ak是未在前面出现过的最小自然数,所以有:
$a_k>a_{k-1},而b_k=a_k+k>a_{k-1}+k-1=b_{k-1}>a_{k-1}$
所以性质1。成立。
b.任意操作都可将奇异局势变为非奇异局势
事实上,若只改变奇异局势$(a_k,b_k)$的某一个分量,那么另一个分量不可能在其他奇异局势中,所以必然是非奇异局势。如果使$(a_k,b_k)$的两个分量同时减少,则由于其差不变,且不可能是其他奇异局势的差,因此也是非奇异局势。
c.采用适当的方法,可以将非奇异局势变为奇异局势
假设面对的局势是(a,b),
1.如果 b = a,则同时从两堆中取走 a 个物体,就变为了奇异局势(0,0);
2.如果$a = a_k ,b > b_k$,那么,取走$b - b_k$个物体,即变为奇异局势;
3.如果 $a = a_k,a_k < b < b_k$ ,则令$m=b-a_k < k$,同时从两堆中拿走$a_k-a_m$个物体,变为奇异局势$(a_m, a_m + m)$;
4.如果$a = a_k,b < a_k$ ,则令$m=a_k - b$,
①m < k,则两边同时拿走$b-a_m$,变为奇异局势$(m+a_m,a_m)$
②m > k,则b必在前面的局势中出现过,因为$a_k$是之前没出现过的最小的数,且$b < a_k$,所以:
a. $b=a_j(j < k)$,则从左边拿走$a_k-b_j$,变成奇异局势$(b_j,a_j)$
b. $b=b_j(j < k)$,则从左边拿走$a_k-a_j$,变成奇异局势$(a_j,b_j)$
5.如果$a > a_k,b= a_k + k$,则从第一堆中拿走多余的数量$a - a_k$ 即可;
6.如果$a < a_k,b= a_k + k$
① $a=a_j (j < k)$,从第二堆里面拿走$b - b_j$ 即可;
② $a=b_j (j < k)$,从第二堆里面拿走$b - a_j$ 即可。
那么任给一个局势(a,b),怎样判断它是不是奇异局势呢?公式如下:
$a_k=\left[k\cdot\frac{\left(1+\sqrt 5\right)}{2}\right]$
$b_k=a_k+k(k=0,1,2,…,n,[]代表取整函数)$
3.算法实现
1 | bool Wythoff_Game(int a,int b) |
斐波那契博弈(Fibonacci Game)
1.QUESTION
有一堆个数为n的石子,游戏双方轮流取石子,满足:
(1)先手不能第一次把所有的石子取完;
(2)之后每次可以取的石子数介于1到对手刚取的石子数的2倍之间(包含1和对手刚取的石子数的2倍)。约定取走最后一个石子的人为赢家。
2.解题思路
当n为Fibonacci(0、1、1、2、3、5、8、13、21)数时,先手必败。即存在先手的必败态当且仅当石头个数为Fibonacci数。
证明:
根据“Zeckendorf定理”(齐肯多夫定理):任何正整数可以表示为若干个不连续的Fibonacci数之和。如n=83 = 55+21+5+2,我们看看这个分解有什么指导意义:假如先手取2颗,那么后手无法取5颗或更多,而5是一个Fibonacci数,那么一定是先手取走这5颗石子中的最后一颗,同理,接下去先手取走接下来的后21颗中的最后一颗,再取走后55颗中的最后一颗,那么先手赢。
3.算法实现
1 | Status Fibonacci(int a[],int n) |
参考
博弈论的总结
Good Luck in CET-4 Everybody!
Problem Description
大学英语四级考试就要来临了,你是不是在紧张的复习?也许紧张得连短学期的ACM都没工夫练习了,反正我知道的Kiki和Cici都是如此。当然,作为在考场浸润了十几载的当代大学生,Kiki和Cici更懂得考前的放松,所谓“张弛有道”就是这个意思。这不,Kiki和Cici在每天晚上休息之前都要玩一会儿扑克牌以放松神经。
“升级”?“双扣”?“红五”?还是“斗地主”?
当然都不是!那多俗啊~
作为计算机学院的学生,Kiki和Cici打牌的时候可没忘记专业,她们打牌的规则是这样的:
1.总共n张牌;
2.双方轮流抓牌;
3.每人每次抓牌的个数只能是2的幂次(即:1,2,4,8,16…)
4.抓完牌,胜负结果也出来了:最后抓完牌的人为胜者;
假设Kiki和Cici都是足够聪明(其实不用假设,哪有不聪明的学生~),并且每次都是Kiki先抓牌,请问谁能赢呢?
当然,打牌无论谁赢都问题不大,重要的是马上到来的CET-4能有好的状态。
Good luck in CET-4 everybody!
Input
输入数据包含多个测试用例,每个测试用例占一行,包含一个整数n(1<=n<=1000)。
Output
如果Kiki能赢的话,晴输出“Kiki”,否则请输出“Cici”,每个实例的输出占一行。
Sample Input
1
3
Sample Output
Kiki
Cici
Procedure
1 | /* |
Stone
Problem Description
Tang and Jiang are good friends. To decide whose treat it is for dinner, they are playing a game. Specifically, Tang and Jiang will alternatively write numbers (integers) on a white board. Tang writes first, then Jiang, then again Tang, etc… Moreover, assuming that the number written in the previous round is X, the next person who plays should write a number Y such that 1 <= Y - X <= k. The person who writes a number no smaller than N first will lose the game. Note that in the first round, Tang can write a number only within range [1, k] (both inclusive). You can assume that Tang and Jiang will always be playing optimally, as they are both very smart students.
Input
There are multiple test cases. For each test case, there will be one line of input having two integers N (0 < N <= 10^8) and k (0 < k <= 100). Input terminates when both N and k are zero.
Output
For each case, print the winner’s name in a single line.
Sample Input
1 1
30 3
10 2
0 0
Sample Output
Jiang
Tang
Jiang
Procedure
1 | /* |
取石子游戏
Problem Description
有两堆石子,数量任意,可以不同。游戏开始由两个人轮流取石子。游戏规定,每次有两种不同的取法,一是可以在任意的一堆中取走任意多的石子;二是可以在两堆中同时取走相同数量的石子。最后把石子全部取完者为胜者。现在给出初始的两堆石子的数目,如果轮到你先取,假设双方都采取最好的策略,问最后你是胜者还是败者。
Input
输入包含若干行,表示若干种石子的初始情况,其中每一行包含两个非负整数a和b,表示两堆石子的数目,a和b都不大于1,000,000,000。
Output
输出对应也有若干行,每行包含一个数字1或0,如果最后你是胜者,则为1,反之,则为0。
Sample Input
2 1
8 4
4 7
Sample Output
0
1
0
Procedure
1 | /* |
Being a Good Boy in Spring Festival
Problem Description
下面是一个二人小游戏:桌子上有M堆扑克牌;每堆牌的数量分别为Ni(i=1…M);两人轮流进行;每走一步可以任意选择一堆并取走其中的任意张牌;桌子上的扑克全部取光,则游戏结束;最后一次取牌的人为胜者。
现在我们不想研究到底先手为胜还是为负,我只想问大家:
——“先手的人如果想赢,第一步有几种选择呢?”
Input
输入数据包含多个测试用例,每个测试用例占2行,首先一行包含一个整数M(1<M<=100),表示扑克牌的堆数,紧接着一行包含M个整数Ni(1<=Ni<=1000000,i=1…M),分别表示M堆扑克的数量。M为0则表示输入数据的结束。
Output
如果先手的人能赢,请输出他第一步可行的方案数,否则请输出0,每个实例的输出占一行。
Sample Input
3
5 7 9
0
Sample Output
1
Procedure
1 | /* |
2012 蓝桥杯 取球博弈
取球博弈
今盒子里有n个小球,A、B两人轮流从盒中取球,每个人都可以看到另一个人取了多少个,也可以看到盒中还剩下多少个,并且两人都很聪明,不会做出错误的判断。
我们约定:
每个人从盒子中取出的球的数目必须是:1,3,7或者8个。
轮到某一方取球时不能弃权!
A先取球,然后双方交替取球,直到取完。
被迫拿到最后一个球的一方为负方(输方)
请编程确定出在双方都不判断失误的情况下,对于特定的初始球数,A是否能赢?
程序运行时,从标准输入获得数据,其格式如下:
先是一个整数n(n<100),表示接下来有n个整数。然后是n个整数,每个占一行(整数<10000),表示初始球数。
程序则输出n行,表示A的输赢情况(输为0,赢为1)。
例如,用户输入:
4
1
2
10
18
则程序应该输出:
0
1
1
0
程序
1 | /* |
第七章 高级搜索算法
A算法
启发式搜索
启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估,得到最好的位置,再从这个位置进行搜索直到目标。这样可以省略大量无畏的搜索路径,提到了效率。在启发式搜索中,对位置的估价是十分重要的。采用了不同的估价可以有不同的效果。
估价函数
从当前节点移动到目标节点的预估费用;这个估计就是启发式的。在寻路问题和迷宫问题中,我们通常用曼哈顿(manhattan)估价函数(下文有介绍)预估费用。
A算法与BFS
可以这样说,BFS是A*算法的一个特例。对于一个BFS算法,从当前节点扩展出来的每一个节点(如果没有被访问过的话)都要放进队列进行进一步扩展。也就是说BFS的估计函数h永远等于0,没有一点启发式的信息,可以认为BFS是“最烂的”A*算法。
选取最小估价
如果学过数据结构的话,应该可以知道,对于每次都要选取最小估价的节点,应该用到最小优先级队列(也叫最小二叉堆)。在C++的STL里有现成的数据结构priority_queue,可以直接使用。当然不要忘了重载自定义节点的比较操作符。
A算法的特点
A算法在理论上是时间最优的,但是也有缺点:它的空间增长是指数级别的。
搜索区域
假设有人想从A点移动到一墙之隔的B点,如下图,绿色的是起点A,红色是终点B,蓝色方块是中间的墙。
你应该注意到了,我们把要搜寻的区域划分成了正方形的格子。这是寻路的第一步,简化搜索区域,就像我们这里做的一样。这个特殊的方法把我们的搜索区域简化为了 2 维数组。数组的每一项代表一个格子,它的状态就是可走 (walkalbe) 和不可走 (unwalkable) 。通过计算出从 A 到 B需要走过哪些方格,就找到了路径。一旦路径找到了,人物便从一个方格的中心移动到另一个方格的中心,直至到达目的地。
方格的中心点我们成为“节点 (nodes) ”。如果你读过其他关于 A* 寻路算法的文章,你会发现人们常常都在讨论节点。为什么不直接描述为方格呢?因为我们有可能把搜索区域划为为其他多变形而不是正方形,例如可以是六边形,矩形,甚至可以是任意多变形。而节点可以放在任意多边形里面,可以放在多变形的中心,也可以放在多边形的边上。我们使用这个系统,因为它最简单。
开始搜索
方格的中心点我们成为“节点 (nodes) ”。如果你读过其他关于 A* 寻路算法的文章,你会发现人们常常都在讨论节点。为什么不直接描述为方格呢?因为我们有可能把搜索区域划为为其他多变形而不是正方形,例如可以是六边形,矩形,甚至可以是任意多变形。而节点可以放在任意多边形里面,可以放在多变形的中心,也可以放在多边形的边上。我们使用这个系统,因为它最简单。
我们这样开始我们的寻路旅途:
1.从起点 A 开始,并把它就加入到一个由方格组成的 open list( 开放列表 ) 中。这个 open list 有点像是一个购物单。当然现在 open list 里只有一项,它就是起点 A ,后面会慢慢加入更多的项。 Open list 里的格子是路径可能会是沿途经过的,也有可能不经过。基本上 open list 是一个待检查的方格列表。
2.查看与起点 A 相邻的方格 ( 忽略其中墙壁所占领的方格,河流所占领的方格及其他非法地形占领的方格 ) ,把其中可走的 (walkable) 或可到达的 (reachable) 方格也加入到 open list 中。把起点 A 设置为这些方格的父亲 (parent node 或 parent square) 。当我们在追踪路径时,这些父节点的内容是很重要的。稍后解释。
3.把 A 从 open list 中移除,加入到 close list( 封闭列表 ) 中, close list 中的每个方格都是现在不需要再关注的。
如下图所示,深绿色的方格为起点,它的外框是亮蓝色,表示该方格被加入到了 close list 。与它相邻的黑色方格是需要被检查的,他们的外框是亮绿色。每个黑方格都有一个灰色的指针指向他们的父节点,这里是起点 A 。
接着,我们选择开启列表中的临近方格,大致重复前面的过程,如下。但是,哪个方格是我们要选择的呢?是那个F值最低的。
路径排序
计算出组成路径的方格的关键是下面这个等式:
F = G + H
这里,
G = 从起点 A 移动到指定方格的移动代价,沿着到达该方格而生成的路径。
H = 从指定的方格移动到终点 B 的估算成本。这经常被称为启发式的,可能会让你有点迷惑。这样叫的原因是因为它只是个猜测。我们没办法事先知道路径的长度,因为路上可能存在各种障碍(墙,水,等等)。虽然本文只提供了一种计算H的方法,但是你可以在网上找到很多其他的方法。
这个通常被称为试探法,有点让人混淆。为什么这么叫呢,因为这是个猜测。直到我们找到了路径我们才会知道真正的距离,因为途中有各种各样的东西 ( 比如墙壁,水等 ) 。本教程将教你一种计算 H 的方法,你也可以在网上找到其他方法。
我们的路径是这么产生的:反复遍历 open list ,选择 F 值最小的方格。这个过程稍后详细描述。我们还是先看看怎么去计算上面的等式。
如上所述, G 是从起点A移动到指定方格的移动代价。在本例中,横向和纵向的移动代价为 10 ,对角线的移动代价为 14 。之所以使用这些数据,是因为实际的对角移动距离是 2 的平方根,或者是近似的 1.414 倍的横向或纵向移动代价。使用 10 和 14 就是为了简单起见。比例是对的,我们避免了开放和小数的计算。这并不是我们没有这个能力或是不喜欢数学。使用这些数字也可以使计算机更快。稍后你便会发现,如果不使用这些技巧,寻路算法将很慢。
既然我们是沿着到达指定方格的路径来计算 G 值,那么计算出该方格的 G 值的方法就是找出其父亲的 G 值,然后按父亲是直线方向还是斜线方向加上 10 或 14 。随着我们离开起点而得到更多的方格,这个方法会变得更加明朗。
有很多方法可以估算 H 值。这里我们使用 Manhattan 方法,计算从当前方格横向或纵向移动到达目标所经过的方格数,忽略对角移动,然后把总数乘以 10 。之所以叫做 Manhattan 方法,是因为这很像统计从一个地点到另一个地点所穿过的街区数,而你不能斜向穿过街区。重要的是,计算 H 是,要忽略路径中的障碍物。这是对剩余距离的估算值,而不是实际值,因此才称为试探法。
把 G 和 H 相加便得到 F 。我们第一步的结果如下图所示。每个方格都标上了 F , G , H 的值,就像起点右边的方格那样,左上角是 F ,左下角是 G ,右下角是 H 。
好,现在让我们看看其中的一些方格。在标有字母的方格, G = 10 。这是因为水平方向从起点到那里只有一个方格的距离。与起点直接相邻的上方,下方,左方的方格的 G 值都是 10 ,对角线的方格 G 值都是 14 。
H 值通过估算起点于终点 ( 红色方格 ) 的 Manhattan 距离得到,仅作横向和纵向移动,并且忽略沿途的墙壁。使用这种方式,起点右边的方格到终点有 3 个方格的距离,因此 H = 30 。这个方格上方的方格到终点有 4 个方格的距离 ( 注意只计算横向和纵向距离 ) ,因此 H = 40 。对于其他的方格,你可以用同样的方法知道 H 值是如何得来的。
每个方格的 F 值,再说一次,直接把 G 值和 H 值相加就可以了。
继续搜索
为了继续搜索,我们从 open list 中选择 F 值最小的 ( 方格 ) 节点,然后对所选择的方格作如下操作:
4.把它从 open list 里取出,放到 close list 中。
5.检查所有与它相邻的方格,忽略其中在 close list 中或是不可走 (unwalkable) 的方格 ( 比如墙,水,或是其他非法地形 ) ,如果方格不在open lsit 中,则把它们加入到 open list 中。把我们选定的方格设置为这些新加入的方格的父亲。
6.如果某个相邻的方格已经在 open list 中,则检查这条路径是否更优,也就是说经由当前方格 ( 我们选中的方格 ) 到达那个方格是否具有更小的 G 值。如果没有,不做任何操作。
相反,如果 G 值更小,则把那个方格的父亲设为当前方格 ( 我们选中的方格 ) ,然后重新计算那个方格的 F 值和 G 值。如果你还是很混淆,请参考下图。
Ok ,让我们看看它是怎么工作的。在我们最初的 9 个方格中,还有 8 个在 open list 中,起点被放入了 close list 中。在这些方格中,起点右边的格子的 F 值 40 最小,因此我们选择这个方格作为下一个要处理的方格。它的外框用蓝线打亮。
首先,我们把它从 open list 移到 close list 中 ( 这就是为什么用蓝线打亮的原因了 ) 。然后我们检查与它相邻的方格。它右边的方格是墙壁,我们忽略。它左边的方格是起点,在 close list 中,我们也忽略。其他 4 个相邻的方格均在 open list 中,我们需要检查经由这个方格到达那里的路径是否更好,使用 G 值来判定。让我们看看上面的方格。它现在的 G 值为 14 。如果我们经由当前方格到达那里, G 值将会为 20(其中 10 为到达当前方格的 G 值,此外还要加上从当前方格纵向移动到上面方格的 G 值 10) 。显然 20 比 14 大,因此这不是最优的路径。如果你看图你就会明白。直接从起点沿对角线移动到那个方格比先横向移动再纵向移动要好。
当把 4 个已经在 open list 中的相邻方格都检查后,没有发现经由当前方格的更好路径,因此我们不做任何改变。现在我们已经检查了当前方格的所有相邻的方格,并也对他们作了处理,是时候选择下一个待处理的方格了。
因此再次遍历我们的 open list ,现在它只有 7 个方格了,我们需要选择 F 值最小的那个。有趣的是,这次有两个方格的 F 值都 54 ,选哪个呢?没什么关系。从速度上考虑,选择最后加入 open list 的方格更快。这导致了在寻路过程中,当靠近目标时,优先使用新找到的方格的偏好。但是这并不重要。 ( 对相同数据的不同对待,导致两中版本的 A* 找到等长的不同路径 ) 。
我们选择起点右下方的方格,如下图所示。
这次,当我们检查相邻的方格时,我们发现它右边的方格是墙,忽略之。上面的也一样。
我们把墙下面的一格也忽略掉。为什么?因为如果不穿越墙角的话,你不能直接从当前方格移动到那个方格。你需要先往下走,然后再移动到那个方格,这样来绕过墙角。 ( 注意:穿越墙角的规则是可选的,依赖于你的节点是怎么放置的 )
这样还剩下 5 个相邻的方格。当前方格下面的 2 个方格还没有加入 open list ,所以把它们加入,同时把当前方格设为他们的父亲。在剩下的3 个方格中,有 2 个已经在 close list 中 ( 一个是起点,一个是当前方格上面的方格,外框被加亮的 ) ,我们忽略它们。最后一个方格,也就是当前方格左边的方格,我们检查经由当前方格到达那里是否具有更小的 G 值。没有。因此我们准备从 open list 中选择下一个待处理的方格。
不断重复这个过程,直到把终点也加入到了 open list 中,此时如下图所示。
注意,在起点下面 2 格的方格的父亲已经与前面不同了。之前它的 G 值是 28 并且指向它右上方的方格。现在它的 G 值为 20 ,并且指向它正上方的方格。这在寻路过程中的某处发生,使用新路径时 G 值经过检查并且变得更低,因此父节点被重新设置, G 和 F 值被重新计算。尽管这一变化在本例中并不重要,但是在很多场合中,这种变化会导致寻路结果的巨大变化。
那么我们怎么样去确定实际路径呢?很简单,从终点开始,按着箭头向父节点移动,这样你就被带回到了起点,这就是你的路径。如下图所示。从起点 A 移动到终点 B 就是简单从路径上的一个方格的中心移动到另一个方格的中心,直至目标。就是这么简单!
A方法总结
好,现在你已经看完了整个说明,让我们把每一步的操作写在一起:
1.把起始格添加到开启列表。
2.重复如下的工作:
a)寻找开启列表中F值最低的格子。我们称它为当前格。
b)把它切换到关闭列表。
c)对相邻的格中的每一个?
- 如果它不可通过或者已经在关闭列表中,略过它。反之如下。
- 如果它不在开启列表中,把它添加进去。把当前格作为这一格的父节点。记录这一格的F,G,和H值。
- 如果它已经在开启列表中,用G值为参考检查新的路径是否更好。更低的G值意味着更好的路径。如果是这样,就把这一格的父节点改成当前格,并且重新计算这一格的G和F值。如果你保持你的开启列表按F值排序,改变之后你可能需要重新对开启列表排序。
d)停止,当你 - 把目标格添加进了关闭列表(注解),这时候路径被找到,或者
- 没有找到目标格,开启列表已经空了。这时候,路径不存在。
3.保存路径。从目标格开始,沿着每一格的父节点移动直到回到起始格。这就是你的路径。
参考
A*算法入门A*算法
- 最近又对A算法有了更深理解,来补充补充
- 在BFS算法中,若对每个状态n都设定估价函数f(n)=g(n)+h(n),并且每次从Open表中选节点进行扩展时,都选取f值最小的节点,则该搜索算法为启发式搜索算法,又称A算法。
- g(n):从起始状态到当前状态n的代价
- h(n):从当前状态n到目标状态的估价代价
- A算法中的估价函数若选取不当,则可能找不到解,或者找到的解也不是最优解。因此,需要对估价函数做一些限制,使得算法确保找到最优解(步数,即状态转移次数最少的解)。A*算法即为对估价函数做了特定限制,且确保找到最优解的A算法。
- $f^*(n)=g^*(n)+h^*(n)$
$f^*(n)$:从初始节点$S_0$出发,经过节点n到达目标节点的最小步数(真实值)
$g^*(n)$:从$S_0$出发,到达n的最小步数(真实值)
$h^*(n)$:从n出发,到达目标节点的最小步数(真实值)
估价函数$f(n)$是$f^*(n)$的估计值。 - $f(n)=g(n)+h(n)$,且满足以下限制:
- $g(n)$是从$s_0$到n的真实步数(未必是最优的),因此:$g(n)>0且g(n)>=g*(n)$
- $h(n)$是从n到目标的估计步数。估计总是过于乐观的,即$h(n)<=h*(n)$,且$h(n)$相容,则A算法转变为A*算法。证明暂无。
- $h(n)$的相容:
如果h函数对任意状态s_1和s_2还满足:
$h(s_1)<=h(s_2)+c(s_1,s_2)$
$c(s_1,s_2)$是$s_1$转移到$s_2$的步数,则称h是相容的。
h相容能确保随着一步步往前组,f递增,这样A*能更高效找到最优解。
h相容$\Rightarrow g(s_1)+h(s_1)<=g(s_1)+h(s_2)+c(s_1,s_2)=g(s_2)+h(s_2)\Rightarrow f(s_1)<=f(s_2)$ 即f是递增的。
- A*算法的搜索效率很大程度上取决于估价函数h(n)。一般来说,在满足h(n)<=h^*(n)的前提下,h(n)越大越好
1 | open=[Start] |
Knight Moves
Description
A friend of you is doing research on the Traveling Knight Problem (TKP) where you are to find the shortest closed tour of knight moves that visits each square of a given set of n squares on a chessboard exactly once. He thinks that the most difficult part of the problem is determining the smallest number of knight moves between two given squares and that, once you have accomplished this, finding the tour would be easy.
Of course you know that it is vice versa. So you offer him to write a program that solves the “difficult” part.
Your job is to write a program that takes two squares a and b as input and then determines the number of knight moves on a shortest route from a to b.
Input
The input will contain one or more test cases. Each test case consists of one line containing two squares separated by one space. A square is a string consisting of a letter (a-h) representing the column and a digit (1-8) representing the row on the chessboard.
Output
For each test case, print one line saying “To get from xx to yy takes n knight moves.”.
Sample Input
e2 e4
a1 b2
b2 c3
a1 h8
a1 h7
h8 a1
b1 c3
f6 f6
Sample Output
To get from e2 to e4 takes 2 knight moves.
To get from a1 to b2 takes 4 knight moves.
To get from b2 to c3 takes 2 knight moves.
To get from a1 to h8 takes 6 knight moves.
To get from a1 to h7 takes 5 knight moves.
To get from h8 to a1 takes 6 knight moves.
To get from b1 to c3 takes 1 knight moves.
To get from f6 to f6 takes 0 knight moves.
Procedure
1 | /* |
1 |
|
D. Olya and Energy Drinks
Description
Olya loves energy drinks. She loves them so much that her room is full of empty cans from energy drinks.
Formally, her room can be represented as a field of n × m cells, each cell of which is empty or littered with cans.
Olya drank a lot of energy drink, so now she can run k meters per second. Each second she chooses one of the four directions (up, down, left or right) and runs from 1 to k meters in this direction. Of course, she can only run through empty cells.
Now Olya needs to get from cell (x1, y1) to cell (x2, y2). How many seconds will it take her if she moves optimally?
It’s guaranteed that cells (x1, y1) and (x2, y2) are empty. These cells can coincide.
Input
The first line contains three integers n, m and k (1 ≤ n, m, k ≤ 1000) — the sizes of the room and Olya’s speed.
Then n lines follow containing m characters each, the i-th of them contains on j-th position “#”, if the cell (i, j) is littered with cans, and “.” otherwise.
The last line contains four integers x1, y1, x2, y2 (1 ≤ x1, x2 ≤ n, 1 ≤ y1, y2 ≤ m) — the coordinates of the first and the last cells.
Output
Print a single integer — the minimum time it will take Olya to get from (x1, y1) to (x2, y2).
If it’s impossible to get from (x1, y1) to (x2, y2), print -1.
Examples
1 | input |
Procedue
1 | /* |
第八章 线段树和树状数组
线段树(Interval Tree)
- 实际上还是称为区间树更好理解一些
- 树:一棵二叉树
- 线段:树上的每个节点对应于一个线段(还是叫“区间”更容易理解,区间的起点和终点通常为整数)
- 同一层的节点所代表的区间,相互不会重叠。同一层节点所代表的区间,加起来十个连续的区间。
- 叶子节点的区间是单位长度,不能再分了。
- 线段树是一棵二叉树,树中的每一个节点表示了一个区间[a,b]。a,b通常是正数。每一个叶子节点表示了一个单位区间(长度为1)。对于每一个非叶子节点所表示的节点[a,b],其左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b](除法去尾取整)。
- 每个区间的长度是区间内正数的个数
- 叶子节点长度为1,不能再往下分
- 若一个节点对应的区间是[a,b],则其子节点对应的区间分别是[a,(a+b)/2]和[(a+b)/2+1,b](除法去尾取整)
$n$
$\frac{n}{2}\cdot2$
$\frac{n}{4}\cdot4$
…
$1\cdot n$
$\iff$
$n$
$\frac{n}{2}\cdot2$
$\frac{n}{2^2}\cdot2^2$
…
$1\cdot2^x$
$2^x=n$
$x=\log_2 n$
- 线段树的平分构造,实际上是用了二分的方法。若根节点对应的区间是[a,b],那么它的深度为$\log_2 {\left(b-a+1\right)}$(向上取整)
- 叶子节点的数目和根节点表示区间的长度相同。
- 线段树节点要么0度,要么2度,因此若叶子节点数目为N,则线段树总节点数目为2N-1。
- 若叶子节点为N,要想用连续的数组表示一棵线段树,则数组的大小应该为4N。
因为,根据性质3,线段树总节点数目为2N-1,又由于线段树不是完全二叉树,因此其最低的叶子一层并不是紧靠最左边,这样在其倒数第二层上的索引号接近2N的位置,按照2index+1和2index+2的方式来访问其左右子节点,这就导致整个数组的大小要约为 4N.线段树的特征
1.线段树的深度不超过$\log_2 {n}+1$(向上取整,n是根节点对应区间的长度)。
2.线段树上,任意一个区间被分解后得到的“终止节点”数目都是$\log_2 n$量级。
3.线段树上更新叶子节点和进行区间分解时间复杂度都是$O\left(\log_2 {n}\right)$
这些结论为线段树能在$O\left(\log_2 {n}\right)$的时间内完成插入、更新、查找、统计等工作,提供了理论依据。
线段树的构建
1 | function 以节点v为根建树、v对应区间为[l.r] |
线段树的基本用途
- 线段树适用于和区间统计有关的问题。比如某些数据可以按区间进行划分,按区间动态进行修改,而且还需要按区间多次进行查询,那么使用线段树可以达到较快查询速度。
线段树应用举例
给你一个数的序列$A_1A_2…A_n$,并且可能多次进行下列两个操作:
1.对序列里面的某个数进行加减
2.询问这个序列里面任意一个连续的子序列的和是多少
- 希望第2个操作每次能在$\log_2 n$
- 显然,[1,n]就是根节点对应的区间
- 可以在每个节点记录该节点对应的区间里面的数和Sum
- 对于操作1:因为序列里面$A_i$最多只会被线段树的$\log_2 n$个节点覆盖。只要求对线段树覆盖$A_i$的节点Sum进行加操作,因此复杂度是$\log_2 n$
- 对于操作2:同样只需要找到区间所覆盖的“终止”接地单,然后把所找到“终止”节点的Sum累加起来。因为这些节点的数量是$O\left(\log_2 {n}\right)$的,负责度也是$O\left(\log_2 {n}\right)$
- 如果走到节点[L,R]时,如果要查询的区间就是[L,R],那么直接返回该节点的Sum,并累加到总的和尚
- 如果不是,则对于区间[L,R],去mid=(L+R)/2
- 然后看要查询的区间与[L,mid]或[mid+1,R]哪个有交集,就进入哪个区间进行进一步查询
- 因为这个线段树的深度最深的LogN,所以每次遍历操作都在LogN内完成。但是常数可能很大。
- 如果是对区间所对应的一些数据进行修改,过程和查询类似。
- 用线段树解题,关键是要想清楚每个节点要存哪些信息(当然区间起终点,以及左右子节点指针是必须的),以及这些信息如何搞笑更新,维护,查询。不要一更新到叶子节点,那样更新效率最坏可能变成O(n)的了。
- 先建树,然后插入数据、更新、查询。
动态建树与静态建树
做A_Simple_Problem_with_Integers的时候,强迫症,想改成动态建树,测试发现居然更耗时间,而且内存反而开销更大?!!更耗时间可能了解,动态的话每次申请都得时间,内存更大就搞不懂了…
做了些测试,发现应该不是左右指针的问题,但是测试发现几乎内存增加了一倍,这应该不是偶然啊,但是没找到具体原因,先不管了,以后会顿悟的。
暂且先记住用静态建树的方法分配开始就分配内存,采用动态建树分配就比较好。
结合了动态建树的节点少的问题,又结合了静态建树节省时间的问题。
还是强迫症啊!!!!!!什么鬼!!!!
Balanced Lineup
Description
For the daily milking, Farmer John’s N cows (1 ≤ N ≤ 50,000) always line up in the same order. One day Farmer John decides to organize a game of Ultimate Frisbee with some of the cows. To keep things simple, he will take a contiguous range of cows from the milking lineup to play the game. However, for all the cows to have fun they should not differ too much in height.
Farmer John has made a list of Q (1 ≤ Q ≤ 200,000) potential groups of cows and their heights (1 ≤ height ≤ 1,000,000). For each group, he wants your help to determine the difference in height between the shortest and the tallest cow in the group.
Input
Line 1: Two space-separated integers, N and Q.
Lines 2..N+1: Line i+1 contains a single integer that is the height of cow i
Lines N+2..N+Q+1: Two integers A and B (1 ≤ A ≤ B ≤ N), representing the range of cows from A to B inclusive.
Output
Lines 1..Q: Each line contains a single integer that is a response to a reply and indicates the difference in height between the tallest and shortest cow in the range.
Sample Input
6 3
1
7
3
4
2
5
1 5
4 6
2 2
Sample Output
6
3
0
Procedrue
1 | /* |
1 | //默写了一遍,改用指针,坐等26号POJ维护完成测试,看看能不能一次AC |
1 | //对比下,就会发现问题,坐等26号POJ维护完成,爆了这么多天了... |
A Simple Problem with Integers
Description
You have N integers, A1, A2, … , AN. You need to deal with two kinds of operations. One type of operation is to add some given number to each number in a given interval. The other is to ask for the sum of numbers in a given interval.
Input
The first line contains two numbers N and Q. 1 ≤ N,Q ≤ 100000.
The second line contains N numbers, the initial values of A1, A2, … , AN. -1000000000 ≤ Ai ≤ 1000000000.
Each of the next Q lines represents an operation.
“C a b c” means adding c to each of Aa, Aa+1, … , Ab. -10000 ≤ c ≤ 10000.
“Q a b” means querying the sum of Aa, Aa+1, … , Ab.
Output
You need to answer all Q commands in order. One answer in a line.
Sample Input
10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4
Sample Output
4
55
9
15
Procedure
1 | /* |
1 | /* |
1 | //默写——还是有点小问题,不过对问题和代码过程有了更深的理解,嘻嘻。 |
1 |
|
离散化
有时,区间的断点不是整数,或者区间太大导致建树内存开销过大MLE,那么就需要进行“离散化”后再建树。
Mayor’s Poster
Description
The citizens of Bytetown, AB, could not stand that the candidates in the mayoral election campaign have been placing their electoral posters at all places at their whim. The city council has finally decided to build an electoral wall for placing the posters and introduce the following rules:
Every candidate can place exactly one poster on the wall.
All posters are of the same height equal to the height of the wall; the width of a poster can be any integer number of bytes (byte is the unit of length in Bytetown).
The wall is divided into segments and the width of each segment is one byte.
Each poster must completely cover a contiguous number of wall segments.
They have built a wall 10000000 bytes long (such that there is enough place for all candidates). When the electoral campaign was restarted, the candidates were placing their posters on the wall and their posters differed widely in width. Moreover, the candidates started placing their posters on wall segments already occupied by other posters. Everyone in Bytetown was curious whose posters will be visible (entirely or in part) on the last day before elections.
Your task is to find the number of visible posters when all the posters are placed given the information about posters’ size, their place and order of placement on the electoral wall.
Input
The first line of input contains a number c giving the number of cases that follow. The first line of data for a single case contains number 1 <= n <= 10000. The subsequent n lines describe the posters in the order in which they were placed. The i-th line among the n lines contains two integer numbers li and ri which are the number of the wall segment occupied by the left end and the right end of the i-th poster, respectively. We know that for each 1 <= i <= n, 1 <= li <= ri <= 10000000. After the i-th poster is placed, it entirely covers all wall segments numbered li, li+1 ,… , ri.
Output
For each input data set print the number of visible posters after all the posters are placed.
The picture below illustrates the case of the sample input.
Sample Input
1
5
1 4
2 6
8 10
3 4
7 10
Sample Output
4
Procedure
1 | /* |
1 | //默写,恩,以后看完一个就默写一遍,我先把前两个的线段树也默写一遍吧! |
1 |
|
Atlantis
Description
There are several ancient Greek texts that contain descriptions of the fabled island Atlantis. Some of these texts even include maps of parts of the island. But unfortunately, these maps describe different regions of Atlantis. Your friend Bill has to know the total area for which maps exist. You (unwisely) volunteered to write a program that calculates this quantity.
Input
The input consists of several test cases. Each test case starts with a line containing a single integer n (1 <= n <= 100) of available maps. The n following lines describe one map each. Each of these lines contains four numbers x1;y1;x2;y2 (0 <= x1 < x2 <= 100000;0 <= y1 < y2 <= 100000), not necessarily integers. The values (x1; y1) and (x2;y2) are the coordinates of the top-left resp. bottom-right corner of the mapped area.
The input file is terminated by a line containing a single 0. Don’t process it.
Output
For each test case, your program should output one section. The first line of each section must be “Test case #k”, where k is the number of the test case (starting with 1). The second one must be “Total explored area: a”, where a is the total explored area (i.e. the area of the union of all rectangles in this test case), printed exact to two digits to the right of the decimal point.
Output a blank line after each test case.
Sample Input
2 10 10 20 20 15 15 25 25.5 0
Sample Output
Test case #1 Total explored area: 180.00
Procedure
1 | /* |
1 | //在理解的基础上,自己再默写一遍真的很有用,坚持下!Keep! |
1 | //恩,再来一遍换个方向扫描的,但你妈,出现了一个问题 |
树状数组
- 对于序列a,我们设一个数组C
– $C[i]=a[i-2^k+1]+…+a[i]$
– k为i在二进制下末尾0的个数
– $2^k$就是i保留最右边的1,其余位全变0
– i从1开始算! - C即为a的树状数组
- 对于i,如何求$2^k$?
- $2^k=i&{(-1)}$
关于$2^k=i&(-i)$的说明:
由于k是i末尾0的个数,那么$2^k$就是$0.010..0$(1后k个0),那么也就是说保留i的最低位1,其余全变成0,做到这一点可以这么考虑:
i各位取反,可以知道$i&!i=0$,那么为了只保留最低位的1——由于最低位1后面都为0,那么最低位1后面0各位取反都会得到1,那么i的各位取反+1后就可以得到构造出新的$i’=!i+1$,而$i’$的最低位1与i的最低位1位置相同,最低位1之前各位与$!i$相同,最低位1后都为0
那么$i&i’=2^k$,而$i’$的表示在这里恰好就是负数的补码定义,而计算机中存储负数恰好就是采用补码,所以$2^k=i&(-i)$
通常我们用$Lowbit(x)$表示对应的$2^k$
$Lowbit(x)=x&(-x)$
$Lowbit(x)$实际上就是x的二进制表示形式留下最右边的1,其他位都变成0
$C[i]=a[i-Lowbit(i)+1]+…+a[i]$
C[i]表示的区间的最后一个元素一定是a[i]
树状数组的好处在于能快速求任意区间的和$a[i]+a[i+1]+…+a[j]$
设$sum(k)=a[1]+a[2]+a[3]+…+a[k]$
则$a[i]+a[i+1]+…+a[j]=sum(j)-sum(i-1)$
有了树状数组,$sum(k)$就能在$O(\log_2 N)$时间内求出,N是a数组元素
有了树状数组,$sum(k)$就能在$O(\log_2 n)$时间内求出,N是a数组元素个数。而且更新一个a的元素所花的时间也是$O(\log_2 n)$的(因为a更新了C也得更新)。
根据C的构成规律,可以发现sum(k)可以表示为:
$sum(k)=C[n_1]+C[n_2]+…+C[n_m]$
其中$n_m=k$
$n_{i-1}=n_i-Lowbit(n_i)$而且$n_1-Lowbit(n_1)$必须等于0,$n_1$大于0
如:$sum(6)=C[4]+C[6]$
$Lowbit(x)$实际上就是x的二进制表示形式留下最右边的1,其他为都变成0
那么,$sum(k)$最多有几项?这个决定了求区间和的时间复杂度
$n_i-Lowbit(n_i)$就是$n_i$的二进制去掉最右边的1
k的二进制里最多有$ceil(\log_2 k)$个1
$sum(k)$最多$ceil(\log_2 k)$项,所以本次求和的复杂度就是$\log_2 k$
证明:$sum(k)=a[i]+…+a[k]=C[n_1]+…C[n_k]$
$C[n_m]=a[n_m-Lowbit(n_m)+1]+…+a[n_m]$
$C[n_m]=a[n_{m-1}-Lowbit(n_{m-1})+1]+…+a[n_{m-1}]$
$=a[n_{m-1}-Lowbit(n_{m-1})+1]+…+a[n_m-Lowbit(n_m)]$
$C[n_{m-2}]=a[n_{m-2}-Lowbit(n_{m-2})+1]+…+a[n_{m-2}]$
……
$C[n_1]=a[n_1-Lowbit(n_1)+1]+…+a[n_1]$
$=a[1]+..+a[n_1]$
(因$n_1-Lowbit(n_1)$必须等于0,否则就还需要$C[n_1-Lowbit(n_1)]$了)
- 更新一个a元素,C也要跟着更新,复杂度是多少呢?即C里有几项要更新呢?
如果a[i]更新了,那么以下的几项都需要更新:
$C[n_1],C[n_2],…,C[n_m]$
其中,$n_1=i,n_{i+1}=n_i+Lowbit(n_i)$
$n_m+Lowbit(n_m)$必须大于a的元素个数N,$n_m$小于等于N,同理,总的来说更新一个元素的时间,也是$\log_2 N$
原因如下:
$a[i]$更新->$C[i]$必须更新,因为$C[i]=a[i-Lowbit(i)+1]+…+a[i]$
$C[k]=a[k-Lowbit(k)+1]+…+a[k]$
$C[k+Lowbit(k)]=a[k+Lowbit(k)-Lowbit(k+Lowbit(k))+1]+…+a[k+Lowbit(k)]$
注意第一项,一个数加上自身最低位1,然后新的数减去自身最低位1,结果肯定比这个数小,即$k+Lowbit(k)-Lowbit(k+Lowbit(k))<k$,故$k+Lowbit(k)-Lowbit(k+Lowbit(k))+1<=k$,所以说$C[k+Lowbit(k)]$的起始项不晚于$C[k]$的起始项,所以,若$C[k]$包含$a[i]$,则$C[k+Lowbit(k)]$也包含$a[i]$,即$C[k]$需要更新->$C[k+Lowbit(k)]$也需要更新
- 初始状态下由a构建树状数组C的时间复杂度是多少?
显然是$O(N)$的:
$∵C[k]=sum(k)-sum(k-Lowbit(k))$
$sum(k)=C[n_1]+C[n_2]+…+C[n_{m-1}]+C[n_m],\left(n_m=k\right)$
$n_{m-1}=k-Lowbit(k)$
$sum(k-Lowbit(k))=C[n_1]+C[n_2]+…+C[n_{m-1}]$
所以,树状数组适合单个元素经常修改而且还反复要求部分的区间的和的情况。
上述问题虽然也可以用线段树解决,但是用树状数组来做,编程效率和程序运行效率都更高(时间复杂度相同,但是树状数组常数小)
如果每次要修改的不是单个元素,而是一个区间,那么就不能用树状数组了(效率过低)
树状数组时间复杂度总结:
建数组:$O(N)$
更新:$O(\log_2 n)$
局部求和:$O(\log_2 n)$注意:图示的每个节点和这里表示的$sum(k)=a[i]+…+a[k]=C[n_1]+…C[n_k]$就会发现,树状数组其实也是二分的性质,同线段树类似。
参考
Apple Tree
Description
There is an apple tree outside of kaka’s house. Every autumn, a lot of apples will grow in the tree. Kaka likes apple very much, so he has been carefully nurturing the big apple tree.
The tree has N forks which are connected by branches. Kaka numbers the forks by 1 to N and the root is always numbered by 1. Apples will grow on the forks and two apple won’t grow on the same fork. kaka wants to know how many apples are there in a sub-tree, for his study of the produce ability of the apple tree.
The trouble is that a new apple may grow on an empty fork some time and kaka may pick an apple from the tree for his dessert. Can you help kaka?
Input
The first line contains an integer N (N ≤ 100,000) , which is the number of the forks in the tree.
The following N - 1 lines each contain two integers u and v, which means fork u and fork v are connected by a branch.
The next line contains an integer M (M ≤ 100,000).
The following M lines each contain a message which is either
“C x” which means the existence of the apple on fork x has been changed. i.e. if there is an apple on the fork, then Kaka pick it; otherwise a new apple has grown on the empty fork.
or
“Q x” which means an inquiry for the number of apples in the sub-tree above the fork x, including the apple (if exists) on the fork x
Note the tree is full of apples at the beginning
Output
For every inquiry, output the correspond answer per line.
Sample Input
3
1 2
1 3
3
Q 1
C 2
Q 1
Sample Output
3
2
Procedure
1 | /* |
树状数组求逆序对
这个思路很巧妙啊!
1
2
3
4
5struct Node
{
int val;//数组值
int order;//数组顺序
}首先引入例子:
原始数组:
i: 1 2 3 4 5
val: 9 0 1 5 4
order: 1 2 3 4 5对原始数组按照val值进行升序排列:
i: 1 2 3 4 5
val: 0 1 4 5 9
order: 2 3 5 4 1接下来,重定序,也就是说按照输入的顺序给出关于自然顺序定序:
(找出原数组元素排列在1-n中的对应排列映射关系)
i: 1 2 3 4 5
val: 0 1 4 5 9
order: 2 3 5 4 1
val: 9 0 1 5 4
record:5 1 2 4 3record和order的映射关系:
record[order]=i而后求逆序对,按照i=1 2 3 4 5一次插入record进树状数组:
这里的i的意义为当前树状数组中插入的元素的个数,先对C全部初始化为0
那么逆序对,就是插入一个数,对该元素的C进行更新,表示该元素插入,
而计算逆序对的时候,只需要返回i-GetSum(record)就是插入该元素后,获得的逆序对个数
例如:
①插入i=1,record=5,那么
1 2 3 4 5
0 0 0 0 1
计算区间总和为1,i-GetSum(record)=1-1=0,这里的意思就表示插入5后当前树状数组中没有比5更小的数,
因为当前插入个数为i=1,那么找出当前树状数组中更小的数的个数就是当前所得到的逆序对个数
换言之,i就是当前区间总和i=GetSum(5)=1,GetSum(record)=GetSum(5)=1
②插入i=2,record=1,那么
1 2 3 4 5
1 0 0 0 1
i-GetSum(record)=2-GetSum(1)=2-1=1;
即GetSum(5)-GetSum(record)=i-GetSum(1)=2-1=1;
……所以总的思路就是:
找出插入当前区间时较小的数的个数,累加结果就是逆序对的个数,即:
求出区间总和与当前插入区间的总和之差,累加的结果就是逆序对的个数:
当前区间总和有两部分组成:当前插入区间(左半部分区间)总和和右半部分区间总和
而右半部分区间的总和就是数较大的部分
左半部分区间就是数较小的部分
①如果右半部分区间的总和为0,那么在当前插入区间(左半部分区间)就是区间总和,故此时逆序对个数为0
②如果右半部分区间的总和不为0,那么区间总和-左半部分区间总和就是当前插入时的逆序对个数
所以每次插入元素,就是找之前插入的数中比当前插入元素大的个数!!!!
Ultra-QuickSort
Description
In this problem, you have to analyze a particular sorting algorithm. The algorithm processes a sequence of n distinct integers by swapping two adjacent sequence elements until the sequence is sorted in ascending order. For the input sequence
9 1 0 5 4 ,
Ultra-QuickSort produces the output
0 1 4 5 9 .
Your task is to determine how many swap operations Ultra-QuickSort needs to perform in order to sort a given input sequence.
Input
The input contains several test cases. Every test case begins with a line that contains a single integer n < 500,000 – the length of the input sequence. Each of the the following n lines contains a single integer 0 ≤ a[i] ≤ 999,999,999, the i-th input sequence element. Input is terminated by a sequence of length n = 0. This sequence must not be processed.
Output
For every input sequence, your program prints a single line containing an integer number op, the minimum number of swap operations necessary to sort the given input sequence.
Sample Input
5
9
1
0
5
4
3
1
2
3
0
Sample Output
6
0
Procedure
1 | /* |
差分数组
对于一个数组A[ ],其差分数组D[i]=A[i]-A[i-1] (i>0)且D[0]=A[0]
令SumD[i]=D[0]+D[1]+D[2]+…+D[i] (SumD[ ]是差分数组D[ ]的前缀和)
则SumD[i]=A[0]+A[1]-A[0]+A[2]-A[1]+A[3]-A[2]+…+A[i]-A[i-1]=A[i]
所以A[i]=D[0]+D[1]+D[2]+…+D[i]
即A[i]的差分数组是D[i], 而D[i]的前缀和是A[i]
- 最好自己代入例子试一遍,加深理解
- 总的来说差分数组适用于离线的区间修改问题,如果是在线的话应该用线段树或其他数据结构。
- 差分数组其实就相当于通过改变区间前端和末端与其他部分的差值,在最后进行累加的时候实行对整个区间的值的改变。
- 但为什么要存差值呢?————因为数列中的数满A[i]=sum{D[1]…D[i]},便于用递推求得最后的值。
- [L,R]的元素值加C:
D[L]+=C,D[R+1]-=C
那么,
A[L]=D[0]+…+D[L]=A[L]+C
A[L+1]=D[0]+…+D[L]+D[L+1]=A[L]+C
…
A[R]=D[0]+…+D[L]+…+D[R]=A[R]+C
A[R+1]=D[0]+…+D[L]+…+D[R+1]=A[R]+C-C=A[R]
…
Color the ball
Problem Description
N个气球排成一排,从左到右依次编号为1,2,3….N.每次给定2个整数a b(a <= b),lele便为骑上他的“小飞鸽”牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是N次以后lele已经忘记了第I个气球已经涂过几次颜色了,你能帮他算出每个气球被涂过几次颜色吗?
Input
每个测试实例第一行为一个整数N,(N <= 100000).接下来的N行,每行包括2个整数a b(1 <= a <= b <= N)。
当N = 0,输入结束。
Output
每个测试实例输出一行,包括N个整数,第I个数代表第I个气球总共被涂色的次数。
Sample Input
3
1 1
2 2
3 3
3
1 1
1 2
1 3
0
Sample Output
1 1 1
3 2 1
Procedure
1 | /* |
第九章 并查集
并查集
并查集(Union-find Sets)是一种非常精巧而实用的数据结构,它主要用于处理一些不相交集合的合并问题。一些常见的用途有求连通子图、求最小生成树的 Kruskal 算法和求最近公共祖先(Least Common Ancestors, LCA)等。
使用并查集时,首先会存在一组不相交的动态集合$S={S_1,S_2,⋯,S_k}$,一般都会使用一个整数表示集合中的一个元素。
每个集合可能包含一个或多个元素,并选出集合中的某个元素作为代表。每个集合中具体包含了哪些元素是不关心的,具体选择哪个元素作为代表一般也是不关心的。我们关心的是,对于给定的元素,可以很快的找到这个元素所在的集合(的代表),以及合并两个元素所在的集合,而且这些操作的时间复杂度都是常数级的。
并查集的基本操作有三个:
①makeSet(s):建立一个新的并查集,其中包含 s 个单元素集合。
②UnionSet(x, y):把元素 x 和元素 y 所在的集合合并,要求 x 和 y 所在的集合不相交,如果相交则不合并。
③Find(x):找到元素 x 所在的集合的代表,该操作也可以用于判断两个元素是否位于同一个集合,只要将它们各自的代表比较一下就可以了。
- 并查集的实现原理也比较简单,就是使用树来表示集合,树的每个节点就表示集合中的一个元素,树根对应的元素就是该集合的代表
图中有两棵树,分别对应两个集合,其中第一个集合为 {a,b,c,d},代表元素是 a;第二个集合为 {e,f,g},代表元素是 e。
树的节点表示集合中的元素,指针表示指向父节点的指针,根节点的指针指向自己,表示其没有父节点。沿着每个节点的父节点不断向上查找,最终就可以找到该树的根节点,即该集合的代表元素。
现在,应该可以很容易的写出 makeSet 和 find 的代码了,假设使用一个足够长的数组来存储树节点(很类似之前讲到的静态链表),那么 makeSet 要做的就是构造出如图的森林,其中每个元素都是一个单元素集合,即父节点是其自身:
相应的代码如下所示,时间复杂度是 O(n):
1 | Status MakeSet(int size){ |
- 接下来,就是 find 操作了,如果每次都沿着父节点向上查找,那时间复杂度就是树的高度,完全不可能达到常数级。这里需要应用一种非常简单而有效的策略——路径压缩。
路径压缩,就是在每次查找时,令查找路径上的每个节点都直接指向根节点。
1 | int Get_Set_Parent(int x) |
注意:这里的Get_Set_Parent的时间复杂度可以说是<=4,具体分析以后再说,这里记住即可,反正就是效率高!没错的!没毛病!
- 最后是合并操作 unionSet,并查集的合并也非常简单,就是将一个集合的树根指向另一个集合的树根
1 | Status MergeSet(int x,int y) |
The Suspects
Description
Severe acute respiratory syndrome (SARS), an atypical pneumonia of unknown aetiology, was recognized as a global threat in mid-March 2003. To minimize transmission to others, the best strategy is to separate the suspects from others.
In the Not-Spreading-Your-Sickness University (NSYSU), there are many student groups. Students in the same group intercommunicate with each other frequently, and a student may join several groups. To prevent the possible transmissions of SARS, the NSYSU collects the member lists of all student groups, and makes the following rule in their standard operation procedure (SOP).
Once a member in a group is a suspect, all members in the group are suspects.
However, they find that it is not easy to identify all the suspects when a student is recognized as a suspect. Your job is to write a program which finds all the suspects.
Input
The input file contains several cases. Each test case begins with two integers n and m in a line, where n is the number of students, and m is the number of groups. You may assume that 0 < n <= 30000 and 0 <= m <= 500. Every student is numbered by a unique integer between 0 and n−1, and initially student 0 is recognized as a suspect in all the cases. This line is followed by m member lists of the groups, one line per group. Each line begins with an integer k by itself representing the number of members in the group. Following the number of members, there are k integers representing the students in this group. All the integers in a line are separated by at least one space.
A case with n = 0 and m = 0 indicates the end of the input, and need not be processed.
Output
For each case, output the number of suspects in one line.
Sample Input
100 4
2 1 2
5 10 13 11 12 14
2 0 1
2 99 2
200 2
1 5
5 1 2 3 4 5
1 0
0 0
Sample Output
4
1
1
Procedure
1 | /* |
Cube Stacking
Description
Farmer John and Betsy are playing a game with N (1 <= N <= 30,000)identical cubes labeled 1 through N. They start with N stacks, each containing a single cube. Farmer John asks Betsy to perform P (1<= P <= 100,000) operation. There are two types of operations:
moves and counts.
- In a move operation, Farmer John asks Bessie to move the stack containing cube X on top of the stack containing cube Y.
- In a count operation, Farmer John asks Bessie to count the number of cubes on the stack with cube X that are under the cube X and report that value.
Write a program that can verify the results of the game.
Input
- Line 1: A single integer, P
- Lines 2..P+1: Each of these lines describes a legal operation. Line 2 describes the first operation, etc. Each line begins with a ‘M’ for a move operation or a ‘C’ for a count operation. For move operations, the line also contains two integers: X and Y.For count operations, the line also contains a single integer: X.
Note that the value for N does not appear in the input file. No move operation will request a move a stack onto itself.
Output
Print the output from each of the count operations in the same order as the input file.
Sample Input
6
M 1 6
C 1
M 2 4
M 2 6
C 3
C 4
Sample Output
1
0
2
Procdure
1 | /* |
第十章 最小生成树(MST)问题
图的生成树
在一个连通图G中,如果取它的全部顶点和一部分边构成一个子图G’,即:$V(G’)=V(G),E(G’)∈E(G)$若边集E(G’)中的边既将图中的所有顶点连通又不形成回路,则称子图G’是原图G的一棵生成树。
一棵含有n个点的生成树,必含有n-1条边。
##最小生成树对于一个连通网(连通带权图,假定每条边上的权均为大于零的实数)来说,每棵树的权(即树中所有边的权值总和)也可能不同
具有权最小的生成树称为最小生成树。
生成树
无向连通图的边的集合
无回路
连接所有的点
最小
所有边的权值之和最小
Prim算法
假设G=(V,E)是一个具有n个顶点的连通网,T=(U,TE)是G的最小生成树,U,TE初值均为空集。
首先从V中任取一个顶点(假定取v1),将它并入U中,此时U={v1},然后只要U是V的真子集(U∈V),就从那些一个端点已在T中,另一个端点仍在T外的所有边中,找一条最短边,设为$(v_i,v_j)$,其中$v_i∈U,v_j∈V-U$,并把改变$(v_i,v_j)$和顶点$v_j$分别并入T的边集TE和顶点集U,如此进行下去,每次往生成树并入一个顶点和一条边,知道n-1次后得到最小生成树。
Prim算法实现
图节点数目为N,正在构造的生成树为T
维护Dist数组,Dist[i]表示v_i到T的“距离”(权值)
开始所有$Dist[i]=∞$,T为空集
①若|T|=N,最小生成树完成。否则取Dist[i]最小的不在T中的点$v_i$,将其加入T
②更新所有与$v_i$有边相连且不在T中的点$v_j$的Dist值:$Dist[i]=min(Dist[j],W(v_i,v_j))$
③转到①
关键问题
每次如何从连接T中和T外顶点的所有边中,找到一条最短的
①如果用邻接矩阵存放图,而且选取最短边的时候遍历所有点进行选取,则总时间复杂度为$O(V^2)$,V位顶点个数
②用邻接表存放图,并且使用堆来选取最短边,则总时间复杂度为$O(ElogV)$
不加堆优化的Prim算法适用于密集图,加堆优化的使用与稀疏图。
参考Agri-Net
Description
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.
Input
The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.
Output
For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.
Sample Input
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
Sample Output
28
Procedure
1 | /* |
1 | /* |
Kruskal算法
- 假设G=(V,E)是一个具有n个顶点的连通网,T=(U,TE)是G的最小生成树,U=V,TE初值为空。
- 将图G中的边按权值从小到大依次选取,若选取的边使生成树不形成回路,则把它并入TE中,若形成回路则将其舍弃,直到TE中包含N-1条边为止,此时T为最小生成树。
关键问题
- 如何判断欲加入的一条边是否与生成树中边构成回路。
- 将各顶点划分为所属集合的方法来解决,每个集合的表示一个无回路的子集。开始时边集为空,N个顶点分属N个集合,每个集合只有一个顶点,表示顶点之间互不联通。
- 当从边集中按顺序选取一条边时,若它的两个端点分属于不同的集合,则表明此边连通了两个的部分,因每个部分连通无回路,故连通后 仍不会产生回路,此边保留,同时把相应两个集合合并。
参考Agri-Net
Description
Farmer John has been elected mayor of his town! One of his campaign promises was to bring internet connectivity to all farms in the area. He needs your help, of course.
Farmer John ordered a high speed connection for his farm and is going to share his connectivity with the other farmers. To minimize cost, he wants to lay the minimum amount of optical fiber to connect his farm to all the other farms.
Given a list of how much fiber it takes to connect each pair of farms, you must find the minimum amount of fiber needed to connect them all together. Each farm must connect to some other farm such that a packet can flow from any one farm to any other farm.
The distance between any two farms will not exceed 100,000.
Input
The input includes several cases. For each case, the first line contains the number of farms, N (3 <= N <= 100). The following lines contain the N x N conectivity matrix, where each element shows the distance from on farm to another. Logically, they are N lines of N space-separated integers. Physically, they are limited in length to 80 characters, so some lines continue onto others. Of course, the diagonal will be 0, since the distance from farm i to itself is not interesting for this problem.
Output
For each case, output a single integer length that is the sum of the minimum length of fiber required to connect the entire set of farms.
Sample Input
4
0 4 9 21
4 0 8 17
9 8 0 16
21 17 16 0
Sample Output
28
Procedure
1 | /* |
Kruskal和Prim比较
Kruskal:将所有边从小到大加入,在此过程中判断是否构成回路
- 使用数据结构:并查集
- 时间复杂度:$O(ElogE)$
- 适用于稀疏图
Prim:从任一节点出发,不断扩展
- 使用数据结构:堆
- 时间复杂度:$O(ElogV)$或$O(VlogV+E)$(斐波那契堆)
- 适用于密集图
- 若不用堆则时间复杂度为$O(V^2)$
第十一章 最短路径
Dijkstra算法
基本思想
- 解决无负权边的带权有向图或无向图的单源最短路问题
- 贪心思想,若离源点s前k-1近的点已经被确定,构成点集P,那么从s到离s第k近的点t的最短路径,${s,p_1,p_2,…,p_i,t}$,满足$s,p_1,p_2,…,p_i∈P$
- 否则假设$p_i∉P$,则因为边权非负,$p_i$到t的路径≥0,则$d[p_i]≤d[t]$,$p_i$才是第k近。将$p_i$看作t,重复上面过程,最终一定会有找不到$p_i$的情况。
- $d[i] = min(d[p_i] + cost(p_i,i)),i∉P,p_i∈P$
$d[t] = min(d[i]),i∉P$ - 初始令$d[s]=0,d[i]=+∞,P=∅$
- 找到点$i∉P$,且$d[i]$最小
- 把i添入P,对于任意$j∉P$,若$d[i]+cost(i,j)<d[j]$,则更新$d[j]=d[i]+cost(i,j)$。
- 用邻接表,不优化,时间复杂度$O(V^2+E)$
- Dijkstra+堆的时间复杂度$O(ElogV)$
- 用斐波那契堆可以做到$O(VlogV+E)$
- 若要输出路径,则设置prev数组记录每个节点的前驱点,在$d[i]$更新时更新$prev[i]$。
- Dijkstra算法也适用于无向图,但不适用于有负权边的图。
算法实现
- 已经求出到$v_0$点的最短路的点的集合为T
- 维护Dist数组,Dist[i]表示目前$v_i$到$v_0$的“距离”
- 开始Dist[0]=0,其他Dist[i]=∞,T为空集
- ①若|T|=N,算法完成,Dist数组就是解。否则取Dist[i]最小的不在T中的点$V_i$,将其加入T,Dist[i]就是$v_i$到$v_0$的最短路长度。
- ②更新所有与$v_i$有边相连且不在T中的点$v_j$的Dist值:
$Dist[j]=min(Dist[j],Dist[i]+W(v_i,v_j))$ - ③转到①
Candies
Description
During the kindergarten days, flymouse was the monitor of his class. Occasionally the head-teacher brought the kids of flymouse’s class a large bag of candies and had flymouse distribute them. All the kids loved candies very much and often compared the numbers of candies they got with others. A kid A could had the idea that though it might be the case that another kid B was better than him in some aspect and therefore had a reason for deserving more candies than he did, he should never get a certain number of candies fewer than B did no matter how many candies he actually got, otherwise he would feel dissatisfied and go to the head-teacher to complain about flymouse’s biased distribution.
snoopy shared class with flymouse at that time. flymouse always compared the number of his candies with that of snoopy’s. He wanted to make the difference between the numbers as large as possible while keeping every kid satisfied. Now he had just got another bag of candies from the head-teacher, what was the largest difference he could make out of it?
Input
The input contains a single test cases. The test cases starts with a line with two integers N and M not exceeding 30 000 and 150 000 respectively. N is the number of kids in the class and the kids were numbered 1 through N. snoopy and flymouse were always numbered 1 and N. Then follow M lines each holding three integers A, B and c in order, meaning that kid A believed that kid B should never get over c candies more than he did.
Output
Output one line with only the largest difference desired. The difference is guaranteed to be finite.
Sample Input
2 2
1 2 5
2 1 4
Sample Output
5
Procedure
参考
1 | /* |
1 |
|
1 | //超时!对于稠密图,SPFA的效率果然降低了,我是不是得去考虑学SPFA的两个优化啊。 |
Bellman-Ford 算法
基本思想
- 解决含负权边的带权有向图的单源最短路径问题
- 不能处理带负权边的无向图(因可以来回走一条负权边)
- 限制条件:要求图中不能包含权值总和为负值回路(负权值回路),如图所示。
- 构造一个最短路径长度数组序列$dist^{1}[u],dist^{2}[u],…,dist^{n-1}[u]$(u=0,1,…,n-1,n为点数)
①$dist^{1}[u]$为从源点v到终点u的只经过一条边的最短路径长度,并有dist^{1}[u]=Edge[v][u];
②$dist^{2}[u]$为从源点v最多经过两条边到达终点u的最短路径长度;
③$dist^{3}[u]$位从源点v出发最多经过不构成负权值回路的三条边到达终点u的最短路径长度;
……
④$dist^{n-1}[u]$为从源点v出发最多经过不构成负权值回路的n-1条边到达终点u的最短路径长度。 - 算法最终的目的是计算出$dist^{n-1}[u]$,为源点v到顶点u的最短路径长度。
$dist^{k}[u]$的计算
- 设已经求出了$dist^{k-1}[u],u=0,1,…,n-1,$即从源点v经过最多不构成负权值回路的k-1条边到达终点u的最短路径的长度
- 递推公式(求顶点u到源点v的最短路径):
$dist^{1}[u]=Edge[v][u]$
$dist^{k}[u]=min${$dist^{k-1}[u]$}$,min${$dist^{k-1}[j]+Edge[j][u]$}$,j=0,1,…,n-1,j≠u$
Dijkstra算法与Bellman-Ford算法的区别
- Dijkstra算法和Bellman算法思想有很大的区别:
①Dijkstra算法在求解过程中,源点到集合S内各顶点的最短路径一旦求出,则之后不变了,修改的仅仅是源点到S外各顶点的最短路径长度。
②Bellman-Ford算法在求解过程中,每次循环都要修改所有顶点的$dist[]$,也就是说源点到各顶点最短路径长度一直要到算法结束才确定下来。
负权回路的判断
- 如果存在从源点可达的负权值回路,则最短路径不存在,因为可以重复走这个回路,使得路径长度无穷小。
- 思路:在求出$dist^{n-1}[]$之后,再对每条边$<u,k>$判断一下:加入这条边是否会使得顶点k的最短路径值再缩短,即判断:$dist[u]+w(u,k)<dist[k]$是否成立,如果成立,则说明存在从源点可达的负权值回路。
证明: - 如果成立,则说明找到了一条经过了n条边的从s到k的路径,且其比任何少于n条边的从s到k的路径都短。
- 一共n个顶点,路径却经过了n条边,则必有一个顶点m经过了至少两次。则m是一个回路的起点和终点。走这个回路比不走这个回路路径更短,只能说明这个回路是负权回路。
参考Wormholes
Description
While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.
As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .
To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.
Input
Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.
Output
Lines 1..F: For each farm, output “YES” if FJ can achieve his goal, otherwise output “NO” (do not include the quotes).
Sample Input
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
Sample Output
NO
YES
Procedure
1 | /* |
算法复杂度分析
- 假设图的顶点个数为n,边的个数为e
①使用邻接表存储图,复杂度$O(N*E)$
②使用邻接矩阵存储图,复杂度为$O(N^3)$算法改进
- Bellman-Ford算法不一定要循环n-1次,n为顶点个数
- 只要在某次循环过程中,考虑每条边后,源点到所有顶点的最短路径长度都没有变,那么Bellman-Ford算法就可以提前结束了,同冒泡排序的方法相同
SPFA(Shortest Path Faster Algorithm)算法
基本思想
- 快速求解含负权边的带权有向图的单源最短路径问题
- 是Bellman-Ford算法的改进版,利用队列动态更新$Dist[]$
- 维护一个队列,里面存放所有需要进行迭代的点。初始时队列中只有一个源点S,用一个布尔数组记录每个点是否处在队列中。
- 每次迭代,取出队头的点v,依次枚举从v出发的边$v->u$,若$Dist[v]+len(v->u)<Dist[u]$,则更新$Dist[u]$(可同时将u前驱记为v)。此时由于S到u的最短距离变小了,有可能u可以更新其他的点,所以若u不在队列中,就将它放入队尾。这样一直迭代下去直到队列变空,也就是S到所有节点的最短距离都确定下来,结束算法。若一个点最短路被改进的 次数达到n,则有负权环(原因同B-F算法)。可以用SPFA算法判断图有无负权环。
- 在平均情况下,SPFA算法的期望时间复杂度为$O(E)$。
- 类似BFS,但与之不同的是,同一个点可以反复加入和退出队列。
- BFS版不太稳定,对于稠密图,效率降低。
- 这里需要说明的是,标记数组用来标记是否在队列中,如果已经在队列中,那么不用重复添加,因为这里队列记录的是点,而不是整个状态Edge,所以在对Dist[]更新的时候在队列中的点的Dist[]已经是当前最小值了!这里举个例子,1->2,2->3,2->5,3->5,… 从2扩展3,5,然后从3更新Dist[5],这里假设1->2->5的路径比1->2->3->5路径长,那么此时5在队列中,并且Dist[5]已经由前一个较长路径值更新至较短路径值,对于5的后继更新而言无影响,因为后继的更新时在5的当前最短路径基础上进行更新松弛的;同理Dist[5]更新且不在队列中,则必须加入队列。(从小打到扩展)
参考Wormholes
Description
While exploring his many farms, Farmer John has discovered a number of amazing wormholes. A wormhole is very peculiar because it is a one-way path that delivers you to its destination at a time that is BEFORE you entered the wormhole! Each of FJ’s farms comprises N (1 ≤ N ≤ 500) fields conveniently numbered 1..N, M (1 ≤ M ≤ 2500) paths, and W (1 ≤ W ≤ 200) wormholes.
As FJ is an avid time-traveling fan, he wants to do the following: start at some field, travel through some paths and wormholes, and return to the starting field a time before his initial departure. Perhaps he will be able to meet himself :) .
To help FJ find out whether this is possible or not, he will supply you with complete maps to F (1 ≤ F ≤ 5) of his farms. No paths will take longer than 10,000 seconds to travel and no wormhole can bring FJ back in time by more than 10,000 seconds.
Input
Line 1: A single integer, F. F farm descriptions follow.
Line 1 of each farm: Three space-separated integers respectively: N, M, and W
Lines 2..M+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: a bidirectional path between S and E that requires T seconds to traverse. Two fields might be connected by more than one path.
Lines M+2..M+W+1 of each farm: Three space-separated numbers (S, E, T) that describe, respectively: A one way path from S to E that also moves the traveler back T seconds.
Output
Lines 1..F: For each farm, output “YES” if FJ can achieve his goal, otherwise output “NO” (do not include the quotes).
Sample Input
2
3 3 1
1 2 2
1 3 4
2 3 1
3 1 3
3 2 1
1 2 3
2 3 4
3 1 8
Sample Output
NO
YES
Procedure
1 | /* |
SPFA算法有两个优化算法 SLF 和 LLL
SLF:Small Label First 策略,设要加入的节点是j,队首元素为i,若dist(j) < dist(i),则将j插入队首,否则插入队尾。
LLL:Large Label Last 策略,设队首元素为i,每次弹出时进行判断,队列中所有dist值的平均值为x,若dist(i)>x则将i插入到队尾,查找下一元素,直到找到某一i使得dist(i)<=x,则将i出对进行松弛操作。
第十二章 强连通分量
定义
- 在有向图G中,如果任意两个不同的顶点相互可达,则称该有向图是强连通的。
- 有向图G的极大强连通子图称为G的强连通分支。
有向图强连通分支的Tarjan算法
- 做一遍DFS,用dfn[i]表示编号为i的节点在DFS过程中的访问序号(也可以做开始时间)。
- 在DFS过程中会形成一搜索树。
- 在搜索树上越先遍历到的节点,显然dfn的值就越小。
- dfc值越小的节点,就称为越“早”。
- 用low[i]表示从i节点出发DFS过程中i下方节点(开始时间大于dfn[i]。且由i可达的节点)所能到达的最早的节点的开始时间。初始时low[i]=dfn[i]
- DFS过程中,碰到哪个节点,就将哪个节点入栈。栈中节点只有在其所属的强连通分量已经全部求出时,才会出栈。
- 如果发现某节点u有边连到栈里的节点v,则更新u的low值为min(low[u],dfn[v]),若low[u]被更新未dfn[v],则表明目前发现u可达的最早的节点是v.
- 对于u的子节点v,从v出发进行的DFS结束回到u时,使得low[u]=min(low[u],low[v])。因为u可达v,所以v可达的最早的节点,也是u可达的。
- 如果一个节点u,从其出发进行的DFS已经全部完成并回到u,而且此时其low值等于dfn值,则说明u可达的所有节点,都不能到达任何比u早的节点——那么该节点u就是一个强连通分量在DFS搜索树中的根。
- 此时,显然栈中u上方的节点,都是不能到达比u早的节点的。将栈中节点弹出,一直弹到u(包括u),弹出的节点就构成一个强连通分量。