2 条题解
-
0
这是一份完全符合 NOIP C++14 标准的解答程序。它简洁、高效,并且使用了
std::string来模拟栈,这样既能享受栈的逻辑特性,又能避免最后需要把栈倒出来才能输出的麻烦。C++14 标准解答代码
/** * 题目: 细胞膜的“分子消消乐” (The Membrane Channel) * 算法: 栈 (Stack) / 模拟 * 时间复杂度: O(N) - 字符串只遍历一次 * 空间复杂度: O(N) - 最坏情况下(无消除)需要存储所有字符 */ #include <iostream> #include <string> #include <vector> using namespace std; int main() { // 1. I/O 提速:关闭 C++ stdio 与 C stdio 的同步,解除 cin 与 cout 的绑定 // 这是在处理 10^5 级别及以上数据输入输出时的标准操作 ios_base::sync_with_stdio(false); cin.tie(NULL); string s; cin >> s; // 2. 使用 string 模拟栈 // string 支持 push_back (入栈), pop_back (出栈), back (查看栈顶) // 相比 std::stack<char>,它的优势在于最后可以直接输出,不需要倒序处理 string ans_stack; // 3. 遍历离子流 for (char c : s) { // 如果栈不为空,且栈顶元素与当前进入的离子相同 if (!ans_stack.empty() && ans_stack.back() == c) { // 发生反应,消除栈顶元素 ans_stack.pop_back(); } else { // 否则,离子进入通道(入栈) ans_stack.push_back(c); } } // 4. 输出结果 if (ans_stack.empty()) { cout << "Empty" << endl; } else { cout << ans_stack << endl; } return 0; }为什么这段代码是优秀的?
- 内存管理:使用
std::string作为容器,内存是连续分配的,比链表式结构的std::stack在缓存(Cache)命中率上表现更好。 - 边界处理:
!ans_stack.empty()的判断至关重要,防止在空栈时访问.back()导致运行时错误(Runtime Error)。 - IO 优化:
ios_base::sync_with_stdio(false)是信奥竞赛中防止 I/O 超时的必备咒语。 - 清晰的逻辑:这段代码忠实地执行了我们之前讨论的规则——包括处理
HHCOOH变为CH的正确逻辑。
- 内存管理:使用
-
0
阿西莫夫的解题指南
这道题是栈 (Stack) 的教科书级应用。
- 数据结构选择:我们需要频繁地检查“当前最新进入的元素”和“即将进入的元素”是否相同。如果相同则删除,不同则添加。这正是栈的特性(LIFO)。
- 实现技巧:
- 可以使用 C++ STL 的
std::stack。 - 更高效的做法是直接使用
std::string或std::vector模拟栈(push_back入栈,pop_back出栈,back()查看栈顶)。最后直接输出字符串即可,省去了把栈倒出来的麻烦。
- 可以使用 C++ STL 的
C++ 标准解答与数据生成器
以下代码包含标准解答(Solution)和数据生成器(Generator),会自动生成
1.in~10.in及对应的.out文件。请保存为
gen_membrane.cpp并运行。/** * Problem: The Membrane Channel (Stack Application) * Function: Generates 10 test cases covering various stack scenarios. */ #include <iostream> #include <string> #include <vector> #include <stack> #include <fstream> #include <random> #include <algorithm> using namespace std; // ========================================== // Part 1: 标准解答逻辑 (The Solver) // ========================================== class Solution { public: void solve(string in_file, string out_file) { ifstream cin(in_file); ofstream cout(out_file); if (!cin.is_open()) return; string s; cin >> s; // 使用 string 直接模拟栈,方便最后输出 string stk = ""; for (char c : s) { if (!stk.empty() && stk.back() == c) { // 发生同质化合反应,消除 stk.pop_back(); } else { // 不同,入栈 stk.push_back(c); } } if (stk.empty()) { cout << "Empty" << endl; } else { cout << stk << endl; } cin.close(); cout.close(); cout << "Generated: " << out_file << endl; } }; // ========================================== // Part 2: 数据生成逻辑 (The Generator) // ========================================== mt19937 rng(2025); // 生成随机字符 char rand_char(int complexity) { // complexity 越小,字符种类越少,消除概率越大 int range = min(26, max(2, complexity)); return 'A' + (rng() % range); } void generate_input(int case_id) { string filename = to_string(case_id) + ".in"; ofstream fout(filename); int len; string s = ""; // 1. 基础测试:极短,手动可算 if (case_id == 1) { s = "HOOH"; } else if (case_id == 2) { s = "HHCOOH"; } // 2. 全部消除测试 (构造回文结构) else if (case_id == 3) { // 构造像 ABCCBA 这样的完美消除串 int half_len = 50; string half = ""; for(int i=0; i<half_len; i++) half += rand_char(5); string reverse_half = half; reverse(reverse_half.begin(), reverse_half.end()); s = half + reverse_half; } // 3. 没有任何消除 (相邻字符均不同) else if (case_id == 4) { len = 100; char last = ' '; for(int i=0; i<len; i++) { char c = rand_char(5); while(c == last) c = rand_char(5); // 强制不同 s += c; last = c; } } // 4. 连续消除 (如 AAAAAA) else if (case_id == 5) { len = 100; for(int i=0; i<len; i++) s += 'A'; } // 5. 大规模随机 (高消除率 - 字符集小) else if (case_id >= 6 && case_id <= 8) { len = 10000; // 1e4 int complexity = (case_id == 6) ? 3 : 10; // Case 6 只有 ABC,极易消除 for(int i=0; i<len; i++) s += rand_char(complexity); } // 6. 最大规模压力测试 (1e5) else { len = 100000; for(int i=0; i<len; i++) s += rand_char(26); // 字符集大,消除较少,堆积严重 } fout << s << endl; fout.close(); } int main() { Solution solver; cout << "--- Generating Cell Membrane Data ---" << endl; for (int i = 1; i <= 10; i++) { generate_input(i); string in = to_string(i) + ".in"; string out = to_string(i) + ".out"; solver.solve(in, out); } cout << "--- Done! ---" << endl; return 0; }阿西莫夫的测试点设计解析:
为了让学生全面掌握栈的特性,这 10 个测试点各有侧重:
- Case 1-2: 教科书样例。确保学生读懂了题目规则。
- Case 3: 完美镜像(Empty)。构造形如
AB...CC...BA的数据。考察代码是否能处理最终为空的情况(输出 "Empty")。 - Case 4: 最坏情况(无消除)。强制相邻字符不同。考察栈在满负载下的内存和处理能力。
- Case 5: 连环爆破。
AAAA...。奇数个剩1个,偶数个剩0个。考察逻辑是否严密。 - Case 6-8: 高频反应。字符集很小(只有 'A', 'B', 'C'),反应极其剧烈,栈会频繁地
push和pop。 - Case 9-10: 深海压力。数据量达到 ,字符集全覆盖(A-Z)。这是对时间复杂度 和 I/O 速度的最终考验。
这道题既有生物学的画面感(看着分子一个个结合消失),又是绝对纯粹的数据结构练习。非常适合初学者!
- 1
信息
- ID
- 19235
- 时间
- 1000ms
- 内存
- 32MiB
- 难度
- (无)
- 标签
- (无)
- 递交数
- 0
- 已通过
- 0
- 上传者