目錄
- JZOJ.1747【NOIP2014模擬11.5】無窮迷宮
- 比賽時
- 之后
- 總結
- JZOJ1478.【NOIP2014模擬11.5】近似乘積
- 比賽時
- 之后
- 總結
- JZOJ3926. 【NOIP2014模擬11.5】開關燈
- 比賽時
- 之后
JZOJ.1747【NOIP2014模擬11.5】無窮迷宮
比賽時
比賽時沒多想，隨便打了一個BFS，把迷宮復制成五份——上下左右中，然后跑BFS，如果能從1個S跑到另1個S，就可以無盡走下去否則不可以，WA30，
之后
其實，有一種特殊情況沒有考慮例如下面這個：
##.#######.#
#..#......S#
#.#..#######
..#.###.....
##..##..####
#..##..#####
..##..#.....
###..##.####
##..#...####
#..##.######
..##..####..
##...#####.#
我們發現，如果按照我的方法復制5份，是無法到達另一個S點的，但是在下面多復制幾份，就發現可以，正解：也是BFS，可以無盡走下去就說明出現了環（相對位置——小矩陣，形成的環，也就是說相對位置形成的以S點路徑上有兩個相同的點），而且絕對位置——大矩陣不出現重復，由于相對位置不同的點只有\(NM\)個所以時間復雜度為\(O(Tnm)\)，這個正解我現在還沒看太懂，呵呵呵
總結
手模很有用，可以出一些坑的資料來測驗程式，做題時要仔細想清楚特殊情況！！！
JZOJ1478.【NOIP2014模擬11.5】近似乘積
比賽時
我最討厭這種數學題，尤其是這種涉及到優化回圈的數學題，很顯然，如果不加優化地列舉\(x\),\(y\),\(z\)，會在\(40\)～\(70\)分左右，于是決定先干完T3再回來打暴力，可惜：最后沒來得及，
之后
這題的做法同學們有兩個
-
同樣是列舉\(x\),\(y\),\(z\)，但是要加上一些判斷條件來優化，第一個——\(x*x*x<=n\)，因為我們列舉的時候是\(x \leq y \leq z\)，而\(x*x*x>n\)的時候，當前\(x\)的最優答案必定是\(x*x*x\)，后面兩重回圈列舉的頂多相等或是越來越大，差值也就越來越大，第二個——\(x*y*y \leq n\)，其實這個式子和上面的原理是差不多的，所以說，這個方法的上限時間復雜度是\(O(\sqrt[3]{n}*\sqrt{n}*n)\)，但實際上會小很多，可以過（不只是資料太水還是演算法本身夠快，有興趣打大佬可以來仔細算算時間復雜度）
-
這是一個穩定的演算法，雖然實際時間沒有上面的快，處理出一個\(B\)陣列，表示可用的數字，范圍是\(1\)～\(n\)，再加上第一個\(>n\)且可用的數字，兩重回圈列舉\(x\),\(y\)（當然是在\(B\)里面列舉），保證\(x<=y\&\&x*y \leq n\)，然后二分求出第一個使得\(x*y*z \geq n\)的\(z\)，那么答案有可能是\(z\)，也有可能是\(z-1\)，判斷一下即可，還需要注意的是這里求出的\(z\)有可能比\(x\)或\(y\)小，時間復雜度的上限是\(O(\sqrt n*n*\log_2n)\)，同樣的，我們也可運用上面的判斷條件加以優化，上限即\(O(\sqrt[3] n* \sqrt n*\log_2n)\)，看起來超快？實際我們求\(B\)陣列也需要一些時間最多是需要\(2000000\)（如果人家故意卡你的話），\(O(\sqrt[3] n* \sqrt n*\log_2n*2n)\)，這才是真的！！！當然，這個演算法可以過！！！
總結
看到我最討厭的這種題，也不要灰心喪氣，可以從中找出一些優化的方法，拿高分就不在話下了，
JZOJ3926. 【NOIP2014模擬11.5】開關燈
比賽時
我老以為這題很難，在哪兒又想DP又想網路流，最后沒想到，打了個暴力——統計每一列0的個數（初始狀態和期望狀態都要），對于每一列判斷是否相等或者與期望狀態這一列的0的個數相加等于\(n\)，如果相等直接跳過，相加等于\(n\)就按一下按鈕，如果兩個條件都滿足，就遞回按或不按，到遞回出口時，\(n*nl\)的暴力看一下兩行交換是否能達到最終狀態，
之后
這題可以用二進制來做，對于每行用一個\(long \ long\)來存，我們列舉原本狀態的第一行與目標狀態的第幾行匹配，異或代表這兩行的數，得到一個數\(c\)，每\(i\)位為1就表示第\(i\)列要按，否則不按，然后把原本狀態的每行異或一下這個數，這樣就可以求出按后的狀態，再把按后的與目標的進行匹配，匹配成功且按的次數少的就更新答案，注意要把按后的狀態再按回來，時間復雜度\(O(n^3)\)，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/91952.html
標籤：其他
上一篇：[LeetCode] 2. Add Two Numbers
下一篇：Linux內核單鏈表