「CEOI2013」串并联停车场 题解

题目重述

我们有一个特殊结构的无向图（停车场），由停车位（节点）和双向道路（边）组成。图通过递归定义：

1. 单节点：编码为 o（空）或 x（有车）
2. 串联组合：S + 子图1编码 + 子图2编码 + #
3. 并联组合：P + 源点状态 + | + 子图1编码 + 子图2编码 + | + 终点状态 + #

目标：在不阻挡任何已有车辆（即每个已有车辆都能到达全局源点）的前提下，可以增加停车（o → x），求最大停车数，并输出一种方案。

核心思路

1. 数据结构与解析

• 将编码解析为语法树
• 节点类型：单节点、串联组合、并联组合
• 自底向上进行树形 DP

2. DP 状态设计

对于每个子图，我们需要追踪：

• 入口（s）和出口（t）是否被占用
• 入口到出口是否连通（内部可达性）
• 在满足不阻挡已有车辆的前提下，最大停车数

状态用 3 位表示：(s_occupied, t_occupied, connected)，共 8 种状态。

3. 状态转移

单节点：

• 空节点（o）：可以选择占或不占
• 已有车（x）：必须占用入口

串联组合：

• 新图的入口 = 左子图入口
• 新图的出口 = 右子图出口
• 连通性 = 左连通 ∧ 右连通 ∧ 中间边通畅
• 中间边通畅 = 左出口空 ∧ 右入口空

并联组合：

• 新加源点 s' 和终点 t'
• 新图的入口 = s'，出口 = t'
• 连通性 = (s'到左入口连通 ∧ 左连通 ∧ 左出口到t'连通) ∨ (s'到右入口连通 ∧ 右连通 ∧ 右出口到t'连通)
• 需要枚举 s' 和 t' 的状态

4. 合法性检查

关键约束：已有车辆不能被阻挡

• 在并联中，如果 s' 被占，则两个子图的入口都不可达
• 在串联中，如果左出口被占，则左图的车无法到右图
• 通过 DP 状态确保每个已有车辆都能到达入口

5. 构造方案

• 从根节点最优状态回溯
• 记录每个节点的选择
• 修改原始编码中的 o 为 x

完整 C++ 实现

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <stack>
#include <cassert>
using namespace std;

const int INF = 1e9;
const int BAD = -INF;

// DP 状态：(s_occupied, t_occupied, connected)
// 状态编码: 0-7
// 0: s空,t空,不连通  1: s空,t空,连通
// 2: s空,t占,不连通  3: s空,t占,连通
// 4: s占,t空,不连通  5: s占,t空,连通
// 6: s占,t占,不连通  7: s占,t占,连通
struct DPState {
    int cars;      // 最大车辆数
    int choice;    // 选择编码，用于回溯
    
    DPState(int c = BAD, int ch = -1) : cars(c), choice(ch) {}
    
    bool operator<(const DPState& other) const {
        return cars < other.cars;
    }
};

struct Node {
    char type;          // 'o'/'x' 单节点, 'S' 串联, 'P' 并联
    int start, end;     // 在原始字符串中的位置
    Node* left = nullptr;
    Node* right = nullptr;
    
    // DP 值
    DPState dp[8];
    
    // 用于构造方案
    int best_state = -1;
    int child1_state = -1, child2_state = -1;
    char s_char = 'o', t_char = 'o'; // 并联时额外的 s,t 字符
    char new_s_char = 'o', new_t_char = 'o'; // 并联时选择的新状态
    
    ~Node() {
        delete left;
        delete right;
    }
};

// 解析编码字符串
Node* parse(const string& s, int& pos) {
    Node* node = new Node();
    node->start = pos;
    
    if (s[pos] == 'o' || s[pos] == 'x') {
        node->type = s[pos];
        pos++;
    } 
    else if (s[pos] == 'S') {
        node->type = 'S';
        pos++; // 跳过 'S'
        node->left = parse(s, pos);
        node->right = parse(s, pos);
        pos++; // 跳过 '#'
    } 
    else if (s[pos] == 'P') {
        node->type = 'P';
        pos++; // 跳过 'P'
        node->s_char = s[pos]; // 源点字符
        pos++;
        assert(s[pos] == '|');
        pos++;
        node->left = parse(s, pos);
        node->right = parse(s, pos);
        assert(s[pos] == '|');
        pos++;
        node->t_char = s[pos]; // 终点字符
        pos++;
        pos++; // 跳过 '#'
    }
    node->end = pos;
    return node;
}

// 初始化单节点的 DP
void initSingleDP(Node* node) {
    for (int i = 0; i < 8; i++) node->dp[i] = DPState(BAD, -1);
    
    if (node->type == 'o') {
        // 空节点
        node->dp[0] = DPState(0, -1);     // 空,空,不连通
        node->dp[1] = DPState(BAD, -1);  // 空,空,连通（不可能）
        node->dp[2] = DPState(BAD, -1);  // 空,占,不连通
        node->dp[3] = DPState(BAD, -1);  // 空,占,连通（不可能）
        node->dp[4] = DPState(1, -1);    // 占,空,不连通
        node->dp[5] = DPState(BAD, -1);  // 占,空,连通（不可能）
        node->dp[6] = DPState(BAD, -1);  // 占,占,不连通
        node->dp[7] = DPState(BAD, -1);  // 占,占,连通（不可能）
    } 
    else { // 'x'
        // 已有车
        node->dp[0] = DPState(BAD, -1);  // 空,空,不连通（不可能）
        node->dp[1] = DPState(BAD, -1);
        node->dp[2] = DPState(BAD, -1);
        node->dp[3] = DPState(BAD, -1);
        node->dp[4] = DPState(1, -1);    // 占,空,不连通
        node->dp[5] = DPState(BAD, -1);
        node->dp[6] = DPState(BAD, -1);
        node->dp[7] = DPState(BAD, -1);
    }
}

// 检查状态是否合法
bool isStateValid(int state, bool has_car_at_s, bool has_car_at_t) {
    int s_occ = (state >> 2) & 1;
    int t_occ = (state >> 1) & 1;
    
    // 如果节点本身有车，对应位置必须是占用的
    if (has_car_at_s && s_occ == 0) return false;
    if (has_car_at_t && t_occ == 0) return false;
    
    return true;
}

// 串联组合的 DP
void combineSeriesDP(Node* node) {
    for (int i = 0; i < 8; i++) node->dp[i] = DPState(BAD, -1);
    
    for (int ls = 0; ls < 8; ls++) {
        if (node->left->dp[ls].cars < 0) continue;
        for (int rs = 0; rs < 8; rs++) {
            if (node->right->dp[rs].cars < 0) continue;
            
            int ls_occ = (ls >> 2) & 1;
            int lt_occ = (ls >> 1) & 1;
            int lconn = ls & 1;
            
            int rs_occ = (rs >> 2) & 1;
            int rt_occ = (rs >> 1) & 1;
            int rconn = rs & 1;
            
            // 检查中间边是否可通
            bool middle_blocked = (lt_occ == 1) || (rs_occ == 1);
            
            // 计算新状态
            int new_s_occ = ls_occ;
            int new_t_occ = rt_occ;
            int new_conn = 0;
            
            if (lconn && rconn && !middle_blocked) {
                new_conn = 1;
            }
            
            int new_state = (new_s_occ << 2) | (new_t_occ << 1) | new_conn;
            int new_cars = node->left->dp[ls].cars + node->right->dp[rs].cars;
            
            if (new_cars > node->dp[new_state].cars) {
                node->dp[new_state] = DPState(new_cars, ls * 8 + rs);
            }
        }
    }
}

// 并联组合的 DP
void combineParallelDP(Node* node) {
    for (int i = 0; i < 8; i++) node->dp[i] = DPState(BAD, -1);
    
    // 枚举新增的 s' 和 t' 的状态
    for (int s_occ = 0; s_occ <= 1; s_occ++) {
        if (s_occ == 1 && node->s_char == 'x') continue; // 不能改变已有车
        
        for (int t_occ = 0; t_occ <= 1; t_occ++) {
            if (t_occ == 1 && node->t_char == 'x') continue; // 不能改变已有车
            
            // 枚举左子图和右子图的状态
            for (int ls = 0; ls < 8; ls++) {
                if (node->left->dp[ls].cars < 0) continue;
                
                int ls_occ = (ls >> 2) & 1;
                int lt_occ = (ls >> 1) & 1;
                int lconn = ls & 1;
                
                // 检查左子图是否可达
                bool left_s_reachable = (s_occ == 0); // s' 空才能到左入口
                bool left_t_reachable = (t_occ == 0); // t' 空才能从左出口出
                bool left_path = left_s_reachable && lconn && left_t_reachable;
                
                for (int rs = 0; rs < 8; rs++) {
                    if (node->right->dp[rs].cars < 0) continue;
                    
                    int rs_occ = (rs >> 2) & 1;
                    int rt_occ = (rs >> 1) & 1;
                    int rconn = rs & 1;
                    
                    // 检查右子图是否可达
                    bool right_s_reachable = (s_occ == 0);
                    bool right_t_reachable = (t_occ == 0);
                    bool right_path = right_s_reachable && rconn && right_t_reachable;
                    
                    // 计算新图的连通性
                    int new_conn = (left_path || right_path) ? 1 : 0;
                    
                    // 计算新状态
                    int new_state = (s_occ << 2) | (t_occ << 1) | new_conn;
                    int new_cars = node->left->dp[ls].cars + node->right->dp[rs].cars;
                    if (s_occ == 1) new_cars++;
                    if (t_occ == 1) new_cars++;
                    
                    // 编码选择
                    int choice = (s_occ << 7) | (t_occ << 6) | (ls << 3) | rs;
                    
                    if (new_cars > node->dp[new_state].cars) {
                        node->dp[new_state] = DPState(new_cars, choice);
                    }
                }
            }
        }
    }
}

// 计算 DP
void computeDP(Node* node) {
    if (node->type == 'o' || node->type == 'x') {
        initSingleDP(node);
    } 
    else if (node->type == 'S') {
        computeDP(node->left);
        computeDP(node->right);
        combineSeriesDP(node);
    } 
    else if (node->type == 'P') {
        computeDP(node->left);
        computeDP(node->right);
        combineParallelDP(node);
    }
}

// 回溯构造方案
void buildSolution(Node* node, int state, string& result) {
    if (!node) return;
    
    node->best_state = state;
    
    if (node->type == 'o' || node->type == 'x') {
        // 单节点
        int s_occ = (state >> 2) & 1;
        if (node->type == 'o' && s_occ == 1) {
            result[node->start] = 'x';
        }
    } 
    else if (node->type == 'S') {
        // 串联
        int choice = node->dp[state].choice;
        int ls = choice / 8;
        int rs = choice % 8;
        
        node->child1_state = ls;
        node->child2_state = rs;
        
        buildSolution(node->left, ls, result);
        buildSolution(node->right, rs, result);
    } 
    else if (node->type == 'P') {
        // 并联
        int choice = node->dp[state].choice;
        int s_occ = (choice >> 7) & 1;
        int t_occ = (choice >> 6) & 1;
        int ls = (choice >> 3) & 7;
        int rs = choice & 7;
        
        node->new_s_char = s_occ ? 'x' : 'o';
        node->new_t_char = t_occ ? 'x' : 'o';
        node->child1_state = ls;
        node->child2_state = rs;
        
        // 修改 s 和 t 的字符
        if (node->s_char == 'o' && s_occ == 1) {
            result[node->start + 1] = 'x'; // 在 P 后面的位置
        }
        if (node->t_char == 'o' && t_occ == 1) {
            // 找到 t 的位置
            int pos = node->start + 1; // 跳过 P
            pos++; // 跳过 s
            while (result[pos] != '|') pos++;
            pos++; // 跳过 |
            // 跳过左子图
            stack<char> st;
            st.push('(');
            while (!st.empty()) {
                pos++;
                if (result[pos] == 'S' || result[pos] == 'P') st.push('(');
                else if (result[pos] == '#') st.pop();
            }
            // 跳过右子图
            st.push('(');
            while (!st.empty()) {
                pos++;
                if (result[pos] == 'S' || result[pos] == 'P') st.push('(');
                else if (result[pos] == '#') st.pop();
            }
            pos++; // 跳过 |
            result[pos] = t_occ ? 'x' : 'o';
        }
        
        buildSolution(node->left, ls, result);
        buildSolution(node->right, rs, result);
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    string s;
    cin >> s;
    
    int pos = 0;
    Node* root = parse(s, pos);
    
    computeDP(root);
    
    // 找到最优状态
    int best_state = -1;
    int max_cars = BAD;
    for (int i = 0; i < 8; i++) {
        if (root->dp[i].cars > max_cars) {
            max_cars = root->dp[i].cars;
            best_state = i;
        }
    }
    
    cout << max_cars << "\n";
    
    // 构造方案
    string result = s;
    buildSolution(root, best_state, result);
    cout << result << "\n";
    
    delete root;
    return 0;
}

算法分析

时间复杂度

• 解析：$O(n)$，其中 $n$ 是编码长度
• DP 计算：每个节点计算常数时间（8×8 状态枚举）
• 总时间复杂度：$O(n)$

空间复杂度

• 语法树：$O(n)$
• DP 状态：每个节点 8 个状态
• 总空间复杂度：$O(n)$

算法标签

• 树形 DP
• 递归解析
• 状态压缩
• 串并联图处理

关键点

1. 通过 8 种状态完整描述子图的信息
2. 串联时检查中间边的通畅性
3. 并联时枚举新加节点的状态
4. 始终保证已有车辆不被阻挡
5. 回溯构造方案时记录选择

这个解法在 $n \leq 10^5$ 的数据范围内可以高效运行，并且能输出最优方案。