目錄
- JZOJ2290. 【佛山市選2010】組合數計算
- 比賽時
- 之后
- JZOJ2291. 【佛山市選2010】生成字串
- 比賽時
- 之后
- 總結
- JZOJ2292. PPMM
- 比賽時
- 之后
JZOJ2290. 【佛山市選2010】組合數計算
比賽時
一看到數學題就有一種厭倦感，不論如何，還是仔細思考吧，按照公式的直接求法顯然時間會爆（聽同學說有一種快速求階乘的方法，但是對于這題肯定要高精度，太麻煩了），間接入手，楊輝三角？？？時間復雜度和空間復雜度均為\(O(n^2)\)，顯然不行，有沒有快速求組合數的方法呢，顯然我除了楊輝三角一個都沒有學，于是我開始找楊輝三角的其他規律——一無所獲，大數學家都不能找到，蒟蒻的我肯定找不到，突然蹦出一個奇妙的想法，楊輝三角+暴力，因為題目保證答案在64位無符號整數取值范圍內，于是便輸出了一下楊輝三角，發現當n很大以后(\(\geq 1000\)左右)，答案很大，幾乎當\(m>20\)時，全都爆表了，于是我預處理\(n \leq 2000\)的組合數，其他暴力算，加了一點點小優化，比如說n=5,m=2，c(5,2)=(54)/(21)，那么我們再算54的程序中，如果除21中的某個數沒有余數就除，再標記一下除過了，另外，記得輸出用%llu，騙了50分！！！
之后
有一個變態的資料——\(n=0,m=0\)特殊判斷一下，我比賽時腦子卡殼，居然忘記加上\(if(n-m<m),m=n-m\)，一頓改良之后，騙了AC100！！！，正解——lucas，自閉改題中，
JZOJ2291. 【佛山市選2010】生成字串
比賽時
我猜想是貪心或者DP，一下子想不出來，果斷棄療，我最不擅長這種區間DP，
之后
首先，簡化題目，把相鄰的相同的多個字符合成一個，設\(s\)表示合并之后的字符陣列，\(f_{j,i}\)表示從第\(j\)個字符開始長度為\(i\)的字串生成最小步數，，轉移
-
\(f_{j,i}=f_{j,i-1}(s_j==s_{j+i-1})\)，因為這段字串的第一個等于最后一個，所以他們有可能是在一起的，只用生成一次，中間再插入其他東西，
-
\(f_{j,i}=min(f_{j,i},f_{j,k-j+1}+f_{k+1,(j-i+1)-(k+1)+1})(無條件)\)，這個很容易理解吧，劈成兩半，
總結
遇到一些題目時，可以嘗試簡化題目，另外，我得加強一下我的區間DP了，
JZOJ2292. PPMM
比賽時
題目寫著\(-231<x<231\)，于是打了個權值線段樹，因為有了取反的操作，所以如果不真的進行取反，答案就是要么取最大（取反次數為偶數時），要么取最小 （取反次數為奇數時），加入的時候如果取反次數為奇數，對加入的數取反即可，線段樹維護最大和最小，想著能AC，結果10分，
之后
題目出錯了！！！\(-2^{31}<x<2^{31}\)，實際是這樣的，坑人呀！！！我想了一個方法——兩個堆，一個大根，一個小根，跟之前的線段樹思想差不多，但是洗掉上會遇到麻煩，因為要知道它在堆中的位置，正解——單調佇列，插入排序的思想，感覺這個時間復雜度太玄學了！！！自己的想法（雖然不想打）——離散化+權值線段樹，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93587.html
標籤：其他
上一篇：紀中集訓2020.02.03【NOIP提高組】模擬B 組總結反思——登機(board)，游戲(game)，分組(group)
下一篇：簡單實用演算法—獲取分頁總頁碼