新的一天从#include <cstdio>开始。 ——C2024XSC249

题目描述 有 n n n 节车厢从 A 方向驶入车站，按进站顺序编号为 1... n 1...n 1...n。

你的任务是让他们按照某中特定的顺序进入 B 方向的铁轨并驶出车站。为了重组车厢，你可以借助中转站 C。这是一个可以停放任意多节车厢的车站，但由于末端封顶，驶入 C 的车厢必须按照相反的顺序驶出 C。对于每个车厢，一旦从 A 移入 C，就不能再回到 A 了；一旦从 C 移入 B，就不能回到 C 了。换句话说，在任意时刻，只有两种选择：A->C 和 C->B。

现在需要你写一个程序，判断给定的 B 方向驶出车站的车箱顺序是否可行，若不可行输出 no；若可行则输出 yes，并输出要能得到这个出站顺序，中转站 C 至少需要几个存放车厢的位置。

输入格式 第 1 1 1 行一个整数 n n n，表示有 n n n 节车厢； 第 2 2 2 行 n n n 个整数，是 1... n 1...n 1...n 的排列，表示 B 方向驶出的车厢顺序。

输出格式 若 B 方向出站车厢顺序不可行输出 no，若可行，则输出 yes，并在第二行输出中转站至少要提供车厢位置数。

样例 输入样例

5
1 2 3 4 5

输出样例

yes
1

数据范围与提示 n ≤ 10000 n \le 10000 n≤10000

一看这个火车轨道，就想到栈。

栈中先存 1... n 1...n 1...n的排列。每枚举到一个放一个即可。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

int main () { 
        
	int n, x, a[10005], step = 1, ans = 1;
	//a数组表示放车的顺序，step表示现在正在放的车的编号。
	stack <int> s;
	scanf ("%d", &n);
	for (int i = 1; i <= n; i ++) { 
        
		scanf ("%d", &a[i]);
	}
	for (int i = 1; i <= n; i ++) { 
        
		s.push (i);
		ans = max (ans, (int) s.size());
		while (s.size()) { 
        
			if (s.top() == a[step]) { 
        //可以放车就pop
				step ++;
				s.pop();
			} else { 
        
				break;
			}
		}
	}
	if (s.size()) { 
        //输出，注意yes后还要写ans。
		printf ("no");
	} else { 
        
		printf ("yes\n");
		printf ("%d", ans);
	}
	return 0;
}

题目描述 读入一个只包含+、-、*、/、的非负整数计算表达式，计算该表达式的值。

输入格式 测试数据有多组，每组占一行。

每行不超过200个字符，整数和运算符之间用一个空格分隔。

没有非法表达式。

当一行中只有一个0时，表示输入结束，相应的结果不要输出。

输出格式 对于每组测试数据输出一行，即该表达式的值，精确到小数点后两位。

样例 输入样例

30 / 90 - 26 + 97 - 5 - 6 - 13 / 88 * 6 + 51 / 29 + 79 * 87 + 57 * 92
0

输出样例

12178.21

也是用栈进行模拟。

由于输入当中含空格，所以要注意过滤空格。

先输入第一个数和第一个空格。

如果第一个数是 0 0 0且不是空格，就表示输入结束，结束程序。

否则，就每一次已符号+' '+数+' '的格式进行输入：

• 如果符号为+，直接压入栈；
• 如果符号为-，将相反数压入栈；
• 如果符号为*或/，则将栈顶元素取出，乘除操作后再压入。

每行操作完后，栈中的元素相当于原式的代数和，最后累加这些代数和即可。

代码

#include <cstdio>
#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
#include <stack>
using namespace std;

stack <double> s;
double a, p;
char b, k;

int main () { 
        
    while (scanf ("%lf", &a) == 1) { 
        //第一个数+' '
        k = getchar ();
        if (a == 0 && k != ' ') { 
        
            break;
        }
        s.push(a);
        while (~scanf ("%c%lf", &b, &a)) { 
        //符号+' '+数+' '
            k = getchar ();
            if (b == '*') { 
        
                p = s.top() * a;
                s.pop();
                s.push(p);
            } else if (b == '/') { 
        
                p = s.top() / a;
                s.pop();
                s.push(p);
            } else { 
        
                if (b == '-') { 
        
                    a = -a;
                }
                s.push(a);
            }
            if (k != ' ') { 
        
                break;
            }
        }
        double ans = 0;
        while (s.size()) { 
        //累加
            ans += s.top();
            s.pop();
        }
        printf ("%.2lf\n", ans);
    }
    return 0;
}

题目描述 在本题中，题目会先给你一个包含小括号()及中括号[]的字串。当字串符合下列条件时我们称它为正确的运算式：

1. 该字串为一个空字串。

2. 如果 A 和 B 都为正确的运算式，则 AB 也为正确的运算式。

3. 如果 A 为正确的运算式，则 (A) 及 [A] 都为正确的运算式。

现在，请你写一支程序可以读入这类字串并检查它们是否为正确的运算式。字串的长度不超过 128 128 128。

输入格式 第一行为正整数 n n n，代表接下来有 n n n 个字符串。

接下来的 n n n 行，每行是一个仅含小括号和大括号的字符串（长度不大于 10000 10000 10000）。

输出格式 针对每个输入的括号字符串，如果是正确的运算式，则输出 Yes，否则输出 No。

样例 输入样例

4 
([])
(([()])))
([()[]()])()
([)]

输出样例

Yes
No
Yes
No

数据范围与提示 1 ≤ n ≤ 100 1 \leq n \leq 100 1≤n≤100

还是用栈进行模拟。

• 如果输入的字符能与栈顶字符匹配，则pop；
• 否则压进栈。

若最后栈内没有元素，输出Yes； 否则输出No。

代码

#include <cstdio>
#include <stack>
#include <algorithm>
#include <cstring>
using namespace std;

int n, len;
stack <char> s;
char a[10005];

bool match (char a, char b) { 
        
	return (a == '(' && b == ')') || (a == '[' && b == ']');
}

int main () { 
        
	scanf ("%d", &n);
	while (n --) { 
        
		scanf ("%s", a);
		len = strlen (a);
		for (int i = 0; i < len; i ++) { 
        
			if (s.size() && match (s.top(), a[i])) { 
        //可以匹配，pop
				s.pop();
			} else { 
        
				s.push(a[i]);
			}
		}
		if (s.size()) { 
        //还有东西，输出No
			printf ("No\n");
			while (s.size()) { 
         s.pop(); }//清空栈，为下一个数据做准备
		} else { 
        
			printf ("Yes\n");
		}
	}
	return 0;
}

题目描述 桌子上有一叠牌，从第一张牌（即位于顶面的牌）开始从上到下依次编号为 1... n 1...n 1...n，当至少还剩下两张牌时进行以下操作：把第一张扔掉，然后把新的一张放到整叠牌的最后。 输入 n n n，输出每次扔掉的牌，以及最后剩下的牌。

输入格式 第一行是一个整数 n n n 。

输出格式 一行 n n n 个整数，按顺序输出扔掉的 n − 1 n-1 n−1 张牌的序号和最后剩牌的序号。

样例 输入样例

7

输出样例

1 3 5 7 4 2 6

数据范围与提示 n ≤ 20000 n \le 20000 n≤20000

按照题目要求用栈模拟即可。

• 先输入并取出。
• 在把这时顶上的加在后面去，并删除。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

queue <int> q;
int n;

int main () { 
        
	scanf ("%d", &n);
	for (int i = 1; i <= n; i ++) { 
        
		q.push(i);
	}
	while (q.size() >= 2) { 
        
		printf ("%d ", q.front());
		q.pop();
		q.push(q.front());
		q.pop();
	}
	printf ("%d", q.front());
	return 0;
}

题目描述 队列（queue）：在线性表的一端插入元素，在另一端删除元素，所以遵循先进先出（ FIFO）原则，元素从队尾进，队首出，不允许插队！

其中删除元素的一端称为队首(front)，插入元素的一端称为队尾（rear）。

队列就像我们排队打饭，先来的先打饭，后来的只能排在队尾。

输入格式 第1行包含一个整数 n n n，表示有 n n n 条关于 queue 的操作，在进行任何操作之前，queue 都是空的。接来的 n n n 行，每行是一个关于 queue 的操作，格式和含义如下： clear：把队列置空。

empty：判断队列是否为空。

push：把整数 x x x 插入队尾（ x x x 为 int 范围里的数）。

pop： 队首元素出队列。

front：获取队首元素的值。

输出格式 对于 front 操作，输出一个整数，如果这个操作失败，则输出单词 error。

对于 pop 操作，如果这个操作失败，则输出单词 error。

对于 empty 操作，如果队列是空，则输出 empty，否则输出 not empty。

样例 输入样例

8
push 10
front 
push 15
pop
front 
clear
front
pop

输出样例

10
15
error
error

数据范围与提示

n ≤ 20000 n \le 20000 n≤20000

按照题目的相应方式调用queue中的成员函数即可。

代码

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
using namespace std;

queue <int> q;
int n, k;
char str[15];

int main () { 
        
	scanf ("%d", &n);
	for (int i = 1; i <= n; i ++) { 
        
		scanf ("%s", str);
		if (strcmp (str, "push") == 0) { 
        
			scanf ("%d", &k);
			q.push(k);
		} else if (strcmp (str, "pop") == 0) { 
        
			if (q.size() == 0) { 
        
				printf ("error\n");
			} else { 
        
				q.pop();
			}
		} else if (strcmp (str, "front") == 0) { 
        
			if (q.size() == 0) { 
        
				printf ("error\n");
			} else { 
        
				printf ("%d\n", q.front());
			}
		} else if (strcmp (str, "empty") == 0) { 
        
			if (q.empty()) { 
        
				printf ("empty\n");
			} else { 
        
				printf ("not empty\n");
			}
		} else if (strcmp (str, "clear") == 0) { 
        
			while (q.size()) { 
        
				q.pop();
			}
		}
	}
	return 0;
}

题目描述