a tutorial on computer science

     摘要: 據(jù)說不作此題人生不完整。好吧。很久以前就做過了，寫過BFS，A*，和雙搜。A*用了200+ms,汗，BFS都比他快。正好這幾天在看搜索估價(jià)函數(shù)之類的東西，就把這道經(jīng)典題拿出來，再做一遍，突然發(fā)現(xiàn)，估價(jià)函數(shù)+迭代加深搜索就是IDA*算法，好吧。以前傻傻看黑書的時(shí)候，理解不了A* ，覺得巨麻煩（現(xiàn)在也覺得挺麻煩），現(xiàn)在寫起來IDA*，覺得還挺簡(jiǎn)潔，并且比較通用，而且這玩意又好寫又比較通用，就詳細(xì)研究了一下。看了別人的一個(gè)IDA*的算法，覺得寫的很簡(jiǎn)潔很工整，就參詳了一下，然后改造成了自己的，A掉了1077題。樓教主寫的那個(gè)百度之星的版本的Allyes.com，還沒有詳細(xì)看，覺得有點(diǎn)復(fù)雜。有機(jī)會(huì)要好好研究下。  閱讀全文

     摘要: 題目鏈接在這里http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1026
題意很簡(jiǎn)單：從起始點(diǎn)開始走，最多可以走K步，只能向左，向右，向前走，地圖上有一些豆豆，問你最多可以吃到多少豆豆。其實(shí)這個(gè)題可以這么看，每?jī)蓚€(gè)豆豆之間的最短距離是固定的，我們的目的是吃豆豆，不是來玩的，所以就是一個(gè)最短哈密頓路徑問題，當(dāng)然題目有一些限制。上篇博客里寫的那個(gè)用一條鏈把N個(gè)點(diǎn)串起來，求最短長(zhǎng)度問題和這個(gè)問題是類似的，但是那個(gè)題作者給出了一個(gè)DP解法，我表示很疑惑。如果看懂了作者的那個(gè)辦法，這個(gè)題就瞬秒了。上一篇在這  閱讀全文

     摘要: 這幾天在做搜索，看到一篇比較好玩的論文，估價(jià)函數(shù)在信息學(xué)競(jìng)賽中的應(yīng)用。發(fā)現(xiàn)有點(diǎn)難懂。好了，第一道就是uva10605。
題意就不廢話了。這題我剛剛看到作者列舉了下暴力時(shí)候深度為1-17的時(shí)候搜索的次數(shù)，我也很傻很天真的寫了個(gè)暴力。我是枚舉不定次數(shù)個(gè)邊界，然后找最小值。程序就一直在那兒搜，還沒用迭代加深搜索。。。傻傻寫了半小時(shí)。結(jié)果這種暴力中的最暴力需要的節(jié)點(diǎn)數(shù)太驚人了。然后就。。卡住了。  閱讀全文

     摘要:   閱讀全文

     摘要:   閱讀全文

     摘要:   閱讀全文

     摘要:   閱讀全文

     摘要:   閱讀全文

     摘要:   閱讀全文

     摘要:    hash算法一直被我認(rèn)為成一種處理大數(shù)據(jù)量的高效算法(時(shí)間復(fù)雜度)。   從一道百度面試題開始。    搜索引擎會(huì)通過日志文件把用戶每次檢索使用的所有檢索串都記錄下來，每個(gè)查詢串的長(zhǎng)度為1-255字節(jié)。    假設(shè)目前有一千萬個(gè)記錄（這些查詢串的重復(fù)度比較高，雖然總數(shù)是1千萬，但如果...  閱讀全文