藍橋杯突擊特訓
大家平時主要訓練都是ICPC這樣的ACM賽制,而藍橋杯的OI賽制不同之處主要是:
1.看不到代碼運行結果且按照最后一次提交來算
2.每個題每個測試點都有相應的得分
對此給大家介紹兩種騙分技巧:記憶化搜索和打表
記憶化搜索
普通的暴力搜索(dfs bfs)往往會出現大量重復搜索,因此會浪費大量時間和空間,因此面對我們寫不出來的dp,可以使用記憶化搜索混分甚至AC
以2021藍橋省賽-李白打酒 為例:
本題顯然需要dp,但是我太菜了寫不出dp,那么我們一般會寫個dfs暴搜混分
然而dfs當數據略大就會爆,所以需要記憶化搜索來減少無效的搜索
記憶化搜索,即每次搜索后將當前結果存入數組,如果再搜到本位置不需要再次搜索,直接查表即可
打表
那么會不會出現我們就是不會做的題呢?答案是幾乎一定會有的,那么面對這樣的題目,我們往往會寫個暴力直接跑路,但這樣混分顯然太虧,于是在范圍不大時我們可以選擇打表優(yōu)化
以21級某次考核題為例:
我們一眼看出fake思路:記錄斜率是否被訪問過,然后遍歷找出所有被訪問了的斜率
然后結果:tle

于是我們觀察,發(fā)現這題每組樣例都是輸入一個數,輸出一個數
那么我們可以選擇先跑出結果然后直接查表,這就是打表

可以看出我們的解法:暴力跑完答案,然后把答案直接存進一個數組之后查表
這兩個都是面對不會題目的奇技淫巧,不建議在這上面耽誤太多時間,還是要將更多時間投入到賽時自己會的題目上