ezdlapoj解题报告

1、寒假作业 情况&解题报告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的问题即可。455

2、8942 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

3、则发生变化的地方只有三个地方，如果要同时消除三个“不符数对”，则要求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:47360

4、2 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商场举行“买二送一”的活动，其中的“一”是三件商品最便宜的一件。给出若干件要买的商品的价钱，问最多能省下多少钱。贪心，每

5、次都选最大价值的三件去结账，这样免去的一件的价值就会高，最大值也就能求出来了。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

6、)=(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 2

7、009-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头奶牛要进行选举，有两次投票（投票的票数分别都给出），第一次得

8、票数前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），求是否有两个字符串符合：其中一

《ezdlapoj解题报告》由会员自***分享，可在线阅读，更多相关《ezdlapoj解题报告》请在金锄头文库上搜索。