Online JudgeProblem SetAuthorsOnline ContestsUser
Web Board
Home Page
F.A.Qs
Statistical Charts
Problems
Submit Problem
Online Status
Prob.ID:
Register
Update your info
Authors ranklist
Current Contest
Past Contests
Scheduled Contests
Award Contest
User ID:
Password:
  Register

这样算不算证明?

Posted by oikid at 2010-06-07 22:14:06 on Problem 2159
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:
User ID:
Password:
Title:

Content:

Home Page   Go Back  To top


All Rights Reserved 2003-2013 Ying Fuchen,Xu Pengcheng,Xie Di
Any problem, Please Contact Administrator