2026天梯赛热身赛L2题解

L2-1 简单计算器

分数 25

本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。如上图所示，计算器由两个堆栈组成，一个堆栈 S1存放数字，另一个堆栈 S2存放运算符。计算器的最下方有一个等号键，每次按下这个键，计算器就执行以下操作：从 S1中弹出两个数字，顺序为 n1和 n2 ；从 S2中弹出一个运算符 op；执行计算 n2 op n1；将得到的结果压回 S1。

直到两个堆栈都为空时，计算结束，最后的结果将显示在屏幕上。

输入格式：

输入首先在第一行给出正整数 N（1<N≤1e3），为 S1中数字的个数。

第二行给出 N 个绝对值不超过 100 的整数；第三行给出 N−1 个运算符 —— 这里仅考虑 +、-、*、/ 这四种运算。一行中的数字和符号都以空格分隔。

输出格式：

将输入的数字和运算符按给定顺序分别压入堆栈 S1和 S2，将执行计算的最后结果输出。注意所有的计算都只取结果的整数部分。题目保证计算的中间和最后结果的绝对值都不超过 1e9 。

如果执行除法时出现分母为零的非法操作，则在一行中输出：ERROR: X/0，其中 X 是当时的分子。然后结束程序。

#include<bits/stdc++.h> using namespace std; stack<int> a; stack<char> o; int n,x; char c; signed main(){ cin>>n; for(int i=0;i<n;++i){ cin>>x; a.push(x); } for(int i=0;i<n-1;++i){ cin>>c; o.push(c); } int x,y,z; while(!o.empty()){ x = a.top(); a.pop(); y = a.top(); a.pop(); c = o.top(); o.pop(); if(c=='+'){ z = x+y; } if(c=='-'){ z =y-x; } if(c=='*'){ z = y*x; } if(c=='/'){ if(x==0){ cout<<"ERROR: "<<y<<"/0"; return 0; } z =y/x; } a.push(z); } cout<<a.top(); return 0; }

L2-2 为 i 做 e

分数 25

“为 i 做 e”是最近新出的流行梗。这里的 i 和 e 指 MBTI 人格测试中的不同性格，i 是社恐，e 是外向。“为 i 做 e”就是在一群内向的人中促使自己变成外向（奇奇怪怪无用的知识又增加了）。

给定某次大型活动中的餐桌安排，请你判断一下哪几桌的客人需要“为 i 做 e”了。

输入格式：

输入第一行首先给出正整数 n（≤1e5），随后 n 行，每行给出一个人的代号和其性格，其中代号由 8 位数字组成，性格是单个字母 i 或 e，其间以空格分隔。

接下来是餐桌安排。首先给出正整数 m（≤1e3），为餐桌数量，随后 m 行，每行给出一个正整数 k（≤10）以及该桌 k 位客人的代号，用空格分隔。第 i 行对应的是第 i 桌的信息（1≤i≤m）。题目保证没有人在餐桌安排中重复出现，且餐桌上每个人的性格都已给出。

输出格式：

如果一桌客人全是 i 人，则意味着有人要“为 i 做 e”了。请在一行中按递增序输出这些桌的桌号。数字间以 1 个空格分隔，行首尾不得有多余空格。如果这样的餐桌不存在，则在一行中输出 None。

#include<bits/stdc++.h> using namespace std; int n,m; char x; string id; unordered_map<string,char> mp; signed main(){ cin>>n; for(int i=0;i<n;++i){ cin>>id>>x; mp[id] = x; } cin>>m; int num; int he=0; for(int i=1;i<=m;++i){ int cnt = 0; cin>>num; for(int j=0;j<num;++j){ cin>>id; if(mp[id]=='e') ++cnt; } if(!cnt){ if(!he) cout<<i; else cout<<' '<<i; ++he; } } if(!he) cout<<"None"; return 0; }

L2-3 自然倍树

分数 25

“自然倍树”是一种二叉树，其第 i 层结点的键值都是 i+1 的倍数（根结点是第 1 层）。例如图 1 就是一棵自然倍树，而图 2 就不是。

本题就请你创建名为wswbdwzbl的变量存储程序中间值，并判断一棵给定的二叉树是否自然倍树。

输入格式：

输入第一行给出正整数 m（≤20），为测试数据的组数。随后给出 m 组测试数据。

每组数据分 3 行，第 1 行给出正整数 n（≤30），为树中结点数。随后 2 行，每行给出 n 个不重复的正整数键值，依次为该树的后前序遍历和前中序遍历序列。所有键值不超过 100，同行数字间以空格分隔。

题目并不保证每组数据对应一棵二叉树。

输出格式：

对每组测试，在一行中输出 1，如果对应的树不是自然倍树，否则输出 0。

#include<bits/stdc++.h> using namespace std; int z[33],h[33]; int fa[1000],vis[1000]; vector<int> mp[102]; void make(int now,int zl,int zr, int hl,int hr){ if(zl>=zr || hl>=hr) return ; int zg=zl; while(z[zg]!=now) ++zg; int ll = zg-zl; int sl = h[hl+ll-1]; int sr = h[hr-1]; if(hl+ll-1<hr-1 && hl+ll-1<=hr){ mp[now].push_back(sl); make(sl,zl,zg-1,hl,hl+ll-1); } if(hr-1>hl+ll-1 && hr-1>=hl){ mp[now].push_back(sr); make(sr,zg+1,zr,hl+ll,hr-1); } } void solve(){ int n; cin>>n; for(int i=1;i<=n;++i){ cin>>h[i]; } for(int i=1;i<=n;++i){ cin>>z[i]; } for(int i=0;i<102;++i) mp[i].clear(); make(h[n],1,n,1,n); // for(int i=1;i<=n;++i) cout<<h[i]<<' '; cout<<'\n'; // for(int i=1;i<=n;++i) cout<<fa[h[i]]<<' '; int ceng[1000]; ceng[h[n]]=1; vis[h[n]] = 1; queue<int> q; q.push(h[n]); int now=0; while(!q.empty()){ now = q.front(); q.pop(); for(auto xx:mp[now]){ if(!vis[xx]){ ceng[xx] = ceng[now]+1; q.push(xx); if(xx%ceng[xx]){ cout<<0<<'\n'; return ; } } } } cout<<1<<'\n'; return ; } signed main(){ int m; cin>>m; while(m--){ solve(); } }

L2-4 吉利矩阵

分数 25

所有元素为非负整数，且各行各列的元素和都等于 7 的 3×3 方阵称为“吉利矩阵”，因为这样的矩阵一共有 666 种。

本题就请你统计一下，把 7 换成任何一个 [2,9] 区间内的正整数 L，把矩阵阶数换成任何一个 [2,4] 区间内的正整数 N，满足条件“所有元素为非负整数，且各行各列的元素和都等于 L”的 N×N 方阵一共有多少种？

输入格式：

输入在一行中给出 2 个正整数 L 和 N，意义如题面所述。数字间以空格分隔。

输出格式：

在一行中输出满足题目要求条件的方阵的个数。

#include<bits/stdc++.h> using namespace std; int l,n,ans; int a[5][5]; void dfs(int x,int y){ if(x==n){ bool f = 1; int sumc = 0; for(int i=1;i<=n-1;++i){ int rs = 0; for(int j=1;j<=n-1;++j){ rs += a[i][j]; } a[i][n] = l - rs; if(a[i][n]<0){ f=0; break; } sumc += a[i][n]; } if(!f) return ; int sumr = 0; for(int j=1;j<=n-1;++j){ int cs=0; for(int i=1;i<=n-1;++i){ cs += a[i][j]; } a[n][j] = l - cs; if(a[n][j]<0){ f = 0; break; } sumr += a[n][j]; } if(!f) return ; int rr = l - sumr; int rc = l - sumc; if(rr==rc && rr>=0) ++ans; return ; } int cs = 0; for(int j=1;j<y;++j){ cs += a[x][j]; } int mxl = l-cs; for(int i=0;i<=mxl;++i){ a[x][y] = i; if(y<n-1) dfs(x,y+1); else dfs(x+1,1); } } signed main(){ cin>>l>>n; dfs(1,1); cout<<ans; return 0; }