算法分析与设计课件习题选讲2wxyz.ppt

习题选讲,赵浩泉wxyz202soj.me,蹦孤赠术喷香鸣耀症友绞兄懒奏把埋帝烫镣擅厦历剂制证神巴字凄兆柱英算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,2,第一章,Sicily 地址:http:/soj.me1020 Big Integer1021 Couple1027 MJ,Nowhere to Hide1035 DNA matching1046 Plane Spotting1051 Bikers Trip Odomete1198 Substring1176 Two Ends,践求古讼恳帖彬酣控吸迂艳瑟澡纽礼闷誓惟吨警挛微漆礼仿孵点橱弓闽挚算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,3,1020 Big Integer,题目大意：给出n个整数b1,b2,.,bn，和一个大整数x，求x对每个数bi取模的结果。n=100,1bi=1000,x的长度不超过400。,瘩密隔技脸儒绰咱诺距姚素胡火窑乘樊眶霹靡碰正磺清摆呛苹陇肤竟峭疗算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,4,1020 Big Integer,解题思路：对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;,窗琵注池皖代碘捡菊迅领遇柿剔频炸乱椰淤巍宁沛堆酝茄鹰刹志慧架忌币算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,5,1021 Couple,题目大意：N对夫妇站成一圈如果某对夫妇站在相邻位置，则从圈中移走重复以上操作问最后会不会没人如1 3是一对，2 4是一对，则No如1 4是一对，2 3是一对，则Yes1=N=100,000,鹰觅巡卒项褪寒童练播剪粱普迅滑栓症椰苯膳怒鬼卵杯赢抚军羹却焙藉锣算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,6,1021 Couple,解题思路：类似于括号匹配，可将n对夫妇看成n种括号用一个栈来模拟，将括号逐个push到栈里当栈顶存在匹配对时进行pop操作看最后栈是否为空,递赂卉惮轻谋邵笑你警攒烃旭念荒表手隧搽迅皑绵拢君奎屋揪蜗酝辽唇汛算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,7,1021 Couple,如1 3是一对，2 4是一对,最后栈不为空，输出No,赦抹铡板耀叼顶抨挠辆善侣谐幼饺典构遍暮迸郑戏扶襟者兆矣欠汞烘慈克算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,8,1021 Couple,如1 4是一对，2 3是一对,1,1,2,1,2,3,1,1,4,最后栈为空，输出Yes,着若拌憾氓劫却鄂遥舌谜厌穗琶敖挥衫宏皇也棱愁俘趣琢莹香秩气傅辊覆算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,9,1021 Couple,stack s;for(int i=1;i=2*n;i+)if(!s.empty(),昼忻旬傍溯始慰诈疏督摘撵锈快劝输瞎倔胺粉舔忠窟恫醛翔兄锐耿骗未佳算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,10,1027 MJ,Nowhere to Hide,题目大意：给出N对BBS_ID IP_Address，求出IP_Address相同的BBS_ID。N=20,戊旨张热端弘拢勉断据莱硒撅该馆盅悯财翱迟翁湛涟钟列插闹沃堡元贩费算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,11,1027 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);,溺颊知损篱愈荷么余斟嵌遵迪君例姥磺砚哑评写兼祟悔陪瓜继院颓廖豌寥算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,12,1035 DNA matching,题目大意：给出n个DNA单链，问可以用这些DNA单链组成多少个DNA双链；每个DNA单链最多使用一次；两个DNA单链能组成DNA双链，当且仅当两个DNA单链的长度相等，且对应位置上能配对，A与T配对，C与G配对；n=100,每个单链长度不超过100。,灸黍汝疚簇耘愿附哥菱硒讽迷质吱谦熙烤瞪拌剧垮朴鞠翻箕虹嗜否睛痒膜算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,13,1035 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;,诅取姻堕袜健磐胡诽侯匈眩裹导铲丈沽丸阅珊孜嘿擂毅侨用梳古召昔像天算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,14,1046 Plane Spotting,题目大意：给出一个长度为N的非负整数序列（所有数不超过200），还有两个整数M和K，求前M个最优的长度不小于K的连续子序列。连续子序列的优先级如何比较1、平均值大的序列优于平均值小的2、条件1相同情况下，长度大的序列优于长度小的3、条件1和2相同情况下，结束位置靠前的序列优于结束位置靠后的1N300，1M100，1K300,亡铣拖膘妖壹礁戎成梯仓斡戳锌如毛纤蚁余知卡裴样贬撞狭锭桶蹈撑输法算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,15,1046 Plane Spotting,解题思路：使用结构体表示一个子序列，重写比较操作“1e-6)return a.averb.aver;if(a.length!=b.length)return a.lengthb.length;return a.endsb.ends;,面悯凯巳沦糊报吮画角织咒题杰亲肋铀藩怜拣妹诱戌郸捧秤娟道详丰惜洋算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,16,1046 Plane Spotting,for(i=0;i=m)pcnt.length=j-i+1;pcnt.ends=j+1;pcnt.aver=(double)temp/(j-i+1);cnt+;sort(p,p+cnt);,柞南芝采圃迁谍喇懦芬眶缘尚伞帅倚攀潘多刚奥负衷坦惹侵半氮苯姨困拖算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,17,1051 Bikers Trip Odomete,题目大意：给出车前轮的直径，转圈数以及时间，求出车行走的路程和平均速度。,焚持淤彤严载浩渣苹翅敏华津嫁鬃采泞敬收耳儿腆矣材掖聪篆考件梗花兜算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,18,1051 Bikers Trip Odomete,解题思路：车轮周长=直径 圆周率路程=周长 转圈数平均速度=路程/时间,料卜扁肌喘旁啡轨哮祥弥僚扫赞集狮挝撩骂颈荧狂蕊呆问沽黄万编腮线他算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,19,1198 Substring,题目大意：用N个字符串拼成一个新的字符串要求新字符串字典序最小如：a ab ac则答案为：aabac1=N=8,每个字符串长度不超过100,吊武强没帐缄船疾罕撂拯韭赂此梢恃京腊窟鸵馆届谓虏号寇幅副娜估福势算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,20,1198 Substring,解题思路：枚举n!种情况，最多为8!=40320种情况；每枚举一种情况，与当前字典序最小字符串比较，如果字典序更小，则更新答案；递归求解。,坞愧睡馅刘辜茸潜削范单缴臃牲狼即柞饼邮矛汝坊迢迄穴呕讶哄曼此捻罚算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,21,1198 Substring,void 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;,恭武粉迸尼嘻氛黄任均辜阐砌炭棘蚌秃狰症总耻沦闷微申考汰锄办都糟称算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,22,1176 Two Ends,题目大意：给出n个正整数排成一列，A和B轮流取数，只能取两端的数，最后取到的数的和较大的人胜利，A和B之间的差为分值；A可以自由选择策略，B的贪心策略取两端中较大的数，如果相等则取左边的数；问A赢B的分值最大为多少。n=1000,且n为偶数。,滤镶烛禁勤幽坟戊帧芋钥厦沃茧盖慷辽堪踩贼春吾穆颂造祖雾杯势掌乓桶算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,23,1176 Two Ends,解题思路：A尝试计算所有情况，并选出自己得分最多的情况；计算所有情况时，减少重复计算（动态规划），每个状态为当前数列的左右端点位置。,罐甄焚握尝屋譬仪玉尤霖纶抗棉醚截刨买历壕比绥财亲朴尼煽蛙防绝唱仓算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,24,1176 Two Ends,int 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,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);,时代升左侵俊鱼掐琐躇综沾翌失橇根浆臭痕种咆厂斟拖厦共碍洽滚稠槛椒算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,25,第二章,1150 1151 1515 魔板1007 To and Fro1036 Crypto Columns1006 Team Rankings1009 Mersenne Composite N1050 Numbers&Letters1443 Printer Queue1156 Binary tree1063 Whos the Boss1024 Magic Island,臼书揉苔忠狼乞寒潮坏矗盏脓拭女黑柜绦阐耀什竿瘫旅声铜森道氖拐奥捻算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,26,如1150，初始状态如右图，三种基本操作分别是：A.上下两行互换B.每行循环右移一格C.中间四块顺时针转一格,1150 1151 1515 魔板,题目大意：给出魔板的起始状态，并给定三种基本操作，给出一个步数上限和目标状态，求从起始状态到目标状态的操作序列，长度不得超过上限。,红躲惰超疾器兴拿燃特垃转棠佰途辰是个版隔屹惺堑磨镇斟渗蜡啸族翁俊算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,27,1150 1151 1515 魔板,解题思路：对模板进行状态搜索；由一种状态可以转移到另外三种状态，搜索树为一棵三叉树；在这棵三叉树上搜索，目的是求出最优解。,掣浩贺倔愁晚加畔寅蓑韭叔哎雏蜕灯疙娇脂狭摩伸坟一男造我涉怯砍门缔算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,28,1150 1151 1515 魔板,算法一：盲目DFS对这棵三叉树进行DFS若想求得最优解，需要遍历整棵树需要进行重复扩展优化：若已找到一个可行解，可剪去大于等于这个深度的所有子树勉强可过1150。,死认反沛独窘恬湃缝炼睦舌汾腿唾椰政打琢辰直缮房板褒搬挣得跳钾卢罢算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,29,1150 1151 1515 魔板,算法二：BFS对这棵三叉树进行BFS第一个可行解即是最优解可以过1150，但过不了1151。,枚夸芜溜坍豪顺酿洽犁前罚益鼎毙佯定怔战至虐朱呻诵撂疤坦挚猜尧媚洗算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,30,1150 1151 1515 魔板,算法三：BFS+判重对这棵三叉树进行BFS，相同的节点不再重复扩展第一个可行解即是最优解判重：BFS每经过一个节点，把它放进已搜索列表中，每遇到一个节点，如果在已搜索列表存在，则不再扩展该节点，共8!=40320个节点。判重编码：康托展开、自定义编码，如初始状态可编码为整数12348765。可以轻松通过三个题目。,既囤乖踊抱干访咖策韶哪吊篡淤聋寻胯玫颧后其垒灿滇株诛纬跳还能式穴算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,31,1150 1151 1515 魔板,state q40320;void update(state new_state,int,曙个攘邻免亿刑掳夺艘湾港俘园毅湍脓辙佛阑介小和涤浸捣爸束韶誊梁伍算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,32,1150 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 new_state=C(qtail);if(visithash(new_state)=false)update(new_state,head,tail,C)tail+;,拴陪蔓醉周蘑塑供信亢陆苗忌鲤需耳蠕求剥休梨悄滑榔茶剩送澳顷浚飘贝算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,33,1007 To and Fro,题目大意：给出一种加密方式，把一个字符串按列写成二维形式，再逐行从左到右或从右到左交替输出。给出加密后的字符串，还原本来的字符串。,袱踩冶窿黎瓣窒阎么蛇啊辣仓章欺腹永溃娩嘘晋窿拂蛛励端时驳婶揪供陵算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,34,1007 To and Fro,解题思路：按照解密规则把输入字符串写在二维数组上，再输出。int k=0;for(int i=0;i row;i+)for(int j=0;j column;j+)if(i%2!=0)ansij=sk+column-1-2*j;else ansij=sk;k+;,盆咱岔崇狂溅迫篆黔折妈倾撼抠拘鸥霓寥奥挖哑岔尧傻拥太俄茧洞掘老眶算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,35,1036 Crypto Columns,题目大意：给出一种加密方式，把一个字符串按行写成二维形式，再按照给定字符串的字符大小顺序逐列替输出。给出加密后的字符串，还原本来的字符串。,兰苍仟浴喜纽砂乒扩霓冈则敌梭雌椎峡尊蛙搐棋舌漾配统翰钎悟看括昆忧算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,36,1036 Crypto Columns,解题思路：按照解密规则把输入字符串写在二维数组上，再输出。for(i=0;icolumn;i+)temp=a;for(j=0;jcolumn;j+)if(keywordjtemp)temp=keywordj;now=j;keywordnow=a;for(j=1;j=row;j+)cjnow=sk+;,芳壕丰抨治诚缘背贮钓挫涉片靡工裳逊糜硕钮饰脯趾直反凳札慌视围发气算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,37,1006 Team Rankings,题目大意：对于两个排列p,q，定义 distance(p,q)为在p,q中出现的相对次序不同的元素的对数。相当于以p为基准，求q的逆序数。给出n个5元排列，构造一个排列，使得该排列对n个排列的distance之和最小。n=100,牵监刨涣力擅薛听蒜道婴咀私坯激入潜酸润慷喜谊萧优涵雾蜀翟叔锥陈迸算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,38,1006 Team Rankings,解题思路：枚举所有5元排列，与n个排列一一比较5个元素之间顺序并累加；枚举方法可用递归。,溜相兢宽祸裴坟享拉什浑翠爱彬盈妒短晋闯钡晰蔫妓晶瞻轩损崔苔实把援算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,39,1006 Team Rankings,void 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;,障茬澎志磺符沾句遗疡菩君俐辟撮咬埃查滥坝鳖重裤叭哈膝刘甘胆接蚊费算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,40,1006 Team Rankings,void cal(char rank)int count=0;for(int i=0;in;i+)count+=distance(ranksi,rank);if(countans_count)ans_count=count;strcpy(ans,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;,谜傈泵稠晴义态虏啊膝船寒舜环汝澈膛渝趟锯损流燃释即霸峻绰还猴仇胳算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,41,1009 Mersenne Composite N,题目大意：梅森素数Mn：定义为2n-1其中n为素数且2n-1也为素数的数。给定k，求出所有素数n=k，且满足2n-1不是梅森素数的数，并且将它们分解。k=63,绩坯肿捣揽惜穗腋票坍先炽竭喉醉妨氨瞄娩咕澄填胺衬精挤细歹钻墙伎乖算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,42,1009 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只对这些数进行分解。,凳惨花物掌步毯霜企麦批畦操限碟卒拱俗分澈轿寂缝枫滴褪颐安咏箩猾她算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,43,1009 Mersenne Composite N,vector cal(long long x)vectorfactor;long long n,i,k;n=(1LLx)-1;for(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;,首笨稿抡瑟竟肆钠彭耘斡糟辉撂费蕊奢亥毫关吞怨瑞戍腕还枕杯示编弧凯算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,44,1050 Numbers&Letters,题目大意：给出5个数和一个目标数，从5个数中选出一部分数通过加减乘除运算得到小于等于目标数的最大数。,抑枢臀腻联狠茄匣犊剑圆蕊知赢峦逸占浩然菱似办洼袭瓮则室斑疹誊让胡算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,45,1050 Numbers&Letters,解题思路：DFS求出所有可能的运算组合和顺序，得到最接近目标数的答案。,冠碳号鼠虞窖讽淳煎傀掐智毁陵祈晨单片招用校祝沸铆糖俭追扛山稗蒸姬算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,46,1050 Numbers&Letters,void dfs(int a,int n)if(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,啤经哈眷癣吩谤搁淳帛玫紧士密梅流眺虏德愉币丙诧光撤袍携抢释瞒逆假算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,47,1443 Printer Queue,题目大意：给出一个长度为n的打印任务队列，每个任务有优先级。每次从队列头得到一个任务，如果它是剩余任务中优先级最高的，则打印它，否则放到队列尾。求出其中某个特定任务是第几个被执行的。n=100,为配猴潭此量好乐消斟酱途洁攻澎贩蹦暗暂蝎仑迅离苛施力潜性镜咀寝私算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,48,1443 Printer Queue,解题思路：使用队列直接模拟。取出队列头判断是否打印，如果打印则已打印任务数加一。直到特定的任务完成，输出答案。,翰乎静森殿烘肯哉货克井黍铺意欢撵砸状奈姿两澡鸳厄柬烩憾摘徘锦践姻算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,49,1443 Printer Queue,while(true)cur=q.front();if(cur.priority!=highest_priority)q.push(cur);else minute+;if(cur.number=m)break;while(highest_priority0,靡嗓惩党瓶式蛇呈倚探嘎皂黔窥贾煎抽为杠押酮速舵摸官嘘花原软聋潮印算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,50,1156 Binary tree,题目大意：给出一棵二叉树每个节点的编号，内容以及左右子节点的编号，以先序遍历二叉树输出每个节点的内容。,继叙冕表增唉辊窒箕刻疹裴囚双丢断窿滤咕据贤下阁臆骂强破治窄黑昨熟算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,51,1156 Binary tree,解题思路：先序遍历：先输出当前节点的内容，然后遍历左子树，最后遍历右子树。先找出没有父节点的节点，即根。从根开始遍历进行先序遍历。void preorder(node*s)visit(s);preorder(s-leftchild)preorder(s-rightchild),窝确列糊涉送北落唉士念榨秉奴茶神旋茹痕氟芹孙滔络试区豪鉴钦柑之则算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,52,1063 Whos the Boss,题目大意：给出n个人的编号，身高和工资，一个人的直接上司是身高不比他小且工资比他高最少的人。一个人的下属同时也是他直接上司的下属。给出q个询问，输出询问的编号的直接上司的编号，以及这个编号有多少个下属。,呛穴拢社亮贷放酗酬鸥隧丛江胚喳附干侩庄恭入诽壁逗售焰乏澡都屠名淹算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,53,1063 Whos the Boss,解题思路：对所有人按身高从大到小排序，相同则按工资从大到小排序。枚举每个人，在已检查的人中找出工资比他高最少的人，这个人就是他的直接上司。可以使用STL里的set。(upper_bound()再按身高从小到大枚举每个人，把每个人的下属个数累加进他的直接上司的下属个数。对每个询问，查找ID给出答案。,殿顽埃吟磐甚奢逆追盎赐窗内赦丽禽浙嫉移痕西蜂馈笛晓痉种具特蛊刊密算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,54,1063 Whos the Boss,struct employeeint height,id,earn,number,farther,sub;bool cmp(const employee,偏挣底纪炯宴砰氢鬃粳组痊雄示蓖无墒被为贿私石蔡勇棉虐哀溺庙骋政刘算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,55,1063 Whos the Boss,sort(a,a+n,cmp);for(i=0;i=0;i-)it=h.upper_bound(ai);if(it=h.end()ai.farther=-1;else ai.farther=(*it).number;h.insert(ai);for(i=0;in;i+)if(ai.farther!=-1)aai.farther.sub+=ai.sub+1;ai.farther=aai.farther.id;else ai.farther=0;sort(a,a+n,cmp2);,虐椽途蒸解玲堤泵碳涯召芍栈嚣扮歪议肾倦缺梯丫娠龋武熊鼎著脑匪宁易算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,56,1024 Magic Island,题目大意：给出一个有N个节点的树，从结点K开始出发，不重复经过任意一条边，求最远可以走的路程。,愁圣氰屡意腕氮接砰列躲俏肃碘厘浊祟王亚扶吵舱侨衔贯粘糖四覆觉社篆算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,57,1024 Magic Island,解题思路：树的性质：两个节点不经过重复边的路径有且只有一条。从起点开始BFS或DFS，求出到所有节点的不经过重复边的路径长度，取其中的最大值即为答案。void dfs(int current,int parent,int l)if(lans)ans=l;for(int i=0;iedgecurrent.length();i+)if(edgecurrenti.number!=parent)dfs(edgecurrenti.number,current,l+edgecurrenti.l);,叹方臼态且傈嗓庸虞洛详突德瘦焙涣各押刮措钻潜揍筒华炳桓均砌贰桅部算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,2011-10-08,58,谢谢！,轧著冀幼酌某慌脱矛匀评四睫煤恶冠勒腥贝吠撮怪舶靠雁院恭痴钾沁匈喇算法分析与设计课件：习题选讲2 by wxyz算法分析与设计课件：习题选讲2 by wxyz,