本片为洛谷题目
纯手打,请您放心食用!
目录
U121029 全排列(可重复)
题目描述
输入格式
输出格式
输入输出样例
题解
P1157 组合的输出
题目描述
输入格式
输出格式
输入输出样例
题解
P2404 自然数的拆分问题
题目描述
输入格式
输出格式
输入输出样例
说明/提示
U121029 全排列(可重复)
题目描述
输入n,从1~n的数可重复的排列:(n<9) 例如:n=3
1 1 1
1 1 2
1 1 3
1 2 1
1 2 2
1 2 3
1 3 1
……
3 3 3
输入格式
输入n
输出格式
输出所有排列。
输入输出样例
输入 #1
3
输出 #1
1 1 1 1 1 2 1 1 3 1 2 1 1 2 2 1 2 3 1 3 1 1 3 2 1 3 3 2 1 1 2 1 2 2 1 3 2 2 1 2 2 2 2 2 3 2 3 1 2 3 2 2 3 3 3 1 1 3 1 2 3 1 3 3 2 1 3 2 2 3 2 3 3 3 1 3 3 2 3 3 3
题解
#include<bits/stdc++.h>
using namespace std;
int n,a[11];
void bfs(int g){if(g>n){for(int i=1;i<=n;i++)cout<<a[i]<<" ";cout<<endl;return; }for(int i=1;i<=n;i++){a[g]=i;bfs(g+1);}
}
int main(){cin>>n;bfs(1);return 0;
}
P1157 组合的输出
题目描述
排列与组合是常用的数学方法,其中组合就是从 n 个元素中抽出 r 个元素(不分顺序且 r≤n),我们可以简单地将 n 个元素理解为自然数 1,2,…,n,从中任取 r 个数。
现要求你输出所有组合。
例如 n=5,r=3,所有组合为:
123,124,125,134,135,145,234,235,245,345123,124,125,134,135,145,234,235,245,345。
输入格式
一行两个自然数 n,r(1<n<21,0≤r≤n)。
输出格式
所有的组合,每一个组合占一行且其中的元素按由小到大的顺序排列,每个元素占三个字符的位置,所有的组合也按字典顺序。
注意哦!输出时,每个数字需要 3 个场宽。以 C++ 为例,你可以使用下列代码:
cout << setw(3) << x;
输出占 33 个场宽的数 x。注意你需要头文件 iomanip
。
输入输出样例
输入 #1
5 3
输出 #1
1 2 31 2 41 2 51 3 41 3 51 4 52 3 42 3 52 4 53 4 5
题解
#include<bits/stdc++.h>
using namespace std;
int n,r,a[21];
void bfs(int g){if(g>r){for(int i=1;i<=r;i++)cout<<setw(3)<<a[i];cout<<endl;return; }for(int i=a[g-1]+1;i<=n;i++){a[g]=i;bfs(g+1);}
}
int main(){cin>>n>>r;bfs(1);return 0;
}
P2404 自然数的拆分问题
题目描述
任何一个大于 11 的自然数 n,总可以拆分成若干个小于 n 的自然数之和。现在给你一个自然数 n,要求你求出 n 的拆分成一些数字的和。每个拆分后的序列中的数字从小到大排序。然后你需要输出这些序列,其中字典序小的序列需要优先输出。
输入格式
输入:待拆分的自然数 n。
输出格式
输出:若干数的加法式子。
输入输出样例
输入 #1
7
输出 #1
1+1+1+1+1+1+1 1+1+1+1+1+2 1+1+1+1+3 1+1+1+2+2 1+1+1+4 1+1+2+3 1+1+5 1+2+2+2 1+2+4 1+3+3 1+6 2+2+3 2+5 3+4
说明/提示
数据保证,2≤n≤8
题解
#include<bits/stdc++.h>
using namespace std;
int n,a[11]={1},sum=0;
void bfs(int g,int sum){if(sum==n&&g>2){for(int i=1;i<=g-2;i++)cout<<a[i]<<"+";cout<<a[g-1]<<endl;return;}for(int i=a[g-1];i<=n-sum;i++){a[g]=i;sum+=i;bfs(g+1,sum);sum-=i;}
}
int main(){cin>>n;bfs(1,0);return 0;
}
P1706 全排列问题
题目描述
按照字典序输出自然数 11 到 n 所有不重复的排列,即 n 的全排列,要求所产生的任一数字序列中不允许出现重复的数字。
输入格式
一个整数 n。
输出格式
由 1∼n 组成的所有不重复的数字序列,每行一个序列。
每个数字保留 55 个场宽。
输入输出样例
输入 #1
3
输出 #1
1 2 31 3 22 1 32 3 13 1 23 2 1
说明/提示
1≤n≤9。
题解
#include<bits/stdc++.h>
using namespace std;
int n,a[11];
bool f[11];
void bfs(int g){if(g>n){for(int i=1;i<=n;i++)cout<<setw(5)<<a[i];cout<<endl;return;}for(int i=1;i<=n;i++){if(f[i]==false){f[i]=true;a[g]=i;bfs(g+1);f[i]=false;}}
}
int main(){cin>>n;bfs(1);return 0;
}
P1657 选书
题目描述
学校放寒假时,信息学奥赛辅导老师有 1,2,3,⋯,x 本书,要分给参加培训的 x 个人,每人只能选一本书,但是每人有两本喜欢的书。
老师事先让每个人将自己喜欢的书填写在一张表上。然后根据他们填写的表来分配书本,希望设计一个程序帮助老师求出所有可能的分配方案,使每个学生都满意。
输入格式
第 11 行一个数 x。
第 22 行至第 1+x 行,每行两个数,表示 ai 喜欢的书的序号。
输出格式
只有一个数,总方案数 total。
输入输出样例
输入 #1
5 1 3 4 5 2 5 1 4 3 5
输出 #1
2
说明/提示
数据范围及约定
对于全部数据,1≤x≤20。
update 2022/03/07update 2022/03/07,阮行止
本题原始数据中,最后一个数据点的 x 为 0,期望输出为 0。考虑到这个数据不合理,予以删去。现在提交这个题目不会遇到 x=0 的数据点。
题解
#include<bits/stdc++.h>
using namespace std;
int n,a[21],b[21],sum=0;
bool f[21];
void bfs(int g){if(g>n){sum++;return;}if(f[a[g]]==false){f[a[g]]=true;bfs(g+1);f[a[g]]=false;}if(f[b[g]]==false){f[b[g]]=true;bfs(g+1);f[b[g]]=false;}
}
int main(){cin>>n;for(int i=1;i<=n;i++)cin>>a[i]>>b[i];bfs(1);cout<<sum;return 0;
}
P1036 [NOIP2002 普及组] 选数
题目描述
已知 n 个整数 x1,x2,⋯,xn,以及 11 个整数 k(k<n)。从 n 个整数中任选 k 个整数相加,可分别得到一系列的和。例如当 n=4,k=3,44 个整数分别为 3,7,12,193,7,12,19 时,可得全部的组合与它们的和为:
3+7+12=223+7+12=22
3+7+19=293+7+19=29
7+12+19=387+12+19=38
3+12+19=343+12+19=34
现在,要求你计算出和为素数共有多少种。
例如上例,只有一种的和为素数:3+7+19=293+7+19=29。
输入格式
第一行两个空格隔开的整数 n,k(1≤n≤20,k<n)。
第二行 n 个整数,分别为 x1,x2,⋯,xn(1≤xi≤5×10^6)。
输出格式
输出一个整数,表示种类数。
输入输出样例
输入 #1
4 3 3 7 12 19
输出 #1
1
说明/提示
【题目来源】
NOIP 2002 普及组第二题
题解
#include<bits/stdc++.h>
using namespace std;
int n,r,a[21],b[21],c[21],ans=0;
bool func(int n){if(n<=1)return false;for(int i=2;i<=sqrt(n);i++)if(n%i==0)return false;return true;
}
void bfs(int g){if(g>r){int temp=0;for(int i=1;i<=r;i++)temp+=c[i];ans+=func(temp);return; }for(int i=b[g-1]+1;i<=n;i++){b[g]=i;c[g]=a[i];bfs(g+1);c[g]=0;}
}
int main(){cin>>n>>r;for(int i=1;i<=n;i++)cin>>a[i];bfs(1);cout<<ans;return 0;
}