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

Re:解题报告

Posted by qunideba at 2019-08-24 16:04:13 on Problem 2229
In Reply To:解题报告 Posted by:13jczhuang at 2014-07-24 14:47:26
> poj 2229 Sumsets
> //解题报告
> /*
> 题意:给出一个整数n,求解该整数n有多少种由2的幂次之和组成的方案.
> 解题思路:
> 1.可以将n用二进制表示.
> n=1,只有1种表示方法。
> n=2,10(2),二进制表示下,可以分拆成{1,1},{10}有两种表示方法
> n=3, 11(2),可以分拆成{1,1,1},{10,1}.
> n=4, 100(2),{1,1,1,1},{10,1,1},{10,10},{100}.
> 总结:如果所求的n为奇数,那么所求的分解结果中必含有1,因此,直接将n-1的分拆结果中添加一个1即可 为s[n-1]
> 如果所求的n为偶数,那么n的分解结果分两种情况
> 1.含有1 这种情况可以直接在n-1的分解结果中添加一个1即可 s[n-1]
> 2.不含有1 那么,分解因子的都是偶数,将每个分解的因子都除以2,刚好是n/2的分解结果,并且可以与之一一对应,这种情况有 s[n/2]
> 
> */
> #include<stdio.h>
> #include<string.h>
> 
> int a[1000010];
> int main()
> {
>     a[1]=1;
>     a[2]=2;
>     int n,i=3;
>     while(i<=1000000){
>             a[i++]=a[i-1];
>             a[i++]=(a[i-1]+a[i>>1])%1000000000;
>     }
>     while(scanf("%d",&n)!=EOF){
>         printf("%d\n",a[n]);
>     }
>     return 0;
> }

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