算法分析习题选讲2

习题选讲2011-10-082第一章nSicily 地址:http:/soj.men1020 Big Integern1021 Couplen1027 MJ,Nowhere to Hiden1035 DNA matchingn1046 Plane Spottingn1051 Bikers Trip Odometen1198 Substringn1176 Two Ends2011-10-0831020 Big Integern题目大意：n给出n个整数b1,b2,.,bn，和一个大整数x，求x对每个数bi取模的结果。nn=100,1bi=1000,x的长度不超过400。2011-10-0841020 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;n2011-10-0851021 Couplen题目大意：nN对夫妇站成一圈n如果某对夫妇站在相邻位置，则从圈中移走n重复以上操作n问最后会不会没人n如1 3是一对，2 4是一对，则Non如1 4是一对，2 3是一对，则Yesn1=N=100,0002011-10-0861021 Couplen解题思路：n类似于括号匹配，可将n对夫妇看成n种括号n用一个栈来模拟，将括号逐个push到栈里n当栈顶存在匹配对时进行pop操作n看最后栈是否为空2011-10-0871021 Couple如1 3是一对，2 4是一对112123最后栈不为空，输出No14232011-10-0881021 Couple如1 4是一对，2 3是一对112123114最后栈为空，输出Yes2011-10-0891021 Couplenstack s;nfor(int i=1;i=2*n;i+)nif(!s.empty()&s.top()=couplei)ns.pop();nelsens.push(i);n2011-10-08101027 MJ,Nowhere to Hiden题目大意：n给出N对BBS_ID IP_Address，求出IP_Address相同的BBS_ID。nN=202011-10-08111027 MJ,Nowhere to Hiden解题思路：n枚举每两个BBS_ID IP_Address对，比较IP_Address是否相同；n字符串比较。nfor(int i=0;in;i+)nfor(int j=i;jn;j+)nif(strcmp(ipi,ipj)=0)nanscnt+=make_pair(idi,idj);n2011-10-08121035 DNA matchingn题目大意：n给出n个DNA单链，问可以用这些DNA单链组成多少个DNA双链；n每个DNA单链最多使用一次；n两个DNA单链能组成DNA双链，当且仅当两个DNA单链的长度相等，且对应位置上能配对，A与T配对，C与G配对；nn=100,每个单链长度不超过100。2011-10-08131035 DNA matchingn解题思路：n枚举每个没有被匹配的DNA单链，再枚举另外一个没有被匹配的DNA单链，如果它们能匹配，则都标记为匹配，答案加一。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;nn2011-10-08141046 Plane Spottingn题目大意：n给出一个长度为N的非负整数序列（所有数不超过200），还有两个整数M和K，求前M个最优的长度不小于K的连续子序列。n连续子序列的优先级如何比较1、平均值大的序列优于平均值小的2、条件1相同情况下，长度大的序列优于长度小的3、条件1和2相同情况下，结束位置靠前的序列优于结束位置靠后的n1N300，1M100，1K3002011-10-08151046 Plane Spottingn解题思路：n使用结构体表示一个子序列，重写比较操作“”。n对所有可能的子序列进行排序。nstruct period ndouble 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;n2011-10-08161046 Plane Spottingnfor(i=0;in;i+)ntemp=0;nfor(j=i;j=m)npcnt.length=j-i+1;npcnt.ends=j+1;npcnt.aver=(double)temp/(j-i+1);ncnt+;nnnnsort(p,p+cnt);2011-10-08171051 Bikers Trip Odometen题目大意：n给出车前轮的直径，转圈数以及时间，求出车行走的路程和平均速度。2011-10-08181051 Bikers Trip Odometen解题思路：n车轮周长=直径 圆周率n路程=周长 转圈数n平均速度=路程/时间2011-10-08191198 Substringn题目大意：n用N个字符串拼成一个新的字符串n要求新字符串字典序最小n如：a ab acn则答案为：aabacn1=N=8,每个字符串长度不超过1002011-10-08201198 Substringn解题思路：n枚举n!种情况，最多为8!=40320种情况；n每枚举一种情况，与当前字典序最小字符串比较，如果字典序更小，则更新答案；n递归求解。2011-10-08211198 Substringnvoid dfs(char now,int lev)nif(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;nn2011-10-08221176 Two Endsn题目大意：n给出n个正整数排成一列，A和B轮流取数，只能取两端的数，最后取到的数的和较大的人胜利，A和B之间的差为分值；nA可以自由选择策略，B的贪心策略取两端中较大的数，如果相等则取左边的数；n问A赢B的分值最大为多少。nn=1000,且n为偶数。2011-10-08231176 Two Endsn解题思路：nA尝试计算所有情况，并选出自己得分最多的情况；n计算所有情况时，减少重复计算（动态规划），每个状态为当前数列的左右端点位置。2011-10-08241176 Two Endsnint 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+1 arrright)ans_left+=cal(left+1,right-1);n else ans_left+=cal(left+2,right);n int ans_right=arrright;n if(arrleft arrright-1)ans_right+=cal(left,right-2);n else ans_right+=cal(left+1,right-1);n is_calleftright=true;n return ansleftright=max(ans_left,ans_right);n2011-10-0825第二章n1150 1151 1515 魔板n1007 To and Fron1036 Crypto Columnsn1006 Team Rankingsn1009 Mersenne Composite Nn1050 Numbers&Lettersn1443 Printer Queuen1156 Binary treen1063 Whos the Bossn1024 Magic Island2011-10-0826如1150，初始状态如右图，三种基本操作分别是：A.上下两行互换B.每行循环右移一格C.中间四块顺时针转一格1150 1151 1515 魔板n题目大意：n给出魔板的起始状态，并给定三种基本操作，给出一个步数上限和目标状态，求从起始状态到目标状态的操作序列，长度不得超过上限。2011-10-08271150 1151 1515 魔板n解题思路：n对模板进行状态搜索；n由一种状态可以转移到另外三种状态，搜索树为一棵三叉树；n在这棵三叉树上搜索，目的是求出最优解。2011-10-08281150 1151 1515 魔板n算法一：盲目DFSn对这棵三叉树进行DFSn若想求得最优解，需要遍历整棵树n需要进行重复扩展n优化：n若已找到一个可行解，可剪去大于等于这个深度的所有子树n勉强可过1150。2011-10-08291150 1151 1515 魔板n算法二：BFSn对这棵三叉树进行BFSn第一个可行解即是最优解n可以过1150，但过不了1151。2011-10-08301150 1151 1515 魔板n算法三：BFS+判重n对这棵三叉树进行BFS，相同的节点不再重复扩展n第一个可行解即是最优解n判重：BFS每经过一个节点，把它放进已搜索列表中，每遇到一个节点，如果在已搜索列表存在，则不再扩展该节点，共8!=40320个节点。n判重编码：康托展开、自定义编码，如初始状态可编码为整数12348765。n可以轻松通过三个题目。2011-10-08311150 1151 1515 魔板nstate q40320;nvoid update(state new_state,int&head,int&tail,char opt)nqhead=new_state;nvisithash(new_state)=true;nparenthead=tail;nophead+=opt;n2011-10-08321150 1151 1515 魔板nvoid bfs(state start)nint head=0,tail=0;nupdate(start,head,tail,0);nwhile(tailhead)nstate new_state=A(qtail);nif(visithash(new_state)=false)nupdate(new_state,head,tail,A)nnew_state=B(qtail);nif(visithash(new_state)=false)nupdate(new_state,head,tail,B)nstate new_state=C(qtail);nif(visithash(new_state)=false)nupdate(new_state,head,tail,C)ntail+;nn2011-10-08331007 To and Fron题目大意：n给出一种加密方式，把一个字符串按列写成二维形式，再逐行从左到右或从右到左交替输出。给出加密后的字符串，还原本来的字符串。2011-10-08341007 To and Fron解题思路：n按照解密规则把输入字符串写在二维数组上，再输出。nint k=0;nfor(int i=0;i row;i+)for(int j=0;j column;j+)n if(i%2!=0)n ansij=sk+column-1-2*j;n elsen ansij=sk;n k+;n2011-10-08351036 Crypto Columnsn题目大意：n给出一种加密方式，把一个字