題目連結：http://www.ifrog.cc/acm/problem/1111
分析：容易發現本題就是排序不等式， 将A數組與B數組分别排序之後， 答案即N∑i=1Ai×Bi
此題有坑，反正據我送出而言，一直RE，之後發現兩個地方會出錯，一是定義數組要放在main函數之前，第二是ans+=1LL*a[i]*b[i],如果少了1LL,結果肯定WA，這就是此題的亮點所在！
題目連結：http://www.ifrog.cc/acm/problem/1112
分析：
一個顯然的想法是每一次二分加入到第幾個數的時候， 混亂度超過M， 然後暴力檢驗， 複雜度顯然可以是O(N2logN)
級别
我們可以換一種二分方式
令目前左端點為L
， 我們先找到一個最小的K， 使得[L,L+2K)這個區間混亂度超過M
然後右端點在[L+2K−1,L+2K)
中二分即可
考慮每删去至少2K−1
個數， 所需要的時間複雜度最大為O(2KKlogN)
故總複雜度為O(Nlog2N)
題目連結：http://www.ifrog.cc/acm/problem/1113
注意到， K條路徑兩兩相交的充要條件是這K
條路徑有一段公共路徑。
對于一條路徑， 點數-邊數恒為1
是以我們可以算出所有可能的情況中， K
條路徑的公共點的個數 減去K
條路徑的公共邊的條數， 即為答案
我們可以枚舉每一個點以及每一條邊的貢獻， 對于一個點來說， 它的貢獻就是所有經過它的路徑條數的K
次方，邊同理
複雜度O(NlogK)
， 瓶頸在于快速幂
題目連結：http://www.ifrog.cc/acm/problem/1114
記SMN 為左邊N個點， 右邊M
個點的完全二分圖生成樹個數
答案即SKN−K×(N−1K−1)
， 證明顯然， 因為把樹上的點按照奇偶分層，即得到一個二分圖， 每一棵樹都對應了這個完全二分圖的一個生成樹
SMN=NM−1×MN−1
， 暴力用Matrix−Tree可以消元得到這個結論。
題目連結：http://www.ifrog.cc/acm/problem/1115