《算法分析与设计课件：习题选讲1bywxyz》由会员分享，可在线阅读，更多相关《算法分析与设计课件：习题选讲1bywxyz（34页珍藏版）》请在金锄头文库上搜索。
1、算法分析习题选讲算法分析习题选讲nSicily 地址地址: http:/soj.me2012-9-202题目题目n1020 Big Integern1021 Couplen1027 MJ, Nowhere to Hiden1035 DNA matchingn1046 Plane Spottingn1051 Bikers Trip Odometen1198 Substringn1176 Two Endsn1433 Optimal Parkingn1325 Digit Generator2012-9-2031020 Big Integern题目大意：题目大意：n给给出出n个个整整数数b1,b2,.
2、,bn，和和一一个个大大整整数数x，求，求x对每个数对每个数bi取模的结果。取模的结果。nn=100, 1bi=1000, x的长度不超过的长度不超过400。2012-9-2041020 Big Integer n解题思路：解题思路：n对对bi逐个计算；逐个计算；n高精度，模拟竖式计算。高精度，模拟竖式计算。nint div(char x, int b) nint a=0;nfor (int i=0;xi!=0;i+) na=(a*10+xi-0)%b;nreturn a;n2012-9-2051021 Couplen题目大意：题目大意：nN对夫妇站成一圈对夫妇站成一圈n如果某对夫妇站在相邻位
3、置，则从圈中移走如果某对夫妇站在相邻位置，则从圈中移走n重复以上操作重复以上操作n问最后会不会没人问最后会不会没人n如如1 3是一对，是一对，2 4是一对，则是一对，则Non如如1 4是一对，是一对，2 3是一对，则是一对，则Yesn1=N=100,0002012-9-2061021 Couplen解题思路：解题思路：n类似于括号匹配，可将类似于括号匹配，可将n对夫妇看成对夫妇看成n种括种括号号n用一个栈来模拟，将括号逐个用一个栈来模拟，将括号逐个push到栈里到栈里n当栈顶存在匹配对时进行当栈顶存在匹配对时进行pop操作操作n看最后栈是否为空看最后栈是否为空2012-9-2071021 Co
4、uple如1 3是一对，2 4是一对112123最后栈不为空，输出No14232012-9-2081021 Couple如1 4是一对，2 3是一对112123114最后栈为空，输出Yes2012-9-2091021 Couplenstack s;nfor (int i=1;i=2*n;i+) nif (!s.empty()&s.top()=couplei)ns.pop();nelsens.push(i);n2012-9-20101027 MJ, Nowhere to Hiden题目大意：题目大意：n给出给出N对对BBS_ID IP_Address，求出，求出IP_Address相同的相同的B
5、BS_ID。nN=202012-9-20111027 MJ, Nowhere to Hiden解题思路：解题思路：n枚举每两个枚举每两个BBS_ID IP_Address对，比较对，比较IP_Address是否相同；是否相同；n字符串比较。字符串比较。nfor (int i=0;in;i+) n for (int j=i;jn;j+)n if (strcmp(ipi,ipj)=0)n anscnt+=make_pair(idi,idj);n2012-9-20121035 DNA matchingn题目大意：题目大意：n给出给出n个个DNA单链，问可以用这些单链，问可以用这些DNA单链组成单链组
6、成多少个多少个DNA双链；双链；n每个每个DNA单链最多使用一次；单链最多使用一次；n两个两个DNA单链能组成单链能组成DNA双链，当且仅当两个双链，当且仅当两个DNA单链的长度相等，且对应位置上能配对，单链的长度相等，且对应位置上能配对，A与与T配对，配对，C与与G配对；配对；nn=100, 每个单链长度不超过每个单链长度不超过100。2012-9-20131035 DNA matchingn解题思路：解题思路：n枚举每个没有被匹配的枚举每个没有被匹配的DNA单链，再枚举另外一个没有被单链，再枚举另外一个没有被匹配的匹配的DNA单链，如果它们能匹配，则都标记为匹配，答单链，如果它们能匹配，则
7、都标记为匹配，答案加一。案加一。nfor (i = 0; i N; i+) if (!vsti)nfor (j = i + 1; j N; j+) if (!vstj) nif (match(DNAi, DNAj) nans+;nvsti = vstj = true;nbreak;nn2012-9-20141046 Plane Spottingn题目大意：题目大意：n给出一个长度为给出一个长度为N的非负整数序列（所有数不超的非负整数序列（所有数不超过过200），还有两个整数），还有两个整数M和和K，求前，求前M个最优的个最优的长度不小于长度不小于K的连续子序列。的连续子序列。n连续子序列的优先
8、级如何比较连续子序列的优先级如何比较1、平均值大的序列优于平均值小的、平均值大的序列优于平均值小的2、条件、条件1相同情况下，长度大的序列优于长度小的相同情况下，长度大的序列优于长度小的3、条件、条件1和和2相同情况下，结束位置靠前的序列优于结相同情况下，结束位置靠前的序列优于结束位置靠后的束位置靠后的n1N300，1M100，1K3002012-9-20151046 Plane Spottingn解题思路：解题思路：n使用结构体表示一个子序列，重写比较操作使用结构体表示一个子序列，重写比较操作“”。n对所有可能的子序列进行排序。对所有可能的子序列进行排序。nstruct period ndo
9、uble aver;nint length,ends;n;nbool operator 1e-6) return a.averb.aver;nif (a.length!=b.length) return a.lengthb.length;nreturn a.endsb.ends;n2012-9-20161046 Plane Spottingnfor (i=0;in;i+) ntemp=0;nfor (j=i+1;j=k) npcnt.length=j-i+1;npcnt.ends=j+1;npcnt.aver=(double)temp/(j-i+1);ncnt+;nnnnsort(p,p+cn
10、t);2012-9-20171051 Bikers Trip Odometen题目大意：题目大意：n给出车前轮的直径，转圈数以及时间，求给出车前轮的直径，转圈数以及时间，求出车行走的路程和平均速度。出车行走的路程和平均速度。2012-9-20181051 Bikers Trip Odometen解题思路：解题思路：n车轮周长车轮周长 = 直径直径 圆周率圆周率n路程路程 = 周长周长 转圈数转圈数n平均速度平均速度 = 路程路程 / 时间时间2012-9-20191198 Substringn题目大意：题目大意：n用用N个字符串拼成一个新的字符串个字符串拼成一个新的字符串n要求新字符串字典序最
11、小要求新字符串字典序最小n如：如： a ab acn则答案为：则答案为：aabacn1=N=8,每个字符串长度不超过每个字符串长度不超过1002012-9-20201198 Substringn解题思路：解题思路：n枚举枚举n!种情况，最多为种情况，最多为8!=40320种情况；种情况；n每枚举一种情况，与当前字典序最小字符每枚举一种情况，与当前字典序最小字符串比较，如果字典序更小，则更新答案；串比较，如果字典序更小，则更新答案；n递归求解。递归求解。n反例反例 ba bnbab bba2012-9-20211198 Substringnvoid dfs(char now,int lev) n
12、if (lev=n) nupdate(now);nreturn;nnchar now2850;nfor (int i=0;in;i+) if (!usedi) nstrcpy(now2,now);nstrcat(now2,si);nusedi=true;ndfs(now2,lev+1);nusedi=false;nn2012-9-20221176 Two Endsn题目大意：题目大意：n给出给出n个正整数排成一列，个正整数排成一列，A和和B轮流取数，只能轮流取数，只能取两端的数，最后取到的数的和较大的人胜利，取两端的数，最后取到的数的和较大的人胜利，A和和B之间的差为分值；之间的差为分值；nA
13、可以自由选择策略，可以自由选择策略，B的贪心策略取两端中较大的贪心策略取两端中较大的数，如果相等则取左边的数；的数，如果相等则取左边的数；n问问A赢赢B的分值最大为多少。的分值最大为多少。nn=1000,且且n为偶数。为偶数。2012-9-20231176 Two Endsn解题思路：解题思路：nA尝试计算所有情况，并选出自己得分最多尝试计算所有情况，并选出自己得分最多的情况；的情况；n计算所有情况时，减少重复计算（动态规计算所有情况时，减少重复计算（动态规划），每个状态为当前数列的左右端点位划），每个状态为当前数列的左右端点位置。置。2012-9-20241176 Two Endsnint
14、cal(int left,int right) n if (right left) return 0;n if (is_calleftright) return ansleftright;n int ans_left = arrleft;n if(arrleft+1arrright) ans_left += cal(left+1,right-1);n else ans_left += cal(left+2,right);n int ans_right = arrright;n if (arrleftarrright-1) ans_right += cal(left,right-2);n els
15、e ans_right += cal(left+1,right-1);n is_calleftright = true;n return ansleftright = max(ans_left,ans_right);n2012-9-20251433 Optimal Parkingn题目大意：题目大意：nn个商店排在一条街上，每个商店各有一个位置。个商店排在一条街上，每个商店各有一个位置。n要求在街上找出一个整数表示的位置，需要从这要求在街上找出一个整数表示的位置，需要从这个位置出发经过所有商店最后回到出发位置的最个位置出发经过所有商店最后回到出发位置的最短路程。短路程。nn不超过不超过20，商
16、店位置用，商店位置用0到到99之间的整数表示。之间的整数表示。2012-9-20261433 Optimal Parkingn解题思路：解题思路：n把街看作数轴，各个位置看作数轴上的点。把街看作数轴，各个位置看作数轴上的点。n首先想到，在选定一个位置后，必定是从这个位首先想到，在选定一个位置后，必定是从这个位置开始向数轴负方向走，到达最小位置的商店，置开始向数轴负方向走，到达最小位置的商店，再向数轴正方向走，到达最大位置的商店，再回再向数轴正方向走，到达最大位置的商店，再回到出发点。到出发点。n普通方法：枚举每个点作为出发位置，计算所有普通方法：枚举每个点作为出发位置，计算所有位置的路程，取最
17、小值。位置的路程，取最小值。2012-9-20271433 Optimal Parkingn更好的方法：其实只要出发点在最小值的更好的方法：其实只要出发点在最小值的点与最大值的点之间，则路程是固定的，点与最大值的点之间，则路程是固定的，为为(max-min)*2。2012-9-20281433 Optimal Parkingnint cal(int x,int n)nnmax=-1;nmin=101;nfor (i=0;imax)nmax=xi;nif (ximin)nmin=xi;nnreturn (max-min)*2;n2012-9-20291325 Digit Generatorn题目
18、大意：题目大意：n对于一个整数对于一个整数N，定义，定义N的的digit-sum:ndigit-sum = N + （N的各位数字）。的各位数字）。n如果如果M是是N的的digit-sum，则称，则称N为为M的的generator。n例如，例如，245的的digit-sum是是256 (= 245 + 2 + 4 + 5).因此，因此，245是是256的的generator。n但有些数有多个但有些数有多个generator，例如，例如216的的generator可以是可以是198，也可以是，也可以是207。n问：给定一个问：给定一个N (1 = N = 100000), 求求N的最小的最小ge
19、nerator，如果，如果N没有没有generator则输出则输出0。2012-9-20301325 Digit Generatorn解题思路：解题思路：n枚举。枚举。n给出一个给出一个N，则按顺序枚举从，则按顺序枚举从1到到N的所有的所有整数，直到找到整数，直到找到N的一个的一个generator，或全，或全部数都不是部数都不是N的的generator。2012-9-20311325 Digit Generatorn更快的方法：更快的方法：n注意到注意到1 = N = 100000，在这些数中，在这些数中，各个数字之和最大为各个数字之和最大为99999的的45，因此，因此N的的generator必定在必定在N-45到到N-1之间，枚举范之间，枚举范围大大减少。围大大减少。2012-9-20321325 Digit Generatornint generator(int n) nint i,j,k;nfor (k=n-45;k0) nj+=i%10;ni/=10;nnif (j+k=n)nreturn k;nnreturn 0;n2012-9-2033谢谢！谢谢！2012-9-2034
