Posted on 2007-02-20 13:46
oyjpart 閱讀(1447)
評(píng)論(9) 編輯 收藏 引用 所屬分類:
ACM/ICPC或其他比賽
躊躇滿志,遙望山頂--開始上路
The Counting Problem Accepted 2-20 2Y的 WA一次因?yàn)闆]考慮1位數(shù)的特殊情況 這是一道簡(jiǎn)單題 但是需要細(xì)心 Y掉他！
Always On the Run Accepted 2-20 階段明顯的DP 每一階段直接更新地圖即可
Video Surveillance Accepted 2-20 原這個(gè)題目要想寫的復(fù)雜可以很復(fù)雜(比如我的) 要想寫的簡(jiǎn)單 可以很簡(jiǎn)單(看了10小川的代碼 orz) 其實(shí)只用在轉(zhuǎn)角處直接限定可放置Video范圍就可以了 而限定也可以簡(jiǎn)化 比如向上的墻只需要限定可選范圍的左端
Jugs Accepted 居然死廣搜就可以過...比賽的時(shí)候我還按數(shù)學(xué)方法遞推來著...真郁悶
City Game Accepted 上->下DP過的
Calendar Game Accepted 2-20 簡(jiǎn)單的博弈樹(有無數(shù)學(xué)方法?) 只需判斷先手是否能獲勝 根據(jù)題意構(gòu)建博弈樹 一次DP或記憶化搜索即可
John's trip Accepted 2-21 MS聽說要轉(zhuǎn)化的？我用DFS的Euler求法過的
從零開始 踏上山腳--真正的旅程
Dividing Accepted 搜過去的 正解是DP
Closest Common Ancestors Accepted 用的是LCA的tanjar算法 注意輸入x，x的情況只加入一次詢問（這種算法是從下到上合并 簡(jiǎn)單的邏輯推理+并查集）
Frame Stacking
Piggy-Bank Accepted 很明顯的背包
Code the Tree Accepted 看明白題意 直接模擬就可以了 輸入有點(diǎn)煩
Square Ice 模擬題 不想做...
千辛萬苦 收獲頗豐--漸入佳境
1011 Accepted 絕對(duì)經(jīng)典的搜索強(qiáng)剪枝
1018 Accepted 簡(jiǎn)單題
2662 Accepted 2-27 1.Dijkstra或者Bellman-Ford確定每個(gè)定點(diǎn)的距離標(biāo)號(hào) 2.對(duì)所有點(diǎn)進(jìn)行排序 按照距離標(biāo)號(hào)從大到小進(jìn)行DP
1568 Accepted 3-2 極大極小搜索+Alpha-Beta剪枝
1036
1038
1042 Accepted 2-17簡(jiǎn)單題 直接枚舉結(jié)束湖泊+貪心選擇就可以了因?yàn)榧?xùn)的時(shí)候這個(gè)題目莫名WA 故再A一遍 以解心頭之恨！
1050 Accepted 簡(jiǎn)單題
1088 Accepted 排序+記錄（可以看成DP么？哈哈）
1093
1096
1112
1117
回望四周 云霧繚繞--勇敢前行
1155 Accepted 2-16 如果能做Apple Tree 相信就能做這題 父結(jié)點(diǎn)狀態(tài)由子結(jié)點(diǎn)從左到右DP后的結(jié)果決定 逐子樹合并
1156
1157 Accepted 簡(jiǎn)單DP IOI很少有這么簡(jiǎn)單的題目了 呵呵
1159 Accepted 簡(jiǎn)單題
1160 Accepted 典型的DP 階段很明顯
1163 Accepted 簡(jiǎn)單DP
1170
1185
1190
1191
1195
1200
1221
1338 Accepted 簡(jiǎn)單隊(duì)列維護(hù)
1416
脫離險(xiǎn)境 笑看風(fēng)云--無愧于心
1458 Accepted2-16 這個(gè)題目有問題么？用cin就錯(cuò)！用scanf就對(duì)。。害我WA。。
1523 Accepted2-15求割點(diǎn) DFS求subnet 注意 數(shù)據(jù)有點(diǎn)faint 點(diǎn)不是相連的
1579
1631 Accepted DP+Greedy
1632
1639
1651
1659
1680
1683
1691
1703 Accepted 并查集（可以建立一個(gè)敵人的對(duì)應(yīng)關(guān)系 這樣隊(duì)后續(xù)的判定很方便）
藝術(shù)使者 靈魂主人--心靈之旅
1709
1714
1753
1769
1771
1826
1855
1856 Accepted2-15搜索（搜索方式：可以向右向下搜得到覆蓋區(qū)域，檢查內(nèi)部是否全部為#，再檢查環(huán)繞一圈是否全部為.即可）注意相遇corner仍然算Bad 比如
.#
#.
1890
見證生命 每一分鐘--For the loved ones
1924
1935
1944
1945
1946
1947
1948 Accepted2-15由于數(shù)據(jù)量不大 利用可行性的狀態(tài) 進(jìn)行DP Heron公式
搜索也能過 呵呵 需要預(yù)先找到一個(gè)較好解 大->小搜 加一定的剪枝
1949
這才是我真正的舞臺(tái)！-- Go For it！
1950
1951
1952
1979
1980
2170
2288
2331
2339 Accepted 3-4 簡(jiǎn)單題
解開面紗 最后決戰(zhàn)--看看山頂上的風(fēng)景
2340
2486 Accepted 3x to magicpig 在treeDP中 如果結(jié)點(diǎn)的多個(gè)子結(jié)點(diǎn)既相互分離 又存在狀態(tài)表示中的局部聯(lián)系 采用從左到右和并的方式是很好的
2492
2524 Accepted 直接用并查集就OK
2540
2761
2777 Accepted 線段樹 比較好的做法是用2進(jìn)制壓縮存儲(chǔ) 也可以不用 直接記錄顏色是否采用
1012 Accepted 打表
1013 Accepted 2-16 24情況枚舉 簡(jiǎn)單題
1019 Accepted 分段統(tǒng)計(jì) 先位數(shù)在尾數(shù)再位置 我最惡心這類題了
1647
1654
1655 Accepted 最簡(jiǎn)單的treedp --alpc01
1804 Accepted 逆序?qū)?我見過比較好的算法是 1.歸并排序中記錄逆序?qū)?2.線段樹
2084
回望歷史 欣然笑過--路在心中
2187
2195
2242
2295
2353
2354
2362 Accepted 暴搜的簡(jiǎn)單題
2411 Accepted 狀態(tài)DP的經(jīng)典教材
3131
風(fēng)景這邊獨(dú)好--永遠(yuǎn)學(xué)習(xí)！
Feedback
為什么你可以做題目，而我現(xiàn)在要一天到晚寫那個(gè)BT網(wǎng)站哦……
55555555555555555555555555555……………………
為什么你可以寫網(wǎng)站，而我現(xiàn)在要一天到晚寫這個(gè)BT題目啊……
55555555555555555555555555555……………………
這位不知名的大牛，你好
我是一名普通的高二學(xué)生，現(xiàn)在正在準(zhǔn)備信息學(xué)竟賽。
pku1018已經(jīng)纏了我好久，請(qǐng)你幫幫忙，只要告訴我思路就好。
你可以以回復(fù)的形式告訴我，我會(huì)常來這里看你是否解答。
你也可以給我發(fā)郵件 我的郵箱是 hnaygy1990@163.com
先謝謝你啦。
你可以枚舉那個(gè)Mininum 帶寬 然后把其他的排序 選擇比較小的 呵呵
如果需要代碼我可以發(fā)郵件給你
看到你的回復(fù)我感到十分激動(dòng)，再次對(duì)你的幫助表示感謝。
疑問：假設(shè)當(dāng)前我枚舉的最小寬帶為b0。我對(duì)于每一個(gè)裝置都選其寬帶大于b0且價(jià)格最小的方案。這樣可以得到系統(tǒng)寬帶不小于b0時(shí)的最小價(jià)格。但這樣的話不能保證系統(tǒng)寬帶就是b0。這時(shí)候需要在找到確切的最小寬帶。那么上述對(duì)于枚舉為b0是的時(shí)間復(fù)雜度是a=n*m*n。枚舉量要b<m*n。那么總的時(shí)間復(fù)雜度要a*b*t，可能超時(shí)。（描述中m是m[i]（1<=i<=n）的平均值）
如果你能把標(biāo)程給我的話，那我就很猥瑣的受下啦。
希望你能解釋這個(gè)疑問，
然后...(說不出口啊...唉，減rp嘍)請(qǐng)你把標(biāo)程發(fā)給我吧。
哦，對(duì)啦，還有一個(gè)疑問，為什么很多人都說這是一道dp題呀？
（我最近正在自己找dp題以強(qiáng)化訓(xùn)練，開始還順利，卻被這題卡住啦）
枚舉的帶寬實(shí)際上是有限制的，也就是說只需要枚舉數(shù)據(jù)中給出的帶寬（100＊100）個(gè)就可以了。然后每個(gè)機(jī)器都選擇在這個(gè)帶寬之上的最小費(fèi)用。也就是枚舉之后每個(gè)機(jī)器需要遍歷廠商一次，所以總復(fù)雜度是100＊100＊100＊100，的卻會(huì)超時(shí)。但是可以對(duì)上述算法做一些簡(jiǎn)單的優(yōu)化。就是說，枚舉帶寬的時(shí)候，其實(shí)要保證帶寬對(duì)于每個(gè)機(jī)器都是又相應(yīng)的廠商的，也就是說如果枚舉之前可以先去掉相當(dāng)多不需要枚舉的帶寬。也就是說每句的帶寬的下界變成了每個(gè)機(jī)器在不同廠商下的最小帶寬的最大帶寬，上界也有類似的變化。這個(gè)時(shí)間復(fù)雜度下的卻可能超時(shí)，不過你可以試驗(yàn)下這個(gè)優(yōu)化的效果。
我剛剛在oibh得到了標(biāo)程，
http://www.oibh.org/bbs/viewthread.php?tid=17328&pid=194920&page=1&extra=page%3D1#pid194920
(忘啦告訴你，我現(xiàn)在使用pascal語(yǔ)言)
在我對(duì)這題的苦苦求解中遇到一個(gè)人的bolg與你分享：
http://mrroach.blog.hexun.com/9013336_d.html
他應(yīng)該是noip或noi的選手吧。
和你交流真的很愉快，不過我想我要暫時(shí)說再見啦。
如果這次noip我能拿到一等講的話，我會(huì)轉(zhuǎn)c++。那時(shí)我們會(huì)再“見面”的。
（只是如果）
就這樣吧，謝謝你的幫助啦。