Online Judge | Problem Set | Authors | Online Contests | User | ||||||
---|---|---|---|---|---|---|---|---|---|---|
Web Board Home Page F.A.Qs Statistical Charts | Current Contest Past Contests Scheduled Contests Award Contest |
这样算不算证明?In Reply To:一种O(n)算法 Posted by:asterix314 at 2009-01-12 12:11:25 若strlen(buf1) == strlen(buf2) 则长度相等,均为L 又总元素相同,均为N ai,bi(i = 1...n)分别为各元素出现次数 且a1^2 + a2^2 + ... + an^2 == b1^2 + b2^2 + ... + bn^2 已a1 + a2 + ... +an == b1 + b2 + ... +bn == L 设x,y (L - x)^2 + x^2 == (L - y)^2 + y^2 可得:x + y = L 所以,一个L、N对应唯一的一组数 同理可推出当N>2时,均对应唯一的一组数。 如N == 3时, 设x1,x2,y1,y2 令x1 == y1, x2 == y2,显然成立 令x1 != y1, x2 == y2 可化简得:L - x1 - x2 - y1 == 0,结论成立 令x1 != y1, x2 != y2 反证 所以结论成立 Followed by: Post your reply here: |
All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator