2 条题解

  • 0
    @ 2025-12-1 16:18:23

    这是一份完全符合 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;
    }
    

    为什么这段代码是优秀的?

    1. 内存管理:使用 std::string 作为容器,内存是连续分配的,比链表式结构的 std::stack 在缓存(Cache)命中率上表现更好。
    2. 边界处理!ans_stack.empty() 的判断至关重要,防止在空栈时访问 .back() 导致运行时错误(Runtime Error)。
    3. IO 优化ios_base::sync_with_stdio(false) 是信奥竞赛中防止 I/O 超时的必备咒语。
    4. 清晰的逻辑:这段代码忠实地执行了我们之前讨论的规则——包括处理 HHCOOH 变为 CH 的正确逻辑。
    • 0
      @ 2025-12-1 16:16:24

      阿西莫夫的解题指南

      这道题是栈 (Stack) 的教科书级应用。

      1. 数据结构选择:我们需要频繁地检查“当前最新进入的元素”和“即将进入的元素”是否相同。如果相同则删除,不同则添加。这正是的特性(LIFO)。
      2. 实现技巧
        • 可以使用 C++ STL 的 std::stack
        • 更高效的做法是直接使用 std::stringstd::vector 模拟栈(push_back 入栈,pop_back 出栈,back() 查看栈顶)。最后直接输出字符串即可,省去了把栈倒出来的麻烦。

      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 个测试点各有侧重:

      1. Case 1-2: 教科书样例。确保学生读懂了题目规则。
      2. Case 3: 完美镜像(Empty)。构造形如 AB...CC...BA 的数据。考察代码是否能处理最终为空的情况(输出 "Empty")。
      3. Case 4: 最坏情况(无消除)。强制相邻字符不同。考察栈在满负载下的内存和处理能力。
      4. Case 5: 连环爆破AAAA...。奇数个剩1个,偶数个剩0个。考察逻辑是否严密。
      5. Case 6-8: 高频反应。字符集很小(只有 'A', 'B', 'C'),反应极其剧烈,栈会频繁地 pushpop
      6. Case 9-10: 深海压力。数据量达到 10510^5,字符集全覆盖(A-Z)。这是对时间复杂度 O(N)O(N) 和 I/O 速度的最终考验。

      这道题既有生物学的画面感(看着分子一个个结合消失),又是绝对纯粹的数据结构练习。非常适合初学者!

      • 1

      信息

      ID
      19235
      时间
      1000ms
      内存
      32MiB
      难度
      (无)
      标签
      (无)
      递交数
      0
      已通过
      0
      上传者