博文

pku题目类型划分(4)(2005-09-08 04:27:00)

摘要:算法入门(简单题)
1000 1003 1004 1005 1006 1007 1015(学会dp) 1016 10171018 1042(dp) 1046(简单数学) 1054(简单的剪枝) 1062(dp) 1068
1095 1113(凸包,但规模小,O(n^2)的也行)1125112711521154
1183(用笔算算)1218 1221 1244 1281 1312 1313(找找规律)
1315(学会搜索) 1321(同1315) 1323(dp)1326 1331 1491
1493(找规律) 1503(高精度) 1504 1517 1519 1547 1552
1563(考虑仔细一点,还要注意精度) 1650(不是好题) 1651(dp) 1656
1657 1658 1663 1675(计算几何) 1681 1702(三进制运算) 1799
1828 1862(简单数学) 1887 1906(实战好题) 1914 1915(宽搜)
1928 1936 1978 1979 2000 2019(dp好题) 2027(垃圾题) 2028
2078(不要重复搜索) 2080 2081 2083 2140 2141 2184(活用dp)
2190 2192 2193 2196 2199 2209 22112243 2248(搜索)
2260 2261 2262 2291 2301 2304 2309(找规律) 2316 2317
2318 2325 2355 2357 2363 2378(树的dp) 2381 2385 2393
2394 2395 2413(高精度基础) 2418 2419

经典
1011(搜索好题)
1012(学会打表)
1013
1019(它体现了很多此类问题的特点)
1050(绝对经典的dp)
1088(dp好题)
1157(花店,经典的dp)
1163(怎么经典的dp那么多呀???)
1328(贪心)
1458(最长公共子序列)
1647(很好的真题,考临场分析准确和下手迅速)
1654(学会多边形面积的三......

阅读全文(4775) | 评论:0 | 复制链接

pku题目类型划分(3)(2005-09-08 04:26:00)

摘要:部分题目分类统计:

网络流:
最大流:
1087 a plug for UNIX
1149 PIGS
1273 drainage ditches
1274 the perfect stall
1325 machine schedule
1459 power network
2239 selecting courses
最小费用最大流:
2195 going home
?2400 supervisor, supervisee

压缩存储的DP
1038 bugs integrated inc
1185 炮兵阵地
2430 lazy cow

最长公共子串(LCS):
1080 human gene functions
1159 palindrome
1458 common subsequence
2192 zipper

凸包
1113 wall
2187 beauty contest

......

阅读全文(3992) | 评论:0 | 复制链接

pku题目类型划分(1)(2005-09-08 04:24:00)

摘要:排序 1002(需要字符处理,排序用快排即可) 1007(稳定的排序) 2159(题意较难懂) 2231 2371(简单排序) 2388(顺序统计算法) 2418(二叉排序树)

回溯搜索:1979(和迷宫类似) 1980(对剪枝要求较高)

数学计算简单(或不值得做的题):1003 1004 1005 1068 1326 1656 1657 1658 1663 1922 1978 2000 2013 2014 2017 2070 2101 2105 2140 2190 2272 2301 2405 2419
中等:1006(中国剩余定理) 1323 1969 2015(解密码) 2081(预处理) 2085(找规律)
难:1014 1037 1147 2082(这些是上课讲的)

高精度计算:1001(高精度乘法) 2413(高精度加法,还有二分查找)

历法:1008 2080 (这种题要小心)

枚举:1054(剪枝要求较高) 1650 (小数的精度问题)

数据结构的典型算法:1125(弗洛伊德算法) 2421(图的最小生成树)

动态规划:1163(经典题)

贪心:1328 1755(或用单纯形方法) 2054

模拟: 1281 1928 2083 2141 2015

递归: 1664
字符串处理:2121 2403

......

阅读全文(5896) | 评论:1 | 复制链接

pku题目类型划分(2)(2005-09-08 04:24:00)

摘要:简单、模拟题:
1001 Exponentiation 、
1002 487-3279、
1003 Hangover 、
1701 Dissatisfying Lift、
2301 Beat the Spread!、
2304 Combination Lock、
2328 Guessing Game、
2403 Hay Points 、
2406 Power Strings、
2339 Rock, Scissors, Paper、
2350 Above Average、
2218 Does This Make Me Look Fat?、
2260 Error Correction、
2262 Goldbach\'s Conjecture、
2272 Bullseye、
2136 Vertical Histogram、
2174 Decoding Task、
2183 Bovine Math Geniuses、
2000 Gold Coins、
2014 Flow Layout、
2051 Argus、
2081 Calendar、
1918 Ranking List、
1922 Ride to School、
1970 The Game、
1972 Dice Stacking、
1974 The Happy Worm、
1978 Hanafuda Shuffle、
1979 Red and Black、
1617 Crypto Columns、
1666 Candy Sharing Game、
1674 Sorting by Swapping、
1503 Integer Inquiry、
1504 Adding Reversed Numbers、
1528 Perfection、
1546 Basically Speaking、
1547 Clay Bully、
1573 Robot Motion、
1575 Easier Done Than Said?、
1581 A Contesting Decision、
1590 P......

阅读全文(4614) | 评论:0 | 复制链接

pku(1080)(2005-09-08 04:16:00)

摘要:/*1080
观察题目给出的一个最优解:
AGTGATG
-GTTA-G
将其从某一处切开,如果左边部分的分值不是最大,那么将其进行调整,使其分值变大,
则整个解分值变大,与已知的最优矛盾。所以左边部分的分值必是最大。
同理,右边也是。可见满足最优子结构的性质。考虑使用DP:

设两个DNA序列分别为s1,s2,长度分别为len1,len2,score为分值表。
f[i,j]表示子串s1[1..i]和s2[1..j]的分值。考虑一个f[i,j],我们有:

  1.s1取第i个字母,s2取“-”:f[i-1,j] + score[s1[i],'-']

  2.s1取“-”,s2取第j个字母:f[i,j-1] + score['-',s2[j]]

  3.s1取第i个字母,s2取第j个字母:f[i-1,j-1] + score[s1[i],s2[j]]

  即f[i,j] = max(f[i-1,j] + score[s1[i],'-'], f[i,j-1] + score['-',s2[j]], f[i-1,j-1] + score[s1[i],s2[j]]);

然后考虑边界条件,这道题为i或j为0的情况。
当i=j=0时,即为f[0,0],这是在计算f[1,1]时用到的,根据f[1,1] = f[0,0] + score[s1[i], s2[j]],明显有f[0,0] = 0。
当i=0时,即为f[0,1..len2],有了f[0,0],可以用f[0,j] = f[0,j-1] + table['-',s2[j]]来计算。
当j=0时,即为f[1..len1,0],有了f[0,0],可以用f[i,0] = f[i-1,0] + table[s1[i],'-']来计算。

至于计算顺序,只要保证计算f[i,j]的时候,使用到的f[i-1,j],f[i,j-1],f[i-1,j-1]都计算出来了就行了。
所谓划分阶段也就是为了达到这个目的。这样我们使用一个二重......

阅读全文(3478) | 评论:0 | 复制链接