2025寒假算法练习——Week 6
文章目录
前段时间做 DP 有些头晕，今天做些水题。
习题均来自 NEFU OJ
Problem 1624 | 栈-程序员输入问题
- Description
程序员输入程序出现差错时，可以采取以下的补救措施：按错了一个键时，可以补按一个退格符“#”，以表示前一个字符无效；发现当前一行有错，可以按一个退行符“@”，以表示“@”与前一个换行符之间的字符全部无效。
- Input
输入一行字符，个数不超过 100。
- Output
输出一行字符，表示实际有效字符。
- Sample Input
1sdfosif@for (ii#=1,#;i<.#=8;i+++#);
- Sample Output
1for (i=1;i<=8;i++);
- Hint
例子输入2：1234##
例子输出2：12
也许是不同语言对字符串的处理有差异，用 Java 会 WA。
1#include <iostream>
2#include <stack>
3#include <string>
4
5using namespace std;
6
7int main() {
8 string s;
9 getline(cin, s);
10 stack<char> st;
11
12 for (char ch : s) {
13 if (ch == '#') {
14 st.pop();
15 }
16 else if (ch == '@') {
17 while (!st.empty()) {
18 st.pop();
19 }
20 }
21 else {
22 st.push(ch);
23 }
24 }
25
26 stack<char> temp;
27 while (!st.empty()) {
28 temp.push(st.top());
29 st.pop();
30 }
31
32 while (!temp.empty()) {
33 cout << temp.top();
34 temp.pop();
35 }
36
37 return 0;
38}
getline(cin, s) 是为了将空格也读取进去，用 cin >> s 会在空格截断。
Problem 1627 | 栈-溶液模拟器
- Description
小谢虽然有很多溶液，但是还是没有办法配成想要的溶液，因为万一倒错了就没有办法挽回了。因此，小谢到网上下载了一个溶液配置模拟器。模拟器在计算机中构造一种虚拟溶液，然后可以虚拟地向当前虚拟溶液中加入一定浓度、一定体积的这种溶液，模拟器会快速地算出倒入后虚拟溶液的浓度和体积。当然，如果倒错了可以撤销。
模拟器的使用步骤如下：
1）为模拟器设置一个初始体积和浓度 V0、C0%。
2）进行一系列操作，模拟器支持两种操作：
P(v,c)操作：表示向当前的虚拟溶液中加入体积为 v 浓度为 c 的溶液；
Z 操作：撤销上一步的 P 操作。
- Input
第一行两个整数，表示 V0 和 C0，0≤C0≤100；
第二行一个整数 n，表示操作数，n≤10000；
接下来 n 行，每行一条操作，格式为：P_v_c 或 Z。
其中 _ 代表一个空格，当只剩初始溶液的时候，再撤销就没有用了，这时只输出初始的体积和浓度。
任意时刻质量不会超过 2^31 -1。
- Output
n 行，每行两个数 Vi，Ci，其中 Vi 为整数，Ci 为实数（保留 5 位小数）。
其中，第 i 行表示第 i 次操作以后的溶液体积和浓度。
- Sample Input
1100 100
22
3P 100 0
4Z
- Sample Output
1200 50.00000
2100 100.00000
- Hint
例子输入2：
100 100
2
Z
P 100 0
例子输出2：
100 100.00000
200 50.00000
这道题中的数对显然用 C++ 中的 pair 更方便。
1#include <iostream>
2#include <stack>
3
4using namespace std;
5
6stack<pair<double, double>> solution;
7
8int main() {
9 double v, c;
10 int n;
11 cin >> v >> c;
12 cin >> n;
13
14 double vi, ci, s = v * c / 100.0;
15 char op;
16 while (n--) {
17 cin >> op;
18 if (op == 'Z' && !solution.empty()) {
19 vi = solution.top().first;
20 ci = solution.top().second;
21 solution.pop();
22 v -= vi;
23 s -= vi * ci / 100.0;
24 c = s / v * 100.0;
25 printf("%d %0.5f\n", (int)v, c);
26 }
27 else if (op == 'Z' && solution.empty()) {
28 printf("%d %0.5f\n", (int)v, c);
29 }
30 else if (op == 'P') {
31 cin >> vi >> ci;
32 solution.push(make_pair(vi, ci));
33 v += vi;
34 s += vi * ci / 100.0;
35 c = s / v * 100.0;
36 printf("%d %0.5f\n", (int)v, c);
37 }
38 }
39
40 return 0;
41}
Problem 1628 | 栈-火车编组
- Description
如果一列火车有4列车厢，经过编组后，车厢的编组顺序为3,2,4,1；你知道编组站是如何编组的吗？编组的过程是由若干个进栈，出栈操作构成的。
- Input
第1行1个正整数n,n<=100;
第2行n个小于或等于n的正整数，表示有 n节车厢，编号为1,2,3，...n,编组时按照进栈，第2行数据表示列车经过编组后的车厢编号顺序。
- Output
一行一个由大写字母A和B构成的字符串,A表示进栈，B表示出栈。表示编组时进栈出栈的操作序列。
- Sample Input
14
23 2 4 1
- Sample Output
1AAABBABB
只要模拟一下进出栈的顺序就可以了。一个指针指向原顺序，一个指针指向现顺序，当栈顶元素和现指针指向的元素相同时则出栈且现指针后移，否则入栈且原指针后移。
1import java.util.Scanner;
2import java.util.Stack;
3
4public class Main {
5 public static void main(String[] args) {
6 try (Scanner sc = new Scanner(System.in)) {
7 int n = sc.nextInt();
8 int[] nums = new int[n];
9 for (int i = 0; i < n; i++) {
10 nums[i] = sc.nextInt();
11 }
12
13 Stack<Integer> stack = new Stack<>();
14 StringBuilder sb = new StringBuilder();
15 int i = 0;
16 int number = 1;
17 while (i < n) {
18 if (stack.isEmpty() || stack.peek() != nums[i]) {
19 stack.push(number);
20 number++;
21 sb.append("A");
22 }
23 if (!stack.isEmpty() && stack.peek() == nums[i]) {
24 stack.pop();
25 i++;
26 sb.append("B");
27 }
28 }
29 System.out.println(sb.toString());
30 }
31 }
32}
Problem 1629 | 栈-洗盘子
- Description
Bessie 和 Canmuu 将联手洗掉N (1<= N <= 10,000) 个脏盘子。
Bessie 洗; Canmuu 来擦干它们.
每个盘子有一个指定的编号，范围1..N. 开始,所有盘子按顺序排列在栈中，1号盘子在顶端，N号盘子在底端.
Bessie 会先洗一些盘子，然后放在洗过的盘子栈里（这样原来的顺序颠倒）.
然后，或者她洗别的盘子，或者Canmuu 擦干她已经洗好的部分或全部盘子，放在擦干的盘子栈里。
这样直到所有盘子洗完擦干后放置的顺序是什么？
- Input
第一行: 一个整数N，表示盘子的数量
以下若干行: 每一行两个整数 ，第一整数为1表示洗盘子，为2表示擦盘子，第二个整数表示数量
- Output
共N行:擦干后盘子从顶端到底端的顺序
- Sample Input
15
21 3
32 2
41 2
52 3
- Sample Output
11
24
35
42
53
1import java.util.Scanner;
2import java.util.Stack;
3
4public class Main {
5 public static void main(String[] args) {
6 try (Scanner sc = new Scanner(System.in)) {
7 int n = sc.nextInt();
8 Stack<Integer> dirty = new Stack<>();
9 Stack<Integer> washed = new Stack<>();
10 Stack<Integer> dried = new Stack<>();
11
12 for (int i = n; i > 0; i--) {
13 dirty.push(i);
14 }
15
16 int op, num;
17 while (dried.size() < n) {
18 op = sc.nextInt();
19 num = sc.nextInt();
20 if (op == 1) {
21 while (num-- > 0) {
22 washed.push(dirty.pop());
23 }
24 } else if (op == 2) {
25 while (num-- > 0) {
26 dried.push(washed.pop());
27 }
28 }
29 }
30
31 while (!dried.isEmpty()) {
32 System.out.println(dried.pop());
33 }
34 }
35 }
36}
Problem 1630 | 栈-括号匹配
- Description
假设表达式中允许包含圆括号和方括号两种括号，其嵌套的顺序随意，如（［］（））或［（［］［］）］等为正确的匹配，［（］）或（［］（）或（（）））均为错误的匹配。
本题的任务是检验一个给定表达式中的括号是否正确匹配。
输入一个只包含圆括号和方括号的字符串，判断字符串中的括号是否匹配，匹配就输出“OK”，不匹配就输出“Wrong”。
- Input
一行字符，只含有圆括号和方括号，个数小于 255。
- Output
匹配就输出一行文本“OK”，不匹配就输出一行文本“Wrong”。
- Sample Input
1[(])
- Sample Output
1Wrong
1import java.util.Scanner;
2import java.util.Map;
3import java.util.HashMap;
4import java.util.Stack;
5
6public class Main {
7 public static void main(String[] args) {
8 try (Scanner sc = new Scanner(System.in)) {
9 Map<Character, Character> map = new HashMap<>();
10 map.put('(', ')');
11 map.put('[', ']');
12
13 Stack<Character> stack = new Stack<>();
14 String brackets = sc.nextLine();
15 for (char c : brackets.toCharArray()) {
16 if (c == '(' || c == '[') {
17 stack.push(c);
18 } else if (!stack.isEmpty() && map.get(stack.peek()) == c) {
19 stack.pop();
20 } else if (stack.isEmpty() || map.get(stack.peek()) != c) {
21 System.out.println("Wrong");
22 return;
23 }
24 }
25 System.out.println(stack.isEmpty() ? "OK" : "Wrong");
26 }
27 }
28}