C/C++编程七级 题库
区间DP的核心思想是?( )
走出迷宫
当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。
假设你已经得到了一个n*m的迷宫的图纸,请你找出从起点到出口的最短路。
时间限制:1000
内存限制:65536
输入
第一行是两个整数n和m(1<=n,m<=100),表示迷宫的行数和列数。 接下来n行,每行一个长为m的字符串,表示整个迷宫的布局。字符'.'表示空地,'#'表示墙,'S'表示起点,'T'表示出口。
输出
输出从起点到出口最少需要走的步数。
样例输入
3 3 S#T .#. ...
样例输出
6
#include <bits/stdc++.h>
using namespace std;
int n, m, p[10008], q[10008], ans[108][108], qx, qy, zx, zy;
char a[108][108];
int xx[5] = {0, 1, -1, 0, 0};
int yy[5] = {0, 0, 0, 1, -1};
void bfs() {
a[qx][qy] = '#';
ans[qx][qy] = 0;
int head = 1;
int tail = 1;
p[1] = qx;
q[1] = qy;
while (head <= tail) {
for (int i = 1; i <= 4; i++) {
int h = p[head] + xx[i];
int l = q[head] + yy[i];
if (a[h][l] != '#' && h >= 1 && l >= 1 && h <= n && l <= m) {
a[h][l] = '#';
tail++;
p[tail] = h;
q[tail] = l;
ans[h][l] = ans[p[head]][q[head]] + 1;
if (h == zx && l == zy) {
cout << ans[h][l] << endl;
return;
}
}
}
head++;
}
}
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
if (a[i][j] == 'S') {
qx = i;
qy = j;
}
if (a[i][j] == 'T') {
zx = i;
zy = j;
}
}
}
bfs();
return 0;
}拯救公主
多灾多难的公主又被大魔王抓走啦!国王派遣了第一勇士阿福去拯救她。
身为超级厉害的术士,同时也是阿福的好伙伴,你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图,上面标记了阿福和公主所在的位置,以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门,通过一个传送门可以瞬间转移到任意一个传送门,当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外,你还查探到公主所在的地方被设下了结界,需要集齐K种宝石才能打开。当然,你在地图上也标记出了不同宝石所在的位置。
你希望阿福能够带着公主早日凯旋。于是在阿福出发之前,你还需要为阿福计算出他最快救出公主的时间。
地图用一个R×C的字符矩阵来表示。字符S表示阿福所在的位置,字符E表示公主所在的位置,字符#表示不能踏入的禁区,字符$表示传送门,字符.表示该位置安全,数字字符0至4表示了宝石的类型。阿福每次可以从当前的位置走到他上下左右四个方向上的任意一个位置,但不能走出地图边界。阿福每走一步需要花费1个单位时间,从一个传送门到达另一个传送门不需要花费时间。当阿福走到宝石所在的位置时,就视为得到了该宝石,不需要花费额外时间。
时间限制:1000
内存限制:65536
输入
第一行是一个正整数T(1 <= T <= 10),表示一共有T组数据。 每一组数据的第一行包含了三个用空格分开的正整数R、C(2 <= R, C <= 200)和K,表示地图是一个R×C的矩阵,而阿福需要集齐K种宝石才能够打开拘禁公主的结界。 接下来的R行描述了地图的具体内容,每一行包含了C个字符。字符含义如题目描述中所述。保证有且仅有一个S和E。$的数量不超过10个。宝石的类型在数字0至4范围内,即不会超过5种宝石。
输出
对于每一组数据,输出阿福救出公主所花费的最少单位时间。若阿福无法救出公主,则输出“oop!”(只输出引号里面的内容,不输出引号)。每组数据的输出结果占一行。
样例输入
1 7 8 2 ........ ..S..#0. .##..1.. .0#..... ...1#... ...##E.. ...1....
样例输出
11
#include <cmath>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
struct POINT {
int x, y, tot;
bool get_jewel[7], enchantment;
} point, door;
int main() {
int k, F[4][2] = {-1, 0, 1, 0, 0, -1, 0, 1};
scanf("%d", &k);
for (int kk = 1; kk <= k; kk++) {
queue<POINT> que;
int r, c, needkind, door_coord[15][2] = {}, sdoor_coord = 0;
char maze[205][205] = {};
bool walked[205][205][35] = {}, finish = false;
scanf("%d%d%d", &r, &c, &needkind);
for (int i = 0; i < r; i++) {
scanf("%s", maze[i]);
for (int j = 0; j < c; j++) {
if (maze[i][j] == 'S') {
memset(point.get_jewel, false, sizeof(point.get_jewel));
point.x = i;
point.y = j;
point.tot = 0;
point.enchantment = true;
}
if (maze[i][j] == '$') {
door_coord[sdoor_coord][0] = i;
door_coord[sdoor_coord++][1] = j;
}
}
}
que.push(point);
while (!que.empty()) {
for (int i = 0; i < 4; i++) {
point = que.front();
point.tot++;
point.x += F[i][0];
point.y += F[i][1];
if (point.x < 0 || point.x >= r || point.y < 0 || point.y >= c ||
maze[point.x][point.y] == '#')
continue;
if ('0' <= maze[point.x][point.y] && maze[point.x][point.y] <= '4')
point.get_jewel[maze[point.x][point.y] - '0'] = true;
int sget_jewel = 0, ss = 0;
for (int i = 0; i < 5; i++)
if (point.get_jewel[i])
sget_jewel += pow(2, i), ss++;
if (walked[point.x][point.y][sget_jewel])
continue;
walked[point.x][point.y][sget_jewel] = true;
if (ss >= needkind)
point.enchantment = false;
if (maze[point.x][point.y] == '$') {
door = point;
for (int i = 0; i < sdoor_coord; i++)
if (door_coord[i][0] != point.x || door_coord[i][1] != point.y) {
door.x = door_coord[i][0];
door.y = door_coord[i][1];
que.push(door);
}
}
if (maze[point.x][point.y] == 'E' && !point.enchantment) {
printf("%d\n", point.tot);
finish = true;
}
if (finish)
break;
que.push(point);
}
if (finish)
break;
que.pop();
}
if (!finish)
printf("oop!\n");
}
return 0;
}// 参考答案2
#include <cstdio>
#include <cstring>
#include <iostream>
#include <queue>
#define N 210
using namespace std;
int dir[2][4] = {{1, 0, 0, -1}, {0, 1, -1, 0}};
int dp[N][N][1 << 5 - 1], trans[20][2], n, m, k, tot, num, T, x, y, ans;
char map[N][N];
struct node {
int x, y, step, key;
node(int xx, int yy, int ss, int kk) : x(xx), y(yy), step(ss), key(kk){};
};
bool check(int key) {
int cnt = 0;
for (int i = 0; i <= 5; i++)
if ((key >> i) & 1)
cnt++; // 位运算 统计这条路上可获不同种类的宝石数量
if (cnt >= k)
return 1;
return 0;
}
int bfs(int x, int y) {
queue<node> que; // 根据结构体 定义队列que
dp[x][y][0] = 1;
node now(x, y, 0, 0); // 相当于 定义了now这个结构体变量
que.push(now); // 进队
while (!que.empty()) // 当队列不为空时 .empty()-->若队列为空返回1;
{
now = que.front(); // 把队头的值赋给now这个结构体上
que.pop(); // 弹出队首
for (int i = 0; i < 4; i++) // 上下左右四个执行方案
{
int xx = now.x + dir[0][i]; // 具体变动
int yy = now.y + dir[1][i];
int step = now.step; // 步数
int key = now.key; //
if (xx < 0 || xx >= n || yy < 0 || yy >= m)
continue; // 判断边界
if (dp[xx][yy][key])
continue; // 若在队中 不走
if (map[xx][yy] == '#')
continue; // 禁区 不走
if (map[xx][yy] == 'E' && check(key)) // 既到达营救点 且 宝石够数
{
return step + 1; // 返回步数 //结束遍历
}
if (isdigit(map[xx][yy])) //
{
dp[xx][yy][key] = 1; // 标记 相当于vis
key = key | (1 << (map[xx][yy] - '0')); // 记录宝石
que.push(node(xx, yy, step + 1, key)); // 进队
}
if (map[xx][yy] == '.') // 普通地带
{
dp[xx][yy][key] = 1; // 标记
que.push(node(xx, yy, step + 1, key));
}
if (map[xx][yy] == '$') // 传送门
{
dp[xx][yy][key] = 1; // 标记
que.push(node(xx, yy, step + 1, key)); // 进队
for (int j = 1; j <= tot; j++) // 遍历 方案
{
xx = trans[j][0], yy = trans[j][1];
if (!dp[xx][yy][key]) {
dp[xx][yy][key] = 1; // 标记
que.push(node(xx, yy, step + 1, key)); // 进队
}
}
}
}
}
return -1; // 若遍历完还没返回 就说明没有可行方案
}
main() {
cin >> T; // 组数
while (T--) {
memset(dp, 0, sizeof(dp));
tot = 0;
num = 0; // 初始化
scanf("%d%d%d", &n, &m, &k);
// cin>>n>>m>>k;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
cin >> map[i][j];
// scanf("%c",&map[i][j]);还是没搞明白为什么不能用scanf和getchar
// map[i][j]=getchar();
if (map[i][j] == 'S')
x = i, y = j, map[i][j] = '.'; // 标记起点
if (map[i][j] == '$')
trans[++tot][0] = i, trans[tot][1] = j; // 记录传送门
if (isdigit(map[i][j]))
num++; // 判断是否是宝石(数字)
}
if (k > num) {
printf("oop!\n");
continue;
} // 没有足够的宝石
ans = bfs(x, y);
if (ans == -1)
printf("oop!\n");
else
printf("%d\n", ans);
}
}有多少种二叉树(2023.3)
输入n(1<n<13),求n个结点的二叉树有多少种形态
时间限制:1000
内存限制:65536
输入
整数n
输出
答案
样例输入
3
样例输出
5
#include <iostream>
using namespace std;
long long cat(int n) {
if (n == 0)
return 1;
long long sum(0);
for (int i = 0; i < n; i++)
sum += cat(i) * cat(n - 1 - i);
return sum;
}
int main() {
int n;
cin >> n;
cout << cat(n);
return 0;
}Sequence
给定m个数字序列,每个序列包含n个非负整数。我们从每一个序列中选取一个数字组成一个新的序列,显然一共可以构造出n^m个新序列。接下来我们对每一个新的序列中的数字进行求和,一共会得到n^m个和,请找出最小的n个和
时间限制:3000
内存限制:65536
输入
输入的第一行是一个整数T,表示测试用例的数量,接下来是T个测试用例的输入 每个测试用例输入的第一行是两个正整数m(0 < m <= 100)和n(0 < n <= 2000),然后有m行,每行有n个数,数字之间用空格分开,表示这m个序列 序列中的数字不会大于10000
输出
对每组测试用例,输出一行用空格隔开的数,表示最小的n个和
样例输入
1 2 3 1 2 3 2 2 3
样例输出
3 3 4
#include <algorithm>
#include <iostream>
#include <queue>
using namespace std;
priority_queue<int> que;
int a[2005];
int b[2005]; // 用作中间数组
int main() {
int T;
cin >> T;
int m, n;
while (T--) {
cin >> m >> n;
for (int i = 0; i < n; i++) {
scanf("%d", &a[i]);
}
sort(a, a + n); // 用a做总的和数组
for (int i = 1; i < m; i++) // 轮接下来的序列
{
for (int j = 0; j < n; j++) {
scanf("%d", &b[j]);
que.push(a[0] + b[j]);
}
for (int j = 1; j < n; j++) {
for (int k = 0; k < n; k++) {
if (a[j] + b[k] < que.top()) {
que.pop();
que.push(a[j] +
b[k]); // 比最大值小就顶了它,想要得到ab两个里面最小的n个数
}
}
}
for (int i = 0; i < n; i++) {
a[n - i - 1] = que.top(); // 由于是最大值堆,要反过来让a有序
que.pop(); // 队列已经被清空了,轮下一次
}
}
for (int i = 0; i < n - 1; i++)
printf("%d ", a[i]);
printf("%d\n", a[n - 1]);
}
return 0;
}走迷宫
一个迷宫由R行C列格子组成,有的格子里有障碍物,不能走;有的格子是空地,可以走。 给定一个迷宫,求从左上角走到右下角最少需要走多少步(数据保证一定能走到)。只能在水平方向或垂直方向走,不能斜着走。
时间限制:1000
内存限制:65536
输入
第一行是两个整数,R和C,代表迷宫的长和宽。(1<= R,C <= 40) 接下来是R行,每行C个字符,代表整个迷宫。 空地格子用'.'表示,有障碍物的格子用'#'表示。 迷宫左上角和右下角都是'.'。
输出
输出从左上角走到右下角至少要经过多少步(即至少要经过多少个空地格子)。计算步数要包括起点和终点。
样例输入
5 5 ..### #.... #.#.# #.#.# #.#..
样例输出
9
#include <iostream>
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
const int idata = 1000 + 5;
char maps[idata][idata];
int judge[idata][idata];
int change[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int nx, ny;
int x[idata], y[idata];
int Count[idata][idata];
int soux, souy;
int exitx, exity;
bool flag;
int m, n;
int main() {
int i, j;
int tail = 1, head = 0;
cin >> m >> n;
for (i = 1; i <= m; i++) {
for (j = 1; j <= n; j++) {
cin >> maps[i][j];
if (maps[i][j] == '#')
judge[i][j] = 1;
}
}
judge[1][1] = 1;
Count[1][1] = 1;
x[1] = 1, y[1] = 1;
while (head < tail) {
head++;
for (i = 0; i < 4; i++) {
nx = x[head] + change[i][0];
ny = y[head] + change[i][1];
if (nx >= 1 && nx <= m && ny >= 1 && ny <= n && !judge[nx][ny]) {
judge[nx][ny] = 1;
tail++;
x[tail] = nx;
y[tail] = ny;
Count[x[tail]][y[tail]] = Count[x[head]][y[head]] + 1;
if (nx == m && ny == n) {
flag = 1;
break;
}
}
}
if (flag)
break;
}
cout << Count[m][n] << endl;
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至倒数第二个点是树的右子树节点。
*/快速堆猪
小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。
时间限制: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;
}表达式· 表达式树· 表达式求值
众所周知, 任何一个表达式, 都可以用一棵表达式树来表示。 例如,
表达式 a+b*c, 可以表示为如下的表达式树:
+
/ \
a *
/ \
b c
现在, 给你一个中缀表达式, 这个中缀表达式用变量来表示(不含数字), 请你将这个中缀表达式用表达式二叉树的形式输出出来。
时间限制: 1000
内存限制: 65535
输入
输入分为三个部分。 第一部分为一行,即中缀表达式(长度不大于50)。中缀表达式可能含有小写字母代表变量(a-z),也可能含有运算符(+、-、*、/、小括号),不含有数字,也不含有空格。 第二部分为一个整数n(n < 10),表示中缀表达式的变量数。 第三部分有n行,每行格式为C x,C为变量的字符,x为该变量的值。
输出
输出分为三个部分,第一个部分为该表达式的逆波兰式,即该表达式树的后根遍历结果。占一行。 第二部分为表达式树的显示,如样例输出所示。如果该二叉树是一棵满二叉树,则最底部的叶子结点,分别占据横坐标的第1、3、5、7……个位置(最左边的坐标是1),然后它们的父结点的横坐标,在两个子结点的中间。如果不是满二叉树,则没有结点的地方,用空格填充(但请略去所有的行末空格)。每一行父结点与子结点中隔开一行,用斜杠(/)与反斜杠(\)来表示树的关系。/出现的横坐标位置为父结点的横坐标偏左一格,\出现的横坐标位置为父结点的横坐标偏右一格。也就是说,如果树高为m,则输出就有2m-1行。 第三部分为一个整数,表示将值代入变量之后,该中缀表达式的值。需要注意的一点是,除法代表整除运算,即舍弃小数点后的部分。同时,测试数据保证不会出现除以0的现象。
样例输入
a+b*c 3 a 2 b 7 c 5
样例输出
abc*+ + / \ a * / \ b c 37
#include <cmath>
#include <cstring>
#include <iostream>
#include <stack>
#include <string>
#define OK 1
#define ERROR 0
#define MAXSIZE 50
using namespace std;
struct number {
char ch;
int value;
};
number a[10];
// 定义二叉树类型
typedef struct BiNode {
char date;
struct BiNode *lchild, *rchild;
} BiNode;
// 定义栈类型
typedef struct SqStack {
char *base;
char *top;
int stacksize;
} SqStack;
// 初始化栈
int InitStack(SqStack &S) {
S.base = new char[MAXSIZE];
if (!S.base)
exit(ERROR);
S.top = S.base;
S.stacksize = MAXSIZE;
return OK;
}
// 出栈
char Pop(SqStack &S) {
if (S.top == S.base)
return ERROR;
char e = *(--S.top);
return e;
}
// 入栈
int Push(SqStack &S, char e) {
if (S.top - S.base == S.stacksize)
return ERROR;
*(S.top++) = e;
return OK;
}
// 将中缀表达式转化为后缀表达式
string Change(string str) {
// str为中缀表达式,str2为后缀表达式
string str2 = "";
char ch, e; // e用于保存栈中弹出的元素
SqStack S1; // S1用于存放操作符(为辅助栈),S用于存放后续表达式
InitStack(S1);
for (int i = 0; i < str.size(); i++) {
ch = str[i];
if (ch >= 'a' && ch <= 'z') {
str2 += ch;
}
if (ch == '(')
Push(S1, ch);
if (ch == ')') {
while (*(S1.top - 1) != '(') {
e = Pop(S1);
str2 += e;
}
Pop(S1); // 左括号出栈但不入S2栈中
}
// 遇到+或-时
// 栈空/栈顶为左括号:直接入栈
// 否则一直出栈,直到栈空/栈顶为左括号,再入栈
if (ch == '+' || ch == '-') {
while (*(S1.top - 1) != '(' && S1.base != S1.top) {
e = Pop(S1);
str2 += e;
}
Push(S1, ch);
}
// 遇到*或/时
// 栈空/栈顶为左括号/栈顶操作符为+ or -:直接入栈
// 否则一直出栈,直到满足上述条件,再入栈
if (ch == '*' || ch == '/') {
while (S1.base != S1.top && *(S1.top - 1) != '(' &&
*(S1.top - 1) != '-' && *(S1.top - 1) != '+') {
e = Pop(S1);
str2 += e;
}
Push(S1, ch);
}
}
// 中缀表达式遍历完成,还需检查栈中是否有未输出字符
// 判断栈空,非空则直接出栈
while (S1.base != S1.top) {
e = Pop(S1);
if (e != '(')
str2 += e;
}
return str2;
}
struct BiNode *s[MAXSIZE]; // 定义栈,该栈用于存放树
int top = -1;
// 建立二叉树
BiNode *CreatTree(string str) {
// str为后缀表达式
BiNode *T, *T2;
SqStack S;
BiNode *e1, *e2;
int i;
InitStack(S);
for (i = 0; i < str.size() - 1; i++) {
if (str[i] >= 'a' && str[i] <= 'z') {
T = new BiNode;
T->date = str[i];
T->lchild = T->rchild = NULL;
s[++top] = T;
} else {
T = new BiNode;
T->date = str[i];
e1 = s[top--];
e2 = s[top--];
T->lchild = e2;
T->rchild = e1;
s[++top] = T;
}
}
T = new BiNode;
T->date = str[i];
T->rchild = s[top--];
T->lchild = s[top--];
s[++top] = T;
T2 = new BiNode;
T2 = s[top];
return T2;
}
int Seek(char e, int n) {
for (int i = 0; i < n; i++) {
if (a[i].ch == e)
return a[i].value;
}
}
int Count(string str, int n) {
// str为后缀表达式数组,n变量个数
int sum = 0;
stack<int> S;
int x, x1, x2;
for (int i = 0; i < n; i++) {
cin >> a[i].ch >> a[i].value;
}
for (int i = 0; i < str.size(); i++) {
if (str[i] >= 'a' && str[i] <= 'z') {
x = Seek(str[i], n);
S.push(x);
} else {
x2 = S.top();
S.pop(); // 左操作数
x1 = S.top();
S.pop(); // 右操作数
switch (str[i]) {
case '+':
sum = x1 + x2;
break;
case '-':
sum = x1 - x2;
break;
case '*':
sum = x1 * x2;
break;
case '/':
sum = x1 / x2;
break;
}
S.push(sum);
}
}
sum = S.top();
return sum;
}
char arr[1000][1000];
// 打印二叉树
void PrintTree(int tag, BiNode *T, int x, int m, int y) {
arr[2 * tag - 1][(x + m) / 2] = T->date;
if (tag != 1) {
if (y == 1)
arr[2 * tag - 2][m] = '/';
else
arr[2 * tag - 2][x] = '\\';
}
if (T->lchild != NULL)
PrintTree(tag + 1, T->lchild, x, (x + m) / 2 - 1, 1);
if (T->rchild != NULL)
PrintTree(tag + 1, T->rchild, (x + m) / 2 + 1, m, 0);
}
// 计算二叉树的深度
int Depth(BiNode *T) {
int m, n;
if (T == NULL)
return 0;
else {
m = Depth(T->lchild);
n = Depth(T->rchild);
if (m > n)
return (m + 1);
else
return (n + 1);
}
}
bool Judge(int i, int j, int n) {
for (int k = j + 1; k <= n; k++) {
if (arr[i][k] != ' ')
return 1;
}
return 0;
}
int main() {
string str1; // 中序表达式
cin >> str1;
int n; // 变量个数
cin >> n;
string str2 = Change(str1); // str2为后序表达式
BiNode *T = CreatTree(str2);
int sum = Count(str2, n);
int dp = Depth(T);
cout << str2 << endl;
memset(arr, ' ', sizeof(arr));
PrintTree(1, T, 1, pow(2.0, dp) - 1, 0);
for (int i = 1; i <= 2 * dp - 1; i++) {
for (int j = 1; j <= pow(2.0, dp) - 1; j++) {
cout << arr[i][j];
if (arr[i][j] != ' ') {
if (Judge(i, j, pow(2.0, dp) - 1))
continue;
else
break;
}
}
cout << endl;
}
cout << sum << endl;
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;
}priority queue练习题
我们定义一个正整数a比正整数b优先的含义是:
*a的质因数数目(不包括自身)比b的质因数数目多;
*当两者质因数数目相等时,数值较大者优先级高。
现在给定一个容器,初始元素数目为0,之后每次往里面添加10个元素,每次添加之后,要求输出优先级最高与最低的元素,并把该两元素从容器中删除。
时间限制:2500
内存限制:131072
输入
第一行: num (添加元素次数,num <= 30)
下面10*num行,每行一个正整数n(n < 10000000).
输出
每次输入10个整数后,输出容器中优先级最高与最低的元素,两者用空格间隔。
样例输入
1 10 7 66 4 5 30 91 100 8 9
样例输出
66 5
#include<bits/stdc++.h>
using namespace std;
int num,d[35][15],pri[500010],tot[500010],a[500010];
int DECOMPOSITION(int x){
int cnt=0,Cnt=0;
for(int i=2;i<=x/i;i++){
for(;x%i==0;x/=i){
a[++cnt]=i;
}
}
if(x>1)a[++cnt]=x;
for(int i=1;i<=cnt;i++,tot[Cnt]++){
if(a[i]!=a[i-1])pri[++Cnt]=a[i];
}
return Cnt;
}
bool isprime(int n){
for(int i=2;i*i<=n;i++){
if(n%i==0){
return 0;
}
}
return 1;
}
struct node{
int tmp;
int cs;
bool operator<(const node &b)const{
if(cs!=b.cs)return cs<b.cs;
else return tmp<b.tmp;
}
};
struct node1{
int tmp;
int cs;
bool operator<(const node1 &b)const{
if(cs!=b.cs)return cs>b.cs;
else return tmp>b.tmp;
}
};
priority_queue<node>q1;
priority_queue<node1>q2;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>num;
for(int i=1;i<=num;i++){
for(int j=1;j<=10;j++){
cin>>d[i][j];
int cyt=DECOMPOSITION(d[i][j]);
if(d[i][j]==1||d[i][j]==0||isprime(d[i][j]))cyt=0;
node top1 ;;
node1 top2;
top1.tmp=d[i][j];
top1.cs=cyt;
top2.tmp=d[i][j];
top2.cs=cyt;
q1.push(top1);
q2.push(top2);
}
cout<<q1.top().tmp<<" "<<q2.top().tmp<<endl;
q1.pop();q2.pop();
}
return 0;
}