如果对你有帮助，希望给个一键三连！
目录
共13题
八皇后
题目描述:
要在国际象棋棋盘（八行八列）中放八个皇后，使任意两个皇后都不能互相吃。（提示：皇后能吃同一行、同一列、同一对角线的任意棋子。）
输入格式:
无输入。输出格式:
若干行，每行一种放置方案；首先输出方案数，然后是八个数，表示每行皇后放置的列号。
限制:
空间限制：128MByte
时间限制：1秒样例:
输出：
<1>1 5 8 6 3 7 2 4
<2>1 6 8 3 7 4 2 5
<3>1 7 4 6 8 2 5 3
<4>1 7 5 8 2 4 6 3
....思路：
开始看题目，先把题目简要条件和问题说一下
有八个皇后同时在一个8*8的棋盘中，使皇后们不会互相吃（皇后攻击与自己同行，同列，同斜线，同反斜线的皇后）这就是大概摘要
先分析这道题（又开始画图）
一个棋盘，是一个平面图形，所以可以想象成二维数组（是想象，不是直接用）
然后，我们来就这个图想一想几个皇后的条件
同行，同列，同斜线，同反斜线我们设 一个皇后的位置 行是a 列是b
同行：只要行是a，就不能放皇后
同列：只要列是b，就不能放皇后
同斜线(斜线是往左斜)：根据观察发现(不理解可以看看上面表格)，a+b在一整个斜线都是不变的，所以? 只要行和列的和与a+b相同，就不能放皇后
同反斜线(斜线是往右斜)：根据观察发现，a-b在一整行反斜线都是不变的，因为a-b是负数，所以必须更改一下 只要行和列加8与a+b+8相同，就不能放皇后
(这是重要条件，需要好好理解)
然后我们来用自己人脑来写一下这道题
先选1 1，然后这一行这一列都不可以选了，2 2是1 1的反斜线，不能选，2 3可以选...然后遇到了一种情况，有个皇后没法放了，这时候我们就要改变一下上一个皇后的位置。我们现在就是要模拟这个过程
这符合了递归的运算模式相同，范围更小?而没法放的情况就是回溯
既然想好了方向，就按照递归的想法一步步写DFS搜索与回溯的函数吧
void dfs(int step)first截止条件:这里当皇后放到第8个时，就不用递归了，但是因为上一次递归中会多加一个，所以是当step==9时，截止，把获得的位置给输出出来
if(step==9){
for(int i=1;i<=8;i++){
cout<<selected[i]<<" ";
}
cout<<endl;
}second搜索和回溯：判断是否与以前放的皇后冲突(是否在其他皇后的同行同列同斜线同反斜线)根据我们上面所分析的，我们用三个数组来存位置是否可以放(flag1[],flag2[],flag3[])。我们进行判断时，我们要用到8次循环，所以我们可以将for循环中的i定为位置中的列来用。当我们把这个棋盘的选择想成树时(这里我就不画了，可以自己画理解一下)，每次都有8次选择，所以我们可以用回溯算法，一颗子树搜索完后，将flag1,2,3回溯为零，继续进行下一个子树的搜索，由此我们写出代码
else{
for(int i=1;i<=8;i++){
if(!flag1[i]&&!flag2[step+i]&&!flag3[i-step+8]){
flag1[i]=1;
flag2[step+i]=1;
flag3[i-step+8]=1;
selected[step]=i;
dfs(step+1);
flag1[i]=0;
flag2[step+i]=0;
flag3[i-step+8]=0;
}
}
}?
}这里再次申明一下，i是列，step是行
这里判断是否flag里面有数，如果有数就不能放。如果没数，就先把flag同行同列同斜线同反斜线都设定为1 (没理解看之前说的皇后的条件)
因为这个输出是按第一个数字输出是第一行皇后的列数，其次是第二行....所以我们只要把记位置的数组selected中的第step行赋值所对应的i就行了
然后dfs递归，递归下一层，也就是把层数加一，直到这一个子树搜索完(也就是step==9时)后，就又回到了这里，我们后面要搜索下一棵子树，所以我们要把flag都给归零。
third输出样式：这里输出要输出这是第多少种情况，所以我们定义一个变量cnn来记这是第多少种情况，所以我们要对first里的的代码进行修改
if(step==9){
cout<<"<"<<++cnn<<">";
for(int i=1;i<=8;i++){
cout<<selected[i]<<" ";
}
cout<<endl;
}这样，我们就可以拼凑出完整的dfs函数
dfs：
void dfs(int step){
if(step==9){
cout<<"<"<<++cnn<<">";
for(int i=1;i<=8;i++){
cout<<selected[i]<<" ";
}
cout<<endl;
}else{
for(int i=1;i<=8;i++){
if(!flag1[i]&&!flag2[step+i]&&!flag3[i-step+8]){
flag1[i]=1;
flag2[step+i]=1;
flag3[i-step+8]=1;
selected[step]=i;
dfs(step+1);
flag1[i]=0;
flag2[step+i]=0;
flag3[i-step+8]=0;
}
}
}
}这个题并没有任何输入，所以我们只需要从第一行开始dfs就可以了
主函数：
int main(){
dfs(1);
return 0;
}其中需要的变量：
int selected[20];
int flag1[20];
int flag2[20];
int flag3[20];
int cnn;头文件：
#include <iostream>
using namespace std;完整代码：
#include <iostream>
using namespace std;
int selected[20];
int flag1[20];
int flag2[20];
int flag3[20];
int cnn;
void dfs(int step);
int main(){
dfs(1);
return 0;
}
void dfs(int step){
if(step==9){
cout<<"<"<<++cnn<<">";
for(int i=1;i<=8;i++){
cout<<selected[i]<<" ";
}
cout<<endl;
}else{
for(int i=1;i<=8;i++){
if(!flag1[i]&&!flag2[step+i]&&!flag3[i-step+8]){
flag1[i]=1;
flag2[step+i]=1;
flag3[i-step+8]=1;
selected[step]=i;
dfs(step+1);
flag1[i]=0;
flag2[step+i]=0;
flag3[i-step+8]=0;
}
}
}
}彩票
题目描述:
有一种彩票的玩法是从1~49这49个整数中挑选6个数字。小明为此研究出一个选号的策略，就是从这49个数字中选出一个子集S，S中包含了k（6<=k<20）个数字，然后从S中再选择6个数字作为最终选定的号码。
你的任务是，给你k和集合S，输出从S中选择投注号码的所有组合。
输入格式:
输入包含多组测试数据。每组输入首先是一个整数k（6<=k<20）。然后是k个整数，表示集合S，这k个整数按升序给出。当k=0时，输入结束。输出格式:
对于每组输入，输出所有的投注组合，每行一种，每种按照号码升序排列，所有组合按照字典序升序排列。
每两组输出之间输出一个空行。限制:
空间限制：128MByte
时间限制：1秒样例:
输入：
7 1 2 3 4 5 6 7
8 1 2 3 5 8 13 21 34
0输出：
1 2 3 4 5 6
1 2 3 4 5 7
1 2 3 4 6 7
1 2 3 5 6 7
1 2 4 5 6 7
1 3 4 5 6 7
2 3 4 5 6 7
1 2 3 5 8 13
1 2 3 5 8 21
1 2 3 5 8 34
1 2 3 5 13 21
1 2 3 5 13 34
1 2 3 5 21 34
1 2 3 8 13 21
1 2 3 8 13 34
1 2 3 8 21 34
1 2 3 13 21 34
1 2 5 8 13 21
1 2 5 8 13 34
1 2 5 8 21 34
1 2 5 13 21 34
1 2 8 13 21 34
1 3 5 8 13 21
1 3 5 8 13 34
1 3 5 8 21 34
1 3 5 13 21 34
1 3 8 13 21 34
1 5 8 13 21 34
2 3 5 8 13 21
2 3 5 8 13 34
2 3 5 8 21 34
2 3 5 13 21 34
2 3 8 13 21 34
2 5 8 13 21 34
3 5 8 13 21 34思路：
把六个数扫一遍，组合一下就完了
代码如下：
#include<bits/stdc++.h>
using namespace std;
int n,a[60],ans[60];
void dfs(int num,int start) {
if(num==6) {
for(int i=0; i<6; i++) printf("%d ",ans[i]);
printf("\n");
return;
}
for(int i=start; i<n; i++) {
ans[num]=a[i];
dfs(num+1,i+1);
}
}
int main() {
while(scanf("%d",&n)&&n) {
for(int i=0; i<n; i++)
scanf("%d",&a[i]);
sort(a,a+n);
dfs(0,0);
printf("\n");
}
}堆积木
题目描述:
小明的侄子要过生日了，小明买了一套儿童积木送他。这套积木由N个边长为1厘米的正方体小块组成，小明想把这些小块堆成一个大的矩形方体，然后将整个方体包裹上漂亮的包装纸，请问小明最少需要多少平方厘米的包装纸即可？
输入格式:
输入的第一行为一个正整数C，表示测试样例的组数。
每组输入是一个正整数N（1<=N<=1000），表示积木块的个数。
输出格式:
对于每组输入，输出将整个方体完全包裹上包装纸所需要的包装纸的最小面积。限制:
空间限制：32MByte
时间限制：1秒样例:
输入：
5
9
10
26
27
100输出：
30
34
82
54
130思路：
把积木块组成的方体的面积算一下，在比较一下大小就完了
代码如下:
#include<iostream>
using namespace std;
int main() {
int k,i,j,min,are,q,n;
cin>>q;
while(q--) {
cin>>n;
min=10000000;
for(i=1; i<=n; i++) {
for(j=1; j*i<=n; j++) {
if(n%(i*j)==0) {
k=n/i/j;
are=2*(i*j+i*k+j*k);
if(are<min) min=are;
}
}
}
cout<<min<<endl;
}
return 0;
}排三角形
题目描述:
将1，2，······,9共9个数排成下列形态的三角形。
??????????????????????? a
???????????????????? b????? c
????????????????? d????? ??????e
??????????????? f???? g???? h???? i
???
????其中：a～i分别表示1，2，······,9中的一个数字，并要求同时满足下列条件：
????（1）a<f<i;
????（2）b<d, g<h, c<e
??? （3）a+b+d+f=f+g+h+i=i+e+c+a=P
程序要求：
??????根据输入的边长之和P，输出所有满足上述条件的三角形的个数。
输入格式:
每个测试文件只包含一组测试数据，每组输入一个整数P，表示边长之和。
输出格式:
对于每组输入数据，输出所有满足上述条件的三角形的个数。
如果无解，则输出"Not exist"（引号不输出）。
限制:
空间限制：125MByte
时间限制：1秒样例:
输入：
23输出：
2思路：
输入，然后把每一个条件都给判断一下，用一个变量来记成立次数，最后输出变量就完了
代码如下：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,a[10],b[4][3],c[4][3],d[4],vis[35];
int cnt=0;
void judge(int one,int two,int three) {
d[0]=b[0][0]+c[one][0];
d[1]=b[1][0]+c[two][0];
d[2]=b[2][0]+c[three][0];
if(d[0]==d[1] && d[1]==d[2]) {
vis[d[0]]++;
}
}
void check(int m,int k) {
for(int i=m+1; i<=9; i++) {
if(!a[i]) {
c[k][0]=m+i;
c[k][1]=m;
c[k][2]=i;
if(k==2) {
judge(0,1,2);
judge(0,2,1);
judge(1,0,2);
judge(1,2,0);
judge(2,0,1);
judge(2,1,0);
return ;
}
a[i]=1;
for(int j=m+1; j<=9; j++) {
if(!a[j]) {
a[j]=1;
check(j,k+1);
a[j]=0;
break;
}
}
a[i]=0;
}
}
}
void solve() {
memset(vis,0,sizeof(vis));
memset(a,0,sizeof(a));
for(int i=1; i<=9; i++) {
a[i]=1;
for(int j=i+1; j<=9; j++) {
a[j]=1;
for(int k=j+1; k<=9; k++) {
if(i==j || j==k || i==k) continue;
a[k]=1;
b[0][0]=i+j;
b[1][0]=j+k;
b[2][0]=k+i;
b[0][1]=i;
b[1][1]=j;
b[2][1]=k;
for(int z=1; z<=9; z++) {
if(!a[z]) {
a[z]=1;
check(z,0);
a[z]=0;
break;
}
}
a[k]=0;
}
a[j]=0;
}
a[i]=0;
}
}
int main() {
solve();
scanf("%d",&n);
if(vis[n]) printf("%d\n",vis[n]);
else printf("Not exist\n");
return 0;
}迷宫问题
题目描述:
给定一个N * M(1<=N,M<=10)方格的迷宫，迷宫里有T处障碍，障碍处不可通过。给定起点坐标和终点坐标，问: 每个方格最多经过1次，有多少种从起点坐标到终点坐标的方案。在迷宫中移动有上下左右四种方式，每次只能移动一个方格。
输入格式:
第一行N、M和T，N为行，M为列，T为障碍总数。?
第二行起点坐标SX,SY，终点坐标FX,FY。?
接下来T行，每行为障碍点的坐标。?
输出格式:
给定起点坐标和终点坐标，问每个方格最多经过1次，从起点坐标到终点坐标的方案总数。限制:
空间限制：128MByte
时间限制：1秒样例:
输入：
2 2 1
1 1 2 2
1 2输出：
1提示:
数据保证起点上没有障碍。??
数据保证起点与终点不重合。??
思路：
每一步都进行判断，判断周围是否有障碍或终点，如果没有，就向四个方向移动（横纵坐标加减）并标记已经走过，记录能到达终点且路不同的方案，最后输出就完了
代码如下：
#include<iostream>
using namespace std;
int n,m,t,sx,sy,fx,fy;
const int N=100;
int is[N][N];
int sum=0;
void dfs(int x,int y) {
if(x<1||x>n||y<1||y>m){
return;
}
else if(x==fx&&y==fy) {
sum++;
return;
} else {
// is[x][y]=0;
if(!is[x][y-1]) {
is[x][y-1]=1;
dfs(x,y-1);
is[x][y-1]=0;
}
if(!is[x][y+1]) {
is[x][y+1]=1;
dfs(x,y+1);
is[x][y+1]=0;
}
if(!is[x+1][y]) {
is[x+1][y]=1;
dfs(x+1,y);
is[x+1][y]=0;
}
if(!is[x-1][y]) {
is[x-1][y]=1;
dfs(x-1,y);
is[x-1][y]=0;
}
}
}
int main() {
int x,y,i,j;
cin>>n>>m>>t;
cin>>sx>>sy>>fx>>fy;
for(i=1; i<=t; i++) {
cin>>x>>y;
is[x][y]=1;
}
is[sx][sy]=1;
dfs(sx,sy);
cout<<sum;
return 0;
}全排列问题
题目描述:
输出自然数 1 到 n 所有不重复的排列，即 n 的全排列，要求所产生的任一数字序列中不允许出现重复的数字，输出按字典序排列。
输入格式:
一个整数 n。输出格式:
由 1～n 组成的所有不重复的数字序列，每行一个序列。
每个数字保留 5 个宽度。
限制:
空间限制：128MByte
时间限制：1秒样例:
输入：
3输出：
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1提示:
1≤n≤9思路：
初看题目以为好简单，草草写了个全排列就交了，结果发现就过了一个点TAT
注意：此题要求字典序排列输出
仔细一想，加个排序就完了
代码如下：
#include<iostream>
using namespace std;
const int N=15;
int n;
bool flag[N];
int ans[N];
void print(){
for(int i=0;i<n;i++){
printf("%5d",ans[i]);
}
printf("\n");
}
void dfs(int pos){
if(pos==n){
print();
return;
}
for(int i=1;i<=n;i++){
if(flag[i]) continue;
ans[pos]=i;
flag[i]=true;
dfs(pos+1);
flag[i]=false;
}
}
int main(){
scanf("%d",&n);
dfs(0);
return 0;
}素数圆环
题目描述:
如图所示为一个由n个圆圈构成的圆环。将自然数1，2，...，n放入圆圈内，并且要求任意两个相邻的圆圈内的数字之和为素数。请问给你圆圈数，你能给出放置自然数的所有正确方案吗？
注意：圆圈中的数字一定是从1开始的，并且连续不重复。
输入格式:
输入包含多组测试数据。每组输入占一行，为整数n（0<n<20），表示圆圈数。输出格式:
对于每组输入，输出所有正确的方案，按字典序从小到大排序。每组输出后输出一个空行。具体输出格式见输出样例。
注意：只能按照顺时针方向放置数字。
限制:
空间限制：32MByte
时间限制：1秒样例:
输入：
6
8输出：
Case 1:
1 4 3 2 5 6
1 6 5 2 3 4
Case 2:
1 2 3 8 5 6 7 4
1 2 5 8 3 4 7 6
1 4 7 6 5 8 3 2
1 6 7 4 3 8 5 2
思路：?
圆圈中的数字一定是从1开始，任意两个相邻的圆圈内的数字之和为素数。
如图，因为从一开始，所以可以将6和1截断。
1 4 3 2 5 6
这样咱们就可以用搜索，再判断相邻两数和是否是质数就可以了。
首先需要一个判断质数的函数：
bool prine(int a){
if(a==1){
return false;
}
for(int i=2;i<=sqrt(a);++i){
if(a%i==0){
return false;
}
}
return true;
}然后进行搜索：
void dfs(int step){
if(n==1){//如果递归到一，说明已经结束了
return;
}
if(step>n){//第step个数是否比n大
if(prine(1+sel[n])){//判断是不是素数
for(int i=1;i<=n;i++){
cout<<sel[i]<<" ";
}
cout<<endl;
return;
}
}
for(int i=2;i<=n;i++){
if(!flag[i]&&prine(sel[step-1]+i)){//如果没有重复并且是质数
sel[step]=i;//存储
flag[i]=1;//标记
dfs(step+1);//递归
flag[i]=0;//初始化
sel[step]=0;//初始化
}
}
}主函数：
int main(){
while(cin>>n){
sel[1]=1;
flag[1]=1;
cout<<"Case"<<" "<<++cnn<<":";
cout<<endl;
dfs(2);//第一个数为一
cout<<endl;
}
return 0;
}代码如下:
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<ctype.h>
#include<algorithm>
#define inf 0x3f3f3f3f
using namespace std;
int a[50];
int lin[30],n;
int vs[30];
int dat[20][30];
int sushu (int x) {
int i;
int k=(int)sqrt(x);
for(i=2; i<=k; i++)
if(x%i==0)
return 0;
return 1;
}
void dfs(int x) {
int i;
if(x>n) {
if(a[lin[n]+1]==0)
return ;
printf("%d",lin[1]);
for(i=2; i<=n; i++)
printf(" %d",lin[i]);
printf("\n");
return ;
}
for(i=0; dat[lin[x-1]][i]<=n; i++) {
if(vs[dat[lin[x-1]][i]]==0) {
vs[dat[lin[x-1]][i]]=1;
lin[x]=dat[lin[x-1]][i];
dfs(x+1);
vs[dat[lin[x-1]][i]]=0;
}
}
}
int main () {
int i,j,k;
memset(a,0,sizeof(a));
memset(dat,inf,sizeof(dat));
for(i=3; i<=50; i++) {
if(sushu(i)) a[i]=1;
}
for(i=1; i<20; i++) {
for(j=1,k=0; j<20; j++) {
if(a[i+j]) {
dat[i][k]=j;
k++;
}
}
}
int l=0;
while(~scanf("%d",&n)) {
l++;
memset(vs,0,sizeof(vs));
vs[1]=1;
lin[1]=1;
printf("Case %d:\n",l);
dfs(2);
printf("\n");
}
return 0;
}靶形数独
题目描述:
小城和小华都是热爱数学的好学生，最近，他们不约而同地迷上了数独游戏，好胜的他们想用数独来一比高低。但普通的数独对他们来说都过于简单了，于是他们向Z博士请教，Z博士拿出了他最近发明的“靶形数独”，作为这两个孩子比试的题目。
靶形数独的方格同普通数独一样，在9格宽×9格高的大九宫格中有9个3格宽×3格高的小九宫格（用粗黑色线隔开的）。在这个大九宫格中，有一些数字是已知的，根据这些数字，利用逻辑推理，在其他的空格上填入1到9的数字。每个数字在每个小九宫格内不能重复出现，每个数字在每行、每列也不能重复出现。但靶形数独有一点和普通数独不同，即每一个方格都有一个分值，而且如同一个靶子一样，离中心越近则分值越高。（如图）
上图具体的分值分布是：最里面一格（黄色区域）为10分，黄色区域外面的一圈（红色区域）每个格子为9分，再外面一圈（蓝色区域）每个格子为8分，蓝色区域外面一圈（棕色区域）每个格子为7分，最外面一圈（白色区域）每个格子为6分，如上图所示。比赛的要求是：每个人必须完成一个给定的数独（每个给定数独有可能有不同的填法），而且要争取更高的总分数。而这个总分数即每个方格上的分值和完成这个数独时填在相应格上的数字的乘积的总和。如图，在以下这个已经填完数字的靶形数独游戏中，总分为2829。游戏规定，将以总分数的高低决出胜负。
由于求胜心切，小城找到了善于编程的你，让你帮他求出，对于给定的靶形数独，能够得到的最高分数。
输入格式:
每组输入数据一共9行，每行9个整数（每个数都在0—9的范围内），表示一个尚未填满的数独方格，未填满的空格用“0”表示。每两个数字之间用一个空格隔开。
数据规模：
40%的数据，数独中非0数的个数不少于30；
80%的数据，数独中非0数的个数不少于26；
100%的数据，数独中非0数的个数不少于24。
输出格式:
每组输出共1行。输出可以得到的靶形数独的最高分数。如果这个数独无解，则输出整数-1。
限制:
空间限制：128MByte
时间限制：2秒样例:
输入：
7 0 0 9 0 0 0 0 1
1 0 0 0 0 5 9 0 0
0 0 0 2 0 0 0 8 0
0 0 5 0 2 0 0 0 3
0 0 0 0 0 0 6 4 8
4 1 3 0 0 0 0 0 0
0 0 7 0 0 2 0 9 0
2 0 1 0 6 0 8 0 4
0 8 0 5 0 4 0 1 2
0 0 0 7 0 2 4 5 3
9 0 0 0 0 8 0 0 0
7 4 0 0 0 5 0 1 0
1 9 5 0 8 0 0 0 0
0 7 0 0 0 0 0 2 5
0 3 0 5 7 9 1 0 8
0 0 0 6 0 1 0 0 0
0 6 0 9 0 0 0 0 1
0 0 0 0 0 0 0 0 6输出：
2829
2852思路：
开一个二维数组存放，然后每一个格点都算一下值，并比较，最后输出最高分数就完了
代码如下:
#include<bits/stdc++.h>
using namespace std;
struct node{
int x,y;
}node[100];
struct fish{
int x;
int num;
}row[100];
int len=0,num[10][10];
int flag[10][10],ans=-1;
int flag1[10][10],flag2[10][10],flag3[10][10];
int fenshu[10][10] ={{0,0,0,0,0,0,0,0,0,0},
{0,6,6,6,6,6,6,6,6,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,9,10,9,8,7,6,},
{0,6,7,8,9,9,9,8,7,6},
{0,6,7,8,8,8,8,8,7,6},
{0,6,7,7,7,7,7,7,7,6},
{0,6,6,6,6,6,6,6,6,6}};
int cmp(int x,int y){
return (y-1)/3*3+(x-1)/3+1;
}
bool comp(fish r1,fish r2){
if(r1.num<r2.num){
return true;
}
return false;
}
void dfs(int p){
if(p==len){
int sum=0;
for(int i=1;i<=9;++i){
for (int j=1;j<=9;++j){
sum+=num[i][j]*fenshu[i][j];
}
}
ans=max(ans,sum);
}else{
int x=node[p].x;
int y=node[p].y;
for(int i=1;i<=9;i++){
if(!flag1[x][i]&&!flag2[y][i]&&!flag3[cmp(x,y)][i]){
num[x][y]=i;
flag1[x][i]=flag2[y][i]=flag3[cmp(x,y)][i]=1;
dfs(p+1);
num[x][y]=0;
flag1[x][i]=flag2[y][i]=flag3[cmp(x,y)][i]=0;
}
}
}
}
int main(){
for(int i=1;i<=9;++i) {
row[i].x=i;
}
for(int i=1;i<=9;++i) {
for(int j=1;j<=9;++j) {
cin>>num[i][j];
if(!num[i][j]){
row[i].num++;
}else{
flag1[i][num[i][j]]=1;
flag2[j][num[i][j]]=1;
flag3[cmp(i,j)][num[i][j]]=1;
}
}
}
sort(row+1,row+10,comp);
for(int i=1;i<=9;++i){
for(int j=1;j<=9;++j){
if(!num[row[i].x][j]){
node[len].x=row[i].x;
node[len].y=j;
len++;
}
}
}
dfs(0);
cout<<ans<<endl;
return 0;
}产生数
题目描述:
给出一个整数n（n<1030) 和k个变换规则（k<=15）。
规则：
?一位数可变换成另一个一位数：
? ? ? ??规则的右部不能为零。
?例如：n=234。有规则（k＝2）：
? ? ? ? ? ? ? ? ?2->5
? ? ? ? ? ? ? ? ?3->6
? ? ? ? 上面的整数234经过变换后可能产生出的整数为（包括原数）：
? ? ? ? ? ? ? ? ?234
? ? ? ? ? ? ? ? ?534
? ? ? ? ? ? ? ? ?264
? ? ? ? ? ? ? ? ?564
? ? ? ? 共4种不同的产生数
问题：
给出一个整数n和k个规则。
求出：
经过任意次的变换（0次或多次），能产生出多少个不同整数。仅要求输出个数。
输入格式:
每个测试文件只包含一组测试数据，每组输入的第一行输入两个整数n和k（n<1030，k<=15）。
接下来k行每行输入一个规则，每个规则由两个整数构成。
输出格式:
对于每组输入数据，输出一个整数，表示满足条件的个数。
限制:
空间限制：125MByte
时间限制：1秒样例:
输入：
234 2
2 5
3 6输出：
4思路：
按题目说的一步一步来变换就完了
代码如下:
#include<bits/stdc++.h>
#define ll long long
#define next next_
using namespace std;
ll len,k,u[22],v[22],num[11];
string s,ans="1";
bool vis[11];
void dfs(ll t){
vis[t]=true;
for(ll i=1;i<=k;i++){
if(u[i]==t){
if(!vis[v[i]]){
vis[v[i]]=true;
dfs(v[i]);
}
}
}
}
string its(ll a){
stringstream ss;
ss<<a;
string str=ss.str();
return str;
}
string mul(string a,string b){
string s="";
int lena=a.size();
int lenb=b.size();
int aa[1010],bb[1010],cc[1010];
memset(aa,0,sizeof(aa));
memset(bb,0,sizeof(bb));
memset(cc,0,sizeof(cc));
for(int i=1;i<=lena;i++) aa[i]=a[lena-i]-'0';
for(int i=1;i<=lenb;i++) bb[i]=b[lenb-i]-'0';
for(int i=1;i<=lena;i++){
for(int j=1;j<=lenb;j++){
cc[i+j-1]+=aa[i]*bb[j];
if(cc[i+j-1]>=10){
cc[i+j]+=cc[i+j-1]/10;
cc[i+j-1]%=10;
}
}
}
if(cc[lena+lenb]) s+=cc[lena+lenb]+'0';
for(int i=lena+lenb-1;i>=1;i--) s+=cc[i]+'0';
return s;
}
int main(){
cin>>s;
len=s.size();
scanf("%lld",&k);
for(ll i=1;i<=k;i++)
scanf("%lld%lld",&u[i],&v[i]);
for(ll i=0;i<=9;i++){
for(ll j=0;j<=9;j++) vis[j]=false;
dfs(i);
for(ll j=0;j<=9;j++) if(vis[j]) num[i]++;
}
for(ll i=0;i<len;i++)
ans=mul(ans,its(num[s[i]-'0']));
cout<<ans;
return 0;
}选数
题目描述:
已知n个整数 x1,x2,…,xn，以及一个整数 k（k＜n）。从n个整数中任选k个整数相加，可分别得到一系列的和。例如当n=4，k＝3，4个整数分别为 3，7，12，19时，可得全部的组合与它们的和为：
? ? 3＋7＋12=22??3＋7＋19＝29??7＋12＋19＝38??3＋12＋19＝34
现在，要求你计算出和为素数共有多少种。
例如上例，只有一种的和为素数：3＋7＋19＝29
?
输入格式:
每个测试文件只包含一组测试数据，每组输入的第一行输入两个整数n和k（1<=n<=20，k＜n）。 第二行输入n个整数x1,x2,…,xn（1<=xi<=50000）。
输出格式:
对于每组输入数据，输出一个整数，表示满足条件的种数。
限制:
空间限制：125MByte 时间限制：1秒
样例:
输入： 4 3 3 7 12 19
输出： 1
思路:
把每种方案都算一遍，并记录有多少符合条件就完了
代码如下:
#include <iostream>
#include <cmath>
using namespace std;
const int N=100;
int a[N];
int n,k,ans,i;
bool shai(int x) {
for(i=2; i<=sqrt(x); i++)
if(x%i==0)
return false;
return true;
}
void dfs(int s,int l,int u) {
if(u==k) {
if(shai(s))
ans++;
} else {
for(int i=l; i<n; i++)
dfs(s+a[i],i+1,u+1);
}
}
int main() {
scanf("%d%d",&n,&k);
ans=0;
for(i=0; i<n; i++)
scanf("%d",&a[i]);
dfs(0,0,0);
printf("%d\n",ans);
return 0;
}数的划分
题目描述:
将整数n分成k份，且每份不能为空，任意两份不能相同（不考虑顺序）。
例如：n=7，k=3，下面三种分法被认为是相同的。
1，1，5；
1，5，1；
5，1，1；
问有多少种不同的分法。
输入格式:
每个测试文件只包含一组测试数据，每组输入两个整数n和k（6<n<=200，2<=k<=6）。
输出格式:
对于每组输入数据，输出一个整数，即不同的分法。
下面是对样例数据的说明：
样例中的四种分法是：
1，1，5
1，2，4
1，3，3
2，2，3
限制:
空间限制：125MByte 时间限制：1秒
样例:
输入： 7 3
输出： 4
思路：
该题比较简单，只需要把每种情况算一遍，再简单的按题目要求去个重，最后输出分法数就完了
代码如下:
#include<cstdio>
using namespace std;
int f[201][7],i,j,n,k;
int main(){
scanf("%d%d",&n,&k);
for(i=1;i<=n;++i)
for(j=1;j<=k;++j){
if(i<j) f[i][j]=0;
else if(j==1) f[i][j]=1;
else if(i==j) f[i][j]=1;
else f[i][j]=f[i-1][j-1]+f[i-j][j];
}
printf("%d\n",f[n][k]);
return 0;
}单词接龙
题目描述:
单词接龙是一个与我们经常玩的成语接龙相类似的游戏，现在我们已知一组单词，且给定一个开头的字母，要求出以这个字母开头的最长的“龙”（每个单词都最多在“龙”中出现两次），在两个单词相连时，其重合部分合为一部分，例如beast和astonish，如果接成一条龙则变为beastonish，另外相邻的两部分不能存在包含关系，例如at和atide间不能相连。
输入格式:
每个测试文件只包含一组测试数据，每组输入的第一行为一个单独的整数n（n<=20）表示单词数，以下n行每行有一个单词，输入的最后一行为一个单个字符，表示“龙”开头的字母。你可以假定以此字母开头的“龙”一定存在。
输出格式:
对于每组输入数据，输出以此字母开头的最长的“龙”的长度。
下面的测试样例最后连成的“龙”为atoucheatactactouchoose。
限制:
空间限制：125MByte 时间限制：1秒
样例:
输入： 5 at touch cheat choose tact a
输出： 23
思路:
用一个char数组，判断一下数组的首和尾，然后把首尾相同的字符删去，最后输出数组长度就完了
代码如下:
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
char str[101][106],st;
int jl[101],n,tot=0,maxx=0,l[101],n2;
void dfs(int x,int y){
if(tot>maxx) maxx=tot;
for(int i=1;i<=n2;i++){
if(x==1){
if(str[i][0]!=st) continue;
l[i]=1;tot+=jl[i];
dfs(x+1,i);
l[i]=0;tot-=jl[i];
}
if(l[i]==1)continue;
int c=1,k=jl[y]-1;
char a[1001]={'\0'},b[1001]={'\0'};
while(c<=jl[i]&&c<jl[y]){
strncpy(a,str[i],c);
strncpy(b,&str[y][k--],c);
if(strcmp(a,b)==0){
tot+=jl[i]-c;
l[i]=1;
dfs(x+1,i);
tot-=jl[i]-c;
l[i]=0;
break;
}
c++;
}
}
}
int main(){
cin>>n;
n2=2*n;
for(int i=1;i<=n;i++){
cin>>str[i];
jl[i]=strlen(str[i]);
}
for(int i=n+1;i<=n2;i++){
strcpy(str[i],str[i-n]);
jl[i]=jl[i-n];
}
cin>>st;
dfs(1,0);
cout<<maxx<<endl;
return 0;
}工作分配问题
题目描述:
设有n件工作分配给n个人。为第i个人分配工作j所需的费用为c[i][j] 。试设计一个算法，计算最佳工作分配方案，为每一个人都分配1 件不同的工作，并使总费用达到最小。?
输入格式:
第一行一个正整数n(1<=n<=20),接下来的n 行，每行n 个数，表示工作费用 。
输出格式:
输出有1行，每行输出最小总费用。
限制:
空间限制：128MByte 时间限制：1秒
样例:
输入： 5 50 43 1 58 60 87 22 5 62 71 62 98 97 27 38 56 57 96 73 71 92 36 43 27 95
输出： 144
思路：
首先输入，然后记录每个人的工作费用（比较大小（和看电视差不多）），最后输出费用
代码如下:
#include <cstdio>
#include <cstdlib>
int t[31][31],ans = 0x7fffff;
int sum= 0,n;
bool check[300];
void cmp() {
if (ans > sum)
ans = sum;
}
void find(int n, int k) {
if (k == n + 1) {
cmp();
return;
}
for (int i = 1; i <= n; i++) {
if (!check[i]) {
check[i] = true;
sum += t[k][i];
if (sum < ans) {
find(n, k + 1);
}
sum -= t[k][i];
check[i] = false;
}
}
}
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
scanf("%d", &t[i][j]);
find(n, 1);
printf("%d\n",ans);
return 0;
}