P1158 整数拆分 - 题解

登录注册上岸

以下题解仅供学习参考使用。

抄袭、复制题解，以达到刷AC率/AC数量或其他目的的行为，在N诺是严格禁止的。

N诺非常重视学术诚信。此类行为将会导致您成为作弊者。具体细则请查看N诺社区规则。

2024年3月10日 14:45

整数拆分题解：我感觉你有93.6%的可能性能看懂

P1158

回复 0 | 赞 2 | 浏览 555

#include <iostream> #include <string.h> #include <math.h> #include <stdio.h> #include <stdlib.h> #include <algorithm> using namespace std; int main(){ int a[1000005]; int n; a[1]=1; a[2]=2; for(int i=3;i<=1000000;i++){ if(i%2==1) ...

2023年3月28日 18:37

数字的二进制拆分

P1158

回复 0 | 赞 1 | 浏览 2.6k

题目描述一个整数总可以拆分为2的幂的和，例如： 7=1+2+4 7=1+2+2+2 7=1+1+1+4 7=1+1+1+2+2 7=1+1+1+1+1+2 7=1+1+1+1+1+1+1 总共有六种不同的拆分方式。用f(n)表示n的不同拆分的种数，例如f(7)=6. 要求编写程序，读入n(不超过1000000)，输出f(n)%1000000000。题目分析记f(n)为n的划分数，我们有递推公式： f(2m + 1) = f(2m)， f(2m) = f(2m - 1) + f(m)，初始条件：f(1) = 1。证明: 证明的...

2022年3月6日 17:15

记忆化搜索 & dp

P1158

回复 0 | 赞 0 | 浏览 5.3k

记忆化搜索 ``` #include<bits/stdc++.h> using namespace std; const int mod=1e9; const int N=1e6+10; int mp[N][30]; bool st[N][30]; int n; int f(int num,int di){ if(num==0){ return 1; } ...

2021年5月30日 10:28

不就是个简单的完全背包求方案数么？？？

P1158

回复 0 | 赞 1 | 浏览 8.3k

#include <bits/stdc++.h> using namespace std; typedef long long ll;//三年竞赛一场空，不开long long见祖宗 //typedef __int128 lll; #define print(i) cout << "debug: " << i << en...

题目整数拆分

题解数量4

热门题解

1 整数拆分题解：我感觉你有93.6%的可能性能看懂

2 数字的二进制拆分

3 不就是个简单的完全背包求方案数么？？？

4 记忆化搜索 & dp