首页 > 代码库 > CSU 1425 NUDT校赛 I题 Prime Summation
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=0;i<N;i++) tmp[i]=1; for (int i=2;i<N;i++){ for (int j=2;j*i<N;j++){ tmp[i*j]=0; } } cnt=0; for (int i=2;i<N;i++){ if (tmp[i]) prime[cnt++]=i; } // for (int i=0;i<cnt;i++) // cout<<prime[i]<<endl; memset(tot,0,sizeof tot); memset(count,0,sizeof count); } void solve() { dp[2][count[2]++]=2; dp[3][count[3]++]=3; tot[2]=tot[3]=1; tot[0]=1; for (int i=4;i<N;i++){ memset(vis,0,sizeof vis); if (tmp[i]){ dp[i][count[i]++]=i; vis[i]=1; tot[i]++; } int up=lower_bound(prime,prime+cnt,i-2)-prime; while (prime[up]>i-2) up--; for (int j=up;j>=0;j--){ int num=prime[j]; bool flag=0; for (int k=count[i-num]-1;k>=0;k--){ if (dp[i-num][k]>num) break; flag=1; tot[i]+=tot[dp[i-num][k]]; } if (flag) dp[i][count[i]++]=num; } } tot[2]=tot[3]=1; for(int i=4;i<N;i++){ tot[i]=0; for (int j=0;j<count[i];j++){ tot[i]+=tot[dp[i][j]]; } } int test=10; for (int i=0;i<count[test];i++) cout<<i<<" !!! "<<dp[test][i]<<endl; for (int i=2;i<N;i++) cout<<i<<" "<<tot[i]<<endl;; } void print(ll num,ll ret) { if (num==0) return; ll sum=0; int i; ll pre=0; cout<<num<<" "<<ret<<endl; for (i=0;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,0,sizeof prime); for (int i=2;i<N;i++) for (int j=i+i;j<N;j+=i) prime[j]=1; //预处理出素数 memset(f,0,sizeof f); f[0][0]=1; for (int i=2;i<N;i++)//这里处理的非常简练,因为不存在的情况全部置为了0,所以省去了各种判断和限制,而且k是不会大于j的,使得计算结果不会出现重复。 for (int j=2;j<=i;j++) if (!prime[j]) for (int k=0;k<=j;k++){ f[i][j]+=f[i-j][k]; } for (int i=2;i<N;i++) for (int j=2;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=0;; while (n>0){ //递推出式子,这里也处理的比较巧妙。值得学习 if (k>f[n][cur]){ k-=f[n][cur]; cur--; } else { if (flag++) printf("+"); printf("%d",cur); n-=cur; } } printf("\n"); } return 0; }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。