首页 › 题库 › C/C++编程考级 › 1 栈与队列

C/C++编程六级 题库

共 51 道题 ,第 3 / 3 页 · 按题型筛选,点「查看答案」核对解析
章节 1 栈与队列 清除
41 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

宝可梦

image7.png

image8.png

答案与解析
参考答案
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long ll;
const ll INF = 1e18;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    ll dp0 = 0, dp1 = -INF;
    for (int i = 0; i < n; ++i)
    {
        ll x;
        cin >> x;
        ll nd0 = dp0, nd1 = dp1; // 不放走:原样继承
        // 选择击败进行状态更新
        nd0 = max(nd0, dp1 + 2 * x);
        nd1 = max(nd1, dp0 + x);
        dp0 = nd0; dp1 = nd1;
    }
    cout << max(dp0, dp1) << '\n';
    return 0;
}
题目详情
42 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

L形硬币

image9.png

image10.png

答案与解析
参考答案
#include <iostream>
#include <string>
using namespace std;
const int MAXN = 2005;
int row[MAXN], col[MAXN];
string grid[MAXN];
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i = 0; i < n; ++i)
    {
        cin >> grid[i];
        for(int j = 0; j < n; ++j)
        {
            if(grid[i][j] == 'o')
            {
                row[i]++;
                col[j]++;
            }
        }
    }
    long long ans = 0; // 防止int溢出,2000*2000量级乘积会超int范围
    for(int i = 0; i < n; ++i)
    {
        for(int j = 0; j < n; ++j)
        {
            if(grid[i][j] == 'o')
                ans += 1LL * (row[i] - 1) * (col[j] - 1);
        }
    }
    cout << ans << '\n';
    return 0;
}
题目详情
43 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

能量槽

题目描述

在实验室中,有一个“能量槽”和 n 个待处理的能量块。第i个能量块的能级为ai,其蕴含的能量为2ai。

实验需按顺序执行n次操作,第i次操作流程如下:

(1)将第i个能量块放入堆槽的顶部。

(2)随后启动“自动融合程序”,重复执行以下检查,直到无法继续:

若槽中能量块数量≤1,停止融合。

若顶部第 1 个与第 2 个能量块的能级不同,停止融合。

若顶部两个能量块能级相同,则将它们从槽中移除,并向顶部放入一个能级为原能级 + 1的新能量块,其能量为两者之和。

再次回到检查步骤,继续尝试融合。

求 n 次操作全部完成后,槽中剩余的能量块总数。

输入格式

第一行,一个整数n。

接下来 n 行,每行一个整数 ai。

输出格式

输出 n 次操作结束后槽中剩余能量块的数量。

输入样例#1

7
2
1
1
3
5
3
3

输出样例#1

3

输入样例#2

5
0
0
0
1
2

输出样例#2

4

说明提示:

1≤n≤2×10^5,0≤ai≤10^9,输入均为整数。

限制:

时间限制:1000ms,内存限制:256MiB

答案与解析
参考答案
#include <iostream>
#include <stack>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	
	int n;
	cin >> n;
	stack<long long> st;  // 存储能级,用 long long 防止溢出
	
	while (n--) {
		long long x;
		cin >> x;
		st.push(x);
		
		// 循环合并栈顶两个相同的元素
		while (st.size() >= 2) {
			// 取出栈顶两个
			long long a = st.top(); st.pop();
			long long b = st.top(); st.pop();
			
			if (a == b) {
				// 相同则合并成 +1 级,重新压入
				st.push(a + 1);
			} else {
				// 不同则放回,停止合并
				st.push(b);
				st.push(a);
				break;
			}
		}
	}
	
	// 最终栈大小就是答案
	cout << st.size() << endl;
	return 0;
}
题目详情
44 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

博弈游戏

题目描述

两位玩家进行回合制博弈游戏,游戏总计进行 n 轮。每一轮,双方都要从1、2、3三个数字中选择一个出招,胜负规则如下:

(1)若双方选择的数字相同,本轮为平局;

(2)若数字不同,胜负遵循固定克制关系:1克制2,2克制3,3克制1,被克制的一方本轮落败,克制的一方本轮获胜。

其中一位玩家提前掌握了对手的完整出招顺序——对手在第 i 轮选择的数字为 si,所有 si 组成一个长度为 n 的序列。

该玩家需要规划自己每一轮的出招,满足以下全部条件:

(1)任何一轮都不能落败(即每一轮只能获胜或平局);

(2)不能连续两轮选择相同的数字出招;

(3)在满足前两个条件的前提下,尽可能多地获得轮次的胜利。

请计算该玩家最多能赢得的轮次数量。

输入格式

第一行:一个整数表示n。

第二行:n 个整数,表示s1、s2、……、sn,每个数为1、2或3。

输出格式

输出一个整数,表示玩家最多能赢得的游戏轮数。

输入样例#1

6
3 1 2 2 1 2

输出样例#1

5

输入样例#2

24
2 3 1 3 2 1 1 1 1 1 3 3 1 3 1 3 2 2 1 2 3 1 2 2

输出样例#2

18

说明提示:

1≤n≤200,000,si∈{1,2,3}

限制:

时间限制:1000ms,内存限制:256MiB

答案与解析
参考答案
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<int> s(n);
    for (int i = 0; i < n; ++i) {
        cin >> s[i];
    }

    int ans = 0;
    int last = 0; // 上一轮出的数

    for (int x : s) {
        int win;    // 能赢的数
        int draw = x; // 能平的数

        // 计算克制关系:1克2,2克3,3克1
        if (x == 1) win = 3;
        else if (x == 2) win = 1;
        else win = 2;

        // 优先选赢的,只要不和上一轮重复
        if (win != last) {
            ans++;
            last = win;
        }
        // 不能赢 → 只能平
        else {
            last = draw;
        }
    }

    cout << ans << endl;
    return 0;
}
题目详情
45 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

简单计算器

本题要求你为初学数据结构的小伙伴设计一款简单的利用堆栈执行的计算器。计算器由两个堆栈组成,一个堆栈 S1 存放数字,另一个堆栈 S2 存放运算符。

计算器的最下方有一个等号键,每次按下这个键,计算器就执行以下操作:

(1)从 S1 中弹出两个数字,顺序为 n1 和 n2;

(2)从 S2 中弹出一个运算符 op;

(3)执行计算 n2 op n1;

(4)将得到的结果压回 S1。

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

时间限制:7000,内存限制:65536

输入

输入首先在第一行给出正整数 N(1 < N ≤ 10^3),为 S1 中数字的个数。 

第二行给出 N 个绝对值不超过 100 的整数;

第三行给出 N-1 个运算符 —— 这里仅考虑 +、-、*、/ 这四种运算。一行中的数字和符号都以空格分隔。

输出

将输入的数字和运算符按给定顺序分别压入堆栈 S1 和 S2,将执行计算的最后结果输出。

注意所有的计算都只取结果的整数部分。题目保证计算的中间和最后结果的绝对值都不超过 109。

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

样例输入1

5
40 5 8 3 2
/ * - +

样例输出1

2

样例输入2

5
2 5 8 4 4
* / - +

样例输出2

ERROR: 5/0
答案与解析
参考答案
//该答案由AI生成
#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
    int n;
    cin >> n;
    
    stack<int> nums;
    for (int i = 0; i < n; i++) {
        int num;
        cin >> num;
        nums.push(num);
    }
    
    stack<char> ops;
    for (int i = 0; i < n - 1; i++) {
        char op;
        cin >> op;
        ops.push(op);
    }
    
    while (!ops.empty()) {
        int n1 = nums.top();
        nums.pop();
        int n2 = nums.top();
        nums.pop();
        char op = ops.top();
        ops.pop();
        
        int result;
        if (op == '+') {
            result = n2 + n1;
        } else if (op == '-') {
            result = n2 - n1;
        } else if (op == '*') {
            result = n2 * n1;
        } else if (op == '/') {
            if (n1 == 0) {
                cout << "ERROR: " << n2 << "/0" << endl;
                return 0;
            }
            result = n2 / n1;  // 整数除法
        }
        
        nums.push(result);
    }
    
    cout << nums.top() << endl;
    
    return 0;
}
题目详情
46 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

两头进一头出

某队列允许在其两端进行入队操作,但仅允许在一端进行出队操作。现给定入队的序列,请你判断一系列出队序列是否可能。

例如按 1、2、3、4、5 的顺序入队,则 1、3、2、5、4 这样的出队序列是可以得到的,但 5、1、3、2、4 就是不可能得到的。

时间限制:4000,内存限制:65536

输入

输入首先在一行中给出两个正整数 N 和 K(≤ 10),分别是入队元素的个数和待查验的序列个数。

随后一行给出 N 个两两不同的整数组成的入队序列;再跟着 K 行,每行给出由 N 个入队整数组成的出队序列。同行整数间以空格分隔。

输出

对每个需要查验的出队序列,如果是可能的,则在一行中输出 yes,否则输出 no。

样例输入

5 4
10 2 3 4 5
10 3 2 5 4
5 10 3 2 4
2 3 10 4 5
3 5 10 4 2

样例输出

yes
no
yes
no
答案与解析
参考答案
//该答案由AI生成
#include <iostream>
#include <vector>
#include <deque>
#include <set>
#include <map>
using namespace std;

bool check(vector<int>& in, vector<int>& out, const map<int, int>& index_map) {
    deque<int> deq;
    set<int> inDeque;
    int n = in.size();
    int i0 = 0, j0 = 0;

    while (i0 < n) {
        if (!deq.empty() && deq.front() == out[i0]) {
            int x = deq.front();
            deq.pop_front();
            inDeque.erase(x);
            i0++;
        } else {
            if (inDeque.find(out[i0]) != inDeque.end()) {
                return false;
            }

            if (j0 >= n) {
                return false;
            }

            auto it = index_map.find(out[i0]);
            if (it == index_map.end()) {
                return false;
            }
            int pos = it->second;

            if (pos < j0) {
                return false;
            }

            for (int k = j0; k < pos; k++) {
                deq.push_back(in[k]);
                inDeque.insert(in[k]);
            }
            deq.push_front(in[pos]);
            inDeque.insert(in[pos]);
            j0 = pos + 1;

            int x = deq.front();
            deq.pop_front();
            inDeque.erase(x);
            i0++;
        }
    }
    return true;
}

int main() {
    int N, K;
    cin >> N >> K;
    vector<int> in(N);
    map<int, int> index_map;
    for (int i = 0; i < N; i++) {
        cin >> in[i];
        index_map[in[i]] = i;
    }

    for (int i = 0; i < K; i++) {
        vector<int> out(N);
        for (int j = 0; j < N; j++) {
            cin >> out[j];
        }
        if (check(in, out, index_map)) {
            cout << "yes" << endl;
        } else {
            cout << "no" << endl;
        }
    }

    return 0;
}
题目详情
47 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

星星的个数

题目描述

你每天都会收集不同数量的星星贴纸。当收集到第 k 天时 (1≤k≤n),他当天获得的贴纸数量是 k 张,而每张贴纸上印着的星星数量等于 k 这个数字的因数个数(比如数字6有4个因数:1,2,3,6,就印4颗星星)。请计算你这 n 天收集到的星星总数。

输入格式

输入一个整数 n。

输出格式

共一行,这 n 天收集到的星星总数。


输入样例#1

4

输出样例#1

23

输入样例#2

100

输出样例#2

26879

输入样例#3

10000000

输出样例#3

838627288460105

说明提示

数据范围

1 ≤ N ≤ 107

样例1说明

1× 1 + 2× 2 + 3× 2 + 4× 3 =23

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
#include<iostream>
using namespace std;
int main()
{
    long long n;
    cin >> n;
    long long sum = 0;
    for (int d = 1; d <= n; ++d) {
        long long k = n / d;
        sum += d * (k + 1) * k / 2;
    }
    cout << sum << "\n";
    return 0;
}
题目详情
48 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

数零

题目描述

给定一个整数 n,请统计从 1 开始,到 n 为止的所有整数的十进制表示中,一共出现了多少个 0?

例如 n=100 时,1 到 100 中,只有以下数字出现过 0:

10, 20, 30, 40, 50, 60, 70, 80, 90, 100

所以总计出现 11 次。

输入格式

单个整数:表示 n。

输出格式

单个整数:表示 0 出现的次数。


输入样例

99

输出样例

9

说明提示

对于 30% 的数据,n≤100,000;

对于 60% 的数据,n≤10,000,000;

对于 100% 的数据,1≤n≤1,000,000,000,000。

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
#include<iostream>
int main()
{
    long long n;
    std::cin >> n;
    long long c = 0;
    long long p = 1;
    long long t = 0;
    while (n > 0) {
        int d = n % 10;
        n /= 10;
        if (d > 0) {
            c += n * p;
        }
        else {
            c += (n-1) * p;
            c += t + 1; 
        }
        t += d * p;
        p *= 10;
    }
    std::cout << c << "\n";
    return 0;
}
题目详情
49 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

表达式的值

题目描述

后缀表达式,它的定义如下:

单个数字如 6,8 等都是后缀表达式;

如果 e1,e2 都是后缀表达式,则 e1  e2  +e1  e2  +、e1  e2  −e1  e2  −、e1  e2  ∗e1  e2  ∗ 都是后缀表达式;

不满足以上两条规则的表达式都不是后缀表达式。

给定一个后缀表达式(保证合法),请计算表达式的值,并输出它模 10007 的余数。

注意,为了方便起见,我们省略了除法,同时也规定在表达式中出现的数字只能由一位数构成。

输入格式

一个字符序列:表示输入的后缀表达式。每个字符间用一个空格分开。保证输入字符只可能出现 0 到 9 及 +,-,* 三种运算符,且构成一个合法的后缀表达式。

输出格式

单个数字:表示表达式的值模 10007 的余数,注意余数必须大于或等于零。


输入样例#1

3 4 +

输出样例#1

7

输入样例#2

2 3 3 + *

输出样例#2

12

输入样例#3

1 2 * 3 + 4 * 5 - 6 + 7 * 8 - 9 +

输出样例#3

148

输入样例#4

1 5 -

输出样例#4

6

说明提示

数据范围

记输入的可见字符数量为 n,

对于 50% 的数据,1≤n≤100;

对于 100% 的数据,1≤n≤100,000。

样例2解释:

2*(3+3)=12

限制

时间限制:1000ms

内存限制:512MiB

答案与解析
参考答案
#include <iostream>
#include <stack>
using namespace std;
const int mod = 10007;

int main() {
    stack<int> s;
    char c;
    while (cin >> c) {
        if (c >= '0' && c <= '9') {
            s.push(c - '0');
        } else {
            int b = s.top(); s.pop();
            int a = s.top(); s.pop();
            if (c == '+') s.push((a + b) % mod);
            else if (c == '-') s.push((a - b + mod) % mod);
            else if (c == '*') s.push((a * b) % mod);
        }
    }
    cout << s.top() << endl;
    return 0;
}
题目详情
50 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

出栈序列的合法性

给定一个最大容量为 m 的堆栈,将 n 个数字按 1, 2, 3, ..., n 的顺序入栈,允许按任何顺序出栈,则哪些数字序列是不可能得到的?例如给定 m=5、n=7,则我们有可能得到{ 1, 2, 3, 4, 5, 6, 7 },但不可能得到{ 3, 2, 1, 7, 5, 6, 4 }。

时间限制:1000

内存限制:65536

输入

输入第一行给出 3 个不超过 1000 的正整数:m(堆栈最大容量)、n(入栈元素个数)、k(待检查的出栈序列个数)。最后 k 行,每行给出 n 个数字的出栈序列。所有同行数字以空格间隔。

输出

对每一行出栈序列,如果其的确是有可能得到的合法序列,就在一行中输出 `YES`,否则输出 `NO`。


样例输入

5 7 5
1 2 3 4 5 6 7
3 2 1 7 5 6 4
7 6 5 4 3 2 1
5 6 4 3 7 2 1
1 7 6 5 4 3 2

样例输出

YES
NO
NO
YES
NO
答案与解析
参考答案
//参考程序1
#include<bits/stdc++.h>
using namespace std;
int m,n,k;
bool is_possible(int out[])
{
	stack<int> s;
	int x=1,y=0;
	next:
	if(y==n)return 1;
	while(1)
	{
		if(s.size()>=m||x>n)return 0;
		s.push(x);
		x++;
		if(s.top()==out[y])break;
	}
	while(1)
	{
		if(s.size()==0)break;
		if(s.top()==out[y])
		{
			s.pop();
			y++;
		}
		else break;
	}
	goto next;
}
int main()
{
	cin>>m>>n>>k;
	for(int i=0;i<k;i++)
	{
		int out[n];
		for(int j=0;j<n;j++)
			cin>>out[j];
		if(!is_possible(out))cout<<"NO"<<endl;
		else cout<<"YES"<<endl;
	}
	return 0;
}
//参考程序2
#include <iostream>
#include <vector>
#include <stack>
using namespace std;

int main() {
	int m, n, k;
	cin >> m >> n >> k;
	
	while (k--) {
		vector<int> seq(n);
		for (int i = 0; i < n; ++i) {
			cin >> seq[i];
		}
		
		stack<int> st;
		int current_max = 0;
		bool valid = true;
		
		for (int v : seq) {
			if (v > current_max) {
				int needed = v - current_max;
				if (st.size() + needed > m) {
					valid = false;
					break;
				}
				for (int i = current_max + 1; i <= v; ++i) {
					st.push(i);
				}
				current_max = v;
				st.pop(); // 弹出v
			} else {
				if (st.empty() || st.top() != v) {
					valid = false;
					break;
				} else {
					st.pop();
				}
			}
		}
		
		cout << (valid ? "YES" : "NO") << endl;
	}
	
	return 0;
}

题目详情
51 简答题 偏难 C/C++编程考级 ·C/C++编程六级 · 1 栈与队列

取行李

一般机场里,航班到达后,旅客们会去到达区的行李传送带那里取自己的行李。

现假设有一座特别的机场,每条传送带只有一个取行李的窗口。旅客们必须排好队,逐一到窗口取自己的行李。但是当某人到窗口前,发现行李不是自己的,那人就只好走到队尾去等下一次机会。此时那件行李会一直等在窗口,直到它的主人把它取走。假设每一次认领需要 1 分钟,本题就要求你计算传送带清空需要的时间、以及旅客们的平均等待时间。

例如,假设行李 i 属于旅客 i。行李的到达顺序是 1、2、3,旅客的到达顺序是 2、1、3。则 1 号行李要等 2 分钟才能被主人 1 号旅客取走。这时行李队列中有 2、3,旅客队列中是 3、2。于是 2 号行李还要等 2 分钟才能被 2 号旅客取走,最后 3 号在第 5 分钟取走行李。旅客们的平均等待时间是 (2+4+5)/3 ≈ 3.7。

时间限制:1000

内存限制:65536

输入

输入首先在第一行给出一个正整数 N(≤ 103)。下一行给出 N 个数字,是 [1, N] 区间内整数的一个重排列,表示旅客队列。这里我们假设行李队列是按 1、2、……、N 有序的,并且行李 i 属于旅客 i。一行中数字间以空格分隔。

输出

在一行中输出传送带清空需要的时间、以及旅客们的平均等待时间(输出小数点后 1 位)。数字间以 1 个空格分隔,行首尾不得有多余空格。


样例输入

5
3 5 1 2 4

样例输出

9 6.0
答案与解析
参考答案
#include <iostream>
#include <queue>
#include <vector>
#include <iomanip>
using namespace std;

int main() {
	int N;
	cin >> N;
	vector<int> passengers(N);
	for (int i = 0; i < N; ++i) {
		cin >> passengers[i];
	}
	
	queue<int> q;
	for (int p : passengers) {
		q.push(p);
	}
	
	int current_luggage = 1;
	int time = 0;
	vector<int> wait_time(N + 1, 0); // 使用1-based索引
	
	while (current_luggage <= N) {
		int p = q.front();
		q.pop();
		if (p == current_luggage) {
			time += 1;
			wait_time[p] = time;
			current_luggage += 1;
		} else {
			time += 1;
			q.push(p);
		}
	}
	
	int total_time = time;
	double sum = 0;
	for (int i = 1; i <= N; ++i) {
		sum += wait_time[i];
	}
	double avg = sum / N;
	
	cout << total_time << " " << fixed << setprecision(1) << avg << endl;
	
	return 0;
}
题目详情