UVa 12649 Folding Machine

题目描述

折叠机是一种受图灵机启发的计算模型。与图灵机不同，折叠机使用有限长度的磁带，磁带上存储的是整数，且计算过程通过折叠磁带的操作来完成。

一次折叠操作中，机器选择相邻单元格之间的一个位置，将磁带对折，重叠单元格的值相加。折叠可以发生在磁带的任意位置，包括在磁带开头或末尾进行折叠，后者实际上会反转磁带。

现在给定输入磁带和输出磁带，要求判断是否存在一系列折叠操作，能够从输入磁带得到输出磁带。

输入格式

输入包含多个测试用例。每个测试用例包含四行：

• 第一行：整数 $N$
• 第二行：$N$
• 第三行：整数 $M$
• 第四行：$M$

输出格式

对于每个测试用例，输出一行，包含一个字符：

• 如果存在折叠序列能从输入磁带生成输出磁带，输出 S
• 否则输出 N

数据范围

• $1\le M\le N\le 15$
• $0\le v_i,w_j\le 10^8$

题目分析

问题本质

这是一个状态搜索问题。我们需要判断是否能够通过一系列折叠操作，将长度为

N

N

N 的输入磁带转换为长度为

M

M

M 的输出磁带。

关键观察

解题思路

我们可以将问题建模为一个状态空间搜索问题：

折叠操作详解

假设当前磁带为

[

a

1

,

a

2

,

…

,

a

k

]

[a_1, a_2, \\ldots, a_k]

[a1​,a2​,…,ak​]，在位置

p

p

p 进行折叠（即在

a

p

a_p

ap​ 和

a

p

+

1

a_{p+1}

ap+1​ 之间折叠）：

具体实现时，可以统一处理：对于折叠点

p

p

p，设左侧有

p

p

p 个元素，右侧有

k

−

p

k-p

k−p 个元素。从折叠点开始，同时向左右两侧遍历，将对称位置的值相加。如果一侧的元素先用完，剩余的元素直接保留。

算法步骤

时间复杂度分析

• 最坏情况下，每次折叠磁带长度至少减少 $1$
• 对于长度为 $n$
• 状态总数有限，因为 $N\le 15$
• 实际运行时间可以接受

空间复杂度分析

• 主要空间消耗来自已访问状态的集合
• 状态总数有限，空间复杂度可接受

代码实现

// Folding Machine
// UVa ID: 12649
// Verdict: Accepted
// Submission Date: 2026-01-13
// UVa Run Time: 0.000s
//
// 版权所有（C）2026，邱秋。metaphysis # yeah dot net

#include <bits/stdc++.h>
using namespace std;

int n, m;
vector<int> target; // 目标磁带
set<vector<int>> visited; // 已访问状态集合

// 检查当前磁带是否匹配目标（考虑反转）
bool checkMatch(const vector<int>& tape) {
if (tape.size() != m) return false;

// 检查正序匹配
bool match1 = true;
for (int i = 0; i < m; i++) {
if (tape[i] != target[i]) {
match1 = false;
break;
}
}
if (match1) return true;

// 检查反序匹配
for (int i = 0; i < m; i++) {
if (tape[i] != target[m – 1 – i]) {
return false;
}
}
return true;
}

// 深度优先搜索
bool dfs(vector<int> tape) {
// 如果磁带长度等于目标长度，检查是否匹配
if (tape.size() == m) return checkMatch(tape);

// 如果磁带长度小于目标长度，不可能匹配
if (tape.size() < m) return false;

// 如果已访问过该状态，跳过
if (visited.count(tape)) return false;
visited.insert(tape);

int len = tape.size();

// 尝试所有折叠位置
for (int foldPos = 1; foldPos < len; foldPos++) {
// 向左折叠：右侧覆盖左侧
vector<int> newTape1;
int i = foldPos – 1, j = foldPos;

// 处理重叠部分
while (i >= 0 && j < len) {
newTape1.push_back(tape[i] + tape[j]);
i—;
j++;
}

// 处理左侧剩余部分
while (i >= 0) {
newTape1.push_back(tape[i]);
i—;
}

// 处理右侧剩余部分
while (j < len) {
newTape1.push_back(tape[j]);
j++;
}

// 反转结果，因为右侧覆盖了左侧
reverse(newTape1.begin(), newTape1.end());

if (dfs(newTape1)) return true;

// 向右折叠：左侧覆盖右侧
vector<int> newTape2;
i = foldPos – 1, j = foldPos;

// 处理重叠部分
while (i >= 0 && j < len) {
newTape2.push_back(tape[i] + tape[j]);
i—;
j++;
}

// 处理左侧剩余部分
while (i >= 0) {
newTape2.push_back(tape[i]);
i—;
}

// 处理右侧剩余部分
while (j < len) {
newTape2.push_back(tape[j]);
j++;
}

// 注意：这里不需要反转，因为左侧覆盖右侧时顺序保持不变

if (dfs(newTape2)) return true;
}

return false;
}

int main() {
// 处理多个测试用例，直到文件结束
while (cin >> n) {
vector<int> tape(n);
long long sumInput = 0, sumTarget = 0;

// 读入输入磁带并计算总和
for (int i = 0; i < n; i++) {
cin >> tape[i];
sumInput += tape[i];
}

// 读入输出磁带并计算总和
cin >> m;
target.resize(m);
for (int i = 0; i < m; i++) {
cin >> target[i];
sumTarget += target[i];
}

// 快速检查：总和必须相等
if (sumInput != sumTarget) {
cout << "N" << endl;
continue;
}

// 特殊情况：M = 1时，只需检查总和
if (m == 1) {
cout << (sumInput == target[0] ? "S" : "N") << endl;
continue;
}

// 初始化并开始搜索
visited.clear();
bool result = dfs(tape);
cout << (result ? "S" : "N") << endl;
}

return 0;
}

总结

本题的关键在于理解折叠操作的物理过程，并将其转化为状态搜索问题。由于数据范围较小（

N

≤

15

N \\leq 15

N≤15），可以使用深度优先搜索枚举所有可能的折叠序列。需要注意以下几点：

该算法在给定数据范围内能够高效运行，时间复杂度可以接受。通过本题，我们学习了如何将物理过程建模为状态搜索问题，并使用深度优先搜索进行求解。