私はACM ICPCの過去の問題を練習していましたhttp://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1030
私はこの問題を解決することができず、3 秒の制限時間内に効率的に解決する方法がまったくわかりません。この問題は数論に基づいていると思いますが、どうすればよいか正確にはわかりません。ありがとう！
2 に答える
0
だから私は与えられたと信じています：
(a1,b1,c1), (a2,b2,c2) ... (an,bn,cn)
非負の係数が存在するかどうかを判断する必要があります。
X = (x1,x2,...,xn)
そのような
x1*a1 + x2*a2 + ... + xn*an ==
x1*b1 + x2*b2 + ... + xn*bn ==
x1*c1 + x2*c2 + ... + xn*cn
少しの線形代数だけで十分です。
ヒント: n == 4 で入力を作成してみてください。問題を解決するには 4 つの xi がすべて正である必要があります (3 つだけでは解決できません)。これは可能ですか？
于 2012-04-07T18:49:02.123 に答える