问题描述：1. 带分数
100 可以表示为带分数的形式：100 = 3 + 69258 / 714。
还可以表示为：100 = 82 + 3546 / 197。
注意特征：带分数中，数字 1~9 分别出现且只出现一次（不包含 0）。
类似这样的带分数，100 有 11 种表示法。
解决方案：
#include<iostream>
#include<string.h>
using namespace std;
int a[10]={0};
bool Division(int m) //分割数字
{
int t;
while(m)
{
t=m%10;
if(t==0) //为零不符合题意
return 0;
a[t]++;
m=m/10;
}
return 1;
}
int main()
{
int n,ans=0;
cin>>n;
for(int i=1;i<n;i++)
{
for(int j=1;j<=4938;j++)
{
memset(a,0,sizeof(a)); //每次使数组a的各位为零
int k=(n-i)*j;
if(Division(i)&&Division(j)&&Division(k))
{
int flag=1;
for(int x=1;x<10;x++) //判断数字是否重复
{
if(a[x]!=1)
{
flag=0;
break;
}
}
if(flag==1)
ans++;
}
}
}
cout<<ans;
return 0;
} 问题描述：2. 李白打酒
话说大诗人李白，一生好饮。幸好他从不开车。
一天，他提着酒壶，从家里出来，酒壶中有酒 2 斗。他边走边唱：
无事街上走，提壶去打酒。
逢店加一倍，遇花喝一斗。
这一路上，他一共遇到店 5 次，遇到花 10 次，已知最后一次遇到的是花，他正好把酒喝光了。
请你计算李白遇到店和花的次序，可以把遇店记为 a，遇花记为 b。则：
babaabbabbabbbb 就是合理的次序。像这样的答案一共有多少呢？
请你计算出所有可能方案的个数（包含题目给出的）。
解决方案：14
#include <iostream>
using namespace std;
int ans;
void f(int hua,int dian,int jiu)
{
if(hua==1&&dian==0&&jiu==1)
ans++;
if(hua>1)
f(hua-1,dian,jiu-1);
if(dian>0)
f(hua,dian-1,jiu*2);
}
int main()
{
f(10,5,2);
cout<<ans<<endl;
return 0;
}问题描述：3. 第 39 级台阶
小明刚刚看完电影《第 39 级台阶》，离开电影院的时候，他数了数礼堂前的
台阶数，恰好是 39 级!
站在台阶前，他突然又想着一个问题：
如果我每一步只能迈上 1 个或 2 个台阶。先迈左脚，然后左右交替，最后一
步是迈右脚，也就是说一共要走偶数步。那么，上完 39 级台阶，有多少种不同的上法呢？
解决方案：51167078
#include <iostream>
using namespace std;
int ans=0;
void solve(int n,int step)
{
if(n==0 && step % 2==0)
ans++;
if(n<0)
return;
solve(n-1,step+1);
solve(n-2,step+1);
}
int main()
{
solve(39,0);
cout<<ans<<endl;
return 0;
}问题描述：4. 穿越雷区
已知的地图是一个方阵，上面用字母标出了 A，B 区，其它区都标了正号或负号
分别表示正负能量辐射区。
例如：
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
坦克车只能水平或垂直方向上移动到相邻的区。
数据格式要求：
输入第一行是一个整数n，表示方阵的大小， 4<=n<100
接下来是 n行，每行有n个数据，可能是 A，B，+，-中的某一个，中间用空格分开。
A，B 都只出现一次。
要求输出一个整数，表示坦克从 A 区到 B 区的最少移动步数。如果没有方案，则输出-1
例如：用户输入：
5
A + - + -
- + - - +
- + + + -
+ - + - +
B + - + -
则程序应该输出：
10
解决方案：
#include<iostream>
#include<queue>
using namespace std;
const int M = 100,INF = 0x3f3f3f3f;
const int move[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
int n,endx,endy;
char ch[M+5][M+5];
int a[M+5][M+5];
struct Coordinate
{
int x,y;
Coordinate(int x,int y):x(x),y(y){}
};
queue<Coordinate>q;
void bfs()
{
Coordinate t = q.front();
q.pop();
//cout<<t.x<<' '<<t.y<<endl;
for(int i=0;i<4;i++)
{
int tx = t.x + move[i][0];
int ty = t.y + move[i][1];
if(tx<1||ty<1||tx>n||ty>n||a[tx][ty]||ch[tx][ty]==ch[t.x][t.y])
continue;
a[tx][ty]=a[t.x][t.y]+1;
if(tx==endx&&ty==endy)
{
while(!q.empty())
q.pop();
return;
}
q.push(Coordinate(tx,ty));
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
cin>>ch[i][j];
if(ch[i][j]=='A')
{
q.push(Coordinate(i,j));
a[i][j]=0;
}
if(ch[i][j]=='B')
{
endx=i;
endy=j;
}
}
while(!q.empty())
bfs();
cout << a[endx][endy];
return 0;
}问题描述：5. 迷宫
下图给出了一个迷宫的平面图，其中标记为1的为障碍，标记为0的为可以通行的地方。
010000
000100
001001
110000
迷宫的入口为左上角，出口为右下角，在迷宫中，只能从一个位置走到这个它
的上、下、左、右四个方向之一。 对于上面的迷宫，从入口开始，可以按
DRRURRDDDR 的顺序通过迷宫， 一共 10 步。其中 D、U、L、R 分别表示向
下、向上、向左、向右走。对于下面这个更复杂的迷宫（30行50列），请找
出一种通过迷宫的方式， 其使用的步数最少，在步数最少的前提下，请找出字
典序最小的一个作为答案。 请注意在字典序中 D<L<R<U。
解决方案：
#include<iostream>
#include<string.h>
#include<queue>
using namespace std;
const int move[4][2]={{1,0},{0,-1},{0,1},{-1,0}};
const string S[4] = {"D","L","R","U"};
bool a[31][51];
struct Coordinate
{
int x,y;
string s;
Coordinate(int x,int y,string s):x(x),y(y),s(s){}
};
queue<Coordinate> q;
void bfs()
{
Coordinate t = q.front();
q.pop();
for(int i=0;i<4;i++)
{
int tx = t.x + move[i][0];
int ty = t.y + move[i][1];
if(tx<1||tx>30||ty<1||ty>50||a[tx][ty])
continue;
string ts = t.s + S[i];
if(tx==30&&ty==50)
{
while(!q.empty())
q.pop();
cout<<ts;
return;
}
a[tx][ty]=true;
q.push(Coordinate(tx,ty,ts));
}
}
int main()
{
for(int i=1;i<=30;i++)
for(int j=1;j<=50;j++)
{
char ch;
cin>>ch;
a[i][j] = (ch=='1');
}
q.push(Coordinate(1,1,""));
while(!q.empty())
bfs();
return 0;
}问题描述：6.跳马
中国象棋半张棋盘如图1所示。马自左下角(0,0)向右上角（m，n）跳。规定只能往右跳，不准往左跳。比如图1中所示为一种跳行路线，并将路径总数打印出来。
输入格式：
只有一行：两个数n，m
输出格式：
只有一个数：总方案数total。
解决方案：
#include <iostream>
using namespace std;
int n,m,ans;
const int move[4][2]={{1,2},{2,1},{2,-1},{1,-2}};
void dfs(int x,int y)
{
if(x==m&&y==n)
ans++;
for (int i = 0 ; i< 4 ;i++)
{
int tx = x + move[i][0];
int ty = y + move[i][1];
if(tx<0||tx>m||ty<0||ty>n)
continue;
else
dfs(tx,ty);
}
}
int main()
{
cin>>m>>n;
dfs(0,0);
cout<<ans<<endl;
return 0 ;
}问题描述：7.路径之谜
小明冒充X星球的骑士，进入了一个奇怪的城堡。
城堡里边什么都没有，只有方形石头铺成的地面。
假设城堡地面是 n x n 个方格。【如图1.png】所示。
按习俗，骑士要从西北角走到东南角。
可以横向或纵向移动，但不能斜着走，也不能跳跃。
每走到一个新方格，就要向正北方和正西方各射一箭。
（城堡的西墙和北墙内各有 n 个靶子）
同一个方格只允许经过一次。但不必做完所有的方格。
如果只给出靶子上箭的数目，你能推断出骑士的行走路线吗？
有时是可以的，比如图1.png中的例子。
本题的要求就是已知箭靶数字，求骑士的行走路径（测试数据保证路径唯一）
输入：
第一行一个整数N(0<N<20)，表示地面有 N x N 个方格
第二行N个整数，空格分开，表示北边的箭靶上的数字（自西向东）
第三行N个整数，空格分开，表示西边的箭靶上的数字（自北向南）
输出：
一行若干个整数，表示骑士路径。
为了方便表示，我们约定每个小格子用一个数字代表，从西北角开始编号: 0,1,2,3....
比如，图1.png中的方块编号为：
0 1 2 3
4 5 6 7
8 9 10 11
12 13 14 15
示例：
用户输入：
4
2 4 3 4
4 3 3 3
程序应该输出：
0 4 5 1 2 3 7 11 10 9 13 14 15
解决方案：
#include<iostream>
using namespace std;
const int move[4][2]={{1,0},{-1,0},{0,1},{0,-1}};
int n,p=0,a[21],b[21],step[401];
bool st[21][21];
bool dfs(int x,int y)
{
if(!a[y]||!b[x])
return false;
a[y]--,b[x]--;
if(x==n&&y==n)
{
bool st = true;
for(int i=1;i<=n;i++)
if(a[i]||b[i])
st = false;
if(st)
{
step[p++]=(x-1)*n+y-1;
return true;
}
}
for(int i=0;i<4;i++)
{
int tx=x+move[i][0];
int ty=y+move[i][1];
if(tx<1||tx>n||ty<1||ty>n)
continue;
if(dfs(tx,ty))
{
step[p++]=(x-1)*n+y-1;
return true;
}
}
a[y]++,b[x]++;
return false;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>a[i];
for(int j=1;j<=n;j++)
cin>>b[j];
dfs(1,1);
for(int i=p-1;i>=0;i--)
cout<<step[i]<<' ';
return 0;
}问题描述：8.未名湖边的烦恼
每年冬天，北大未名湖上都是滑冰的好地方。北大体育组准备了许多冰鞋，可是人太多了，每天下午收工后，常常一双冰鞋都不剩。
每天早上，租鞋窗口都会排起长龙，假设有还鞋的m个，有需要租鞋的n个。现在的问题是，这些人有多少种排法，可以避免出现体育组没有冰鞋可租的尴尬场面。（两个同样需求的人（比如都是租鞋或都是还鞋）交换位置是同一种排法）
输入格式 ：两个整数，表示m和n
输出格式 ：一个整数，表示队伍的排法的方案数。
样例输入 ：3 2
样例输出 ：5
数据规模和约定 ：m,n∈［0,18］
解决方案：
#include<iostream>
using namespace std;
int solve(int x,int y)
{
if(x<y)
return 0;
if(y==0)
return 1;
return solve(x-1,y)+solve(x,y-1);
}
int main()
{
int m,n;
cin>>m>>n;
int ans=solve(m,n);
cout<<ans<<endl;
}问题描述：9.大臣的旅费
很久以前，T王国空前繁荣。为了更好地管理国家，王国修建了大量的快速路，用于连接首都和王国内的各大城市。
为节省经费，T国的大臣们经过思考，制定了一套优秀的修建方案，使得任何一个大城市都能从首都直接或者通过其他大城市间接到达。同时，如果不重复经过大城市，从首都到达每个大城市的方案都是唯一的。
J是T国重要大臣，他巡查于各大城市之间，体察民情。所以，从一个城市马不停蹄地到另一个城市成了J最常做的事情。他有一个钱袋，用于存放往来城市间的路费。
聪明的J发现，如果不在某个城市停下来修整，在连续行进过程中，他所花的路费与他已走过的距离有关，在走第x千米到第x+1千米这一千米中（x是整数），他花费的路费是x+10这么多。也就是说走1千米花费11，走2千米要花费23。
J大臣想知道：他从某一个城市出发，中间不休息，到达另一个城市，所有可能花费的路费中最多是多少呢？
输入的第一行包含一个整数n，表示包括首都在内的T王国的城市数
城市从1开始依次编号，1号城市为首都。
接下来n-1行，描述T国的高速路（T国的高速路一定是n-1条）
每行三个整数Pi, Qi, Di，表示城市Pi和城市Qi之间有一条高速路，长度为Di千米。
输出一个整数，表示大臣J最多花费的路费是多少。
样例输入1
5
1 2 2
1 3 1
2 4 5
2 5 4
样例输出1
135
解决方案：
#include<iostream>
#include<cstring>
#include<vector>
using namespace std;
const int MAX=10000; //最多城市数
int maxFarNode; //maxFarNode从指定节点出发所能到的最远节点
int maxLen=-1; //maxLen从指定节点出发所能到的最远距离
bool st[MAX]; //标记某个点是否被访问过
struct Node
{ // 存放一个点的子节点及边的权值
int child,length;
Node(int a,int b):child(a),length(b){};
};
vector<Node> v[MAX]; //链式存储，邻接表
void dfs(int node,int nowLen)
{
if(st[node])
return;
st[node]=true;
for(int i=0;i<v[node].size();i++)
{
int child =v[node][i].child;
int length=v[node][i].length;
if(st[child])
continue;
if(nowLen+length>maxLen)
{
maxLen=nowLen+length;
maxFarNode=child;
}
dfs(child,nowLen+length);
}
}
int main()
{
int n;
cin>>n;
for(int i=1;i<n;i++)
{
int x,y,len;
cin>>x>>y>>len;
v[x].push_back(Node(y,len));
v[y].push_back(Node(x,len));
}
dfs(1,0);
memset(st,false,sizeof(st));
maxLen=-1;
dfs(maxFarNode,0);
cout<<(maxLen*10+maxLen*(1+maxLen)/2)<<endl;
return 0;
}问题描述：10.2n 皇后问题
给定一个n*n的棋盘，棋盘中有一些位置不能放皇后。现在要向棋盘中放入n个黑皇后
和n个白皇后，使任意的两个黑皇后都不在同一行、同一列或同一条对角线上，任意的两
个白皇后都不在同一行、同一列或同一条对角线上。问总共有多少种放法？n小于等于8。
Input
输入的第一行为一个整数n，表示棋盘的大小。
接下来n行，每行n个0或1的整数，如果一个整数为1，表示对应的位置可以放皇后，
如果一个整数为0，表示对应的位置不可以放皇后。
Output
输出一个整数，表示总共有多少种放法。
Sample Input
No.1
4
1 1 1 1
1 1 1 1
1 1 1 1
1 1 1 1
No.2
4
1 0 1 1
1 1 1 1
1 1 1 1
1 1 1 1
Sample Output
No.1
2
No.2
0
解决方案：
#include<iostream>
#include<stdlib.h>
using namespace std;
const int maxn=10;
int n,ans=0;
int posb[maxn]={0}; //黑皇后
int posw[maxn]={0}; //白皇后
int map[maxn][maxn];
bool checkw(int cur)
{
for(int i=1;i<cur;i++)
if(posw[i]==posw[cur]||abs(i-cur)==abs(posw[i]-posw[cur]))
return false;
return true;
}
bool checkb(int cur)
{
for(int i=1;i<cur;i++)
if(posb[i]==posb[cur]||abs(i-cur)==abs(posb[i]-posb[cur]))
return false;
return true;
}
void dfs_white(int cur)
{
if(cur==n+1) //白皇后也全部放完，次数+1
ans++;
for(int i=1;i<=n;i++)
{
if(posb[cur]==i) //表示第cur列的第i行位置已经被黑皇后占用，
continue; //结束当前循环，i+1
if(map[cur][i]==0) //再判断前提条件是否成立
continue;
posw[cur]=i; //尝试把第cur列的白皇后放在第i行上
if(checkw(cur)) //判断能否放置白皇后
dfs_white(cur+1); //递归
}
}
void dfs_black(int cur)
{
if(cur==n+1) //当黑皇后处理完时，再处理白皇后
dfs_white(1);
for(int i=1;i<=n;i++)
{
if(map[cur][i]==0) //如果第cur列第i行满足放皇后的前提条件即 mp[cur][i] == 1
continue; //如果不满足，则结束当前循环，进行下一次循环即i+1。
posb[cur] = i; //就尝试把第cur列的黑皇后放在第i行上
if(checkb(cur)) //然后判断该尝试是否成立，如成立，则进行递归，如不成立，则尝试把当前列的黑皇后放在下一行(i+1行)上。
dfs_black(cur+1); //递归
}
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++) //定义棋盘
for(int j=1;j<=n;j++)
cin>>map[i][j];
dfs_black(1); //先把黑皇后放在第一列
cout<<ans<<endl;
return 0;
}