信息学奥赛NOIP分治

分治动态规划无后效性、最优子结构优化：时间复杂度、空间复杂度、编程复杂度空间复杂度的优化一般用滚动数组即可对于初等的dp优化，其对编程复杂度影响不大。有一些单调性优化，需要用到平衡树、凸包等知识，NOIP不作要求。动态规划无后效性、最优子结构优化：时间复杂度、空间复杂度、编程复杂度空间复杂度的优化一般用滚动数组即可对于初等的dp优化，其对编程复杂度影响不大。有一些单调性优化，需要用到平衡树、凸包等知识，NOIP不作要求。寻找假币（NOIP2006普及组）现有80枚硬币，其中有一枚是假币，其重量稍轻，所有真币的重量都相同，如果使用不带砝码的天平称重，最少需要称几次，就可以找出假币？你还要指出第1次的称重方法。请写出你的结果：_________________________。进制转换将一个十进制正整数化为二进制数并输出。辗转相除法求最大公约数设gcd(m,n)表示m,n的最大公约数m(n==0)gcd(m,n)=gcd(n,m%n)(n!=0)mnr=m%n24204204040不难发现，辗转相除法是一种将问题规模不断缩小的解题方法，要求m,n的最大公约数，其实就是求n与m%n的最大公约数。汉诺塔有三根柱子起始柱A,中间柱B,目标柱C，起初A柱上有n个碟子。要求将所有碟子从A柱移到C柱上。规定：每次移动一个碟子,移动时只能将小的碟子叠在大的碟子上面。请输出移动方案。ABCABC1汉诺塔如果起始柱A上只有一个碟子，则直接将其从A柱移到C柱，结束。ABC21汉诺塔第一步：将盘【1】移到B柱第二步：将盘【2】直接移到C柱第三步：将盘【1】移到C柱ABC321汉诺塔第一步：将盘【1,2】移到B柱ABC321汉诺塔第二步：将盘【3】直接移到C柱第一步：将盘【1,2】移到B柱ABC321汉诺塔第三步：将盘【1,2】移到C柱第二步：将盘【3】直接移到C柱第一步：将盘【1,2】移到B柱递归边界：如果起始柱A上只剩一个碟子，则直接将其移到C柱，递归结束。汉诺塔汉诺塔2.否则，如果起始柱A上有n个碟子，则（1）先把最上面的n-1个碟子从A柱通过C柱移到B柱；（2）然后把第n个碟子从A柱直接移到C柱；（3）最后再把B柱上的n-1个碟子通过A柱移到C柱。算算看：总共需要移动几次？分治思想重温经典：1、快速排序、归并排序等2、二分查找分治法的基本思想：分：将原问题分解为若干个规模更小但结构与原问题相似的子问题；治：递归地解这些子问题；合：然后将这些子问题的解组合为原问题的解。快速排序（原地排序）快速排序是信息学竞赛的必备算法之一。C++选手请不要一上来就试图使用STL，虽然你可以使用sort一遍过，但是你并没有掌握快速排序算法的精髓。sort(a,a+10)数组下标范围为[0,10)，默认为升序boolcmp(inta,intb){returnab;}sort(a,a+10,cmp);//降序排列对所有序列快速排序合并治快速排序0123446451ikji从左往右扫，找到第一个不小于基准数的数选取一个基准值（中间、第一个、最后一个，随机）j从右往左扫，找到第一个不大于基准数的数如果i=j，则交换a[i]，a[j],i++,j--lftrgt如果i=j1446左侧元素=基准值右侧元素=基准值分快速排序0123446451ikj对左区间[lft,j]递归操作lftrgt1446治快速排序0123446451ikj对右区间[i,rgt]递归操作lftrgt1446465治归并排序:异地排序归并排序的基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。mergesort一分为二归并排序:异地排序voidmergesort(intlft,intrgt){//coutlftrgtendl;if(lefrig){intmid=(lft+rgt)/2;mergesort(lft,mid);mergesort(mid+1,rgt);}}思考：序列是如何被递归分解的？merge合二为一485745781326123612345678快速排序&归并排序归并排序和快速排序都运用了分治策略，归并排序分解方法十分简单，只需将原数列一分为二即可，但合并时需要调用merge函数合并（异地排序），而快速排序分解相对困难，但合并十分简单（原地排序）。这是归并排序和快速排序的不同。二分查找二分查找也称折半查找（BinarySearch），它是一种效率较高的查找方法。但要求元素有序。查找key时，每次和中间数比较，如果相等，则直接返回mid；如果key小于mid，查找mid左侧的部分；如果key大于mid，则查找mid右侧的部分。抽奖(lottery2，1S，256MB)【问题描述】公司举办聚会，为了活跃气氛，设置了摇奖环节，参加聚会的每位员工都有一张抽奖券。现按由小到大的顺序依次公布的n个不同的获奖号码和某张抽奖券上的号码win，如win号码为获奖号码则输出公布的次序，如不是获奖输出0。【输入格式】包括三行数据。第一行包含1个正整数n，表示有n个获奖号码。第二行包含n个用空格隔开的正整数，表示依次公布的n个获奖号码。第三行包含1个正整数win，表示某张抽奖券上的号码。抽奖(lottery2，1S，256MB)【输出格式】一行，包含1个整数，如找到该获奖号码公布的顺序，0表示没有中奖。【输入样例】7123461795553【输出样例】3【数据规模】对于100%的数据满足：2＜n≤100，1≤num＜10000。跳石头题目描述一年一度的“跳石头”比赛又要开始了!这项比赛将在一条笔直的河道中进行,河道中分布着一些巨大岩石。组委会已经选择好了两块岩石作为比赛起点和终点。在起点和终点之间,有N块岩石(不含起点和终点的岩石)。在比赛过程中,选手们将从起点出发,每一步跳向相邻的岩石,直至到达终点。为了提高比赛难度,组委会计划移走一些岩石,使得选手们在比赛过程中的最短跳跃距离尽可能长。由于预算限制,组委会至多从起点和终点之间移走M块岩石(不能移走起点和终点的岩石)。输入格式：输入文件名为stone.in。跳石头输入文件第一行包含三个整数L,N,M,分别表示起点到终点的距离,起点和终点之间的岩石数,以及组委会至多移走的岩石数。接下来N行,每行一个整数,第i行的整数Di(0DiL)表示第i块岩石与起点的距离。这些岩石按与起点距离从小到大的顺序给出,且不会有两个岩石出现在同一个位置。输出格式：输出文件名为stone.out。输出文件只包含一个整数,即最短跳跃距离的最大值。输入输出样例跳石头输入样例1：2552211141721输出样例1：4跳石头说明输入输出样例1说明：将与起点距离为2和14的两个岩石移走后,最短的跳跃距离为4(从与起点距离17的岩石跳到距离21的岩石,或者从距离21的岩石跳到终点)。另：对于20%的数据,0≤M≤N≤10。对于50%的数据,0≤M≤N≤100。对于100%的数据,0≤M≤N≤50,000,1≤L≤1,000,000,000。