EZdlaPOJ解题报告.doc

寒假作业 情况&解题报告Dai注：1、 作业按照日期排序。2、 红色表示该题通过；蓝色表示该题没通过但有比较成熟的思路或已用程序实现；绿色表示该题有大概思路，但是没有再深入下去。3、 总情况： 提交： 题，通过： 题。日期题号题目大意解题报告提交情况2009-1-163619 Speed Reading有K头牛，一本有N页的书，对于一头牛i，它每分钟能阅读Si页的书，但是它每读Ti分钟就要休息Ri分钟。求每头牛阅读完N页的书所需要的时间。这道题是道水题，但是唯一要注意的地方就是计算时间的取整。对进一取整的讨论要注意整数分钟。4558787 EZ_dla 3619 Accepted 912K 47MS Pascal 758B 2009-01-16 21:56:413672 Long Distance RacingBessie锻炼身体要经过一段有山坡的路程。u表示上坡，f表示平坡，d表示下坡。u、f、d所需要的时间都不同。给定一个时间和一段地形，求在指定时间内来回一次能去到的最远距离。注意u在回去的时候会变成d，反之则然。也是一道水题。注意一下字符串的处理和u变d，d变u的问题即可。4558942 EZ_dla 3672 Accepted 852K 47MS Pascal 705B 2009-01-16 22:38:193620 Avoid The Lakes给定N*M的一个地区和K个格子，求这些格子连接成的最大的地区的面积。N,M=100。经典的FloodFill问题，复习了一次FloodFill。用BFS比DFS快，但是DFS的代码难度显然较低。4559030 EZ_dla 3620 Accepted 980K 94MS Pascal 1337B 2009-01-16 23:07:05本日总结：今天由于是两个星期没碰信息学后的第一次做题，主要是水题为主。2009-1-173705 Reverse给定一个n,n-1,2,1的序列，定义一种“块移动”pos1,len,pos2表示将序列的Seqpos1.Seqpos1+len-1移动到pos2后面。求最小的移动步数。NSi+1称为一个“不符数对”，则一个给定的序列N则有N-1个“不符数对”。我们现在证明，一次“块移动”最多只能消除两个“不符数对”。假设一个序列是aABbCD我们将AB这一块移动到C后面，则有ab.CABD则发生变化的地方只有三个地方，如果要同时消除三个“不符数对”，则要求1.aA2.bB3.CD同时新数列要求1.ab2.CA3.BD则解不等式组有AabBDCA注意到头尾是A=(n+1) div 2。1 4559726 EZ_dla 912K 32MS Pascal 1137B 2009-01-17 10:39:183700 Missile Defence System给定一个序列，表示导弹飞行的高度，现有若干个导弹防御系统，这些防御系统可以拦截一个高度单调下降或上升的导弹序列，求最小需要多少套系统。1=N3s，C大概在1s左右，效率差别非常大76 4559971(4) EZ_dla 180K 1188MS C 823B 2009-01-17 11:58:383618 Exploration给定数轴上的一些点和一个时间，每走一个单位距离需要一个单位时间，求按绝对值大小访问这些点最多能访问多少个。简单的排序题，按照绝对值排序后直接模拟即可。4561929 EZ_dla 3618 Accepted 1108K 110MS Pascal 1227B 2009-01-17 20:57:473602 Typographical Ligatures给定若干个字符串，计算需要用多少个字符来排版出这个字符串。其中ff，fi，fl，ffl，ffi要合并在一起。算是比较基础的字符串处理题，要注意“leftmost”原则，即先判断长的再判断短的，比如说ff和f是两个字符，而且应该先判断ff。本日小结：今天的收获主要在第一题上，结论很有用。2009-1-183632 Optimal Parking给出若干个数轴上的点，现在求将车停在某个地方后走路访问这些点的最小走的距离是多少。这题是道相当让人容易产生思维定势的题目，起初我考虑坐标范围很小，或许可以通过二分法求出一个最小值，后来觉得这个时间复杂度可能会比较郁闷，再仔细思考发现每个商店除端点外最少要访问两次（走回停车场），相当于整个路程走两次，这就变成了一道水题4562939 EZ_dla 3632 Accepted 912K 0MS Pascal 650B 2009-01-18 09:47:043637 Shopaholic商场举行“买二送一”的活动，其中的“一”是三件商品最便宜的一件。给出若干件要买的商品的价钱，问最多能省下多少钱。贪心，每次都选最大价值的三件去结账，这样免去的一件的价值就会高，最大值也就能求出来了。4562961 EZ_dla 3637 Accepted 924K 94MS Pascal 1214B 2009-01-18 09:58:543612 Telephone WireFarmer John要更新电话线，已知有若干根给定长度的电话线杆，增加某电话线杆长度需要费用X2（其中X是增加的长度），在相邻的电话线杆连接一条电话线需要钱C*(两杆长度差)。求连接上所有电话线杆的最小费用。这是一道非常好的Dp题。首先很容易就能列出方程：Dpi,j=minDpi-1,k+C*|j-k|+(Hi-j)2。但是这个方程显然是O(n*h*h)的复杂度，超过了题目要求的时间范围，所以我们只能考虑利用方程的特点来去除重复计算的状态。观察方程，很容易发现|j-k|相当碍眼，所以考虑从这里突破。分情况讨论：1）k=j，此时去掉绝对值号为f(i,j)=min-c*j+mindpi-1,k+c*k+(Hi-j)22）kj，此时去掉就变成了f(i,j)=minc*j+mindpi-1,k-c*k+(Hi-j)2合并即可求得f(i,j)=(Hi-j)2+min-c*j+mindpi-1,k+c*k, -c*j+mindpi-1,k+c*k。这个方程的时间复杂度通过预处理 mindpi-1,k+c*k和mindpi-1,k+c*k（时间复杂度为O(NH)）后再做的时间复杂度为O(NH)，总时间复杂度是O(NH)，符合题目时限要求。这道题给予了我一个启示：Dp的无用状态有时就可以通过这种对情况的讨论、单调性的判断减去，使变量减少，达到将时间复杂度降次的效果。4564948 EZ_dla 3612 Accepted 1304K 438MS Pascal 1473B 2009-01-18 17:01:173615 Cow Hundles给定一个图和每条边的权值，再给出若干个询问点对（x,y），求从x到y的所有路径中路径上最大值最小是多少。非常巧妙的一道题。这道题可以用很多种方法做，但是用Floyed的变种显然是最方便最容易理解的。将原Floyed方程改为Fi,j=min(Fi,j,max(Fi,k,Fk,j)即可。4562906 EZ_dla 3615 Accepted 1212K 641MS Pascal 1058B 2009-01-18 09:23:113624 Charm Bracelet给定一个容量限制的背包，若干件只能用一次的物品，求获得的最大价值。简单的背包直接做就可以，什么优化都不用加。4562912 EZ_dla 3624 Accepted 980K 297MS Pascal 807B 2009-01-18 09:27:543626 Mud Puddles给定一个矩阵，其中有若干个格子不能访问，求到达指定点的最小步数一个经典的BFS。4562917 EZ_dla 3626 Accepted 4504K 125MS Pascal 1829B 2009-01-18 09:29:533650 The Seven Percent Solution给定一个字符串，要求将其中的一些字符串按照题目给定的要求变换。直接读入字符串后判断输出即可，没有什么要注意的地方。4563046 EZ_dla 3650 Accepted 912K 16MS Pascal 1407B 2009-01-18 10:34:583664 Election TimeN头奶牛要进行选举，有两次投票（投票的票数分别都给出），第一次得票数前K个奶牛进入第二轮选举，第二轮获最多票数的奶牛胜利。直接排序后模拟扫描一次就可以了。4563111 EZ_dla 3664 Accepted 1500K 172MS Pascal 1297B 2009-01-18 11:05:243673 Cow Multiplication定义一种操作AB为A的每一位与B的每一位相乘后相加，求给出的A和B的这种操作的值。转换成字符串后直接计算。4564667 EZ_dla 3673 Accepted 912K 16MS Pascal 591B 2009-01-18 16:15:513665 iCowiCow这种新型的MP3（）有一个Shuttle模式，这个模式的定义是：1） 每首歌都有一个初始的评分Ri；2） 每首歌播完后总会播评分最大的歌；3） 当一首歌被播放完后，这首歌的评分就重新变成0，它的评分将被平均分配给其他N-1首歌；4） 如果不能平均分配，则按照第一首歌+1，第二首歌+1，第N首歌+1，第一首歌+1，这种顺序直到分数被分完为止。现在播放了T首歌，求这T首歌的播放顺序。按照定义直接模拟，注意第四条规定的处理。4564799 EZ_dla 3665 Accepted 856K 110MS Pascal 1123B 2009-01-18 16:30:333616 Milking TimeBessie有N小时可用于挤奶，而FJ有若干个“挤奶时间段”，每个挤奶时间段都有不同的开始和结束时间和价值，挤完一次奶Bessie要休息r小时，求使价值最大的方法。先对结束时间按从小到大为区间排序，然后直接DP就行了。时间复杂度是O(m2)。4565156 EZ_dla 3616 Accepted 928K 32MS Pascal 1365B 2009-01-18 18:04:253630 Phone List给出N个字符串（1=N=40000），求是否有两个字符串符合：其中一个字符串是另一个字符串的字串，且该字符串匹配的位置从开头开始。这题方法也非常多，可以用Trie等方法，但是数据范围比较小，所以直接按照字典序排序一次（这样相同前缀的字符串就会排到一起），然后对排序好的字符串两两间比较即可。4565424 EZ_dla 3630 Accepted 3376K 360MS Pascal 1484B 2009-01-18 19:39:443627 Bookshelf有若干头奶牛，每个奶牛都有一个高度，求选择一定数量的奶牛达到或超过指定的高度的最小值。直接排序，然后选择尽量高的奶牛直至超过指定的高度就可以了。4565472 EZ_dla 3627 Accepted 992K 0MS Pascal 1057B 2009-01-18 19:51:003628 Bookshelf 2同上，不过求的答案是选择奶牛使奶牛叠起来的高度既超过指定高度又要离指定高度最小。呃，这个题目数据有点弱，事实上N!的搜索完全可以过掉这题，但是实际上我认为这题应该是可以用动态规划（类似背包）的方法解出来的。4565530 EZ_dla 3628 Accepted 912K 32MS Pascal 782B 2009-01-18 20:02:503617、3623 Best Cow Line给定一个字母序列，每次选择该序列的头或尾进入新序列中，求所有能得到的新序列中字典序最小的一个。3617和3623是完全一样的题目，不同的地方仅仅是数据范围。用O(n2)的贪心算法可以解决此题，具体就是“哪边小选那边，假如两边都一样就一直往里面找直至能分出大小为止”。用后缀数组等高级数据结构可以做到O(nlgn)。4565688 EZ_dla 3623 Accepted 884K 2532MS Pascal 1429B 2009-01-18 20:37:09 4565684 EZ_dla 3617 Accepted 916K 16MS Pascal 1428B 2009-01-18 20:36:433663 Costume Party给定一个长度L和N头牛（1=N=20000）的长度，求两头牛加起来的长度小于等于L的组数。首先显然要先排序，然后我们可以用O(nlgn)的二分查找或者O(n)的线性扫描来计算出组数。其中，O(n)的线性扫描具体做法是指定两个指针（一头一尾），对于头指针，通过尾指针找到一个最大能符合条件的牛，则Ans+=尾指针-头指针，再移动头指针直至头尾相遇。4565755 EZ_dla 3663 Accepted 932K 16MS Pascal 1175B 2009-01-18 20:50:24本日小结：2009-1-193636 Nested Doll给定若干个娃娃，问能一个套一个的福娃的最多数量。Dliworth定理应用。之前有讨论过的题目，跟Tju2936完全一样。4566771 EZ_dla 3636 Accepted 1228K 141MS Pascal 2452B 2009-01-19 08:26:143652 Persistent Bits有一个初始值S，要求根据一个给定的数列发生器(A*X+B)%C，生成一个序列，求该序列转换成2进制后有变过的位置。比如说3经过变换得到11，则二进制为0011和1011，则最终得出的答案为?011。直接模拟，注意若干次变换后必定会重复产生某一个数，但是不一定是产生初始的S。4567468 EZ_dla 3652 Accepted 976K 32MS Pascal 1332B 2009-01-19 12:59:323668 Game of Lines给定若干个点，求两点连成的直线且两两间不平行的集合的大小。这道题数据比较弱，怎么做都行，最简单的自然就是计算出斜率，然后排序一下，有多少个不重复的就是答案了。4568004 EZ_dla 3668 Accepted 1116K 63MS Pascal 1570B 2009-01-19 15:13:303660 Cow Contest若干头牛举行比赛，给出若干个关系“A比B好”，求能确定关系的牛数。考虑一头牛能被确定的情况是什么？是所有牛与它的关系都清楚了。所以，我们按照关系建图后做传递闭包，然后判断所有点对某个点是不是相连，如果是则+1.4568203 EZ_dla 3660 Accepted 864K 47MS Pascal 1087B 2009-01-19 16:03:383669 Meteor Shower有若干颗流星（1=M=头的高度才可以砍掉龙的头。已知雇佣一个骑士的价格=他的身高，求能干掉巨龙的最小价格。贪心就可以了。排序，然后尽量让接近头的高度的骑士干，这样既省钱又防止砍不死龙详细证明略。4568509 EZ_dla 3646 Accepted 1012K 0MS Pascal 1901B 2009-01-19 17:07:083659 Cell Phone Network给一棵树，可以在节点建手机站，每个手机站能够覆盖与其相连的所有结点，求最少需要多少个手机站。经典的TreeDp，分4种状态讨论：1） 该结点选，该结点的父亲选2） 该结点选，该结点的父亲不选3） 该结点不选，该结点的父亲选4） 该节点和其父亲都不选设Dpv,i,j表示v结点自己状态是i，父亲状态是j，则状态转移也很好写出来了。4569702 EZ_dla 3659 Accepted 1456K 63MS Pascal 2051B 2009-01-19 22:04:343670 Eating Together3671 Dining Cow 第i头奶牛有一张标明她用餐批次D_i(1 = D_i = 3)的卡片。虽然所有N(1 = N = 30,000)头奶牛排成了很整齐的队伍，但谁都看得出来，卡片上的号码是完全杂乱无章的。 在若干次混乱的重新排队后，FJ找到了一种简单些的方法：奶牛们不动，他沿着队伍从头到尾走一遍，把那些他认为排错队的奶牛卡片上的编号改掉，最终得到一个他想要的每个组中的奶牛都站在一起的队列，例如111222333或者333222111。哦，你也发现了，FJ不反对一条前后颠倒的队列，那样他可以让所有奶牛向后转，然后按正常顺序进入餐厅。 你也晓得，FJ是个很懒的人。他想知道，如果他想达到目的，那么他最少得改多少头奶牛卡片上的编号。所有奶牛在FJ改卡片编号的时候，都不会挪位置。3671是3670的情况缩减、范围缩小版，在这一并讨论。我们只考虑单调上升的情况，因为只有0、1、2三个状态，所以我们可以分别对这三个状态是否修改进行讨论，由于单调上升，所以我们只加不减。实现时，只需实现上升或下降一边即可，另外一边只需要把序列倒过来做一次就OK。4569823 EZ_dla 3670 Accepted 1408K 0MS Pascal 1284B 2009-01-19 22:41:174569866 EZ_dla 3671 Accepted 1264K 63MS Pascal 1181B 2009-01-19 22:50:093661 RunningBessie要制定一个跑步计划，他有N分钟的限制，每跑一分钟能前进的距离是Di米，疲惫度+；他也可以停下来休息，每休息一分钟疲惫度-。在它跑步结束时，他的疲惫度要为0.他的疲惫度在整个阶段都不能超过M。求最远能跑到的距离。也算是一道比较简单的DP了。设FI,j表示第i分钟j的疲惫度，能跑到最远距离。再讨论一下超过M的情况，就可以写出Dp方程了。这题显然可以滚动，但是也可以直接开数组，一千万的数组不会超内存（但是开到三千万就会OTL）4570070 EZ_dla 3661 Accepted 36276K 657MS Pascal 1339B 2009-01-19 23:43:332009-1-203666 Making the Grade给定一个序列，求变成最长不上升/不下降所需要的代价。代价=|A1 - B1| + |A2 - B2| + . + |AN - BN |。有一个非常强大的结论：变换后的新序列的所有数字都会在旧数列出现。具体的证明可以用中值加反证法证明，不再详写。然后就可以直接Dp了。Dpi,j表示第i个数变成j后总最小的代价，则显然有Dpi,j=min(Dpi-1,j+abs(Ai-Vj),Dpi,j-1);另外，05年黄源河的论文有介绍这题用左偏树的做法。4572166 EZ_