天天看點

關于模拟題的一些弱雞總結

關于模拟題的一些弱雞總結

首先要感謝某位不知名大佬(當時沒關注部落格事後找不到了。。。)給了我很大的啟發,然後本弱雞在此寫一下關于模拟題的一些個人見解(大佬求輕踩_(:з」∠)_)。

衆所周知,模拟題在ACM比賽中主要屬于簽到或銅牌層次的題,銀牌模拟題并不多見。模拟題考點主要在思路,代碼能力以及細節應對能力,而這幾項在銀牌題中大多由構造題來考查。構造題就是另一種東西了,構造題比模拟題費腦子多了我這個弱雞就不摻和了。

模拟題的考點分析下發現其實就一個——細節。因為考慮下什麼是所謂的代碼能力?打比賽的隊伍肯定有一個寫代碼能力最強的代碼手,各隊之間的代碼手的能力或許有差距,但其實都遠超過了模拟題的要求了。無非就是有的大佬STL用的更NB一點,但ACM模拟題涉及到的東西都是大家都會的,沒聽說過什麼模拟題是必須要會某個STL才能過的。這裡的代碼能力其實說的是寫代碼的習慣問題。寫過項目的肯定都明白,寫的時候甯可多一倍工作量也要把代碼寫的粗淺簡約,注釋絕對不會少加,否則一旦出BUG基本上就等着重寫吧(因為重寫比DEBUG快多了)。當然,我不是說比賽時代碼要寫的跟項目一樣,畢竟比賽差一秒可能就是兩種牌了,但根據個人能力适度調整寫代碼的規範程度絕對是有幫助的,尤其是對于模拟題來說。至于思路就更明顯了,模拟題的思路其實就是“如何去實作”,思路的第一步是先确定一個可行的宏觀的做法,但大多模拟題的做法都有很多,這就衍生了第二步——優化思路,使你的思路更容易實作,這也是我這篇總結的主要内容。到這裡我們可以發現其實更優的思路和更強的代碼能力所産生的好處就是使你需要考慮的細節更少。這也是很多人不明白為啥一道題這麼多隐藏細節需要考慮大佬卻總是能在幾分鐘就寫完還一發AC,一方面是大佬見多識廣啊,其次很多時候大佬的方法或者方法實作與我們不一樣,根本不會産生那些問題或者可以規避掉這些坑點。

模拟題雖然多種多樣沒有模闆可以一篇概全,但也不是無迹可尋,程式是服務于需求這一主旨在模拟題上展現的最是淋漓盡緻。很多模拟題的背景以及要求都是我們生活中遇到過的功能,甚至“模拟四個人打麻将”這種功能我們也能在麻将遊戲中用到。是以模拟題其實有很多類似的可以劃分為一類,進而根據分類可以總結出針對的模闆思路,以下就是我個人總結的一點思路。

1:單詞型。

這一類模拟題的要求是對一些一段一段的被分隔符分開的字元串進行處理。典型的就是給你篇文章讓你對其中的句子或單詞進行各種處理,這種的分割符往往是空格,逗号和句号。有時候給你的是整個長串,這種你往往可以通過標明某個字元為分隔符或者手動添加來進行分割。這類題的思路一般是先把“單詞”提取出來,然後按照題目要求進行處理,最後再按照要求拼接回去。因為這類題中可處理的目标一般就兩種——單詞和分隔符,而提取和合并的過程都不容易出錯,對單對象處理也不容易出錯,是以這樣寫可以減少很多邏輯和代碼的細節錯誤。

例題:Gym - 101190A Abbreviation

2:多機關型。

這一類模拟題背景往往是許多機關(不一定是人)在某些規則下進行活動,要求往往是輸出最後或者中間某階段的各機關狀态或活動結果。典型的就是幾個人在一起玩遊戲,告訴你初始狀态讓你模拟出最後誰赢了。這種題的思路一般是把每個機關都獨立化每個機關都是獨立的個體,每個機關相關的資料都用一個單獨的結構體或者數組儲存,每個機關的行動也要獨立考慮。然後根據題目的背景我們可以建立各機關間的影響關系,這時候要考慮的一般主要是兩點——目前機關進行行動會對哪些機關産生影響,有哪些機關會影響目前行動的機關。簡單一點的題中各機關對各機關的影響都是對稱的,稍難一點的題中各機關對各機關的影響往往是不對稱的甚至是會變化的。

例題:2018ICPC北京網絡賽C題 Cheat

3:資料結構 and STL型。

這一類模拟題背景和功能描述往往非常接近某種資料結構或者STL。這種題的思路一般是我們在對應的資料結構或者STL的基礎上再去修改往往更加簡單明了。

例題:HihoCoder - 1383 北京賽區(2016)網絡賽——The Book List

4:其他。

如果是要求比較簡單明顯的模拟題大家肯定都會,如果遇到有些感覺很複雜難以理清關系的模拟題,那麼可以嘗試直接暴力實作。典型的就是涉及某種語言的程式的運作,出題人肯定不會指望每個出題人都是能開發一種語言的巨巨,這種時候我們直接暴力實作加上暴力判斷往往就能過。

例題:2018青島ICPC網絡賽C題 Halting Problem

本人一弱雞,不敢說什麼做遍模拟題,模拟題有很多,這上面隻是我個人見的模拟題中比較多的幾類,有其他類的靠大佬們來總結了。

(最後高喊:蘿莉百合賽高~!♪(^∇^*))

關于模拟題的一些弱雞總結

繼續閱讀