# [split of recursive number] n points K, split of limited range

2022-04-23 15:43:00

I made up the title myself
1.n branch k
Ⅰ：

``````N Split K term ①

Title Description

Problem description

Yes N Marbles are to be distributed to K personal , Given N、K, Find out how many distribution schemes there are .

Input description

a line , Two integers , by N、K

Output description

An integer , Indicates the number of schemes allocated .

sample input

7 3

sample output

36

Data range

1<=K<=8

K<=N<=30

Tips
4 The ball is divided among three people , Yes 15 There are three kinds of distribution schemes
0 0 4
0 1 3
0 2 2
0 3 1
0 4 0
1 0 3
1 1 2
1 2 1
1 3 0
2 0 2
2 1 1
2 2 0
3 0 1
3 1 0
4 0 0
Be careful ：1 3 5, 1 5 3, 3 5 1 Count as 3 Kind of plan
``````
``````#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <list>
#include <limits.h>

using namespace std;

int cnt=0;
int n,k;
void doit(int x,int step) //x Is the number of table tennis balls left ,step Who is currently assigned to
{

if(step==k){
// It's time to count , Can't be divided , The “ return ” 了 ！
cnt++; // As a plan
return; // Keep looking for solutions qwq
}
for(int i=0;i<=x;i++)doit(x-i,step+1); // From everyone's least 0 Start , List every possible solution , And finally get the answer
}

int main()
{

cin>>n>>k;
doit(n,1);
cout<<cnt;
// Direct results

return 0;
}
``````
``````
Title Description

N A ping-pong ball , Divide into K Pile up , How many different ways of dividing .

for example ：n=7,k=3, The following three partition schemes are considered to be the same .
1 1 5

1 5 1

5 1 1
The sample input

7 3

Sample output

4

Tips
6<N<=200
2<=K<=6

``````

The title here clearly states that there can be no such repeated allocation method , So how to allocate n?
This question is actually a recursive Apple , It's just a slight change .
The recursive method ①

``````
int apple(int m,int n){
// Pure recursive thinking
if(m==0||n==1) return 1;
if(n>m) return apple(m,m);
else return apple(m,n-1)+apple(m-n,n);
}
``````

The recursive method ②

``````void apple(int pre,int n,int step){
// The idea of recursion
if(step==1) {

cnt++;
return;
}
for(int i=pre;i<=n/step;i++)apple(i,n-i,step-1);
}
``````
`````` A limited range of splits ①

Title Description

Problem description

Yes N A pearl is to be distributed to K personal , Everyone is required to be at least MIN star , At most MAX star . Given N、K、MIN、MAX, Find the number of schemes that meet the allocation requirements , If there is no suitable scheme , The output 0.

Input description

a line , Four integers , respectively N、K、MIN、MAX

Output description

An integer , Indicates the number of schemes that meet the allocation requirements .

sample input

7 3 1 4

sample output

12

Data range

K<=N<=30

Data range

1<=K<=8

K<=N<=30

Be careful ：1, 3, 5     1, 5, 3       5, 3, 1     Count as 3 Kind of plan
``````

This problem actually limits the boundary between the top and bottom , In fact, we just need to bring the upper and lower boundaries into the problem , It's easy to write

``````#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <stack>
#include <list>
#include <limits.h>

using namespace std;

int cnt=0,maxn,minn;
int n,k;
void doit(int x,int step)
{

if(step==k){

if(x>=minn && x<=maxn)cnt++;  // Judge whether this scheme is legal
return;  // Whether it is legal or not, we should continue to find new solutions
}
for(int i=minn;i<=min(maxn,x);i++)doit(x-i,step+1);  // If the rest is not enough maxn, Then we can only enumerate x（ That is to say min(maxn,x)）
}

int main()
{

cin>>n>>k>>minn>>maxn;
doit(n,1);
cout<<cnt;

return 0;
}
``````
`````` A limited range of splits ②

Title Description
Problem description
Yes N A table tennis ball is divided into K Pile up , Each pile is required to be at least MIN individual , At most MAX individual . Given N、K、MIN、MAX, Find the number of schemes that meet the allocation requirements , If there is no suitable scheme , The output 0.
Input description
a line , Four integers , respectively N、K、MIN、MAX
Output description
An integer , Indicates the number of schemes that meet the allocation requirements .
sample input
7 3 1 4
sample output
3
Data range
K<=N<=30
Data range
1<=K<=8
K<=N<=30
Be careful ：1, 3, 5      1, 5, 3      5, 3, 1     Count as 1 Kind of plan
``````

Again , On the code ：

``````void doit(int x,int step,int o)
{

if(step==k){

if(x>=max(o,minn) && x<=maxn)cnt++;
return;
}
for(int i=max(o,minn);i<=min(maxn,x);i++)doit(x-i,step+1,i);
}
``````

https://yzsam.com/2022/04/202204231531525851.html