KY11 二叉树遍历
题目描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。 例如如下的先序遍历字符串： ABC##DE#G##F### 其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入描述:
输入包括1行字符串，长度不超过100。
输出描述:
可能有多组测试数据，对于每组数据，
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
每个输出结果占一行。
输入
abc##de#g##f###
输出
c b e g d f a
代码
#include <iostream>
#include <string>
using namespace std;
int t;
string pre;
struct TreeNode{
char val;
TreeNode* left, *right;
TreeNode(int x):val(x),left(NULL),right(NULL){}
};
TreeNode* Create_Tree(){
char c = pre[t++];
//若是‘#’，说明该节点为空返回上一级节点
if(c == '#') return NULL;
TreeNode* root = new TreeNode(c);//若不是#，为本节点赋值
root->left = Create_Tree();//递归创建左子树
root->right = Create_Tree();//递归创建右子树
return root;
}
void inOrder(TreeNode* root){
if(root == NULL){
return;
}
inOrder(root->left);
cout << root->val << " ";
inOrder(root->right);
}
int main(){
while(cin >> pre){
t = 0;
TreeNode* root = NULL;
root = Create_Tree();
inOrder(root);
cout << endl;
}
return 0;
}
KY12 玛雅人的秘密
题目描述
玛雅人有一种密码，如果字符串中出现连续的2012四个数字就能解开密码。给一个长度为N的字符串，（2=<N<=13）该字符串中只含有0,1,2三种数字，问这个字符串要移位几次才能解开密码，每次只能移动相邻的两个数字。例如02120经过一次移位，可以得到20120,01220,02210,02102，其中20120符合要求，因此输出为1.如果无论移位多少次都解不开密码，输出-1。
输入描述:
输入包含多组测试数据，每组测试数据由两行组成。
第一行为一个整数N，代表字符串的长度（2<=N<=13）。
第二行为一个仅由0、1、2组成的，长度为N的字符串。
输出描述:
对于每组测试数据，若可以解出密码，输出最少的移位次数；否则输出-1。
输入
5
02120
输出
1
代码
#include <stdio.h>
#include <iostream>
#include <map>
#include <string>
#include <queue>
using namespace std;
map<string, int> M;//M[str]表示str经历的交换次数
queue<string> Q;//队列，用于bfs
string Swap(string str, int i)
{//将字符串i位与i+1位交换
string newStr=str;
char tmp=newStr[i];
newStr[i]=newStr[i+1];
newStr[i+1]=tmp;
return newStr;
}
bool Judge(string str)
{//判断字符串中是否含有"2012"
if(str.find("2012", 0)==string::npos) return false;
else return true;
}
int BFS(string str)
{//广度优先搜索
string newStr;
M.clear();//清空map
while(!Q.empty()) Q.pop();//清空队列
Q.push(str);//初始字符串作为起点放入队列
M[str]=0;//初始字符串经历的交换次数是0
while(!Q.empty())
{
str=Q.front();
Q.pop();//取出队首，存入str
for(unsigned i=0; i<str.size()-1; i++)//尝试进行一次交换
{
newStr=Swap(str, i);//新字符串由str交换i位和i+1位得到
if(M.find(newStr)==M.end())//如果这个字符串没出现过
{
M[newStr]=M[str]+1;//现在出现过了，且交换次数比他爹多1
if(Judge(newStr)==true) return M[newStr];//符合要求，收工
else Q.push(newStr);//不合要求，那继续bfs，把它加入队列
}
else continue;//出现过的字符串，不用进行处理
}
}
return -1;//遍历完成，没发现符合要求的字符串，返回-1
}
int main()
{
int n;
string str;
while(scanf("%d", &n)!=EOF)
{
cin>>str;//读取字符串(前面读取n好像没啥用)
if(Judge(str)==true) printf("0\n");//一开始就符合要求的话
else//初始字符串不符合要求，那就bfs
{
int ans=BFS(str);
printf("%d\n", ans);
}
}
return 0;//大功告成
}
KY13 求最大最小数
题目描述
输入N个（N<=10000）数字，求出这N个数字中的最大值和最小值。每个数字的绝对值不大于1000000。
输入描述:
输入包括多组测试用例，每组测试用例由一个整数N开头，接下去一行给出N个整数。
输出描述:
输出包括两个整数，为给定N个数中的最大值与最小值。
输入
5
1 2 3 4 5
3
3 7 8
输出
5 1
8 3
代码
#include<iostream>
using namespace std;
int main(){
int number;
while(cin>>number){
int* a=new int[number];
int temp;
for(int i=0;i<number;i++)
cin>>a[i];
int min=1000000,max=-1000000;
for(int i=0;i<number;i++){
if(a[i]<min)
min=a[i];
if(a[i]>max)
max=a[i];
}
cout<<max<<' '<<min<<endl;
}
}
KY14 最小邮票数
题目描述
有若干张邮票，要求从中选取最少的邮票张数凑成一个给定的总值。 如，有1分，3分，3分，3分，4分五张邮票，要求凑成10分，则使用3张邮票：3分、3分、4分即可。
输入描述:
有多组数据，对于每组数据，首先是要求凑成的邮票总值M，M<100。然后是一个数N，N<20，表示有N张邮票。接下来是N个正整数，分别表示这N张邮票的面值，且以升序排列。
输出描述:
对于每组数据，能够凑成总值M的最少邮票张数。若无解，输出0。
输入
10
5
1 3 3 3 4
输出
3
代码
#include<stdio.h>
#define INF 1000
int stamp[1000];
int dp[1000];
// 返回最少数量，num表示邮票的个数，deno表示要凑成的面额
int Min_Stamp(int num,int deno){
int i,j;
//将状态全部初始化为最多
for(j=0;j<=deno;++j){
dp[j]= (j==0)?0:INF;
}
for(i=0;i<num;i++){
//从后向前寻找若能凑成，且使数量变少就使用，不能也无所谓因为还是INF
for(j=deno;j>=stamp[i];j--){
if(dp[j-stamp[i]]!=INF)dp[j]=(dp[j] < dp[j-stamp[i]]+1)? dp[j]: dp[j-stamp[i]]+1;
}
}
return dp[deno]==INF?0:dp[deno];
}
int main()
{
int num,deno;
while(scanf("%d %d",&deno,&num)!=EOF){
for(int i=0;i<num;i++)scanf("%d",stamp+i);
printf("%d",Min_Stamp(num,deno));
}
return 0;
}
KY15 abc
题目描述
设a、b、c均是0到9之间的数字，abc、bcc是两个三位数，且有：abc+bcc=532。求满足条件的所有a、b、c的值。
输入描述:
题目没有任何输入。
输出描述:
请输出所有满足题目条件的a、b、c的值。
a、b、c之间用空格隔开。
每个输出占一行。
输入
输出
代码
#include <iostream>
using namespace std;
int main(){
for(int a = 0; a <= 9; ++a){
for (int b = 0; b <= 9 ; ++b) {
for (int c = 0; c <=9 ; ++c) {
if (a * 100 + b * 110 + c * 12 ==532 ){
printf("%d %d %d\n" , a, b, c);
}
}
}
}
return 0;
}
KY16 求root(N, k)
题目描述
N<k时，root(N,k) = N，否则，root(N,k) = root(N',k)。N'为N的k进制表示的各位数字之和。输入x,y,k，输出root(x^y,k)的值 (这里^为乘方，不是异或)，2=<k<=16，0<x,y<2000000000，有一半的测试点里 x^y 会溢出int的范围(>=2000000000)
输入描述:
每组测试数据包括一行，x(0<x<2000000000), y(0<y<2000000000), k(2<=k<=16)
输出描述:
输入可能有多组数据，对于每一组数据，root(x^y, k)的值
输入
4 4 10
输出
4
代码
#include<iostream>
using namespace std;
int root(int x, int y, int k) {
if (y == 1) {
if (x < k)
return x;
else {
while (x >= k) {
int sum = 0;
while (x > 0) {
sum += x % k;
x /= k;
}
x = sum;
}
return x;
}
} else {
int r = root(x, y / 2, k);
r *= r;
if (y % 2 == 1) {
r *= root(x, 1, k);
}
return root(r, 1, k);
}
}
int main() {
int x, y, k;
while (cin >> x >> y >> k)
cout << root(x, y, k) << endl;
return 0;
}
KY17 n的阶乘
题目描述
输入一个整数n，输出n的阶乘（每组测试用例可能包含多组数据，请注意处理）
输入描述:
一个整数n(1<=n<=20)
输出描述:
n的阶乘
示例1
输入
3
输出
6
代码
#include<iostream>
#include<vector>
using namespace std;
int main(){
vector<long long> dp(21, 1);
for(int i = 2; i <= 20; i ++){
dp[i] = dp[i - 1] * i;
}
int n;
while(cin >> n){
cout << dp[n] << endl;
}
}
KY18 特殊乘法
题目描述
写个算法，对2个小于1000000000的输入，求结果。 特殊乘法举例：123 * 45 = 1*4 +1*5 +2*4 +2*5 +3*4+3*5
输入描述:
两个小于1000000000的数
输出描述:
输入可能有多组数据，对于每一组数据，输出Input中的两个数按照题目要求的方法进行运算后得到的结果。
输入
123 45
输出
54
代码
#include <iostream>
#include <string>
using namespace std;
int main() {
string x, y;
while (cin >> x >> y) {
int sum = 0;
for (auto itx : x) {
for (auto ity : y) {
sum += (itx - '0') * (ity - '0');
}
}
printf("%d\n", sum);
}
return 0;
}
KY19 今年的第几天
题目描述
输入年、月、日，计算该天是本年的第几天。
输入描述:
包括三个整数年(1<=Y<=3000)、月(1<=M<=12)、日(1<=D<=31)。
输出描述:
输入可能有多组测试数据，对于每一组测试数据，
输出一个整数，代表Input中的年、月、日对应本年的第几天。
输入
1990 9 20
2000 5 1
输出
263
122
代码
#include <iostream>
using namespace std;
int daytab[2][13] = {
{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
};
bool IsLeapYear(int year){
return (year % 4 ==0 && year % 100 != 0 ) || (year % 400 == 0);
}
int main(){
int year, month, day;
while (scanf("%d %d %d", &year, &month, &day) != EOF){
int number = 0;
int row = IsLeapYear(year);
for (int i = 0; i < month; ++i) {
number += daytab[row][i];
}
number += day;
printf("%d\n",number);
}
return 0;
}
KY20 完数与盈数
题目描述
一个数如果恰好等于它的各因子(该数本身除外)子和，如：6=3+2+1。则称其为“完数”；若因子之和大于该数，则称其为“盈数”。 求出2到60之间所有“完数”和“盈数”。
输入描述:
题目没有任何输入。
输出描述:
输出2到60之间所有“完数”和“盈数”，并以如下形式输出：
E: e1 e2 e3 ......(ei为完数)
G: g1 g2 g3 ......(gi为盈数)
其中两个数之间要有空格，行尾不加空格。
输入
输出
代码
#include<iostream>
#include<cstdio>
#include<vector>
using namespace std;
vector<int> v1, v2;
vector<int>::iterator it;
int main() {
int sum, temp;
for (int i = 2; i <= 60; ++i) {//求因子
sum = 0;
for (int j = 1; j <= i / 2; ++j) {
if (i % j == 0) {
temp = j;
sum += j;
}
}
if (sum == i) {
v1.push_back(i);
}
if (sum > i)
v2.push_back(i);
}
cout << "E:";
for (it = v1.begin(); it != v1.end(); it++) {
cout << " " << *it;//末尾不加空格！！！不然格式会一直错误
}
cout << endl;
cout << "G:";
for (it = v2.begin(); it != v2.end(); it++) {
cout << " " << *it;//末尾不加空格！！！不然格式会一直错误
}
return 0;
}