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