p1025 [noip2001 提高组] 数的划分

题目描述

将正整数n分成k份，且每份不能为空，任意两种划分方案不能相同(不考虑顺序)。

例如：n=7，k=3，下面三种分法被认为是相同的。

1，1，5；

1，5，1；

5，1，1。

输入格式

两个正整数n，k，中间用空格隔开。

输出格式

输出划分方案的总数。

数据范围

1≤n≤200，1≤k≤n。

输入样例

7 3

输出样例

4

算法1

(递归) $O(n^2)$

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

相关问题

p1012 [noip1998 提高组] 拼数

题目描述

给定 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，将它们联接成一排，组成一个最大的多位整数。

例如： $n=3$， $a_1=3$， $a_2=32$， $a_3=321$，则可以联接成的最大整数为 $332321$。

输入格式

第一行输入一个正整数 $n$，表示正整数的个数。

第二行输入 $n$ 个正整数 $a_1,a_2,\cdots,a_n$，表示给定的正整数。

输出格式

输出联接成的最大整数。

数据范围

$1\leq n\leq 100$

输入样例

3
3 32 321

输出样例

332321

算法1

(字符串排序) $O(nlogn)$

1.将所有数字转化为字符串
2.将字符串按照特定规则排序
3.将排序后的字符串拼接起来

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(暴力枚举) $O(n^2)$

blablabla

时间复杂度

参考文献

C++ 代码

p1028 [noip2001 普及组] 数的计算

题目描述

给定一个正整数 n，求有多少个 k 满足 k^2 ≤ n。

输入格式

一个整数 n。

输出格式

一个整数，表示满足条件的 k 的个数。

输入样例

10

输出样例

3

算法1

(暴力枚举) $O(\sqrt{n})$

枚举从 1 到 $\sqrt{n}$ 的整数，统计满足条件的个数。

时间复杂度

参考文献

python3 代码

C++ 代码

算法2

(二分查找) $O(\log n)$

二分查找满足 k^2 ≤ n 的最大的 k 值，然后返回 k。

时间复杂度

参考文献

C++ 代码