算法分析习题选讲2

1、习题选讲2011-10-082第一章Sicily 地址: http:/soj.me1020 Big Integer1021 Couple1027 MJ, Nowhere to Hide1035 DNA matching1046 Plane Spotting1051 Bikers Trip Odomete1198 Substring1176 Two Ends2011-10-0831020 Big Integer题目大意：给出n个整数b1,b2,.,bn，和一个大整数x，求x对每个数bi取模的结果。n=100, 1bi=1000, x的长度不超过400。2011-10-0841020 Big In

2、teger 解题思路：对bi逐个计算；高精度，模拟竖式计算。int div(char x, int b) int a=0;for (int i=0;xi!=0;i+) a=(a*10+xi-0)%b;return a;2011-10-0851021 Couple题目大意：N对夫妇站成一圈如果某对夫妇站在相邻位置，则从圈中移走重复以上操作问最后会不会没人如1 3是一对，2 4是一对，则No如1 4是一对，2 3是一对，则Yes1=N=100,0002011-10-0861021 Couple解题思路：类似于括号匹配，可将n对夫妇看成n种括号用一个栈来模拟，将括号逐个push到栈里当栈顶存在匹配对

3、时进行pop操作看最后栈是否为空2011-10-0871021 Couple如1 3是一对，2 4是一对112123最后栈不为空，输出No14232011-10-0881021 Couple如1 4是一对，2 3是一对112123114最后栈为空，输出Yes2011-10-0891021 Couplestack s;for (int i=1;i=2*n;i+) if (!s.empty()&s.top()=couplei)s.pop();elses.push(i);2011-10-08101027 MJ, Nowhere to Hide题目大意：给出N对BBS_ID IP_Address，求出

4、IP_Address相同的BBS_ID。N=202011-10-08111027 MJ, Nowhere to Hide解题思路：枚举每两个BBS_ID IP_Address对，比较IP_Address是否相同；字符串比较。for (int i=0;in;i+) for (int j=i;jn;j+)if (strcmp(ipi,ipj)=0)anscnt+=make_pair(idi,idj);2011-10-08121035 DNA matching题目大意：给出n个DNA单链，问可以用这些DNA单链组成多少个DNA双链；每个DNA单链最多使用一次；两个DNA单链能组成DNA双链，当且仅当

5、两个DNA单链的长度相等，且对应位置上能配对，A与T配对，C与G配对；n=100, 每个单链长度不超过100。2011-10-08131035 DNA matching解题思路：枚举每个没有被匹配的DNA单链，再枚举另外一个没有被匹配的DNA单链，如果它们能匹配，则都标记为匹配，答案加一。for (i = 0; i N; i+) if (!vsti)for (j = i + 1; j N; j+) if (!vstj) if (match(DNAi, DNAj) ans+;vsti = vstj = true;break;2011-10-08141046 Plane Spotting题目大意：

6、给出一个长度为N的非负整数序列（所有数不超过200），还有两个整数M和K，求前M个最优的长度不小于K的连续子序列。连续子序列的优先级如何比较1、平均值大的序列优于平均值小的2、条件1相同情况下，长度大的序列优于长度小的3、条件1和2相同情况下，结束位置靠前的序列优于结束位置靠后的1N300，1M100，1K3002011-10-08151046 Plane Spotting解题思路：使用结构体表示一个子序列，重写比较操作“”。对所有可能的子序列进行排序。struct period double aver;int length,ends;bool operator 1e-6) return a.

7、averb.aver;if (a.length!=b.length) return a.lengthb.length;return a.endsb.ends;2011-10-08161046 Plane Spottingfor (i=0;in;i+) temp=0;for (j=i;j=m) pcnt.length=j-i+1;pcnt.ends=j+1;pcnt.aver=(double)temp/(j-i+1);cnt+;sort(p,p+cnt);2011-10-08171051 Bikers Trip Odomete题目大意：给出车前轮的直径，转圈数以及时间，求出车行走的路程和平均速度

8、。2011-10-08181051 Bikers Trip Odomete解题思路：车轮周长 = 直径 圆周率路程 = 周长 转圈数平均速度 = 路程 / 时间2011-10-08191198 Substring题目大意：用N个字符串拼成一个新的字符串要求新字符串字典序最小如： a ab ac则答案为：aabac1=N=8,每个字符串长度不超过1002011-10-08201198 Substring解题思路：枚举n!种情况，最多为8!=40320种情况；每枚举一种情况，与当前字典序最小字符串比较，如果字典序更小，则更新答案；递归求解。2011-10-08211198 Substringvoi

9、d dfs(char now,int lev) if (lev=n) update(now);return;char now2850;for (int i=0;in;i+) if (!usedi) strcpy(now2,now);strcat(now2,si);usedi=true;dfs(now2,lev+1);usedi=false;2011-10-08221176 Two Ends题目大意：给出n个正整数排成一列，A和B轮流取数，只能取两端的数，最后取到的数的和较大的人胜利，A和B之间的差为分值；A可以自由选择策略，B的贪心策略取两端中较大的数，如果相等则取左边的数；问A赢B的分值最大

10、为多少。n=1000,且n为偶数。2011-10-08231176 Two Ends解题思路：A尝试计算所有情况，并选出自己得分最多的情况；计算所有情况时，减少重复计算（动态规划），每个状态为当前数列的左右端点位置。2011-10-08241176 Two Endsint cal(int left,int right) if (right left) return 0; if (is_calleftright) return ansleftright; int ans_left = arrleft; if (arrleft+1 arrright) ans_left += cal(left+1,

11、right-1); else ans_left += cal(left+2,right); int ans_right = arrright; if (arrleft arrright-1) ans_right += cal(left,right-2); else ans_right += cal(left+1,right-1); is_calleftright = true; return ansleftright = max(ans_left,ans_right);2011-10-0825第二章1150 1151 1515 魔板1007 To and Fro1036 Crypto Colu

12、mns1006 Team Rankings1009 Mersenne Composite N1050 Numbers & Letters1443 Printer Queue1156 Binary tree1063 Whos the Boss1024 Magic Island2011-10-0826如1150，初始状态如右图，三种基本操作分别是：A.上下两行互换B.每行循环右移一格C.中间四块顺时针转一格1150 1151 1515 魔板题目大意：给出魔板的起始状态，并给定三种基本操作，给出一个步数上限和目标状态，求从起始状态到目标状态的操作序列，长度不得超过上限。2011-10-0827115

13、0 1151 1515 魔板解题思路：对模板进行状态搜索；由一种状态可以转移到另外三种状态，搜索树为一棵三叉树；在这棵三叉树上搜索，目的是求出最优解。2011-10-08281150 1151 1515 魔板算法一：盲目DFS对这棵三叉树进行DFS若想求得最优解，需要遍历整棵树需要进行重复扩展优化：若已找到一个可行解，可剪去大于等于这个深度的所有子树勉强可过1150。2011-10-08291150 1151 1515 魔板算法二：BFS对这棵三叉树进行BFS第一个可行解即是最优解可以过1150，但过不了1151。2011-10-08301150 1151 1515 魔板算法三：BFS + 判

14、重对这棵三叉树进行BFS，相同的节点不再重复扩展第一个可行解即是最优解判重：BFS每经过一个节点，把它放进已搜索列表中，每遇到一个节点，如果在已搜索列表存在，则不再扩展该节点，共8!=40320个节点。判重编码：康托展开、自定义编码，如初始状态可编码为整数12348765。可以轻松通过三个题目。2011-10-08311150 1151 1515 魔板state q40320;void update(state new_state,int &head,int &tail, char opt) qhead=new_state;visithash(new_state)=true;parenthea

15、d=tail;ophead+=opt;2011-10-08321150 1151 1515 魔板void bfs(state start) int head=0,tail=0;update(start,head,tail,0);while (tailhead) state new_state=A(qtail);if (visithash(new_state)=false)update(new_state,head,tail,A)new_state=B(qtail);if (visithash(new_state)=false)update(new_state,head,tail,B)state

16、 new_state=C(qtail);if (visithash(new_state)=false)update(new_state,head,tail,C)tail+;2011-10-08331007 To and Fro题目大意：给出一种加密方式，把一个字符串按列写成二维形式，再逐行从左到右或从右到左交替输出。给出加密后的字符串，还原本来的字符串。2011-10-08341007 To and Fro解题思路：按照解密规则把输入字符串写在二维数组上，再输出。int k = 0;for(int i = 0; i row; i+) for(int j = 0; j column; j+) i

17、f(i %2 != 0) ansij = sk+column-1-2*j; else ansij = sk; k+;2011-10-08351036 Crypto Columns题目大意：给出一种加密方式，把一个字符串按行写成二维形式，再按照给定字符串的字符大小顺序逐列替输出。给出加密后的字符串，还原本来的字符串。2011-10-08361036 Crypto Columns解题思路：按照解密规则把输入字符串写在二维数组上，再输出。for (i=0;icolumn;i+) temp=a;for (j=0;jcolumn;j+) if (keywordjtemp) temp=keywordj;n

18、ow=j;keywordnow=a;for (j=1;j=row;j+)cjnow=sk+;2011-10-08371006 Team Rankings题目大意：对于两个排列p,q，定义 distance( p, q )为在p,q中出现的相对次序不同的元素的对数。相当于以p为基准，求q的逆序数。给出n个5元排列，构造一个排列，使得该排列对n个排列的distance之和最小。n=1002011-10-08381006 Team Rankings解题思路：枚举所有5元排列，与n个排列一一比较5个元素之间顺序并累加；枚举方法可用递归。2011-10-08391006 Team Rankingsvoi

19、d dfs(char rank,int lev) if (lev=5) rank5=0;cal(rank);return;for (char c=A;c=E;c+) if (!usedc) ranklev=c;usedc=true;dfs(rank,lev+1);usedc=false;2011-10-08401006 Team Rankingsvoid cal(char rank) int count=0;for (int i=0;in;i+) count+=distance(ranksi,rank);if (countans_count) ans_count=count;strcpy(an

20、s,rank);int distance(char a,char b) int cnt=0;for (int i=0;i5;i+) posaai=i; posbbi=i; for (char c1=A;c1=E;c1+) for (char c2=A;c2=E;c2+)if (posac1-posac2)*(posbc1-posbc2)0) cnt+;return cnt;2011-10-08411009 Mersenne Composite N题目大意：梅森素数Mn：定义为2n-1其中n为素数且2n-1也为素数的数。给定k，求出所有素数n=k，且满足2n-1不是梅森素数的数，并且将它们分解。

21、k=632011-10-08421009 Mersenne Composite N解题思路：方法一：通过网络查找梅森素数的性质：对Mq（q是素数）有：若a是Mq的因数，则a有如下性质：a 1 mod 2qa 1 mod 8对每个数，枚举所有可能的因数，测试是否能分解。方法二：查找资料可知在n=63内有以下Mn满足答案11,23,29,37,41,43,47,53,59只对这些数进行分解。2011-10-08431009 Mersenne Composite Nvector cal(long long x) vectorfactor;long long n,i,k;n=(1LLx)-1;for

22、(i=3;i*i=n;i+=2) k=0;while (n%i=0) n/=i;k+;if (k!=0) factor.push_back(i);return factor;2011-10-08441050 Numbers & Letters题目大意：给出5个数和一个目标数，从5个数中选出一部分数通过加减乘除运算得到小于等于目标数的最大数。2011-10-08451050 Numbers & Letters解题思路：DFS求出所有可能的运算组合和顺序，得到最接近目标数的答案。2011-10-08461050 Numbers & Lettersvoid dfs(int a, int n) if

23、(n=1) return;int b5,m=0;for (int i=0;in;i+) for (int j=i+i;jn;j+) for (int k=0;kn;k+) if (k!=i & k!=j) bm+=ak;update_answer(bm=ai+aj); dfs(b,m+1);update_answer(bm=ai-aj); dfs(b,m+1);update_answer(bm=aj-ai); dfs(b,m+1);update_answer(bm=ai*aj); dfs(b,m+1);if (aj!=0 & ai%aj=0) update_answer(bm=ai/aj);

24、dfs(b,m+1);if (ai!=0 & aj%ai=0) update_answer(bm=aj/ai); dfs(b,m+1);2011-10-08471443 Printer Queue题目大意：给出一个长度为n的打印任务队列，每个任务有优先级。每次从队列头得到一个任务，如果它是剩余任务中优先级最高的，则打印它，否则放到队列尾。求出其中某个特定任务是第几个被执行的。n0&cnthighest_priority=0) highest_priority-; 2011-10-08501156 Binary tree题目大意：给出一棵二叉树每个节点的编号，内容以及左右子节点的编号，以先序遍历二叉树输出每个节点的内容。2011-10-08511156 Binary tree解题思路：先序遍历：先输出当前节点的内容，然后遍历左子树，最后遍历右子树。先找出没有父节点的节点，即根。从根开始遍历进行先序遍历。void preorder( node* s ) visit(s);preorder( s-leftchild )preorder( s-rightchild )2011-10-08521063 Whos the Boss题目大意：给出n个人的编号，身高和工资，一个人的直接上司是身高不比他小且工资比他高最少的人。一个人的