《算法竞赛入门经典》第六章数据结构基础题解（一）

### 探讨栈与队列的应用
#### 铁轨问题（Rails, ACM/ICPC CERC 1997, UVa 514）
**问题背景**
假设某城市火车站有n节车厢从A方向驶入，这些车厢按照1至n的顺序编号。任务是确定这些车厢是否能以特定的顺序从B方向的铁轨驶出。例如，顺序（5，4，3，2，1）是可行的，而（5，4，1，2，3）则不可行。

```cpp
#include
#include
using namespace std;
const int MAXN = 1010;
int n, target[MAXN];
int main() {
while (scanf("%d", &n) == 1) {
stack s;
int A = 1, B = 1;
for (int i = 1; i <= n; i++) {
scanf("%d", &target[i]);
}
int ok = 1;
while (B <= n) {
if (A == target[B]) {
A++;
B++;
} else if (!s.empty() && s.top() == target[B]) {
B++;
s.pop();
} else if (A <= n) {
s.push(A);
A++;
} else {
ok = 0;
break;
}
}
printf("%s\n", ok ? "Yes" : "No");
}
return 0;
}
```

#### 矩阵链乘问题（Matrix Chain Multiplication, UVa 442）
**问题背景**
给定n个矩阵的维度和一些矩阵链乘表达式，计算乘法所需的总次数。如果乘法无法进行，则输出错误信息。例如，三个矩阵A(50x10)，B(10x20)，C(20x5)，则(A(BC))的乘法次数为10*20*5 + 50*10*5 = 3500。

```cpp
#include
#include
#include
#include
using namespace std;
struct Matrix {
int a, b;
Matrix(int a = 0, int b = 0):a(a), b(b) {}
} m[26];
stack s;
int main() {
int n;
cin >> n;
for (int i = 0; i string name;
cin >> name;
int k = name[0] - 'A';
cin >> m[k].a >> m[k].b;
}
string expr;
while (cin >> expr) {
int len = expr.length();
bool error = false;
int ans = 0;
for (int i = 0; i if (isalpha(expr[i]))
s.push(m[expr[i]-'A']);
else if (expr[i] == ')') {
Matrix m2 = s.top();
s.pop();
Matrix m1 = s.top();
s.pop();
if (m1.b != m2.a) {
error = true;
break;
}
ans += m1.a * m1.b * m2.b;
s.push(Matrix(m1.a, m2.b));
}
}
if (error)
printf("error\n");
else
printf("%d\n", ans);
}
return 0;
}
```

### 链表的应用
#### 破损的键盘问题（Broken Keyboard, UVa 11988）
**问题背景**
输入包含多组数据，每组数据由不超过100000个字母、下划线、字符“[”或“]”组成。其中“[”表示Home键，“]”表示End键。任务是模拟键盘操作，输出最终显示在屏幕上的文本。

```cpp
#include
#include
using namespace std;
const int maxn = 100005;
int last, cur, next[maxn];
char s[maxn];
int main() {
while (scanf("%s", s+1) == 1) {
int n = strlen(s+1);
last = cur = 0;
next[0] = 0;
for (int i = 1; i <= n; i++) {
if (s[i] == '[') {
cur = 0;
} else if (s[i] == ']') {
cur = last;
} else {
next[i] = next[cur];
next[cur] = i;
if (cur == last) {
last = i;
}
cur = i;
}
}
for (int i = next[0]; i != 0; i = next[i]) {
printf("%c", s[i]);
}
printf("\n");
}
return 0;
}
```

#### 盒子移动问题（Boxes in a Line, UVa 12657）
**问题背景**
有一行编号为1至n的盒子，支持四种操作：将盒子X移至Y左侧、将盒子X移至Y右侧、交换X和Y的位置、反转整个序列。任务是在一系列操作后，计算所有奇数位置盒子编号的总和。

```cpp
#include
#include
#include
using namespace std;
const int MAXN = 100050;
int n;
int right[MAXN], left[MAXN];
void Link(int L, int R) {
right[L] = R;
left[R] = L;
}
int main() {
int m, kase = 0;
while (scanf("%d%d", &n, &m) == 2) {
for (int i = 1; i <= n; i++) {
left[i] = i-1;
right[i] = (i+1) % (n+1);
}
right[0] = 1;
left[0] = n;
int op, X, Y, inv = 0;

while (m--) {
scanf("%d", &op);
if (op == 4)
inv = !inv;
else {
scanf("%d%d", &X, &Y);
if (op == 3 && right[Y] == X)
swap(X, Y);
if (op != 3 && inv)
op = 3 - op;
if (op == 1 && X == left[Y])
continue;
if (op == 2 && X == right[Y])
continue;

int LX = left[X], RX = right[X], LY = left[Y], RY = right[Y];
if (op == 1) {
Link(LX, RX);
Link(LY, X);
Link(X, Y);
} else if (op == 2) {
Link(LX, RX);
Link(Y, X);
Link(X, RY);
} else if (op == 3) {
if (right[X] == Y) {
Link(LX, Y);
Link(Y, X);
Link(X, RY);
}else {
Link(LX, Y);
Link(Y, RX);
Link(LY, X);
Link(X, RY);
}
}
}
}
int b = 0;
long long ans = 0;
for (int i = 1; i <= n; i++) {
b = right[b];
if (i%2)
ans += b;
}
if (inv && n%2 == 0)
ans = (long long)n*(n+1) / 2 - ans;
printf("Case %d: %lld\n", ++kase, ans);
}
return 0;
}
```