題目
越往前做題目就越簡單了 而且只有4道
通過省選試題難度的變化 看來JLOI這幾年確實進步了不少
這次的題目全都做上了
第一題是一道數學題 在這里就不多說了
第二題他讓你求的是一個點(x,y)使得sigema(wi*((x-xi)^2+(y-yi)^2))(1<=i<=n 以下同此)最小
初看這個式子里又有x 又有 y 很復雜不好權衡
可是乘法是符合結合率的
所以原式=sigema(wi*(x-xi)^2)+sigema(wi*(y-yi)^2)
所以當sigema(wi*(x-xi)^2)、sigema(wi*(y-yi)^2)都取道最小時既為所求
則就好辦了就是一個帶權平均數問題(這個好像有學名不過忘了)
以x為例x=sigema(wi*xi)/sigema(xi) y同理
第3題：
如果枚舉任意2個為c的方塊然再bfs或并查集找最長曲線顯然是要超時的(O((n*m)^3)，1<=n,m<=30)
發現由于只改動兩個方塊而每次都求一邊最長曲線會造成許多重復運算
如果現將整個矩陣先用并查集做一遍然后枚舉該邊哪兩個為c的方塊再算最長曲線就可以在常數時間內完成最長曲線的求解
如果你總是覺得用什么不對勁的地方 沒關系(其實我一開始也是這樣的)
我還有一種人那你放心的方法：先枚舉一個c然后做一次并查集然后再枚舉另一個c再用并查集求解 這回不亂了吧(能合并的最多有2條曲線) 這個方法只是將常數增大了 而讓算法清晰了 不失為一種不錯的選擇
第4題
想了好久差點放棄了 因為只想到了O((n+m)*(n*m)^2)的算法
但后來一看1<=n,m<=10這個時間復雜度是綽綽有余的
顯然任意一個被切下來的矩形都與其他矩形再無干系 這就使得這個模型沒有后效性
提到后效性不由得讓我們想到DP
狀態為f[x1][y1][x2][y2]表示把左上角為(x1,y1) 右下角為(x2,y2)的矩形分割成題目中要求的形態最少需要的切割長度 轉移只需要枚舉切割線就好了