| 状态 | 题号 | 竞赛题号 | 标题 |
| 1091 | A | 求解逆波兰表达式(Calculate the reverse Polish notation) | |
| 1017 | B | 数列 | |
| 1323 | C | 穷举n位二进制数 | |
| 1579 | D | 三阶幻方 | |
| 1324 | E | 穷举所有排列 | |
| 1203 | F | 装盘子 | |
| 1216 | G | 大数乘法 | |
| 1007 | H | 8皇后问题 | |
| 1004 | I | 0-1背包问题 | |
| 1551 | J | 求给定一组数能构造多少个素数环 | |
| 1141 | K | 走迷宫 | |
| 1142 | L | 踩气球 |
Problem A 求解逆波兰表达式(Calculate the reverse Polish notation) 时限：1000ms 内存限制：10000K 总时限：3000ms 描述： 编写函数int add(char s[]);计算字符串形式的逆波兰表达式（即两个操作数在前，计算符在后）。本题内，保证每个操作数均为1位数。操作符有'+','-','*','/'四种。且保证计算过程中除法运算全部为整数除法，结果为整数。 如23+*,，结果20 Write a function -digit. The operator have only four: '+', '-', '*', '/'. And to ensure that the division operation in the calculation process for all the integer division, the result is an integer. Such +*, the result . 输入： 一行字符串，长度不超过20。 Input a characters. 输出： 逆波兰表达式的计算结果。 Output the result of reverse Polish notation. 输入样例： +* 输出样例：
Problem A 求解逆波兰表达式(Calculate the reverse Polish notation)
#include <iostream>
#include <cmath>
#include <stack>
using namespace std;
int calc(int a, int b, char op);
int main()
{
stack<int> s;
];
cin >> str;
;
int n1, n2, temp;;
while(str[i] != '\0')
{
//若为数字
if(isdigit(str[i]))
{
s.push(str[i++] - ');
}
else //若为操作符
{
n2 = s.top();
s.pop();
n1 = s.top();
s.pop();
temp = calc(n1, n2, str[i++]);
s.push(temp);
}
}
cout<<s.top()<<endl;
;
}
int calc(int a, int b, char op)
{
if(op == '+')
return a+b;
else if(op == '-')
return a-b;
else if(op == '*')
return a*b;
else if(op == '/')
return a/b;
}
A代码 - 栈
#include <iostream>
#include <cmath>
using namespace std;
int calc(int a, int b, char op);
int main()
{
];
cin >> str;
int n1, n2;
n1 = str[] - ';
;
while(str[i] != '\0')
{
//若为数字
if(isdigit(str[i]))
{
n2 = str[i] - ';
}
else //若为操作符
{
n1 = calc(n1, n2, str[i]);
}
i++;
}
cout<<n1<<endl;
;
}
int calc(int a, int b, char op)
{
if(op == '+')
return a+b;
else if(op == '-')
return a-b;
else if(op == '*')
return a*b;
else if(op == '/')
return a/b;
}
/*
例如这种输入：
521--
标准输出：4
用户输出：3
此程序无法解决类似于 "521--" 的表达式
*/
A代码 - 不用栈（错了）
Problem B 数列 时限：1000ms 内存限制：10000K 总时限：3000ms 描述： 已知k阶裴波那契数列的定义为f0=，f1=，…，fk-=, fk-=； fn=fn-+fn-+…+fn-k，n=k，k+，…，试编写求k阶裴波那契数列的第m项值的函数算法，k和m均以值调用的形式在函数参数表中出现。 输入： 输入两个正整数k m(其中1<k<m，本题所有数据都在长整形数据的范围之内) 输出： 输出k阶裴波那契数列的第m项值fm。 输入样例： （注意：本题所涉及的所有数据都在长整形数据的范围之内） 输出样例：
Problem B 数列
#include <iostream>
#include <cmath>
using namespace std;
long fun(int k, int m);
int main()
{
long k1, m1;
while(cin>>k1 && cin>>m1)
{
cout<<fun(k1, m1)<<endl;
}
;
}
long fun(int k, int m)
{
;
&& m<=k-)
fm = ;
)
fm = ;
else
{
; i++)
{
fm += fun(k, i);
}
}
return fm;
}
/*
__int64 和 long long都报错
*/
代码B
Problem C 穷举n位二进制数 时限：100ms 内存限制：10000K 总时限：300ms 描述： 输入一个小于20的正整数n，要求按从小到大的顺序输出所有的n位二进制数，每个数占一行。 输入： 输入一个小于20的正整数n。 输出： 按从小到大的顺序输出所有的n位二进制数，每个数占一行。 输入样例： 输出样例：
Problem C 穷举n位二进制数
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;
int main()
{
int n;
];
int temp, i, j;
memset(a, , sizeof(a));
while(cin>>n)
{
/* 先输出第一个全0*/
; i<n; i++)
{
cout<<;
}
cout<<endl;
/*从1，开始到2的n次方-1，以此打印*/
; i<pow(,n); i++)
{
memset(a, , sizeof(a));
j = ;
temp = i;
//十进制转二进制，并存进数组
while(temp)
{
a[j] = temp % ;
temp /= ;
j++;
}
; j>=; j--)
{
cout<<a[j];
}
cout<<endl;
}
}
;
}
代码C
Problem D 三阶幻方 时限：1000ms 内存限制：10000K 总时限：3000ms 描述： 三阶幻方是最简单的幻方，又叫九宫格，是由1,,,,,,,,9九个数字组成的一个三行三列的矩阵，其对角线、横行、纵向的的和都为15。 输入： 无 输出： 按字典序输出所有的满足条件的幻方矩阵，每两个数字之间带一个空格，行尾无空格，每个幻方后带一个空行。 输入样例： 无 输出样例： 无
Problem D 三阶幻方
#include <iostream>
using namespace std;
void printMatrix();
void testMatrix();
void create(int n);
][]; // 矩阵
]; // 1-9 是否被使用
int main()
{
create();
;
}
/*回溯生成所有矩阵*/
void create(int n)
{
int num; //数字1-9
)
{
testMatrix();
}
else
{
; num<=; num++)
{
if(!isUsed[num])
{
a[n/][n%] = num;
isUsed[num] = ; //已使用过不能再次使用
create(n+); //生成第一个
isUsed[num] = ; //回溯时使isUsed[i]恢复原值
}
}
}
}
/*判断矩阵是否为三阶幻方*/
void testMatrix()
{
;
; i<; i++)
{
//判断行和列
]+a[i][]+a[i][] != || a[][i]+a[][i]+a[][i] != )
{
f = ;
break;
}
}
if(f)
{
//判断两条对角线
][]+a[][]+a[][] != || a[][]+a[][]+a[][] != )
{
f = ;
}
}
if(f)
printMatrix();
}
/*打印矩阵*/
void printMatrix()
{
; i<; i++)
{
; j<; j++)
{
cout<<a[i][j]<<" ";
}
cout<<a[i][]<<endl;
}
cout<<endl;
}
代码D
Problem E 穷举所有排列 时限：100ms 内存限制：10000K 总时限：300ms 描述： 输入一个小于10的正整数n，按把每个元素都交换到最前面一次的方法，输出前n个小写字母的所有排列。 输入： 输入一个小于10的正整数n。 输出： 按把每个元素都交换到最前面一次的方法，输出前n个小写字母的所有排列。 输入样例： 输出样例： abcacbbacbcacbacab
Problem E 穷举所有排列
#include <iostream>
using namespace std;
void array(int m);
];
int n;
int main()
{
/*构造字符数组*/
; i<; i++)
{
letter[i] = + i;
}
while(cin>>n)
{
array();
}
;
}
/*回溯法*/
void array(int m)
{
int i;
if(m == n)
{
; i<n; i++)
{
cout<<letter[i];
}
cout<<endl;
}
else
{
for(i=m; i<n; i++) //每个元素打头一次
{
swap(letter[m],letter[i]);
array(m+);
swap(letter[m],letter[i]);
}
}
}
代码E
Problem F 装盘子 时限：1000ms 内存限制：10000K 总时限：3000ms 描述： N人为了大快朵颐，行至云餐二楼，取了N个盘子，打了M个饺子。现欲将M个饺子装入N个盘子中，试问共有多少种不同的装法？ 假设盘子足够大，并且盘子里可以什么都不放。注意像2 0和5 2之类的属于同一种放法。 输入： 两个整数M、N(=< M,N <=)以空格隔开。 输出： 单独一行输出共有几种装法。 输入样例： 输出样例：
Problem F 装盘子
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
void push(int m, int n);
][];
int main()
{
int m, n;
while(cin>>m && cin>>n)
{
; i <= ; i++)
{
dish[i][] = ;
dish[][i] = ;
dish[i][] = ;
dish[][i] = ;
}
push(m, n);
int num = dish[m][n];
cout<<num<<endl;
}
;
}
void push(int m, int n) //根据数学意义推出的递推方程遍历打表
{
; i <= ; i++)
{
; j <= ; j++)
{
)
continue;
if(i >= j)
{
; k <= j; k++)
{
dish[i][j] += dish[i - k][k];
}
}
else
{
dish[i][j] = dish[i][i];
}
}
}
}
/*
错误思路：递归因为迭代层数太多，很容易导致栈溢出，俗称爆栈，还费时间。
此题关键在于求出递推方程式或状态转移方程，可以根据数学意义推导出公式：
1：定义函数C(m,n)的数学意义为向n个盘子里放入m个饺子，盘子可空；
2：定义函数K(m,n)的数学意义为向n个盘子里放入m个饺子，但是盘子不可空，即每个盘子至少有一个饺子；
3：显然有：c(m,n) = k(m,1) + k(m,2) + ... + k(m,n)——数学意义即：所有情况 = 空n-1个盘子的情况+空n-2个盘子的情况+...+不空的情况；
注意，这样分解问题是可以做到一定没有重复情况干扰答案的。
4：显然还有：k(m,n) = c(m-n, n);————数学意义即：盘子不为空的情况数 = 先用n个饺子填满每一个盘子后剩下m-n个饺子随意放在n个盘子中；
5: 联立以上两个方程可求出状态转移方程如下：
c(m,n) = c(m-1,1) + c(m-2,2) + ... + c(m-n,n);——注意边界值0、1的情况应该需要单独考虑；
6: 得到方程后，直接打表，将所有C(m,n)情况计算出来，时间复杂度应为（100 * 100 （1 + ... + 100))*o(1) = 50500000*o(1),
方案可行。
*/
代码F
Problem G 大数乘法 时限：100ms 内存限制：10000K 总时限：1000ms 描述： 计算两个大整数的乘积。 输入： 输入有两行,第一行单独一个大整数A,第二行单独一个大整数B。每个数的长度不超过1000。 输出： 单独一行输出A,B的精确乘积。结果请注意换行。 输入样例： 输出样例：
Problem G 大数乘法
#include<iostream>
#include<cstring>
using namespace std;
void multiply(int len1, int len2);
];
];
]; //相乘后的位数不会超过a+b
int main()
{
];
];
int len_A, len_B;
int len1, len2;
int i, j;
while(cin>>str_A && cin>>str_B)
{
memset(mul,,sizeof(mul));
len_A = ;
len_B = ;
i = ;
j = ;
while(str_A[len_A] != '\0')
{
len_A++; //计算A的长度
}
while(str_B[len_B] != '\0')
{
len_B++; //计算B的长度
}
len1 = len_A;
len2 = len_B;
while(len_A)
{
A[i++] = str_A[--len_A] - '; //字符数组倒序转int数组
}
while(len_B)
{
B[j++] = str_B[--len_B] - '; //字符数组倒序转int数组
}
multiply(len1, len2);
}
;
}
void multiply(int len1, int len2)
{
; i<len1; i++)
{
; j<len2; j++)
{
mul[i+j] += A[i] * B[j];
}
}
; //mul的下标从0开始，len1和len2是从1开始
|| mul[t]!=)
{
)
{
mul[t+] += mul[t]/;
mul[t] = mul[t]%;
}
t++;
}
)
{
t--;
cout<<mul[t];
}
// for(int i=t; i>=0; i--)
// {
// if(t==len1+len2-1)
// {
// if(mul[t] == 0)
// {
// ;
// }
// else
// {
// cout<<mul[i];
// }
// }
// else
// {
// cout<<mul[i];
// }
// }
cout<<endl;
}
代码G
Problem H 8皇后问题 时限：1000ms 内存限制：10000K 总时限：3000ms 描述： 输出8皇后问题所有结果。 输入： 没有输入。 输出： 每个结果第一行是No n：的形式，n表示输出的是第几个结果；下面8行，每行8个字符，‘A’表示皇后，‘.’表示空格。不同的结果中，先输出第一个皇后位置靠前的结果；第一个皇后位置相同，先输出第二个皇后位置靠前的结果；依次类推。 输入样例： 输出样例： 输出的前几行：No :A...........A..........A.....A....A...........A..A.........A....No :A............A.........A..A...........A....A.....A..........A...
Problem H 8皇后问题
#include <iostream>
#include <cmath>
using namespace std;
void search(int m);
int compare(int row, int col);
void printQueen();
void printQueen2();
; //代表N皇后
]; //数字代表存放皇后的列数；
; //结果编号
int main()
{
search();
;
}
/*假设前m-1行已经摆放好了，从m行穷举所有情况*/
void search(int m)
{
if( m== N)
{
count++;
printQueen(); //输出
}
else
{
; i<; i++)
{
//判断第m行，第i列
if(compare(m,i))
{
//存放皇后
queen[m] = i; //代表第m行第i列存放皇后；
search(m+);
/*
理论上下一步需要去掉皇后；
但是因为存放皇后的时候，会直接覆盖掉上一个皇后
所以不需要那一步（正常回溯是需要有这一步来恢复原值的）
*/
}
}
}
}
int compare(int row, int col)
{
; //1代表可以存放皇后
/*判断前row-1行*/
; i<row; i++)
{
/*
判断列和对角线，行不用判断
对角线通过两个元素的行列互减判断
*/
if(queen[i]==col || abs(queen[i]-col)==row-i)
{
flag = ;
break;
}
}
return flag;
}
void printQueen()
{
int j;
cout<<"No "<<count<<":"<<endl;
; i<N; i++)
{
; j<queen[i]; j++)
{
cout<<".";
}
cout<<"A";
; j<N; j++)
{
cout<<".";
}
cout<<endl;
}
}
/*另一种打印方法*/
void printQueen2()
{
cout<<"No "<<count<<":"<<endl;
; i<N; i++)
{
; j<N; j++)
{
if(j==queen[i])
cout<<"A";
else
cout<<".";
}
cout<<endl;
}
}
代码H
Problem I -1背包问题 时限：1000ms 内存限制：10000K 总时限：3000ms 描述： 需对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为wi ，价值为pi 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳装载是指所装入的物品价值最高。 输入： 多个测例，每个测例的输入占三行。第一行两个整数：n（n<=）和c，第二行n个整数分别是w1到wn，第三行n个整数分别是p1到pn。 n 和 c 都等于零标志输入结束。 输出： 每个测例的输出占一行，输出一个整数，即最佳装载的总价值。 输入样例： 输出样例：
Problem I 0-1背包问题
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
void search(int m);
int n, c;
], p[];
int sumW, sumP, maxP;
int main()
{
while(cin>>n>>c)
{
&& c==)
{
break;
}
; i<n; i++)
{
cin>>w[i];
}
; i<n; i++)
{
cin>>p[i];
}
sumP = ; //目前总价值
sumW = ; //目前总重量
maxP = ; //最大质量
search();
cout<<maxP<<endl;
}
;
}
void search(int m)
{
if(m == n) //搜索到了最底层
{
if(sumW <= c)
{
maxP = max(maxP, sumP); //一直保留所有结果的最大值
}
}
else
{
search(m+);//不装m，直接去装m+1
if(sumW <= c)
{
sumP += p[m];
sumW += w[m];
search(m+); //装完m之后再去装m+1
/*
你加完m之后的状态已经传递到下一层了；
为什么要删除m呢？
是因为那棵树有很多分支，如果不删掉，再计算其他分支的时候，会将之前分支的sumP和sumW带过去
由于那个状态已经传递到下一层了，所以删掉之后，不影响此分支的计算。
*/
sumP -= p[m];
sumW -= w[m];
}
}
}
代码I
Problem J 求给定一组数能构造多少个素数环 时限：1000ms 内存限制：10000K 总时限：3000ms 描述： 给定一组正整数，把他们排成一个环，任意相邻的两个数之和为素数的环称为素数环，问这组数能构成多少个素数环？ 输入： 先输入一个小于等于16的正整数n，然后输入给定的n个不相同的小于等于16的正整数。 输出： 输出这组数能够成的不同的素数环的个数。 输入样例： 输出样例：
Problem J 求给定一组数能构造多少个素数环
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
int isPrime(int k);
void creatPrime();
void search(int m);
]; //存放32以内的所有素数，prime[i]=1,代表i是素数
int n;
];
int countRing; //存储素数环的个数
int main()
{
creatPrime();
while(cin>>n)
{
countRing = ;
; i<n; i++)
{
cin>>num[i];
}
/*
注意一定要从1开始，因为search函数中调用了num[m-1]，如果从0开始，会发生数组越界
而且因为这是一个环，里面的元素无先后顺序，所以无论谁在第1个位置上都无所谓，第1个位置不需要遍历所有
*/
search();
cout<<countRing<<endl;
}
;
}
/*回溯法*/
void search(int m)
{
if(m==n)
{
]+num[n-]])
{
countRing++;
}
}
else
{
for(int i=m; i<n; i++)
{
];
if(prime[temp])
{
swap(num[i], num[m]);
search(m+);
swap(num[i], num[m]);
}
}
}
}
void creatPrime()
{
; i<=; i++)
{
prime[i] = isPrime(i);
}
}
int isPrime(int k)
{
;
; i<=sqrt(k); i++)
{
)
{
flag = ;
break;
}
}
return flag;
}
代码J
Problem K 走迷宫 时限：1000ms 内存限制：10000K 总时限：3000ms 描述： 判断是否能从迷宫的入口到达出口 输入： 先输入两个不超过20的正整数表示迷宫的行数m和列数n，再输入口和出口的坐标，最后分m行输入迷宫，其中1表示墙，0表示空格每个数字之间都有空格。 输出： 只能向上、下、左、右四个方向走若能到达，则输出"Yes"，否则输出"No"，结果占一行。 输入样例： 输出样例： Yes
Problem K 走迷宫
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
void DFsearch(int a, int b);
int m, n;
int beginX, beginY;
int endX, endY;
][]; //迷宫矩阵
int flag; //是否可以走出
][]; //是否已经走过
][] = {{,},{,},{-,},{,-}}; //用来控制上下左右
int main()
{
while(cin>>m>>n)
{
flag = ;
memset(visited,,sizeof(visited)); //初始情况下，什么节点都未访问
memset(matrix,,sizeof(matrix)); //迷宫全都初始化为1，这样未初始化的地方就都是墙壁
cin>>beginX>>beginY;
cin>>endX>>endY;
; i<m; i++)
{
; j<n; j++)
{
cin>>matrix[i][j]; //初始化迷宫
}
}
DFsearch(beginX, beginY);
if(flag)
cout<<"Yes"<<endl;
else
cout<<"No"<<endl;
}
;
}
void DFsearch(int a, int b)
{
if(a==endX&&b==endY)
{
flag = ;
}
else
{
visited[a][b] = ;
; k<; k++)
{
];
];
if(!visited[nextX][nextY] && !matrix[nextX][nextY])//当下一个节点没有被访问而且不是墙壁(1)时
DFsearch(nextX, nextY);
}
}
}
代码K
Problem L 踩气球 时限：1000ms 内存限制：10000K 总时限：3000ms 描述： 六一儿童节，小朋友们做踩气球游戏，气球的编号是1～，两位小朋友各踩了一些气球，要求他们报出自己所踩气球的编号的乘积。现在需要你编一个程序来判断他们的胜负，判断的规则是这样的：如果两人都说了真话，数字大的人赢；如果两人都说了假话，数字大的人赢；如果报小数字的人说的是真话而报大数字的人说谎，则报小数字的人赢（注意：只要所报的小数字是有可能的，即认为此人说了真话）。 输入： 输入为两个数字， 0表示结束； 输出： 输出为获胜的数字。 输入样例： 输出样例：
Problem L 踩气球
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
void dfSearch(int sm, int bg, int k);
int small, big;
int flag_small, flag_big;
int main()
{
while(cin>>small>>big)
{
&& big==)
{
break;
}
flag_big = ;
flag_small = ;
if(small > big)
swap(small, big);
dfSearch(small, big, );
/*
如果small说真的 且 二人不匹配，则small赢；
否则big赢
*/
if(flag_small && !flag_big)
cout<<small<<endl;
else
cout<<big<<endl;;
}
;
}
void dfSearch(int sm, int bg, int k)
{
)
{
flag_small = ;
)
flag_big = ;
}
|| (flag_big&&flag_small))
return;
)
{
dfSearch(sm, bg/k, k-);
}
)
{
dfSearch(sm/k, bg, k-);
}
dfSearch(sm, bg, k-);
}
代码L