CSU 1425 NUDT校赛 I题 Prime Summation

这个题本来有希望在比赛里面出了的

当时也想着用递推因为后面的数明显是由前面的推过来的

但是在计算的时候因为判重的问题。。。很无语。我打算用一个tot[i]来存i的总种树，tot[i]+=tot[j]//j为可以由j推到i的一系列数，但这样是不对的，会产生大量重复计算。。。

看了下标程才发现要用二维来计算出种类总数，f[i][j]+=sum(f[i-j][k]）表示在推i数的时候，第一个素数为j的种类数，注意j一定为素数，而且k不能大于j。。。标程里面处理的比较简练，就学了下他的写法。

至于推导出式子，则可以用递归，比较简练的是用递推。

这是错误的代码：是我之前没把种类数计算好，并且推导式子用的是递归：

#include <iostream>

#include <cstdio>

#include <cstring>

#define N 210

#define ll unsigned long long

using namespace std;

ll n,k;

int dp[N][N],count[N],vis[N];

ll tot[N];

int tmp[N],prime[N],cnt;

void init()

{

    for (int i=;i<N;i++)

        tmp[i]=;

    for (int i=;i<N;i++){

        for (int j=;j*i<N;j++){

            tmp[i*j]=;

        }

    }

    cnt=;

    for (int i=;i<N;i++){

        if (tmp[i]) prime[cnt++]=i;

    }

//    for (int i=0;i<cnt;i++)

//        cout<<prime[i]<<endl;

    memset(tot,,sizeof tot);

    memset(count,,sizeof count);

}

void solve()

{

    dp[][count[]++]=;

    dp[][count[]++]=;

    tot[]=tot[]=;

    tot[]=;

    for (int i=;i<N;i++){

        memset(vis,,sizeof vis);

        if (tmp[i]){

            dp[i][count[i]++]=i;

            vis[i]=;

            tot[i]++;

        }

        int up=lower_bound(prime,prime+cnt,i-)-prime;

        while (prime[up]>i-) up--;

        for (int j=up;j>=;j--){

            int num=prime[j];

            bool flag=;

            for (int k=count[i-num]-;k>=;k--){

                if (dp[i-num][k]>num) break;

                flag=;

                tot[i]+=tot[dp[i-num][k]];

            }

            if (flag)

                dp[i][count[i]++]=num;

        }

    }

    tot[]=tot[]=;

    for(int i=;i<N;i++){

        tot[i]=;

        for (int j=;j<count[i];j++){

            tot[i]+=tot[dp[i][j]];

        }

    }

    int test=;

    for (int i=;i<count[test];i++)

        cout<<i<<" !!! "<<dp[test][i]<<endl;

   for (int i=;i<N;i++)

        cout<<i<<" "<<tot[i]<<endl;;

}

void print(ll num,ll ret)

{

    if (num==) return;

    ll sum=;

    int i;

    ll pre=;

    cout<<num<<" "<<ret<<endl;

    for (i=;i<count[num];i++){

        sum+=tot[num-dp[num][i]];

        if (sum>=ret) break;

        pre+=tot[num-dp[num][i]];

    }

    //if (sum>ret) i--;

   // printf("%d",dp[num][i]);

    //if (num-dp[num][i]>0) printf("+");

    ll nt=ret-pre;

    print(num-dp[num][i],nt);

}

int main()

{

    init();

    solve();

    while (scanf("%llu%llu",&n,&k)!=EOF){

            printf("%llu\n",tot[n]);

            if (k>tot[n]) k=tot[n];

            printf("%d=",n);

            print(n,k);

            printf("\n");

    }

}

//200 15252874192862840692

AC代码：

#include <iostream>

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 210

using namespace std;

int f[N][N];

int prime[N],tot[N];

void init()

{

    memset(prime,,sizeof prime);

    for (int i=;i<N;i++)

        for (int j=i+i;j<N;j+=i) prime[j]=; //预处理出素数

    memset(f,,sizeof f);

    f[][]=;

    for (int i=;i<N;i++)//这里处理的非常简练，因为不存在的情况全部置为了0，所以省去了各种判断和限制，而且k是不会大于j的，使得计算结果不会出现重复。

        for (int j=;j<=i;j++) if (!prime[j])

          for (int k=;k<=j;k++){

            f[i][j]+=f[i-j][k];

          }

    for (int i=;i<N;i++)

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

         tot[i]+=f[i][j];

}

int n,k;

int main()

{

    init();

    while (scanf("%d%d",&n,&k)!=EOF){

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

        printf("%d=",n);

        if (k>tot[n]) k=tot[n];

        int cur=n,flag=;;

        while (n>){ //递推出式子，这里也处理的比较巧妙。值得学习

            if (k>f[n][cur]){

                k-=f[n][cur];

                cur--;

            }

            else

            {

                if (flag++) printf("+");

                printf("%d",cur);

                n-=cur;

            }

        }

        printf("\n");

    }

    return ;

}

巴特西

CSU 1425 NUDT校赛 I题 Prime Summation

最新文章

热门文章