※ 引述《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)