水池
比賽時
我最討厭這種數學類題了，我首先想到了這幾種情況，設\(jl[][]\)表示兩點之間弧的距離，從F到G可以由
- F->G
- F->B->A->G
- F->A->B->G
路徑到達，那么，關鍵就是求弧長了，我于是自己亂寫了一個式子，結果樣例都沒有過，一看時間已經去了很多了，于是放棄了，我覺得很多人會AC.
之后
居然沒有人比賽時A了這道題，這題正解三角函式，初中的蒟蒻我還沒學～～～
求弧長可以用兩點之間的距離先求出圓心角，然后就可以通過圓心角求出弧長了，具體做法等我后續更新
數字排序
比賽時
第一眼看就覺得像我們昨天剛做過的題，注意到只有兩行數，于是回憶起了昨天的題解中對只有兩行數的解法——是二分，但是又回憶不起具體內容來，于是死命得想二分，想了很久，終于想到了一種二分套二分的解法，
我們可以二分答案，那最關鍵的就是如何判斷當前二分到的mid合不合法，mid合法，當且僅當有小于k個數嚴格小于它,于是，這個問題就轉化為了如何求小于mid的有多少個數，考慮到只有兩行數，且\(n \leq 10000\) ，那么可以列舉i,求出\(a_i*b_j(1 \leq j \leq m)\) 有多少個嚴格小于mid，于是我們可以預先對b排序，然后用二分求出最后一個\(a_i*b_j < mid\)的下標，那么對于這個i，\(a_i*b_j(1 \leq j \leq m) < mid\)的就有下標個數，于是這題就解決了，
之后
我們機房的大佬XYX跟我的思路差不多，但是它沒有嵌套的二分，而是用了一個前綴和表示小于mid的有多少個數，具體怎么做unknow
球星
比賽時
仔細看以為是什么主席樹等資料結構，因為要求11大，可我還沒學，于是果斷棄療，
之后
題解的做法時線段樹+歸并排序的思想，線段樹采用動態開點，或者也可以用離散化;歸并排序的思想就是對于兩個已經有序的序列a,b，我們只需要一重回圈就可以將a,b合并（所以叫歸并）為有序的數列c，這樣就可以輕輕松松得求出每個區間的11大，
鉆石交易
比賽時
思考了一會兒，腦子一直在瞎編亂造——最小費用最大流？BFS？狀壓DP？
看到\(m \leq 10\) ,于是決定采用狀壓DP，設\(f[s][i]\)，s表示寶石的狀態——賣或沒賣，i表示當前在第i個城市，那么，處在當前這個狀態，我們可以選擇1.在當前城市賣掉寶石 2.不賣寶石走到其他城市
于是就簡簡單單得打了幾個回圈
之后
拿了30分，答案錯誤，我沒有考慮到一種情況——在當前s狀態下，我們可以在剩余錢大于0時走到其他城市，這就相當與最短路徑問題，而如果我們單單順序列舉更新f，會找不到最優答案，正解：狀壓DP+dijk堆優化，狀壓DP主要處理賣寶石的情況，dijk主要處理在不賣寶石的情況下走到其它城市的情況，狀壓DP里面套dijk，
總結
- 對于求區間前k小的題目（k是固定的！），我們可以用線段樹實作
- 對于狀壓DP但是順序列舉不能保證最優解的題目，可以在狀壓DP內套xxx保證最優解
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/93583.html
標籤：其他
上一篇：Python 實作轉堆排序演算法原理及時間復雜度（多圖解釋）
下一篇：2020.02.01【NOIP提高組】模擬B 組總結反思——數列（sequence） 樹 【2012東莞市選】時間流逝 挖掘機技術哪家強