关闭

关闭

关闭

封号提示

内容

首页 刘汝佳数据结构杂题选.pdf

刘汝佳数据结构杂题选.pdf

刘汝佳数据结构杂题选.pdf

上传者: 泥巴 2010-01-29 评分 0 0 0 0 0 0 暂无简介 简介 举报

简介:本文档为《刘汝佳数据结构杂题选pdf》,可适用于IT/计算机领域,主题内容包含杂题选刘汝佳蚂蚁•一些蚂蚁以cms的速度在长度为Lcm的线段上爬行爬到线段端点就会掉下去。当两只蚂蚁相遇就会立刻掉头返回。已知L和一开始每只蚂蚁的位符等。

杂题选刘汝佳蚂蚁•一些蚂蚁以cms的速度在长度为Lcm的线段上爬行爬到线段端点就会掉下去。当两只蚂蚁相遇就会立刻掉头返回。已知L和一开始每只蚂蚁的位置但不知道它们的方向求它们最早何时全部掉落最迟何时全部掉落。•最多,,只蚂蚁。分析•相遇照明•给出x坐标单调,y坐标为凸的折线表示一个洞穴的地面求一个最低点在此高度的某一个位置放一盏灯就能照亮所有地面一直线上也算照亮蛇•一块正方形土地从(,)到(,)上面有n条蛇(被看成点)每条蛇都有一个攻击距离问一个人能不能在不被蛇咬的情况下从西侧x=走到东侧x=。•如果可以给出尽量靠北(即纵坐标尽量大)的起点和终点。GetOut!•一艘船(形状是圆形)被困在群岛中(每个岛都是圆形)。一共n(n<=)个岛给定它们的坐标和半径又给定船的坐标和半径问船能不能开出来。Sumset•求整数N写成若干个的整数幂的和的不同形式的总数(的最后位数字)•例如:=–=–=–=–=–=•所以Ans()=方法一•令fi,j表示将i写成若干个的整数幂的和且其中最大的一个不超过j的总数•则fi,j=fi,jfij,j•时间复杂度为O(NlogN)如果使用了滚动数组空间复杂度为O(N)方法二•不难得到:当i为奇数时fi=fi•如果i是偶数我们考虑i的表达式中是否含有:–如果有则i的表达式对应了一个i的表达式–如果没有则我们可以将i的表达式的每一项除以就对应了一个i的表达式。•由此我们又得到:当i为偶数时fi=fifi•状态总数只有N个时间复杂度也随之变为O(N)施工队•有一条道路上面有N个坏的地方现在政府准备修理这些坏的地方。政府将整条道路分为若干大小为M的段对于每一段如果有坏处的话就聘请一个施工队去修理。分段的方法如下:如果第个段开始于K那么第L个段的范围即为K(L)*M到KL*M(从K开始连续分配)。现在要求你确定这个K使得聘请的施工队最少。分析•枚举K,每次移动窗口时…•所有坏处按模M分类,每个恰好被处理一次•总时间复杂度为O(n)FiberNetwork•给定一张有向图每条弧上标有至少一个字母。每次查询一对起点和终点要求求出所有的满足以下条件的字母:从起点出发只沿标有该字母的弧可以到达终点TheRotationGame•如图形状的棋盘上分别有个、、要往A~H方向旋转棋盘使中间个方格数字相同Tournament•每次选择两个程序比赛,败者淘汰出局•已知一些程序之间的强弱关系,求出所有可能得冠军的程序•n<=,,m<=,,分析•不知道关系的程序,相互都可能战胜对方,需要连两条边uÆv和vÆu,因此新图的边是O(n)的,需要降为O(m)•方法一:先求无向图补图的连通分量,然后求原图的SCC•方法二:随便生成一个方案,找到一个强连通分量中的点然后扩展理由:基源只有一个!Dept•教授分别欠了A,B,C三个人x,y,z(<=)元钱他决定用手头的N(<=)块水晶来偿还这些债务。一块小水晶值元大水晶则值元。但由于各人的评判标准不同对于同一块水晶有人认为它是大水晶有的却只认为那是小水晶•如何分配水晶以偿还所有债务也就是使得每个人得到的水晶按照他自己的标准价值都不少于教授拖欠的债务。分析•先考虑BSS,SBS,SSB,如果A已经还清则BSS等于SSS•枚举BBS给A的数量,则其他给B如果A还没还完则BSB尽量给A,SBB先给B后给C•再分配BBB,最后是SSSEvilStrawWartsLive•给定一个字符串问通过多次交换相邻的两个字符能否将它变为一个回文串(即从左边和右边读起来一样)。如果能给出最少交换次数分析•有解当且仅当出现奇数次的字母最多个•特殊情况:前一半和后一半中所含的每种字符的个数都一样(假设出现次数为奇数的字母不存在或者恰好在“前一半”和“后一半”中间)•将“后一半”倒过来然后与“前一半”的字母一一对应起来。我们把“前一半”的字母编号那么就可以由“后一半”得到一个序列分析•逆序对个数!出现两个相同的字母(如前面例子里的两个a和两个b)怎么建立对应关系?回答也很简单:最靠左边的与最靠左边的相连第二靠左边的与第二靠左边的相连……最靠右边的与最靠右边的相连即可。假如不这样做逆序对的个数会比原来的大abbcacabab分析•交换相当于在不改变其他字符的相对位置的情况下将一个字符“推移”。假设左边多了个a则把左边的最后一个a推到右边第一个a的左边。•为什么不推其他的a而是推最后一个呢?又为什么只需要推到右边第一个a的左面呢?因为我们后面要进行的计算:求逆序对的个数相当于求出了最优解。假设内部多推几步(把最后一个a以外的a推到右边相当于把它推到最后一个a的左面然后再把最后一个a推到右边然后再浪费一步)后能得到一个更优的解与逆序对最优矛盾Polymania•给出N个点的权值Ri。要求将这些点安排在平面上使得其中任意三个点组成的三角形面积都恰好等于这三个点的权值和。所有权值为正(其中NRN=RN)分析•由于最后可行的安排方案不是唯一的通过任意的旋转、翻转仍然可以保证方案的正确性。因此我们不妨将最后两个点安排在数轴上设它们的坐标PN与PN分别为(x,)与(x,),其中x>,最后两个点的距离|PNPN|等于x•对于一个包含有N个点的合法的安排方案去掉任意一个点剩下的部分将仍然是一个包含有N个点的合法方案。因此可以由较小规模的的问题开始分析找出规律进而解决问题N=•三角形PiPNPN的面积为RiRNRN(<=i<=N)因此Pi到x轴的距离为(RiRNRN)x=(RiRNRN)x这也就是第i个点的纵坐标的绝对值|yi|•N=时只存在一个三角形因此只要第一个点的纵坐标的绝对值符合上文所分析的情况这样的安排就是合法的。令x=则|y|=RRR得到了一种安排方案三个点依次为(,RRR)、(,)和(,)N=•由于R=R因此三角形PPP和三角形PPP的面积相同即P与P到直线PP的距离相同。只存在两种情况:一是直线PP与PP平行二是直线PP经过线段PP的中点(,)N=•P与P、P与P、P与P之间的位置关系都应当分别符合刚才的两种情况之一至少会有两组或两组以上的位置关系符合同一种情况那么就会推出P、P与P三点共线即三角形PPP的面积为与点权为正整数矛盾•结论:N>=时不存在合法的安排方案灭火•在X轴上有N个城市它们的坐标都是非负整数。有一天这N个城市同时着火了。每个城市都有一个初始损失值Ci与增加损失值Di设开始着火的时刻为则如果第i个城市在时刻t被扑灭则它的损失值为Cit*Di不幸的是总共只有一台灭火车。它的初始位置为s灭火车的速度为单位长度单位时间。它的神奇之处在于在它到达某个城市的瞬间那个城市的火就被扑灭。•给定N,s,每个城市的位置Xi以及Ci,Di要求最小的总损失值。分析•被扑灭的区间是连续的•di,j,t,d表示时间为t,方向为d…•时间复杂度O(nt),无法承受巧克力•有一块m*n的巧克力(可以想象成一个网格矩阵)现在需要把它切成m*n个大小相等的小块。沿着某一竖线切与沿着某一横线切都有一定的花费。沿着竖线切的花费依次为x,x,…,xm沿着横线切的花费依次为y,y,…yn在切的过程中只许一次对一块巧克力进行操作且必须将它一刀切成两半。无论此刀的切痕有多长都按照一整刀计算。现在要求出将巧克力切成m*n个小块所需的最小花费。分析•切割过程:不断地选择切割的线并按照这条线完整地切下来如果在与其垂直的方向上已经切割了i条线则总代价就加上这条线的代价*(i)•如图先选x,接着选y然后选y最后选了x。代价就是*x*y*y*x拓扑序•拓扑序是存在的•新问题:为x,x,……,xm,y,y,…,yn安排顺序总代价=(每一项的代价*排在它前面的与其垂直的线所对应的项的个数)求最小总代价dpvsgreedy•解法一:x和y分别从大到小排序,然后dp•解法二:x和y一起排序•相等值无影响过桥•有N(<=N<=)个人想过桥每个人都有重量Wi及独自过桥所需时间Ti为了尽快过桥若干个人可以一起过。他们过桥的时间为其中最慢的那个人所需的时间。必须一组人完全过桥后下一组人才可以出发。但是桥本身也有能够承受的最大重量W所以规定一起过桥的一组人的重量之和不得超过W现在要求所有人都过桥的最短时间Survival•在KOF中你需要扮演一个角色。为了打通关你必须战胜N个对手(<=N<=),包括太阳神。你可以任意安排对手的顺序唯一的要求是太阳神必须是最后一个•整个过关过程就是你依次与安排的对手交战每次HP值减去所需的HP值加上所恢复的HP值(超过取)。要求是任意时刻你的HP值必须非负。问否可能打通关电梯•给定N个用户(<=N<=)乘坐电梯的起始层Ai与终止层Bi以及他们到达电梯口的时间Ti电梯初始时位于第层。电梯从第i层运行到第j层需要|ij|单位时间。每个时刻电梯可以选择上升、下降或停止不动。用户上下电梯的时间忽略不计•要求从初始时刻到所有用户都到达各自终止层所需最短时间分析•状态量:已到达人集合、当前层(离散值),电梯里的人集合•转移–上升一层–下降一层–等待:转移细化•dpdijkstraGame•给定L,L分别代表两个数列的长。这两个数列都是正整数序列。•每次可以从序列的尾部选取K个序列的尾部选取K个。设序列尾部的K个的和为S类似地定义S。这次将KK个数删掉的费用定义为(SK)*(SK)。•注意每次删除后两个序列不能一个为空另一个非空!求将所有元素删除所需要的最小费用分析•最先的想法是容易想到的就是将所有元素减一费用被重新定义为S*S。•对某次操作如K>且K>那么它一定可分解为多次K=的操作费用更小•设ds,I,j表示对于序列的前i个数以及序列的前j个数。若s=那么表示当前正在处理K=的操作否则是K=的操作。Unique•给定N<=个数其中只有一个数只出现一次其它数至少次。•要求找到那个数并且输出JokewithTurtles•有n只乌龟描述一次赛跑中报告自己的成绩(多少比自己快多少比自己慢余下的任何自己成绩相同)。有的乌龟说谎试求一个最大的全说真话的集合。分析•有N个区间每个区间都有某个特定的权值要求选择一些不相交的区间且权值最大。而这在为区间的节点进行O(NlogN)的排序之后完全可以用一个简单的O(N)的DP来完成。如果硬要追求复杂度的话O(N)的基数排序也是可以完成的因此本题算法的时间复杂度仅为:O(N)FunGame•一个组成的圈已知其中的n段弧每段弧可能是顺时针或者逆时针。请还原这个圈使圈是所有可能的情况中最小的一个Rain•在单位时间单位长度降雨量为单位的时候每条“屋顶”都有一个单位时间落下的水量(就是单位时间从屋顶较低的那一侧落下去的水量)对于每个屋顶算出落水量主算法•用扫描法构图,然后BFS统计•x坐标相同的事件点我们要先插入再检测落雨点最后删除才能满足题设条件abcChandelier•寻找与已知串等价的、需要栈深度最小的串每个ring上可以旋转•下图的最优解为,方案aaaaaaaaaaaFindtheBorder•求轮廓线Gunman•如何发射一棵子弹,穿过尽量多的矩形LatticeAnimals•计算w*h的格子里选n个组成的连通图形的个数(旋转、翻转不能重复)IrrelevantElements•给n个数,每次求相邻两个数的和得到新数列,最后变成一个数,求它modm的值•问这个值和最初的哪些数无关BarbarianInvasion•给出n个点,删除一个点使得其他点的凸包周长尽量小BTP•N头奶牛(N<=,总是的幂次)参加网球比赛。在第一轮N对选手进行比赛获胜的N个选手进入下一轮。同样下面的每轮比赛中都是获胜的一半进入下一轮直到只剩一头牛•如果参赛的两头牛排名之间的差距大于一个给定的常数K(<=K<=N)那么排名较高的奶牛总是会赢得比赛的胜利。计算最后有可能夺冠的牛中排名最低的牛的排名并且给出一种能使这头牛获胜的场次安排。分析•二分最后牛的排名X,进行模拟–决赛是X胜XK–每次让每头牛胜尽量强的牛•朴素方法:从XK开始检查XK,XK,…,直到有一个没输过•优化:并查集Fence•有M个油漆工和顺序放置的N个木板。第i个油漆工坐在木板Si前手臂可以伸长Li也就是说他只能对SiLi~SiLi的木板漆油漆。每个油漆工所漆的木板必须是一个连续木板序列并且包含Si。第i个油漆工漆每个木板的费用为Pi•求使得总费用最大的一个安排方案每块木板最多只能由一个油漆工上漆Friends•有N个人分成了若干个组。每次可以询问一个序列的人问他们所在的组的所有的人是哪些•例如:N=组{,,,},{,,},{}–你如果询问{}会得到{,,,}的答案–如果询问{}会得到{,,,}的答案•必须用不超过log(N)的询问次数Race•给定平面上N<=个点的坐标。另外有M<=条无向边。•现在要求从号点开始绕一个圈每次只能左转(转角,)度范围内)并且使路径上的最短的边尽可能长。Empodia•生物序列是一个包含到M的一个排列第一个数是最后一个数是M。任意数都不会比前一个数恰好大。片段是生物序列的连续子序列,帧是特殊的片段它的第一个数和最后一个数分别是整个片段中最小的和最大的而且夹在它们中间的数都在这个片段中出现。empodio是特殊的帧它里面不包含其他的帧•例如(,,,,,,,)本身是帧,但包含另一个帧(,,,)所以它不是empodio。(,,,)不包含帧所以它是empodio。找出一个生物序列的所有empodio。分析•(i,j)为帧的充要条件–ji=AjAi,因此Aii=Ajj–bigger(i)为i左边第一个大于Ai的数的下标,smaller(i)类似,则smaller(i)>j,bigger(j)<i•主算法:先找出一些帧,再排除重复•方法:扫描的同时计算smaller,bigger并维护可能的左端点集合,以Aii的值分类分析•栈Down存放递减序列每次检查下一点如果该点满足递减关系直接将其加入否则逐步退去栈顶元素直至满足递减关系并将新点加入。当栈维护到j并要将j加入时此时的栈顶元素就是bigger(j)•链表List存放候选左端点集合每一个链Listk存放所有Aii=k且可能成为某个片段的左端点的点•栈Up存放递增的序列当栈维护到j并要将i退栈时就表示Smaller(i)=j,同时也表示i所代表的点已经不可能再成为某个右端点在j或j右侧的片段的左端点将i在ListAii中删除分析•从小到大枚举片段的右端点j同时维护栈Down和Up并检查ListAjj链中最后一个点i(即最近加入的点)。–i>bigger(j),则(i,j)是满足要求的片段不需要尝试ListAjj中的其它点因为即使也满足要求但内部已经包含了一条更小的片段(i,j)–否则(i,j)不满足要求则List中比i小的点就更不可能满足要求。但对于更大的j这些点有可能满足要求因此仍将它们留在List中作为候选点。•每个元素都只处理一次总时间O(N)A和B的交•设A为(I,j),B为(I’,j’),则C为(I’,j)•满足Si’<x<Sj的数一定在A中也在B中因此在C中,且不可能有其他数(不满足A和B的范围限制)•结论:有A有BÆ有CABC分析•第一步求出的片段中仍然可能有相互包含的情况,但不可能出现相交但不包含的情况因为A有BÆ有CÆ无A)•删除那些包含其它片段的片段剩下的就是满足题目要求的所有片段这一部分也可以在O(N)时间内完成ABCTheBookShelver’sProblem•有N本书每本高hi宽wi。需要将N本书按顺序放入一宽为W的书橱中。放置时可以将若干本书放在同一层中该层高度h为这些书中最高的高度。将整个书橱至少需要多高才可放下所有书?画矩形•平面上给出N个点以这些点为左上角画N个矩形矩形的边平行于坐标轴每个矩形的大小完全一样且长(横向)正好是宽的倍。所有矩形都不能相交但边或顶点可以重合。Pigs•有M个锁着的猪圈每位顾客都有一些钥匙•买卖的过程是这样的:一个顾客到来后打开所有他可以打开的猪圈,然后你从这些猪圈里牵出固定数目的猪卖给顾客(最多只能和顾客需要数相等)并可以重新安排这些开着的猪圈中的猪。每个猪圈可以存放任意数目的猪•已知所有顾客有的钥匙(每把钥匙只能开一个特定的锁)和他们需要买猪的数量在事先都告诉了你你要使卖出去的猪最多Traffic•在一个数轴上一共有N辆汽车每辆汽车都在以固定的速度行驶给出它们在时刻的位置S以及它们的速度v。•在某一时间t位置St最大的那辆汽车为领先汽车求在时间段a,b内每一辆汽车的领先时间。•规模:N不大于输入数据按照v从大到小给出没有任意两辆汽车速度相同。杂题选蚂蚁分析照明蛇GetOut!Sumset方法一方法二施工队分析FiberNetworkTheRotationGameTournament分析Dept分析EvilStrawWartsLive分析分析分析Polymania分析N=N=N=灭火分析巧克力分析拓扑序dpvsgreedy过桥Survival电梯分析Game分析UniqueJokewithTurtles分析FunGameRain主算法ChandelierFindtheBorderGunmanLatticeAnimalsIrrelevantElementsBarbarianInvasionBTP分析FenceFriendsRaceEmpodia分析分析分析A和B的交分析TheBookShelver’sProblem画矩形PigsTraffic

用户评论(0)

0/200

精彩专题

上传我的资料

每篇奖励 +2积分

资料评价:

/13
仅支持在线阅读

意见
反馈

立即扫码关注

爱问共享资料微信公众号

返回
顶部