首页 > 代码库 > 国防科大校赛I题: Prime Summation
国防科大校赛I题: Prime Summation
地址:click here
国防科大今年校赛的I题目,大意是:对于正整数N、K,N可以表示成若干个质数之和的形式,问合法的方案数有多少(质数相同次序不同视为同一方案),并输出字典序第K大的表示方案。
我第一反应是用DFS去做,并且思路比较清晰敲好代码了。一开始好傻还保存全部状态后来觉得不对,方案太多会溢出,就不保存,每次都更新直到更新到解才停止。当时没有正确估计方案数全部保存下来一直WA,回来改了后通过了全部的测试数据,但是妥妥的TLE。
此题其实是一个DP问题,dp[i][j]是正整数i的分解其中第一个质数j的方案数,递推公式就是dp[i][j] = sum(dp[i-j][k] , 2=<k<=min(i-j, j)),(因为2是素数第一个),一开始预处理从0到200,大概O(N^3)的复杂度,然后输入一个N和K,方案数就是sum(dp[N][k], 2=<k<=N)
关键是求后面一个通过给出的K逆推,因为每一项的DP值都是知道的,要大的排在前面,所以从后面往前加求SUM,直到SUM>K了,就找到第一项了,然后记录这一项,用递归,下一个n是n-i下一个k就是k-sum+dp[n][i],需要注意的是,从后面往前面找的时候,前面的边界就是2,但是后面的边界却是前面记录的那一项,因为分解的时候前面必须要大于等于后面的项。然后直到K==0就找到了。其实N==0和K==0是同时达到的。就是这样
AC代码
#include<cstdio> #include<ctype.h> #include<algorithm> #include<iostream> #include<cstring> #include<vector> using namespace std; int dp[201][201],mark[201],path[105];//定义全局变量的时候千万不要在其他函数再次定义,不然全局变量不会改变,不要嘲笑我。。就是犯了这个错误所以记录下 int nct; void pprime() { int i,j; dp[2][2] = 1; for(i = 2; i < 15; i++) for(j = 2; i*j < 201; j++) mark[j*i] = 1; for(i = 2; i < 201; i++) if(mark[i] == 0) dp[i][i] = 1; } int min(int a,int b) { return a>b?b:a; } void init() { int i,j,k,sum; for(i = 2; i <= 200; i++) { for(j = 2; j <= i; j++) { if(mark[j] != 1 && i != j) { sum = 0; for(k = 2; k <= min(j,i-j); k++) sum+=dp[i-j][k]; dp[i][j] = sum; } } } } void find_path(int n,int k,int w) { int i; if(n == 0 || k ==0) return; int sum = 0; for(i = w; i >= 2; i--) { if(dp[n][i] != 0) sum+=dp[n][i]; if(sum >= k) { path[nct++] = i; break; } } find_path(n-i,k-sum+dp[n][i],i); } int main() { // freopen("input.txt","r",stdin); // freopen("out.in","w",stdout); pprime(); init(); int n,k,i; while(~scanf("%d%d",&n,&k)) { nct = 0; int ans = 0; for(i = 0; i <= 200; i++) ans+=dp[n][i]; if(k > ans) k = ans; printf("%d\n%d=",ans,n); find_path(n,k,200); for(i = 0; i < nct; i++) { printf("%d",path[i]); if(i != nct-1) printf("+"); } printf("\n"); } return 0; } /************************************************************** Problem: 1425 User: HNU_TEAM_3 Language: C++ Result: Accepted Time:0 ms Memory:1644 kb ****************************************************************/
国防科大校赛I题: Prime Summation
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。