C/C++编程七级 题库
二叉树的深度
给定一棵二叉树,求该二叉树的深度
二叉树深度定义:从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的节点个数为树的深度
时间限制:1000
内存限制:65535
输入
第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n <= 10 接下来有n行,依次对应二叉树的n个节点。 每行有两个整数,分别表示该节点的左儿子和右儿子的节点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子
输出
输出一个整型数,表示树的深度
样例输入
3 2 3 -1 -1 -1 -1
样例输出
2
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+7;
struct node{
int left,right;
}t[MAXN];
int n;
void build(){
for(int i=1;i<=n;i++){
cin>>t[i].left>>t[i].right;
}
}
#define rep1(i,n) for(int i=1;i<=n;i++)
inline int dfs(int x){
if(x==-1)return 0;
return max(dfs(t[x].left),dfs(t[x].right))+1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
build();
cout<<dfs(1);
return 0;
}//题解2
#include <algorithm>
#include <iostream>
using namespace std;
int meng[102][30]; /*a[i][0]表示节点i的左孩子节点编号,
a[i][1]表示节点i的右孩子节点编号,a[i][2]表示i节点的父节点编号。*/
int a, b;
int dfs(int root) {
if (meng[root][0] == -1 && meng[root][1] == -1)
return 1;
else {
int left = 0, right = 0;
if (meng[root][0] >= 0)
left = dfs(meng[root][0]);
/*如果该节点满足不为-1证明它有父节点,
递归回去去证明它的父节点上面是否也有父节点*/
if (meng[root][1] >= 0) {
right = dfs(meng[root][1]);
}
return max(right, left) + 1;
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
// 二维是为了更好的判断左孩子还是右孩子,父节点
meng[i][0] = a; // i的左孩子是a
meng[i][1] = b; // i的右孩子是b
}
cout << dfs(1) << 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<bits/stdc++.h>
using namespace std;
int main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
string tp;
int weight,cnt=0;
int minid[100010];
minid[0]=0x3f3f3f3f;
queue<int>q;
while(cin>>tp){
if(tp=="push"){
cin>>weight;
cnt++;
q.push(weight);
minid[cnt]=min(minid[cnt-1],weight);
}else if(tp=="pop"){
if(!q.empty()){
cnt--;
q.pop();
}
}else if(tp=="min"){
if(!q.empty())cout<<minid[cnt]<<endl;
}
}
return 0;
}红与黑(2023.9)
有一间长方形的房子,地上铺了红色、黑色两种颜色的正方形瓷砖。你站在其中一块黑色的瓷砖上,只能向相邻的黑色瓷砖移动。请写一个程序,计算你总共能够到达多少块黑色的瓷砖。
时间限制:1000
内存限制:65536
输入
包括多个数据集合。每个数据集合的第一行是两个整数W和H,分别表示x方向和y方向瓷砖的数量。W和H都不超过20。在接下来的H行中,每行包括W个字符。每个字符表示一块瓷砖的颜色,规则如下 1)‘.’:黑色的瓷砖; 2)‘#’:白色的瓷砖; 3)‘@’:黑色的瓷砖,并且你站在这块瓷砖上。该字符在每个数据集合中唯一出现一次。 当在一行中读入的是两个零时,表示输入结束。
输出
对每个数据集合,分别输出一行,显示你从初始位置出发能到达的瓷砖数(记数时包括初始位置的瓷砖)。
样例输入
6 9 ....#. .....# ...... ...... ...... ...... ...... #@...# .#..#. 0 0
样例输出
45
//解法1:深搜
#include <bits/stdc++.h>
using namespace std;
#define N 25
char mp[N][N];//地图
int w, h, ct;//h:行数,w:ct:结果计数
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组
bool vis[N][N];
void dfs(int sx, int sy)
{
for(int i = 0; i < 4; ++i)
{
int x = sx + dir[i][0], y = sy + dir[i][1];
if(x >= 1 && x <= h && y >= 1 && y <= w && vis[x][y] == false && mp[x][y] != '#')
{
ct++;
vis[x][y] = true;
dfs(x, y);
}
}
}
int main()
{
int stx, sty;//起始位置
while(true)
{
cin >> w >> h;
if(w == 0 && h == 0)
return 0;
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= w; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
stx = i, sty = j;
}
memset(vis, 0, sizeof(vis));//多组数据,注意状态还原
ct = 1;
vis[stx][sty] = true;
dfs(stx, sty);
cout << ct << endl;
}
return 0;
}//解法2:广搜
#include <bits/stdc++.h>
using namespace std;
#define N 25
struct Node
{
int x, y;
Node(){}
Node(int a, int b):x(a),y(b){}
};
char mp[N][N];//地图
int w, h;//w:列数 h:行数
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};//方向数组
bool vis[N][N];
int bfs(int sx, int sy)//传入起始位置
{
queue<Node> que;
vis[sx][sy] = true;
que.push(Node(sx, sy));
int ct = 1;//计数,看可以到达几个黑色格子
while(que.empty() == false)
{
Node u = que.front();
que.pop();
for(int i = 0; i < 4; ++i)
{
int x = u.x + dir[i][0], y = u.y + dir[i][1];
if(x >= 1 && x <= h && y >= 1 && y <= w && vis[x][y] == false && mp[x][y] != '#')
{
vis[x][y] = true;
que.push(Node(x, y));
ct++;
}
}
}
return ct;
}
int main()
{
int stx, sty;
while(true)
{
cin >> w >> h;
if(w == 0 && h == 0)
return 0;
for(int i = 1; i <= h; ++i)
for(int j = 1; j <= w; ++j)
{
cin >> mp[i][j];
if(mp[i][j] == '@')
stx = i, sty = j;
}
memset(vis, 0, sizeof(vis));
cout << bfs(stx, sty) << endl;
}
return 0;
}//解法3:
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#define N 1001
using namespace std;
int m,n;
char ch;
int maps[N][N];
int vis[N][N];
int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}};
int cnt;
void dfs(int x,int y)
{
for(int i=0;i<4;i++)
{
int nx=x+dir[i][0];
int ny=y+dir[i][1];
if(nx>=1&&ny>=1&&nx<=n&&ny<=m&&vis[nx][ny]==0&&maps[nx][ny]==1)
{
vis[nx][ny]=1;
cnt++;
dfs(nx,ny);
}
}
}
int main()
{
while(scanf("%d%d",&m,&n)!=EOF&&m&&n)
{
int x,y;
cnt=1;
memset(vis,0,sizeof(vis));
memset(maps,0,sizeof(maps));
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
cin>>ch;
if(ch=='@')
{
x=i;
y=j;
maps[i][j]=1;
}
if(ch=='.')
maps[i][j]=1;
if(ch=='#')
maps[i][j]=0;
}
vis[x][y]=1;
dfs(x,y);
cout<<cnt<<endl;
}
return 0;
}重建二叉树
给定一棵二叉树的前序遍历和中序遍历的结果,求其后序遍历。
时间限制:1000
内存限制:65536
输入
输入可能有多组,以EOF结束。 每组输入包含两个字符串,分别为树的前序遍历和中序遍历。每个字符串中只包含大写字母且互不重复。
输出
对于每组输入,用一行来输出它后序遍历结果。
样例输入
DBACEGF ABCDEFG BCAD CBAD
样例输出
ACBFGED CDAB
//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码!
#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至倒数第二个点是树的右子树节点。
*/快速堆猪(2023.9)
小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。
时间限制: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
//青少年考级竞赛题库(tiku.scratchor.com)搜集整理,感谢网友提供代码!
#include<iostream>
#include<string>
#include <cstring>
#include<cmath>
#include<stack>
#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;
}迷宫(2023.12)
一天Extense在森林里探险的时候不小心走入了一个迷宫,迷宫可以看成是由n * n的格点组成,每个格点只有2种状态,.和#,前者表示可以通行后者表示不能通行。同时当Extense处在某个格点时,他只能移动到东南西北(或者说上下左右)四个方向之一的相邻格点上,Extense想要从点A走到点B,问在不走出迷宫的情况下能不能办到。如果起点或者终点有一个不能通行(为#),则看成无法办到。
时间限制:3000
内存限制:65536
输入
第1行是测试数据的组数k,后面跟着k组输入。每组测试数据的第1行是一个正整数n (1 <= n <= 100),表示迷宫的规模是n * n的。接下来是一个n * n的矩阵,矩阵中的元素为.或者#。再接下来一行是4个整数ha, la, hb, lb,描述A处在第ha行, 第la列,B处在第hb行, 第lb列。注意到ha, la, hb, lb全部是从0开始计数的。
输出
k行,每行输出对应一个输入。能办到则输出“YES”,否则输出“NO”。
样例输入
2 3 .## ..# #.. 0 0 2 2 5 ..... ###.# ..#.. ###.. ...#. 0 0 4 0
样例输出
YES NO
// 参考答案1
#include <queue>
#include <stdio.h>
#include <string.h>
int m;
char c[100][100];
int xa, ya, xb, yb;
bool vis[100][100];
int dir[][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
struct node {
int x;
int y;
int step;
} q[10000];
void bfs(int xa, int ya, int xb, int yb) {
int head = 1, tail = 1;
memset(vis, 0, sizeof(vis));
q[tail].x = xa;
q[tail].y = ya;
q[tail].step = 0;
tail++;
vis[xa][ya] = 1;
int flag = 1;
while (head < tail) {
int x = q[head].x;
int y = q[head].y;
int step = q[head].step;
if (x == xb && y == yb) {
flag = 0;
printf("YES\n");
break;
}
for (int i = 0; i < 4; i++) {
int nx = x + dir[i][0];
int ny = y + dir[i][1];
if (nx >= 0 && nx < m && ny >= 0 && ny < m && c[nx][ny] == '.' &&
vis[nx][ny] == 0) {
vis[nx][ny] = 1;
q[tail].x = nx;
q[tail].y = ny;
q[tail].step = step + 1;
tail++;
}
}
head++;
}
if (flag == 1) {
printf("NO\n");
}
}
int main() {
int n;
scanf("%d", &n);
while (n--) {
scanf("%d", &m);
for (int i = 0; i < m; i++) {
scanf("%s", c[i]);
}
scanf("%d%d%d%d", &xa, &ya, &xb, &yb);
bfs(xa, ya, xb, yb);
}
return 0;
}// 参考答案1
#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 10;
int k, n, v[102][102];
char a[102][102];
int dx[4] = {-1, 0, 1, 0};
int dy[4] = {0, 1, 0, -1};
bool bfs(int x1, int y1, int x2, int y2) {
if (a[x1][y1] == '#' || a[x2][y2] == '#')
return false;
if (a[x1][y1] != '#' && x1 == x2 && y1 == y2)
return true;
queue<pair<int, int>> q;
pair<int, int> pa;
pa.first = x1;
pa.second = y1;
v[x1][y1] = 1;
q.push(pa);
while (!q.empty()) {
int x = q.front().first;
int y = q.front().second;
q.pop();
for (int i = 0; i < 4; i++) {
int xx = x + dx[i];
int yy = y + dy[i];
if (xx < 0 || xx >= n || yy < 0 || yy >= n)
continue;
if (a[xx][yy] == '.' && v[xx][yy] == 0) {
if (xx == x2 && yy == y2)
return true;
v[xx][yy] = 1;
pa.first = xx;
pa.second = yy;
q.push(pa);
}
}
}
return false;
}
int main() {
cin >> k;
int x1, y1, x2, y2;
while (k--) {
cin >> n;
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++)
cin >> a[i][j];
cin >> x1 >> y1 >> x2 >> y2;
memset(v, 0, sizeof(v));
if (bfs(x1, y1, x2, y2))
cout << "YES" << endl;
else
cout << "NO" << endl;
}
return 0;
}拯救公主(2023.12)
多灾多难的公主又被大魔王抓走啦!国王派遣了第一勇士阿福去拯救她。
身为超级厉害的术士,同时也是阿福的好伙伴,你决定祝他一臂之力。你为阿福提供了一张大魔王根据地的地图,上面标记了阿福和公主所在的位置,以及一些不能够踏入的禁区。你还贴心地为阿福制造了一些传送门,通过一个传送门可以瞬间转移到任意一个传送门,当然阿福也可以选择不通过传送门瞬移。传送门的位置也被标记在了地图上。此外,你还查探到公主所在的地方被设下了结界,需要集齐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);
}
}// 参考答案3
#include <bits/stdc++.h>
using namespace std;
struct Point {
int x, y, step; // 坐标 步长
bool germ[7], ench; // 找到的宝石 结界
} point, door;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
int k;
int main() {
cin >> k;
while (k--) {
// 准备工作
queue<Point> q;
int r, c, needk; // 边界 需要宝石种类
cin >> r >> c >> needk;
int door_c[15][2]{}, door_n = 0; // 传送门坐标 数量
char ma[205][205]{}; // 地图
bool walked[205][205][35]{}, finish = false;
// 标记路是否走过及取得的宝石种类 是否完成
for (int i = 0; i < r; i++) {
cin >> ma[i];
for (int j = 0; j < c; j++) {
if (ma[i][j] == 'S') { // 起点
memset(point.germ, false, sizeof(point.germ));
point.x = i;
point.y = j;
point.step = 0;
point.ench = true;
}
if (ma[i][j] == '$') { // 传送门
door_c[door_n][0] = i;
door_c[door_n][1] = j;
door_n++;
}
}
}
// 广搜
q.push(point);
while (!q.empty()) {
for (int i = 0; i < 4; i++) {
point = q.front();
point.step++;
point.x += dx[i];
point.y += dy[i];
if (point.x < 0 || point.x >= r || point.y < 0 || point.y >= c ||
(ma[point.x][point.y] == '#'))
continue;
if (ma[point.x][point.y] >= '0' &&
ma[point.x][point.y] <= '4') // 找到宝石
point.germ[ma[point.x][point.y] - '0'] = true;
int get_v = 0, s = 0;
for (int i = 0; i <= 4; i++) // 统计宝石
if (point.germ[i]) {
get_v += (int)pow(2, i);
s++;
}
if (walked[point.x][point.y][get_v])
continue; // 之前到达过
walked[point.x][point.y][get_v] = true; // 标记
if (s >= needk)
point.ench = false; // 结界消失
if (ma[point.x][point.y] == '$') { // 找到传送门
door = point;
for (int i = 0; i < door_n; i++) // 遍历所有的传送门
if ((door_c[i][0] != point.x) ||
(door_c[i][1] != point.y)) { // 可传送
door.x = door_c[i][0];
door.y = door_c[i][1];
q.push(door);
}
}
if (ma[point.x][point.y] == 'E' && !point.ench) { // 找到终点且无结界
cout << point.step << endl;
finish = true;
}
if (finish)
break;
q.push(point);
}
if (finish)
break;
q.pop();
}
if (!finish)
cout << "oop!" << endl;
}
return 0;
}二叉树的深度(2023.12)
给定一棵二叉树,求该二叉树的深度
二叉树深度定义:从根结点到叶结点依次经过的结点(含根、叶结点)形成树的一条路径,最长路径的节点个数为树的深度
时间限制:1000
内存限制:65535
输入
第一行是一个整数n,表示二叉树的结点个数。二叉树结点编号从1到n,根结点为1,n <= 10 接下来有n行,依次对应二叉树的n个节点。 每行有两个整数,分别表示该节点的左儿子和右儿子的节点编号。如果第一个(第二个)数为-1则表示没有左(右)儿子
输出
输出一个整型数,表示树的深度
样例输入
3 2 3 -1 -1 -1 -1
样例输出
2
#include<bits/stdc++.h>
using namespace std;
const int MAXN=2e5+7;
struct node{
int left,right;
}t[MAXN];
int n;
void build(){
for(int i=1;i<=n;i++){
cin>>t[i].left>>t[i].right;
}
}
#define rep1(i,n) for(int i=1;i<=n;i++)
inline int dfs(int x){
if(x==-1)return 0;
return max(dfs(t[x].left),dfs(t[x].right))+1;
}
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
cin>>n;
build();
cout<<dfs(1);
return 0;
}//题解2
#include <algorithm>
#include <iostream>
using namespace std;
int meng[102][30]; /*a[i][0]表示节点i的左孩子节点编号,
a[i][1]表示节点i的右孩子节点编号,a[i][2]表示i节点的父节点编号。*/
int a, b;
int dfs(int root) {
if (meng[root][0] == -1 && meng[root][1] == -1)
return 1;
else {
int left = 0, right = 0;
if (meng[root][0] >= 0)
left = dfs(meng[root][0]);
/*如果该节点满足不为-1证明它有父节点,
递归回去去证明它的父节点上面是否也有父节点*/
if (meng[root][1] >= 0) {
right = dfs(meng[root][1]);
}
return max(right, left) + 1;
}
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a >> b;
// 二维是为了更好的判断左孩子还是右孩子,父节点
meng[i][0] = a; // i的左孩子是a
meng[i][1] = b; // i的右孩子是b
}
cout << dfs(1) << endl;
return 0;
}//题解3
#include <bits/stdc++.h>
using namespace std;
struct node {
int left;
int right;
} tree[25];
int depth(int root) {
if (root == -1)
return 0;
int a = depth(tree[root].left);
int b = depth(tree[root].right);
return max(a, b) + 1;
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> tree[i].left >> tree[i].right;
}
cout << depth(1);
return 0;
}Sequence(2023.12)
给定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
// 参考答案1
#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;
}// 参考答案2
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
int m, n;
vector<int> a[105];
struct Plan {
pii ptr;
bool last; // 记录本方案是否是由ptr2++得到的
int sum;
Plan() {}
Plan(int i, int j, pii _ptr, bool _last) {
ptr = _ptr;
last = _last;
sum = a[i][ptr.first] + a[j][ptr.second];
}
bool operator<(const Plan &oth) const { return sum > oth.sum; }
} init;
priority_queue<Plan> Q;
int main() {
int T;
cin >> T;
while (T--) {
scanf("%d%d", &m, &n);
for (int i = 1; i <= m; i++) {
a[i].clear();
for (int j = 1, x; j <= n; j++) {
scanf("%d", &x);
a[i].push_back(x);
}
sort(a[i].begin(), a[i].end());
}
int i = 1;
for (int j = 2; j <= m; j++, i ^= 1) {
init = Plan(i, j, make_pair(0, 0), 0);
while (!Q.empty())
Q.pop();
Q.push(init);
a[i ^ 1].clear();
while (!Q.empty()) {
Plan now = Q.top();
Q.pop();
a[i ^ 1].push_back(now.sum);
if (a[i ^ 1].size() >= n)
break;
if (!now.last && now.ptr.first < n - 1)
Q.push(Plan(i, j, make_pair(now.ptr.first + 1, now.ptr.second), 0));
if (now.ptr.second < n - 1)
Q.push(Plan(i, j, make_pair(now.ptr.first, now.ptr.second + 1), 1));
}
}
for (int k = 0; k < a[i].size(); k++)
printf("%d ", a[i][k]);
printf("\n");
}
}红色警报
战争中保持各个城市间的连通性非常重要。本题要求你编写一个报警程序,当失去一个城市导致国家被分裂为多个无法连通的区域时,就发出红色警报。注意:若该国本来就不完全连通,是分裂的k个区域,而失去一个城市并不改变其他城市之间的连通性,则不要发出警报。
时间限制:5000
内存限制:65536
输入
输入在第一行给出两个整数 N(0 < N <=500)和 M(<=5000),分别为城市个数(于是默认城市从 0 到 N-1 编号)和连接两城市的通路条数。随后 M 行,每行给出一条通路所连接的两个城市的编号,其间以 1 个空格分隔。在城市信息之后给出被攻占的信息,即一个正整数 K 和随后的 K 个被攻占的城市的编号。 注意:输入保证给出的被攻占的城市编号都是合法的且无重复,但并不保证给出的通路没有重复。
输出
对每个被攻占的城市,如果它会改变整个国家的连通性,则输出“Red Alert: City k is lost!”,其中k是该城市的编号;否则只输出“City k is lost.”即可。如果该国失去了最后一个城市,则增加一行输出“Game Over.”。
样例输入
5 4 0 1 1 3 3 0 0 4 5 1 2 0 4 3
样例输出
City 1 is lost. City 2 is lost. Red Alert: City 0 is lost! City 4 is lost. City 3 is lost.
//参考代码1
#include<cstdio>
#include<cstring>
using namespace std;
int pre[505];
bool del[505];
struct node{
int x,y;
}p[5005];
int find(int x){
return x==pre[x]?x:pre[x]=find(pre[x]);
}
void merge(int x,int y){
int fx = find(x);
int fy = find(y);
if(fx!=fy)
pre[fx] = fy;
}
int main(){
int n,m,k,x;
scanf("%d%d",&n,&m);
for(int i=0;i<n;i++)
pre[i]=i;
for(int i=1;i<=m;i++){
scanf("%d%d",&p[i].x,&p[i].y);
merge(p[i].x,p[i].y);
}
int ans=0;
for(int i=0;i<n;i++){
if(i==pre[i]) ans++;
}
scanf("%d",&k);
while(k--){
scanf("%d",&x);
del[x]=true;
for(int i=0;i<n;i++)
pre[i]=i;
for(int i=1;i<=m;i++){
if(!del[p[i].x]&&!del[p[i].y])
merge(p[i].x,p[i].y);
}
int cnt=0;
for(int i=0;i<n;i++)
{
if(pre[i]==i&&!del[i])
cnt++;
}
if(cnt>ans)
printf("Red Alert: City %d is lost!\n",x);
else
printf("City %d is lost.\n",x);
ans=cnt;
if(ans==0)
printf("Game Over.\n");
}
return 0;
}//参考代码2
#include<bits/stdc++.h>
using namespace std;
#define N 510
#define M 5010
int n ,m ,k ,vis[N] ,p[N];
struct node {
int x;
int y;
}g[M];
int find(int x) {
if (x != p[x]) p[x] = find(p[x]);
return p[x];
}
int main() {
cin >> n >> m;
for (int i = 0; i < n; i++)
p[i] = i;
for (int i = 0; i < m; i++) {
cin >> g[i].x >> g[i].y;
if (find(g[i].x) != find(g[i].y))
p[find(g[i].x)] = find(g[i].y);
}
int cnt1 = 0;
for (int i = 0; i < n; i++) {
if (p[i] == i)
cnt1 ++;
}
cin >> k;
for (int j = 0; j < k; j++) {
int x ,cnt2 = 0;
cin >> x;
vis[x] = 1;
for (int i =0 ; i < n; i++)
p[i] = i;
for (int i = 0; i < m; i++) {
if (vis[g[i].x] == 1 ||vis[g[i].y] == 1)
continue;
if (find(g[i].x) != find(g[i].y))
p[find(g[i].x)] = find(g[i].y);
}
for (int i = 0; i < n; i++) {
if (p[i] == i)
cnt2++;
}
if (cnt2 - cnt1 > 1)
printf ("Red Alert: City %d is lost!\n" ,x);
else
printf ("City %d is lost.\n" ,x);
cnt1 = cnt2;
}
if (k >= n) cout << "Game Over.\n";
return 0;
}到底爱不爱我
古代少女有了心上人时,会悄悄折一条树枝,揪那枝上的叶子,揪一片叶子念一句“爱我”,再揪一片念一句“不爱我”…… 这样揪落最后一片叶子的时候,看看是停在“爱”还是“不爱”。
但聪明的慧娘一眼洞穿,只要数一下叶子有多少片,根据这个数字的奇偶性判断是以“爱”开始还是以“不爱”开始,就总是可以最后落在“爱”上。这个游戏顿时就变得无趣了 —— 真的是文科生制造浪漫,理科生杀死浪漫。
于是有着工科生大脑的慧娘打算另外制作一个更有趣的浪漫游戏。她用不同植物的枝条做成了三种“情枝”:
- “专情枝”:是一根有两个分岔的树枝,只有当两个分岔上连接的枝条传过来的情话都是“爱”的时候,这根枝条的根部才传出“爱”;否则树枝根部传出的是“不爱”。
- “博爱枝”:也是一根有两个分岔的树枝,只有当两个分岔上连接的枝条传过来的情话都是“不爱”的时候,这根枝条的根部才传出“不爱”;否则树枝根部传出的都是“爱”。
- “情变枝”:是没有分岔的一根直枝,如果一端接到“爱”,另一端必须传出“不爱”;反之如果一端接到“不爱”,另一端则会传出“爱”。
慧娘将这些树枝摆放在院子里,布了一个“情阵”,从某一枝的根部开始,扩散开去,令它们根枝相连。然后她在末梢的枝杈旁随意写下“爱”或“不爱”。现在请你写个程序帮她算出来,在初始一枝的根部,她能得到“爱”还是“不爱”?
时间限制:10000
内存限制:65536
输入
输入在第一行中给出正整数 N(≤ 30),是慧娘制作的情枝数量。这里假设她将所有的情枝从 1 到 N 做好了编号。随后 N 行,第 i 行给出第 i 枝的描述,格式为 类型 左分枝连接的编号 右分枝连接的编号 其中 `类型` 为 1 代表专情、2 代表博爱、3 代表情变。当然如果是情变枝,则后面跟的是其唯一末端连接的情枝编号,并没有两个分枝的信息。如果一个分枝是末梢,并没有连接其它枝条,则对应编号为 0。 接下来一行中给出正整数 K(≤ 30),是慧娘询问的次数。以下 K 行,每行给出一个由 0 和 1 组成的字符串,其中 0 表示“不爱”,1 表示“爱”—— 这是慧娘从左到右在每个枝杈末梢处写下的。
输出
对慧娘的每个询问,如果她在初始一枝的根部能得到“爱”,就输出 `Ai`;否则输出 `BuAi`。
样例输入
6 2 6 4 1 0 0 3 1 2 0 0 3 0 1 5 2 5 11111 00000 11100 10011 01100
样例输出
BuAi Ai Ai BuAi BuAi
提示
样例说明: 样例对应的情阵以及慧娘第 3 问的情势如图所示,其中完整的心对应 1,裂开的心对应 0。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0)
int t,root,i,tree[44][3],p[44],f[44],n;
string s;
bool dfs(int u){
int x,y;
if(p[u]!=3){
if(tree[u][1])x=dfs(tree[u][1]);
else x=s[i++]-'0';
if(tree[u][2])y=dfs(tree[u][2]);
else y=s[i++]-'0';
if(p[u]==1)return x&&y;
return x||y;
}
else {
if(tree[u][1])return !dfs(tree[u][1]);
else return !(s[i++]-'0');
}
}
signed main(){
ios;
cin>>n;
for(int i=1,x,y;i<=n;i++){
cin>>p[i];
if(p[i]==1||p[i]==2){
cin>>x>>y;
tree[i][1]=x;
tree[i][2]=y;
f[x]=f[y]=1;
}
else {
cin>>x;
tree[i][1]=x;
f[x]=1;
}
}
for(int i=1;i<=n;i++){
if(f[i]==0){
root=i;
break;
}
}
cin>>t;
while(t--){
cin>>s;
i=0;
if(dfs(root))cout<<"Ai\n";
else cout<<"BuAi\n";
}
return 0;
}兰州拉面派餐系统
兰州拉面是著名美食,其煮面很有讲究,不同种类的面需要煮不同的时长。拉面馆的煮面师傅的规则很简单,只要手头有煮面篮子是空闲的,就把下一份客单指定的面放到空闲篮子里煮;如果空闲的篮子不止一个,那么先放到其中编号最小的篮子里煮;如果没有篮子是空闲的,就等待。一个篮子里的面煮够了时间,师傅要准时捞出来放到该客单对应的碗里,招呼服务员端给客人;如果有多个篮子里的面同时到了捞取时间,师傅会同时捞起,但要本着先到先得的原则,按下单顺序招呼送餐。
在生意火爆的拉面馆里,煮面师傅需要很强的记忆力和计时能力,才能面对源源不断的客单,同时照顾一大堆煮面篮子而不出错。如果面的品种不太多,篮子也不太多,那一位拉面师傅的大脑还是能应对的。但如果我们有上千种面、上万只煮面篮、数十万客单呢…… 这就需要请你帮忙,写个派餐系统来完成这个任务了。
时间限制:7000
内存限制:65536
输入
输入在第一行中给出 3 个正整数:N(≤ 103)为面的种类数;M(≤ 104)为煮面篮子的个数;L(≤ 105)为客单总数。于是我们假设面的种类从 1 到 N 编号、篮子从 1 到 M 编号、客单从 1 到 L 编号。 第二行给出 N 个不超过 10 的正整数,第 i 个数字对应第 i 种面需要煮的时间长度(分钟)。 第三行给出 L 个正整数,第 i 个数字对应第 i 份客单所点的面种 —— 这里我们将情况简化为一份客单只要一种面,并且只要一碗,所以只要给出面的种类即可。 一行中数字间以空格分隔。 因为面馆的生意太火爆,我们可以认为所有的客单都是在开门前就预约好的,并且是按预约的顺序递增编号的。此外,与煮面的时长相比,下面、捞面和送餐的时长是可以忽略不计的。
输出
首先按照送单顺序在一行中输出所有客单的编号和送餐时间,格式为 `编号:时间`。 随后在下一行按照编号递增序输出每只篮子煮了多少碗面。 一行的输出之间以 1 个空格分隔,行首尾不得有多余空格。
样例输入
3 5 10 3 5 8 2 1 3 3 1 1 2 1 3 2
样例输出
2:3 5:3 1:5 6:6 3:8 4:8 7:8 8:8 10:13 9:14 3 3 1 1 2
#include <bits/stdc++.h>
using namespace std;
const int N = 100010;
typedef pair<int,int> PII;
int n,m,l;
// t代表每种面需要的时间,c代表每个顾客需要的面的种类,cnt代表每个篮子被用的次数
int t[N], c[N], cnt[N];
// 小跟堆升序,维护篮子所用的时间和篮子编号
priority_queue<PII,vector<PII>,greater<PII>> heap;
// 维护时间,顾客编号,可以实现时间由小到大排序
vector<PII> ans;
//对时间相同的按编号从小到大排序
bool cmp(PII a,PII b)
{
if(a.first!=b.first) return a.first<b.first;
return a.second<b.second;
}
int main()
{
cin>>n>>m>>l;
for(int i=1;i<=n;i++) cin>>t[i]; // 每种面需要的时间
for(int i=1;i<=l;i++) cin>>c[i]; // 每个顾客需要的面的种类
for(int i=1;i<=m;i++) heap.push({0,i}); // 开始时间都是0,然后对篮子编号
for(int i=1;i<=l;i++)
{
auto u=heap.top(); // 取当前时间被用最短的篮子
heap.pop();
int id=u.second, time=u.first;
cnt[id]++;
ans.push_back({time+t[c[i]], i});
heap.push({time+t[c[i]],id});
}
sort(ans.begin(),ans.end(),cmp);
for(int i=0;i<l;i++)
{
if(i!=l-1) cout<<ans[i].second<<":"<<ans[i].first<<" ";
else cout<<ans[i].second<<":"<<ans[i].first<<endl;
}
for(int i=1;i<=m;i++)
{
if(i!=m) cout<<cnt[i]<<" ";
else cout<<cnt[i]<<endl;
}
return 0;
}走出迷宫(2024-3-7级)
当你站在一个迷宫里的时候,往往会被错综复杂的道路弄得失去方向感,如果你能得到迷宫地图,事情就会变得非常简单。
假设你已经得到了一个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;
}有多少种二叉树(2024-3-7级)
输入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;
}迷宫问题(2024-3-7级)
定义一个二维数组:
int maze[5][5] = {
0, 1, 0, 0, 0,
0, 1, 0, 1, 0,
0, 0, 0, 0, 0,
0, 1, 1, 1, 0,
0, 0, 0, 1, 0,
};
它表示一个迷宫, 其中的 1 表示墙壁, 0 表示可以走的路, 只能横着走或竖着走, 不能斜着走, 要求编程序找出从左上角到右下角的最短路线。
时间限制: 1000
内存限制: 65536
输入
一个 5 × 5 的二维数组, 表示一个迷宫。 数据保证有唯一解。
输出
左上角到右下角的最短路径, 格式如样例所示。
样例输入
0 1 0 0 0 0 1 0 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 1 0
样例输出
(0, 0) (1, 0) (2, 0) (2, 1) (2, 2) (2, 3) (2, 4) (3, 4) (4, 4)
/*#include <iostream>*/
#include <bits/stdc++.h>
using namespace std;
const int idata = 50 + 5;
int maps[idata][idata];
bool judge[idata][idata];
int change[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
int nx, ny;
int x[idata], y[idata];
int show[30];
bool flag;
void print(int tail) {
if (show[tail])
print(show[tail]);
cout << "(" << x[tail] << ", " << y[tail] << ")" << endl;
}
int main() {
int head, tail;
register int i, j;
for (i = 0; i < 5; i++) {
for (j = 0; j < 5; j++) {
cin >> maps[i][j];
if (maps[i][j] == 1)
judge[i][j] = 1;
}
}
head = 0;
tail = 1;
judge[0][0] = 1;
show[tail] = head;
while (tail > head) {
head++;
for (i = 0; i < 4; i++) {
nx = x[head] + change[i][0];
ny = y[head] + change[i][1];
if (nx >= 0 && nx < 5 && ny >= 0 && ny < 5 && !judge[nx][ny]) {
tail++;
x[tail] = nx;
y[tail] = ny;
judge[nx][ny] = 1;
show[tail] = head;
if (nx == 4 && ny == 4) {
flag = 1;
print(tail);
break;
}
}
}
if (flag)
break;
}
return 0;
}快速堆猪(2024-3-7级)
小明有很多猪,他喜欢玩叠猪游戏,就是将猪一头头叠起来。猪叠上去后,还可以把顶上的猪拿下来。小明知道每头猪的重量,而且他还随时想知道叠在那里的猪最轻的是多少斤。
时间限制: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;
}二叉树遍历
题目描述
有一棵二叉树,结点数量不超过 26 个,树上的每个结点都有一个大写字母。
给定这棵二叉树的中序遍历及后序遍历,请输出它的前序遍历。
输入格式
第一行:一个字符串,表示二叉树的中序遍历;
第二行:一个字符串,表示二叉树的后序遍历。
输出格式
单独一行:一个字符串,表示二叉树的前序遍历。
输入样例
DBEAC
DEBCA
输出样例
ABDEC
限制
时间限制:1000ms
内存限制:256MiB
#include <iostream>
#include <string>
using namespace std;
// 中序in, 后序post, 输出前序
void build(string in, string post) {
if (in.empty()) return;
// 后序最后一个是根
char root = post.back();
cout << root;
int pos = in.find(root);
// 递归左右
build(in.substr(0, pos), post.substr(0, pos));
build(in.substr(pos+1), post.substr(pos, in.size()-pos-1));
}
int main() {
string in, post;
cin >> in >> post;
build(in, post);
return 0;
}平衡运输
题目描述
远古遗迹中发掘出了 n 件魔力核心,第 i 件核心蕴含的能量为 ki。
为了安全运输,需要将这些核心分配到两个不同的能量舱(记为舱 A 和舱 B)中。
每件核心必须整个放入一个舱,不可拆分。
分配完成后,设舱 A 的总能量为 sa,舱 B 的总能量为 sb。
为了平衡运输风险,希望两个舱中总能量较大的一方尽可能小,即最小化 max(sa,sb)。
请你计算这个最小的最大值。
输入格式
第一行,一个整数 n。
第二行,n 个整数 k1,k2,…,kn。
输出格式
输出一个整数,表示 max(sa,sb) 的最小可能值。
输入样例#1
5 2 3 5 10 12
输出样例#1
17
输入样例#2
6 22 25 26 45 22 31
输出样例#2
89
说明提示
2≤n≤20
1≤ki≤108
限制
时间限制:1000ms
内存限制:256MiB
#include<iostream>
int N;
int A[20];
int S = 0;
int solve(int i, int sum)
{
if (i == N)
{
return std::max(sum, S - sum);
}
else
{
auto pick = solve(i + 1, sum + A[i]);
auto drop = solve(i + 1, sum);
return std::min(pick, drop);
}
}
int main()
{
std::cin >> N;
for (int i = 0; i < N; ++i) {
std::cin >> A[i];
S += A[i];
}
std::cout << solve(0, 0) << "\n";
}