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