Scratch编程一级 题库
广义格雷码
在一组数的编码中,若任意两个相邻(首尾也视为相邻)的代码只有一位二进制数不同,则称这种编码为格雷码。如四位格雷码:
0000、0001、0011、0010、0110、0111、0101、0100、1100、1101、1111、1110、1010、1011、1001、1000
现在将格雷码扩展至其他进制,仍然是相邻两个数只能有一位不同。输入两个正整数n,m分别表示长度和进制,每行输出一个n位m进制数,输出任意一种编码即可。(提示:putchar输出效率更高)
时间限制:1000
内存限制:65536
输入
一行,两个整数n,m。其中 2 ≤ n ≤ 12 ,2 ≤ m ≤ 10 且mn ≤ 500000
输出
任意一种编码方案,每个编码一行。相邻两个编码相差一位。第一个编码和最后一个编码算相邻
样例输入
2 3
样例输出
00 10 20 21 01 11 12 22 02
//答案仅供参考,来源于csdn,有部分错误
#include <cstring> //memset(flag,0,sizeof(bool)*12*50010);
#include <iostream>
#include <queue>
using namespace std;
string a[12][50010];
bool flag[12][50010];
queue<string> q;
int n, m;
int main() {
cin >> n >> m;
string temp = "";
// n为1的时候
if (n == 1) {
for (int i = 0; i < m; i++) {
cout << i << endl;
}
return 0;
}
// n大于2的时候
for (int i = 0; i < m; i++) {
// cout<<(temp+char(i+48))<<endl;
q.push(temp + char(i + 48)); // i=0,把字符0入队
}
for (int time = 2; time <= n; time++) {
memset(flag, 0, sizeof(bool) * 12 * 50010);
int size = q.size(), l = 0; // l这里赋值0 因为要从1开始
while (!q.empty()) {
a[0][++l] = q.front();
// cout<<a[0][l]<<" ";
q.pop();
}
// 复制一份 其他行数的
for (int i = 1; i < m; i++) {
for (int j = 1; j <= size; j++) {
a[i][j] = a[0][j];
}
}
// 添加前面一个值: 0—(m-1)
for (int i = 0; i < m; i++) {
for (int j = 1; j <= size; j++) {
a[i][j] = char(i + 48) + a[i][j];
// cout<<a[i][j]<<" ";
flag[i][j] = true;
}
// cout<<endl;
}
// 蛇形取值
int t = size * m; // t表示当前总个数
// 保存第一行到q队列中
for (int i = 1; i <= size; i++) {
q.push(a[0][i]);
flag[0][i] = false;
t--;
}
// cout<<q.size()<<endl;
int x = 0, y = size;
while (t > 0) {
while (flag[x + 1][y] && t > 0) {
flag[++x][y] = false;
q.push(a[x][y]);
t--;
} // 向下
if (flag[x][y - 1] && t > 0) {
flag[x][--y] = false;
q.push(a[x][y]);
t--;
} // 向左一位
while (flag[x - 1][y] && t > 0) {
flag[--x][y] = false;
q.push(a[x][y]);
t--;
} // 向上
if (flag[x][y - 1] && t > 0) {
flag[x][--y] = false;
q.push(a[x][y]);
t--;
} // 再向左一位
}
}
// 输出
while (!q.empty()) {
cout << q.front() << endl;
q.pop();
}
return 0;
}菲波那契数列
菲波那契数列是指这样的数列: 数列的第一个和第二个数都为1,接下来每个数都等于前面2个数之和。 给出一个正整数a,要求菲波那契数列中第a个数对10000取模的结果是多少。
时间限制:1000
内存限制:65536
输入
第1行是测试数据的组数n,后面跟着n行输入。每组测试数据占1行,包括一个正整数a(1 <= a <= 1000000)。
输出
n行,每行输出对应一个输入。输出应是一个正整数,为菲波那契数列中第a个数对10000取模得到的结果。
样例输入
4 5 2 19 1
样例输出
5 1 181 1
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
int num;
int a, b, c;
while (n--) {
scanf("%d", &num);
a = 1;
b = 1;
c = 2;
if (num == 1 || num == 2) {
printf("1\n");
} else if (num == 3) {
printf("2\n");
} else {
num -= 3;
while (num--) {
a = b;
b = c;
c = (a + b) % 1000;
}
printf("%d\n", c);
}
}
return 0;
}字符统计
给定一个由a-z这26个字符组成的字符串,统计其中哪个字符出现的次数最多。
输入
输入包含一行,一个字符串,长度不超过1000。
输出
输出一行,包括出现次数最多的字符和该字符出现的次数,中间以一个空格分开。如果有多个字符出现的次数相同且最多,那么输出ascii码最小的那一个字符。
样例输入
abbccc
样例输出
c 3
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
char str[1100];
int main() {
int a[30] = {0};
int len, max = -1;
int i, j;
cin >> str;
len = strlen(str);
for (i = 0; i < len; i++)
a[str[i] - 'a']++;
for (i = 0; i < 26; i++)
if (a[i] > max) {
j = i;
max = a[i];
}
cout << char('a' + j) << " " << max << endl;
return 0;
}图像处理
给定n行m列的图像各像素点的灰度值,要求用如下方法对其进行模糊化处理:
1. 四周最外侧的像素点灰度值不变;
2. 中间各像素点新灰度值为该像素点及其上下左右相邻四个像素点原灰度值的平均(舍入到最接近的整数)。
时间限制:1000
内存限制:65536
输入
第一行包含两个整数n和m,表示图像包含像素点的行数和列数。1 <= n <= 100,1 <= m <= 100。 接下来n行,每行m个整数,表示图像的每个像素点灰度。相邻两个整数之间用单个空格隔开,每个元素均在0~255之间。
输出
n行,每行m个整数,为模糊处理后的图像。相邻两个整数之间用单个空格隔开。
样例输入
4 5 100 0 100 0 50 50 100 200 0 0 50 50 100 100 200 100 100 50 50 100
样例输出
100 0 100 0 50 50 80 100 60 0 50 80 100 90 200 100 100 50 50 100
#include <cmath>
#include <iostream>
using namespace std;
const int N = 100 + 10;
int a[N][N], b[N][N];
int main() {
int n, m;
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
b[i][j] = a[i][j];
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (i == n || i == 1 || j == m || j == 1)
continue;
else {
double sum =
a[i][j] + a[i - 1][j] + a[i + 1][j] + a[i][j - 1] + a[i][j + 1];
sum /= 5;
b[i][j] = int(round(sum));
}
}
}
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
if (j == 1)
cout << b[i][j];
else
cout << ' ' << b[i][j];
}
cout << endl;
}
}替换单词
输入一个字符串,以回车结束(字符串长度<=100)。该字符串由若干个单词组成,单词之间用一个空格隔开,所有单词区分大小写。现需要将其中的某个单词替换成另一个单词,并输出替换之后的字符串。
时间限制:1000
内存限制:65536
输入
输入包括3行, 第1行是包含多个单词的字符串 s;
第2行是待替换的单词a(长度 <= 100);
第3行是a将被替换的单词b(长度 <= 100).
s, a, b 最前面和最后面都没有空格.
输出
输出只有 1 行,将s中所有单词a替换成b之后的字符串。
样例输入
You want someone to help you
You
I
样例输出
I want someone to help you
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <string>
using namespace std;
int main() {
string src;
string s, s1;
while (getline(cin, src)) {
getline(cin, s);
getline(cin, s1);
int flag = src.find(s);
while (flag != string::npos) {
if (flag + s.size() < src.size() && src[flag + s.size()] != ' ') {
flag = src.find(s, flag + 1);
continue;
}
src.replace(flag, s.size(), s1);
flag = src.find(s, flag + 1);
}
cout << src << endl;
}
return 0;
}偶数降序输出
给定一个长度为N (不大于500) 的正整数序列,请将其中的所有偶数取出,并按降序输出。
输入描述:
共两行;第一行为N;第二行为N个正数,其间用空格间隔
输出描述:
降序输出的偶数序列,数与数之间用空格间隔
数据保证至少有一个偶数
样例输入:
10
1 3 2 6 5 4 9 8 7 10
样例输出:
10 8 6 4 2
#include <bits/stdc++.h>
using namespace std;
const int N = 100;
int a[N];
bool cmp(int num1, int num2) { return num1 >= num2; }
main() {
int n, t;
int j = 0;
cin >> n;
for (int i = 0; i < n; i++) {
cin >> a[i];
}
for (int i = 0; i < n; i++) {
if (a[i] % 2 == 0) {
t = a[i];
a[j++] = t;
}
}
sort(a, a + j, cmp);
for (int i = 0; i < j; i++) {
cout << a[i] << " ";
}
cout << endl;
}满足条件的数的累加2
现有n个整数,将其中个位数为k的数进行累加求和
输入
第一行一个整数n。第二行n个非负整数,以空格分割,每个数不大于100000。第三行一个整数k。
输出
输出满足题目要求的累加和
样例输入
10 2 5 7 17 11 18 4 27 1 7 7
样例输出
58
#include <iostream>
using namespace std;
int main() {
int n, sum = 0;
cin >> n;
int a[n];
for (int i = 0; i < n; i++) {
cin >> a[i];
}
int k;
cin >> k;
for (int i = 0; i < n; i++) {
if (a[i] % 10 == k) { // 个位数
sum += a[i];
}
}
cout << sum;
return 0;
}//解法2
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,ans=0;
cin>>n>>k;
for(int i=1,x;i<=n;i++){
cin>>x;
if(x%10==k) ans+=x;
}
cout<<ans;
return 0;
}数字判断
输入一个字符,如果输入的字符是数字,输出yes,否则输出no
输入
一个字符
输出
如果输入的字符是数字,输出yes,否则输出no
样例1输入
5
样例1输出
yes
样例2输入
A
样例2输出
no
#include <iostream>
using namespace std;
int main() {
char ch;
cin >> ch;
if (ch >= '0' && ch <= '9') {
cout << "yes";
} else {
cout << "no";
}
return 0;
}满足条件的数的累加
现有n个整数,将其中个位数为k的数进行累加求和。
输入
第一行2个整数n、k,以空格隔开。(0<n<1000,0<=k<=9) 第二行n个非负整数,以空格隔开,每个数不大于100000。
输出
输出满足题目要求的累加和。
样例输入
10 7 2 5 7 17 11 18 4 27 1 7
样例输出
58
//解法1
#include <iostream>
using namespace std;
int main() {
int n, k, a, sum = 0;
cin >> n >> k;
for (int i = 0; i < n; i++) {
cin >> a;
if (a % 10 == 7)
sum += a;
}
cout << sum;
return 0;
}//解法2
#include<bits/stdc++.h>
using namespace std;
int main()
{
int n,k,ans=0;
cin>>n>>k;
for(int i=1,x;i<=n;i++){
cin>>x;
if(x%10==k) ans+=x;
}
cout<<ans;
return 0;
}交换输出
输入两个整数a,b,将它们交换输出
输入
一行两个整数a、b,以空格分割。0<a<108 0<b<1016
输出
一行两个整数b、a,以空格分割。
样例输入
123 12345654321
样例输出
12345654321 123
#include <iostream>
using namespace std;
int main() {
long long a, b;
cin >> a >> b;
cout << b << " " << a;
}计算乘积
给定两个数a,b,计算它们的乘积
输入
一行两个整数a,b,以空格隔开。0<a,b<10的8次方
输出
一个整数,表示a,b的乘积。
样例输入
123456 123456
样例输出
15241383936
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
char x[50010], y[50010];
int a[50010], b[50010], c[50010];
int main() {
cin >> x >> y;
a[0] = strlen(x);
b[0] = strlen(y);
for (int i = 1; i <= a[0]; ++i)
a[i] = x[a[0] - i] - '0';
for (int i = 1; i <= b[0]; ++i)
b[i] = y[b[0] - i] - '0';
for (int i = 1; i <= a[0]; ++i)
for (int j = 1; j <= b[0]; ++j)
c[i + j - 1] += a[i] * b[j];
int len = a[0] + b[0];
for (int i = 1; i <= len - 1; ++i)
if (c[i] > 9) {
c[i + 1] += c[i] / 10;
c[i] %= 10;
}
while (c[len] == 0 && len > 1)
len--;
for (int i = len; i >= 1; --i)
printf("%d", c[i]);
return 0;
}比n小的最大质数
对于给定的n,求比n小的质数中最大的一个
质数是指大于1的自然数,除了1和它自身外,不能被其他自然数整除的数。
输入
一个整数n(2<n<1000)
输出
一个整数,即题目要求的解。
样例输入
100
样例输出
97
#include <iostream>
using namespace std;
bool isPrime(int x) {
for (int i = 2; i < x; i++) {
if (x % i == 0)
return false;
}
return true;
}
int main() {
int n;
cin >> n;
while (n > 0) {
if (isPrime(n)) {
cout << n;
break;
}
n--;
}
return 0;
}逆波兰表达式
逆波兰表达式是一种把运算符前置的算术表达式,例如普通的表达式2 + 3的逆波兰表示法为+ 2 3。逆波兰表达式的优点是运算符之间不必有优先级关系,也不必用括号改变运算次序,例如(2 + 3) * 4的逆波兰表示法为* + 2 3 4。本题求解逆波兰表达式的值,其中运算符包括+ - * /四个。
时间限制:1000
内存限制:65536
输入
输入为一行,其中运算符和运算数之间都用空格分隔,运算数是浮点数。
输出
输出为一行,表达式的值。 可直接用printf("%f\n", v)输出表达式的值v。
样例输入
* + 11.0 12.0 + 24.0 35.0
样例输出
1357.000000
#include <cmath>
#include <cstdlib>
#include <iostream>
using namespace std;
const int N = 40;
char a[N];
double expr(void) {
scanf("%s", a);
if (a[0] == '+')
return expr() + expr();
else if (a[0] == '-')
return expr() - expr();
else if (a[0] == '*')
return expr() * expr();
else if (a[0] == '/')
return expr() / expr();
else
return atof(a);
}
int main() {
printf("%lf\n", expr());
return 0;
}多项式相加
我们经常遇到两多项式相加的情况,在这里,我们就需要用程序来模拟实现把两个多项式相加到一起。首先,我们会有两个多项式,每个多项式是独立的一行,每个多项式由系数、幂数这样的多个整数对来表示。
如多项式2x20- x17+ 5x9- 7x7+ 16x5+ 10x4 + 22x2- 15
对应的表达式为:2 20 -1 17 5 9 - 7 7 16 5 10 4 22 2 -15 0。
为了标记每行多项式的结束,在表达式后面加上了一个幂数为负数的整数对。
同时输入表达式的幂数大小顺序是随机的。
我们需要做的就是把所给的两个多项式加起来。
时间限制:1000
内存限制:65536
输入
输入包括多行。 第一行整数n,表示有多少组的多项式需要求和。(1 < n < 100) 下面为2n行整数,每一行都是一个多项式的表达式。表示n组需要相加的多项式。 每行长度小于300。
输出
输出包括n行,每行为1组多项式相加的结果。 在每一行的输出结果中,多项式的每一项用“[x y]”形式的字符串表示,x是该项的系数、y 是该项的幂数。要求按照每一项的幂从高到低排列,即先输出幂数高的项、再输出幂数低的项。 系数为零的项不要输出。
样例输入
2 -1 17 2 20 5 9 -7 7 10 4 22 2 -15 0 16 5 0 -1 2 19 7 7 3 17 4 4 15 10 -10 5 13 2 -7 0 8 -8 -1 17 2 23 22 2 6 8 -4 7 -18 0 1 5 21 4 0 -1 12 7 -7 5 3 17 23 4 15 10 -10 5 13 5 2 19 9 -7
样例输出
[ 2 20 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 5 9 ] [ 6 5 ] [ 14 4 ] [ 35 2 ] [ -22 0 ] [ 2 23 ] [ 2 19 ] [ 2 17 ] [ 15 10 ] [ 6 8 ] [ 8 7 ] [ -3 5 ] [ 44 4 ] [ 22 2 ] [ -18 0 ]
提示
第一组样例数据的第二行末尾的8 -8,因为幂次-8为负数,所以这一行数据结束,8 -8不要参与计算。
#include <algorithm>
#include <iostream>
using namespace std;
typedef struct LNode {
int num;
int pow;
struct LNode *next;
} LNode, *LinkList;
bool cmp(LNode a, LNode b) { return a.pow > b.pow; }
void ListInsert(LNode *pHead, int a, int b) {
LNode *p = new LNode;
p->num = a;
p->pow = b;
p->next = pHead->next;
pHead->next = p;
}
LNode *find(LNode *pHead, int b) {
LNode *p = pHead->next;
while (p && p->pow != b) {
p = p->next;
}
return p;
}
void sort(LNode *pHead) {
LNode *p, *q;
int ta, tb;
for (p = pHead->next; p != NULL; p = p->next)
for (q = pHead->next; q->next != NULL; q = q->next) {
if (q->pow < q->next->pow) {
ta = q->num;
tb = q->pow;
q->num = q->next->num;
q->pow = q->next->pow;
q->next->num = ta;
q->next->pow = tb;
}
}
}
int main(void) {
LNode *pHead = NULL, *p, *q;
int n, t, a, b, i;
cin >> n;
for (i = 0; i < n; i++) {
pHead = new LNode;
pHead->next = NULL;
t = 1;
while (t <= 2) {
while (cin >> a >> b) {
if (b < 0)
break;
if ((p = find(pHead, b)) != NULL) {
p->num += a;
} else
ListInsert(pHead, a, b);
}
t++;
}
sort(pHead);
p = pHead->next;
while (p != NULL) {
if (p->num == 0) {
p = p->next;
continue;
}
cout << "[ " << p->num << " " << p->pow << " ]"
<< " ";
p = p->next;
}
cout << endl;
p = pHead->next;
while (!p) {
q = p;
p = p->next;
delete q;
}
}
return 0;
}扑克牌排序
假设这里有36张扑克牌,分别为A1~A9,B1~B9,C1~C9,D1~D9,其中A代表方片,B代表草花,C代表红桃,D代表黑桃,那么,设定如下的排序规则:
1.对于两张卡牌,X1Y1与X2Y2,X1与X2表示A~D,Y1与Y2表示1~9,如果X1与X2不同,那么依照D>C>B>A的方式进行排序
2.假如有X1与X2相同时,那么就比较Y1与Y2的大小。
例如,对于如下的四张牌,有如下的升序排序结果:
D3,C4,A4,C1
升序排序的结果为A4,C1,C4,D3
有人提出了如下的排序策略:
先建立9个队列,用于存放点数的大小,将卡牌依点数存放入各自的队列之中,然后再按队列1到队列9依次出队。
例如,对于上面的结果,依次进队后,结果如下:
队列1:C1;队列3:D3,队列4:C4,A4
将其依次出队后,结果为C1,D3,C4,A4
然后,再建立4个队列,用于存放花色。将卡牌依花色A~D存放入队列1~4中,然后再按队列1到队列4依次出队。
例如,对于上面刚刚出队的序列C1,D3,C4,A4,将其依次进队,结果如下:
队列1:A4;队列3:C1,C4;队列4:D3
将其依次出队后,结果为A4,C1,C4,D3,排序结束。
请根据上面的算法,编写一个用队列对扑克牌排序的程序,要求依照上面的排序规则,根据先花色后点数的方法进行排序。
时间限制:1000
内存限制:65536
输入
输入分为两行,第一行为一个整数n,表示一共有n张牌(1<=n<=100) 第二行用XY的形式表示每一张牌,其中X为A~D,Y为1~9
输出
输出三个部分 第一个部分为第一次进队出队的结果,用Queue1:...表示,共9行,结果用空格分隔,下同 第二部分为第二次进队出队的结果,用QueueA:...表示,共4行 第三部分为一行,即将卡牌排序后的结果(升序排序)
样例输入
8 D8 A6 C3 B8 C5 A1 B5 D3
样例输出
Queue1:A1 Queue2: Queue3:C3 D3 Queue4: Queue5:C5 B5 Queue6:A6 Queue7: Queue8:D8 B8 Queue9: QueueA:A1 A6 QueueB:B5 B8 QueueC:C3 C5 QueueD:D3 D8 A1 A6 B5 B8 C3 C5 D3 D8
提示
第二次入队出队时,可以复用第一次时9个队列中的4个。所以其实只需要开辟9个队列即可。
#include <iostream>
#include <queue>
#include <string>
using namespace std;
int main() {
int n = 0;
cin >> n;
queue<string> q1[10], q2[4]; // 分别按照大小和花色存放扑克
string *strs = new string[n];
string newstr[10000];
for (int i = 0; i < n; i++) {
cin >> strs[i];
q1[strs[i][1] - '1'].push(strs[i]); // 按照大小入队q1
}
for (int i = 0; i < n; i++) // 输出q1队列,从小到大
{
cout << "Queue" << i + 1 << ":";
while (!q1[i].empty()) {
cout << q1[i].front() << " ";
q2[q1[i].front()[0] - 'A'].push(q1[i].front()); // 按照花色入队q2
q1[i].pop();
}
cout << endl;
}
int c = 0;
for (int i = 0; i < 4; i++) // 输出q2队列,按照花色
{
char t;
t = (char)i + 'A';
cout << "Queue" << t << ":"; // i+'A'做类型转换
while (!q2[i].empty()) {
cout << q2[i].front() << " ";
newstr[c++] = q2[i].front(); // 将队列q2中的string保存到newstr中
q2[i].pop();
}
cout << endl;
}
for (int i = 0; i < c; i++) // 输出升序排序后的卡牌
cout << newstr[i] << " ";
cout << endl;
return 0;
}表达式求值
求一个可能包含加、减、乘、除、乘方运算的中缀表达式的值。
在计算机中,我们常用栈来解决这一问题。首先将中缀表达式转换到后缀表达式,然后对后缀表达式求值。
加、减、乘、除、乘方分别用+,-,*, /, ^来表示。表达式可以有圆括号()。
时间限制:1000
内存限制:65536
输入
第一行为测试数据的组数N。 接下来的N行,每行是一个中缀表达式。 每个表达式中,圆括号、运算符和运算数相互之间都用空格分隔,运算数是整数。一般运算数可正可负(负数的符号和数字之间无空格),指数一定为自然数(0和正整数)。不必考虑除0的情况。每个运算数均可由int放下。不必考虑溢出。中缀表达式的字符串长度不超过600。乘方的优先级比乘除都高,结合性是向左结合,如2 ^ 3 ^ 4表示( 2 ^ 3 ) ^ 4 = 4096。除法的商向下取整。
输出
对每一组测试数据输出一行,为表达式的值
样例输入
2 31 * ( 5 - ( -3 + 25 ) ) + 70 ^ 2 2 * 5 + 6 * ( 7 - 8 ) + 6
样例输出
4373 10
#include <bits/stdc++.h>
using namespace std;
int get_fast(string op) // 运算符的优先级
{
int ans = -1;
switch (op[0]) {
case '+':
case '-':
ans = 1;
break;
case '*':
case '/':
ans = 2;
break;
case '^':
ans = 3;
break;
}
return ans;
}
vector<string> scaner(string s) // 字符串拆解放入vector
{
vector<string> ans;
string ops = "+-*/^()";
string t = "";
for (int i = 0; i < s.size(); i++) {
if (s[i] == '-' && (i + 1 < s.size()) && s[i + 1] >= '0' && s[i + 1] <= '9')
t = "-";
else if (s[i] >= '0' && s[i] <= '9')
t += s[i];
else if (ops.find(s[i]) != string::npos)
t += s[i];
else if (s[i] == ' ') {
if (t.size() > 0)
ans.push_back(t);
t = "";
}
}
if (t.size())
ans.push_back(t);
return ans;
}
vector<string> infix_Suffix(vector<string> exp) // 中缀表达式转后缀表达式
{
vector<string> ans;
stack<string> st;
string op = "+-*/^()";
for (int i = 0; i < exp.size(); i++) {
if (exp[i] == "(")
st.push(exp[i]);
else if (exp[i] == ")") {
while (st.top() != "(") {
ans.push_back(st.top());
st.pop();
}
st.pop();
} else if (op.find(exp[i]) != string::npos) {
while (st.size() && get_fast(exp[i]) <= get_fast(st.top())) {
ans.push_back(st.top());
st.pop();
}
st.push(exp[i]);
} else
ans.push_back(exp[i]);
}
while (st.size()) {
ans.push_back(st.top());
st.pop();
}
return ans;
}
int suffix_calc(vector<string> exp) // 后缀表达式计算结果
{
stack<int> num;
string ops = "+-*/^";
for (int i = 0; i < exp.size(); i++) {
if (ops.find(exp[i]) != string::npos) {
int a = num.top();
num.pop();
int b = num.top();
num.pop();
if (exp[i] == "+")
num.push(b + a);
else if (exp[i] == "-")
num.push(b - a);
else if (exp[i] == "*")
num.push(b * a);
else if (exp[i] == "/")
num.push(b / a);
else if (exp[i] == "^")
num.push(pow(b * 1.0, a));
} else
num.push(atoi(exp[i].c_str()));
}
cout << num.top() << endl;
return num.top();
}
int main() {
string s;
getline(cin, s);
int n;
n = atoi(s.c_str());
while (n--) {
getline(cin, s);
vector<string> vs = scaner(s);
vs = infix_Suffix(vs);
suffix_calc(vs);
}
return 0;
}有多少种二叉树
输入n(1<n<13),求n个结点的二叉树有多少种形态
时间限制:1000
内存限制:65536
输入
整数n
输出
答案
样例输入
3
样例输出
5
#include <bits/stdc++.h>
using namespace std;
int main() {
long long n, h1 = 1, y = 0;
cin >> n;
for (long long i = 1; i < n + 1; i++) {
y = (4 * i - 2) * h1 / (i + 1);
h1 = y;
}
cout << y;
return 0;
}城堡问题
1 2 3 4 5 6 7
#############################
1 # | # | # | | #
#####---#####---#---#####---#
2 # # | # # # # #
#---#####---#####---#####---#
3 # | | # # # # #
#---#########---#####---#---#
4 # # | | | | # #
#############################
(图 1)
# = Wall
| = No wall
- = No wall
图1是一个城堡的地形图。请你编写一个程序,计算城堡一共有多少房间,最大的房间有多大。城堡被分割成m×n(m≤50,n≤50)个方块,每个方块可以有0~4面墙。
时间限制:1000
内存限制:65536
输入
程序从标准输入设备读入数据。第1、2行每行1个整数,分别是南北向、东西向的方块数。在接下来的输入行里,每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙,1表示西墙,2表示北墙,4表示东墙,8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次,方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间。
输出
输出2行,每行一个数,表示城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。
样例输入
4 7 11 6 11 6 3 10 6 7 9 6 13 5 15 5 1 10 12 7 13 7 5 13 11 10 8 10 12 13
样例输出
5 9
#include <bits/stdc++.h>
using namespace std;
int maze[60][60], M, N;
int book[60][60];
int roomnum = 0, maxroom = 0, room;
void dfs(int x, int y) {
if (book[x][y])
return;
room++;
book[x][y] = 1;
if ((maze[x][y] & 1) == 0)
dfs(x, y - 1);
if ((maze[x][y] & 2) == 0)
dfs(x - 1, y);
if ((maze[x][y] & 4) == 0)
dfs(x, y + 1);
if ((maze[x][y] & 8) == 0)
dfs(x + 1, y);
}
int main() {
cin >> M >> N;
memset(book, 0, sizeof(book));
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++)
cin >> maze[i][j];
for (int i = 0; i < M; i++)
for (int j = 0; j < N; j++) {
if (!book[i][j]) {
room = 0;
roomnum++;
dfs(i, j);
maxroom = maxroom > room ? maxroom : room;
}
}
cout << roomnum << endl << maxroom << endl;
return 0;
}快速堆猪
小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。
时间限制:1000
内存限制:65536
输入
有三种输入 1)push n n是整数(0<=0 <=20000),表示叠上一头重量是n斤的新猪 2)pop 表示将猪堆顶的猪赶走。如果猪堆没猪,就啥也不干 3)min 表示问现在猪堆里最轻的猪多重。如果猪堆没猪,就啥也不干 输入总数不超过100000条
输出
对每个min输入,输出答案。如果猪堆没猪,就啥也不干
样例输入
pop min push 5 push 2 push 3 min push 4 min
样例输出
2 2
#include <iostream>
using namespace std;
typedef long long LL;
int h[2005];
int size_;
void up(int u) {
while (u / 2 && h[u / 2] > h[u]) {
swap(h[u / 2], h[u]);
u /= 2;
}
}
void down(int u) {
int t = u;
if (u * 2 <= size_ && h[u * 2] < h[u])
t = u * 2;
if (u * 2 + 1 <= size_ && h[u * 2 + 1] < h[u])
t = u * 2 + 1;
if (u != t) {
swap(h[u], h[t]);
down(t);
}
}
int main() {
char t[10];
string s;
int n;
while (scanf("%s", t) != EOF) {
s = string(t);
if (s == "pop") {
if (size_ == 0)
continue;
h[1] = h[size_];
size_--;
down(1);
} else if (s == "min") {
if (size_ == 0)
continue;
cout << h[1] << endl;
} else if (s == "push") {
cin >> n;
size_++;
h[size_] = n;
up(size_);
}
}
return 0;
}重建二叉树
给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历。
时间限制:1000
内存限制:65536
输入
输入可能有多组,以EOF结束。 每组输入包含两个字符串,分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。
输出
对于每组输入,用一行来输出它后序遍历结果。
样例输入
DBACEGF ABCDEFG BCAD CBAD
样例输出
ACBFGED CDAB
#include <stdio.h>
#include <string.h>
void bulid(int n, char s1[],
char s2[]) // n是树的节点数,s1是记录先序遍历,s2中序遍历
{
if (n <= 0)
return; // 没有节点了,找到边界return
int p = strchr(s2, s1[0]) - s2;
// strchr(s2,s1[0])是s2的地址+s1[0]第一次出现的位置i。s2是s2的地址
// 所以p是 s1[0]第一次出现在s2中的位置
bulid(p, s1 + 1, s2);
// 数的节点数为s1[0]在s2中之前的所有节点。s1+1是把s1数组整体向前移动一位(s1[0]是以前的s1[1],s1[1]改为以前s1[2]...
// 以前s1[0]是根,现在不需要,所以删除。要它左子树的根节点
// s2不变(假设中序遍历中根节点的位置是a,那么后序遍历中0~a个点是树的左子树节点)
bulid(n - p - 1, s1 + p + 1, s2 + p + 1);
// 数的节点数为s1[0]在s2中之后的所有节点(因为数组从0开始,所以-1)
// 以前s1[0]是根,现在不需要,左子树也不需要,所以都删除。要它右子树的根节点
// s2+p+1(假设中序遍历中根节点的位置是a,a~n-2(数组从0开始)个点是树的右子树节点
// )
printf("%c", s1[0]); // 输出
}
int main() {
char s1[10007], s2[10007]; // s1是树的前序遍历,s2是树的中序遍历
while (scanf("%s %s", s1, s2) != EOF) // 多组数据
{
bulid(strlen(s1), s1, s2);
printf("\n"); // 记得输出\n
}
return 0;
}
/*
先序遍历第一个节点一定是根节点。
中序遍历根节点左侧就是树的左子树,右侧就是树的右子树。
后序遍历最后一个节点一定是根节点,而假设中序序列里根节点位置是m,那么后序序列里0至m-1个节点是树的左子树节点,m至倒数第二个点是树的右子树节点。
*/