SOJ 2785_Binary Partitions

【题意】将一个数用二进制数表示，求一共有多少种表示方法。

【分析】思路一：完全背包

【代码】

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

#include <stack>

#include <queue>

#include <cmath>

#include<ctime>

using namespace std;

const int INF=0x3fffffff,maxn=1e5+40;

const int mod=1000000;

const int total=2000050;

int f[total];

int main (void)

{

    int T,temp;

    f[0]=1;

    scanf("%d",&T);

    for(int i=0;i<=20;i++)//2^20<total<2^21

        for(int j=(1<<i);j<total;j++)

             f[j]+=f[j-(1<<i)]%mod;

   while(T--)

   {

       scanf("%d",&temp);

       printf("%d\n",f[temp]%mod);

   }

}

代码在zoj上AC，但是在soj上就一直TLE，改了好久才勉强AC........渣哭

思路二：看了别人的博客，可以用递推思想，从二进制数的角度，任何一个数都可以由他前一个数+1表示，但如果该数n是偶数，那么他还可以由他的一半n/2表示，即将n/2左移一位

【代码】

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

#include <set>

#include <map>

#include <algorithm>

#include <stack>

#include <queue>

#include <cmath>

#include<ctime>

using namespace std;

const int INF=0x3fffffff,maxn=1e5+40;

const int mod=1000000;

const int total=2000050;

int f[total];

int main (void)

{

    int T,num;

    f[0]=1;

    for(int i=0;i<total;i++)

    {

        if(i%2==0)

            f[i]=(f[i/2]+f[i-1])%mod;

        else

            f[i]=f[i-1]%mod;

    }

    scanf("%d",&T);

    while(T--)

    {

        scanf("%d",&num);

        printf("%d\n",f[num]);

    }

}

巴特西

SOJ 2785_Binary Partitions

最新文章

热门文章