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 frkstyc at 2006-04-04 15:07:16
In Reply To:我把自己的思路和算法分析写一下,大家看有什么漏洞没有。 Posted by:wi at 2006-04-04 15:05:22
> 一、此题考察结果是否整除,即表示为是否有余数;
> 
> 二、N个数相加减,所的结果除以K的余数,等于它们各自对K的余数相加减;
> 
> 三、这些余数计算的结果可能会有重复的,并且只落在[0,K)范围内;
> 
> 四、因此,不必列出N个数相加减的所有组合,只需从头开始逐步计算结果(并取余),每一步的结果再加减下一个,直到最后产生最终不超过K个的结果;
> 
> 五、上述表达用数学描述为:设 计算到第n个的结果为集合A,下一个余数为b,则第n+1个结果为{t+b,t-b|t属于A};
> 
> 六、考察最后的结果集合中是否有0,即表示有无整除项。
> 
> 程序采用C语言,数组方案,用大小为K的数组表示某一步的结果集合,元素用1,0表示有无相应的余数项,如:某一步有结果为i,则令p[i]=1;
> 为方便计算设两个数组,p1是上一步的结果集合,运算时先把p2清零,把p1中元素为1的项数逐个拿来计算,结果映射到p2中去,完成后交换两个数组,进入下一步;
> 读数的时候第一个数据单独处理(因为没有0+t,0-t),后面的数据用循环;
> 最后判断p1[0]是否为1即可。
> 
> 写这个程序修改多次还是WA,自己又想不明白有什么问题,如果大家也认可我上面的分析的话,我再把代码贴上来,请大家指导。

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