※ 引述《sophialiege (爬回來了)》之銘言： : 請問一下學長,Problem G該怎麼做? 感覺起來這題應該是怕前面題目被破台才擺的 我猜如果不是出題的人剛 K 過 paper 就是他正在研究的東西 這種性質的題目可難可簡單 因為其實 solution 也不見得好寫 如果 solution 好寫, test data 也不見得好出 :p 以上是下賊上之心... : 我當初的想法是 : 方案一 : 先用一些gcd充分條件排掉一些不可能的解 : 接下來,隨機灑點,看看是否存在"可能"非必要的Expression : 方案二 : 用N-space的Convex Hull來解,不過很怕求點上precision的問題產生 : 方案三 : 用高斯消去法,依結果分析,不過初判是不可行 : 之前沒接觸過這類型的題目,覺得很生疏,不知道是不是有Reference可以讀? 我是比較傾向用它題目上的定義的方法來想 舉個例子來說吧, 原本題目給的像是這樣的東西: 2x + 3y + z <= 5 5x + y + 2z <= 7 9x + 7y + 4z <= 30 那麼 2 ( 2x + 3y + z ) + ( 5x + y + 2z ) = 9x + 7y + 4z 但前者可推得前者 <= 17, 因而一聯立起來, 第三式就無效了 但是今天可能給的式子是這樣: 2x + 3y + z <= 5 5x + y + 2z <= 7 9x + 7y + 5z <= 30 也就是說這三個方程式並非線性相依的 這時候前兩個平面截出來的區域無論在哪個 "卦限" 都會和第三個切平面相交, 所以第三個切平面是不能省去的 而在下面這個例子 2x + 3y + z <= 5 5x + y + 2z <= 7 9x + 7y + 4z <= 30 9x + 7y + 5z <= 30 式三 9x + 7y + 4z <= 30 被剔除和式四無關 完全是因為和前兩式的線性相依之後再經比較被剔除的 所以我做了這樣的猜想: 是否被剔除的方程式的 "法向量" 得要是 1. 和其它某幾個線性相依的 2. 範圍要被其它幾個線性相依所累算出來的範圍包含 其中 1. 的線性相依要符合題述的 c1, c2, ... ck > 0 如此題目就簡化成 尋找方程式係數 (x1, y1, z1, w1, ...), (x2, y2, z2, w2, ...), ... 是否存在線性相依的關係, 如果有, 那麼那些就是 candidate 至於給定 vector, 要確定是否有線性相依的關係 還得要符合要是正的係數的話... 好像得要把 ┌ x1, y1, z1, ... │1 0 0 0 ... ┐ │ x2, y2, z2, ... │0 1 .... │ │ .... │... │ │ .... │... │ └ xn, yn, zn, ... │0 0 0 ... 1 ┘ 這種東西高斯消去? 我不知道一次要丟幾個進去玩 還沒有想得很清楚, 不過理論上這應該是個 P time 的解法了 XD 不知道對不對呢... -- 有時候，遺忘，是令人快樂的。什麼時候？當然是有人傷了你的心的時候。 　存心傷你的那個人，固然是故意和你過不去，但是被傷了心而耿耿於懷的你 　，卻是和自己過不去了。所以，記性不好的人，通常會是比較快樂的人，也 　是比較不容易被擊倒的人。 --

※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.196.165 ※ 編輯: ledia 來自: 61.228.196.165 (09/12 03:05)