2675. 「NOI2012」三重镇 题解

题目分析

这是一个《三重镇》游戏的AI问题。我们需要在给定的 $n \times m$ 地图上，按照建造序列放置建筑，并可以在任意时刻使用星星和炸弹道具，目标是最大化最终得分。

游戏规则总结

1. 基本放置：

   • 必须按顺序使用建造序列中的建筑
   • 只能放在空格（.）上
   • 放置后立即得分：$score[level]$

2. 合并规则：

   • 放置后，如果与相邻的同等级建筑形成连通块大小 ≥ 3，则合并为下一等级建筑
   • 新建筑位置在最后放置的位置
   • 其他位置变为空格
   • 合并可能引发连锁反应
   • $L_9$ 不会继续合并

3. 道具规则：

   • 星星：放在空格 → 自动变为能引起反应的最高等级建筑（无反应则变 $L_1$），按最终建筑得分
   • 炸弹：放在有建筑的位置 → 炸掉建筑变空格，扣除该建筑一半分数

4. 得分： | 等级 | $L_1$ | $L_2$ | $L_3$ | $L_4$ | $L_5$ | $L_6$ | $L_7$ | $L_8$ | $L_9$ | |------|-------|-------|-------|-------|-------|-------|-------|-------|-------| | 得分 | 4 | 20 | 100 | 500 | 2500 | 12500 | 62500 | 312500 | 1562500 |

---

解题思路

这是一个状态空间搜索问题，但状态空间巨大，需要启发式策略。

1. 基础策略分析

(1) 贪心合并策略

• 尽量让同等级建筑形成3个以上的连通块
• 高级建筑得分是指数级增长，优先追求高等级建筑
• 连锁反应能大幅提高分数

(2) 星星使用时机

• 放在能引发最大反应的位置
• 当自然放置难以形成高等级建筑时使用
• 用于快速升级关键区域

(3) 炸弹使用时机

• 清除阻碍布局的低等级建筑
• 为关键放置清理空间
• 虽然扣分，但可能为后续更高得分创造条件

2. 算法框架

由于是提交答案题，我们可以对每个测试点设计专门策略：

// 伪代码框架
1. 读取输入：n, m, p, q, 初始地图, k, 建造序列
2. 实现游戏状态类，包含：
   - 地图状态 grid[n][m]
   - 当前得分 score
   - 剩余道具 stars_remain, bombs_remain
   - 建造序列位置 seq_pos
   - 操作历史记录
3. 实现游戏模拟器：
   - PUT操作：放置、合并、连锁反应
   - STAR操作：计算最佳等级、放置
   - BOMBER操作：炸毁建筑
4. 设计搜索/决策算法
5. 输出操作序列

---

核心算法实现

1. 游戏模拟器

class TripleTown {
private:
    int n, m;
    vector<vector<int>> grid;  // 0表示空格，1-9表示等级
    long long score;
    int stars, bombs;
    vector<int> build_seq;
    int seq_pos;
    
    // 建筑得分表
    const long long base_score[10] = {0, 4, 20, 100, 500, 2500, 12500, 62500, 312500, 1562500};
    
public:
    TripleTown(int _n, int _m, int _stars, int _bombs, 
               const vector<string>& init_grid,
               const vector<int>& seq) {
        n = _n; m = _m;
        stars = _stars;
        bombs = _bombs;
        build_seq = seq;
        seq_pos = 0;
        score = 0;
        
        // 初始化地图
        grid.resize(n, vector<int>(m, 0));
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (init_grid[i][j] == '.') {
                    grid[i][j] = 0;
                } else {
                    grid[i][j] = init_grid[i][j] - '0';
                }
            }
        }
    }
    
    // 放置建筑并处理合并
    bool put(int x, int y, int level) {
        if (x < 0 || x >= n || y < 0 || y >= m) return false;
        if (grid[x][y] != 0) return false;
        
        // 放置建筑
        grid[x][y] = level;
        score += base_score[level];
        
        // 处理合并
        bool changed;
        do {
            changed = false;
            vector<vector<bool>> visited(n, vector<bool>(m, false));
            
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (grid[i][j] != 0 && !visited[i][j]) {
                        int lvl = grid[i][j];
                        if (lvl == 9) continue;  // L9不合并
                        
                        // BFS找连通块
                        vector<pair<int, int>> component;
                        queue<pair<int, int>> q;
                        q.push({i, j});
                        visited[i][j] = true;
                        
                        while (!q.empty()) {
                            auto [x, y] = q.front(); q.pop();
                            component.push_back({x, y});
                            
                            // 四个方向
                            int dx[] = {0, 0, 1, -1};
                            int dy[] = {1, -1, 0, 0};
                            for (int d = 0; d < 4; d++) {
                                int nx = x + dx[d];
                                int ny = y + dy[d];
                                if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                                    !visited[nx][ny] && grid[nx][ny] == lvl) {
                                    visited[nx][ny] = true;
                                    q.push({nx, ny});
                                }
                            }
                        }
                        
                        // 如果连通块大小≥3，合并
                        if (component.size() >= 3) {
                            // 找到最后放置的位置（如果有多个，取中心或第一个）
                            int center_x = x, center_y = y;  // 简化：使用BFS起点
                            
                            // 清空其他位置
                            for (auto [cx, cy] : component) {
                                if (cx == center_x && cy == center_y) continue;
                                grid[cx][cy] = 0;
                            }
                            
                            // 升级中心位置
                            grid[center_x][center_y] = lvl + 1;
                            score += base_score[lvl + 1];  // 新建筑得分
                            
                            changed = true;
                        }
                    }
                }
            }
        } while (changed);  // 处理连锁反应
        
        return true;
    }
    
    // 使用星星
    bool use_star(int x, int y) {
        if (stars <= 0) return false;
        if (x < 0 || x >= n || y < 0 || y >= m) return false;
        if (grid[x][y] != 0) return false;
        
        stars--;
        
        // 计算能引起的最高等级
        int max_level = 1;
        for (int level = 1; level <= 8; level++) {
            // 临时放置该等级，检查是否能合并
            grid[x][y] = level;
            
            // 检查连通块大小
            vector<vector<bool>> visited(n, vector<bool>(m, false));
            int component_size = 0;
            
            queue<pair<int, int>> q;
            q.push({x, y});
            visited[x][y] = true;
            
            while (!q.empty()) {
                auto [cx, cy] = q.front(); q.pop();
                component_size++;
                
                int dx[] = {0, 0, 1, -1};
                int dy[] = {1, -1, 0, 0};
                for (int d = 0; d < 4; d++) {
                    int nx = cx + dx[d];
                    int ny = cy + dy[d];
                    if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
                        !visited[nx][ny] && grid[nx][ny] == level) {
                        visited[nx][ny] = true;
                        q.push({nx, ny});
                    }
                }
            }
            
            if (component_size >= 3) {
                max_level = level + 1;
            }
            
            // 恢复
            grid[x][y] = 0;
        }
        
        // 放置星星
        return put(x, y, max_level);
    }
    
    // 使用炸弹
    bool use_bomb(int x, int y) {
        if (bombs <= 0) return false;
        if (x < 0 || x >= n || y < 0 || y >= m) return false;
        if (grid[x][y] == 0) return false;
        
        int level = grid[x][y];
        long long deduct = base_score[level] / 2;
        
        grid[x][y] = 0;
        score -= deduct;
        bombs--;
        
        return true;
    }
    
    // 获取下一个建造等级
    int next_build_level() {
        if (seq_pos < build_seq.size()) {
            return build_seq[seq_pos];
        }
        return -1;  // 序列结束
    }
    
    // 消耗一个建造序列
    void consume_build() {
        if (seq_pos < build_seq.size()) {
            seq_pos++;
        }
    }
    
    long long get_score() { return score; }
    int get_stars() { return stars; }
    int get_bombs() { return bombs; }
    const vector<vector<int>>& get_grid() { return grid; }
};

2. 启发式搜索策略

由于完整搜索不可行，我们需要启发式：

class GameSolver {
private:
    TripleTown game;
    
    // 评估函数：估计当前局面的潜力
    long long evaluate_state() {
        long long potential = game.get_score();
        
        // 简单评估：高等级建筑越多越好
        auto& grid = game.get_grid();
        int n = grid.size(), m = grid[0].size();
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                int level = grid[i][j];
                if (level > 0) {
                    potential += (1LL << (level * 2));  // 指数权重
                }
            }
        }
        
        return potential;
    }
    
public:
    GameSolver(const TripleTown& g) : game(g) {}
    
    // 贪心策略：选择当前最佳放置位置
    pair<int, int> find_best_put_position(int level) {
        auto& grid = game.get_grid();
        int n = grid.size(), m = grid[0].size();
        
        long long best_score = -1e18;
        pair<int, int> best_pos = {-1, -1};
        
        // 遍历所有空格
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    // 模拟放置
                    TripleTown sim = game;  // 需要拷贝构造函数
                    if (sim.put(i, j, level)) {
                        long long new_score = sim.get_score();
                        if (new_score > best_score) {
                            best_score = new_score;
                            best_pos = {i, j};
                        }
                    }
                }
            }
        }
        
        return best_pos;
    }
    
    // 寻找最佳星星位置
    pair<int, int> find_best_star_position() {
        auto& grid = game.get_grid();
        int n = grid.size(), m = grid[0].size();
        
        long long best_score = -1e18;
        pair<int, int> best_pos = {-1, -1};
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] == 0) {
                    TripleTown sim = game;
                    if (sim.use_star(i, j)) {
                        long long new_score = sim.get_score();
                        if (new_score > best_score) {
                            best_score = new_score;
                            best_pos = {i, j};
                        }
                    }
                }
            }
        }
        
        return best_pos;
    }
    
    // 寻找最佳炸弹位置
    pair<int, int> find_best_bomb_position() {
        auto& grid = game.get_grid();
        int n = grid.size(), m = grid[0].size();
        
        long long best_score = -1e18;
        pair<int, int> best_pos = {-1, -1};
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (grid[i][j] > 0) {
                    // 炸掉这个建筑是否有利于后续？
                    // 简单策略：只炸低等级建筑
                    if (grid[i][j] <= 3) {
                        TripleTown sim = game;
                        if (sim.use_bomb(i, j)) {
                            // 检查是否能创造更好的合并机会
                            long long new_score = sim.get_score();
                            if (new_score > best_score) {
                                best_score = new_score;
                                best_pos = {i, j};
                            }
                        }
                    }
                }
            }
        }
        
        return best_pos;
    }
};

3. 主决策流程

vector<string> solve_game(int n, int m, int stars, int bombs,
                         const vector<string>& init_grid,
                         const vector<int>& build_seq) {
    TripleTown game(n, m, stars, bombs, init_grid, build_seq);
    GameSolver solver(game);
    
    vector<string> operations;
    
    while (true) {
        // 检查是否可以继续
        int next_level = game.next_build_level();
        if (next_level == -1 && game.get_stars() == 0) {
            // 序列结束且无星星可用
            break;
        }
        
        // 决策：放置建筑 or 使用道具？
        long long best_action_score = -1e18;
        string best_action;
        
        // 选项1：放置下一个建筑
        if (next_level != -1) {
            auto pos = solver.find_best_put_position(next_level);
            if (pos.first != -1) {
                TripleTown sim = game;
                if (sim.put(pos.first, pos.second, next_level)) {
                    long long score = sim.get_score();
                    if (score > best_action_score) {
                        best_action_score = score;
                        best_action = "PUT " + to_string(pos.first+1) + " " + to_string(pos.second+1);
                    }
                }
            }
        }
        
        // 选项2：使用星星
        if (game.get_stars() > 0) {
            auto pos = solver.find_best_star_position();
            if (pos.first != -1) {
                TripleTown sim = game;
                if (sim.use_star(pos.first, pos.second)) {
                    long long score = sim.get_score();
                    if (score > best_action_score) {
                        best_action_score = score;
                        best_action = "STAR " + to_string(pos.first+1) + " " + to_string(pos.second+1);
                    }
                }
            }
        }
        
        // 选项3：使用炸弹
        if (game.get_bombs() > 0) {
            auto pos = solver.find_best_bomb_position();
            if (pos.first != -1) {
                TripleTown sim = game;
                if (sim.use_bomb(pos.first, pos.second)) {
                    long long score = sim.get_score();
                    if (score > best_action_score) {
                        best_action_score = score;
                        best_action = "BOMBER " + to_string(pos.first+1) + " " + to_string(pos.second+1);
                    }
                }
            }
        }
        
        // 执行最佳操作
        if (best_action.empty()) {
            break;  // 无合法操作
        }
        
        operations.push_back(best_action);
        
        // 更新游戏状态
        if (best_action.substr(0, 3) == "PUT") {
            // 解析坐标
            stringstream ss(best_action.substr(4));
            int x, y;
            ss >> x >> y;
            x--; y--;  // 转为0-based
            
            game.put(x, y, next_level);
            game.consume_build();
        } else if (best_action.substr(0, 4) == "STAR") {
            stringstream ss(best_action.substr(5));
            int x, y;
            ss >> x >> y;
            x--; y--;
            
            game.use_star(x, y);
        } else if (best_action.substr(0, 6) == "BOMBER") {
            stringstream ss(best_action.substr(7));
            int x, y;
            ss >> x >> y;
            x--; y--;
            
            game.use_bomb(x, y);
        }
    }
    
    operations.push_back("END");
    return operations;
}

---

优化策略

1. 针对不同测试点的策略

由于是提交答案题，可以对每个测试点设计专门策略：

小地图（n,m ≤ 5）：

• 使用BFS/DFS搜索，深度限制在10-15步
• 可以尝试所有可能的操作序列

中等地图（n,m ≤ 10）：

• 使用带剪枝的搜索
• 优先考虑形成高级建筑的区域

大地图（n,m > 10）：

• 使用局部贪心
• 分区管理：将地图分为几个区域，分别优化

2. 高级启发式

// 更复杂的评估函数
long long advanced_evaluate(const vector<vector<int>>& grid) {
    long long score = 0;
    int n = grid.size(), m = grid[0].size();
    
    // 1. 当前得分
    // 2. 高等级建筑的价值（指数增长）
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] > 0) {
                score += (1LL << (grid[i][j] * 3));
            }
        }
    }
    
    // 3. 合并潜力：统计每个等级的数量
    vector<int> count(10, 0);
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] > 0) {
                count[grid[i][j]]++;
            }
        }
    }
    
    // 接近3的倍数的等级有合并潜力
    for (int lvl = 1; lvl <= 8; lvl++) {
        int remainder = count[lvl] % 3;
        if (remainder == 2) {
            score += (1LL << (lvl * 2));  // 差一个就能合并
        } else if (remainder == 1) {
            score += (1LL << (lvl * 1));  // 需要两个
        }
    }
    
    return score;
}

3. 模拟退火搜索

对于难以用贪心解决的问题，可以使用模拟退火：

vector<string> simulated_annealing(TripleTown& initial_game, int max_iter) {
    vector<string> best_solution;
    long long best_score = -1e18;
    
    double temperature = 1000.0;
    double cooling_rate = 0.99;
    
    vector<string> current_solution;
    TripleTown current_game = initial_game;
    long long current_score = current_game.get_score();
    
    for (int iter = 0; iter < max_iter; iter++) {
        // 生成邻居状态：随机改变一个操作
        // ...
        
        // 计算新得分
        // ...
        
        // 决定是否接受
        // ...
        
        temperature *= cooling_rate;
    }
    
    return best_solution;
}

---

输出格式

输出文件示例：

PUT 1 2
PUT 2 3
STAR 3 1
BOMBER 2 2
PUT 1 1
END

注意事项：

1. 坐标从1开始
2. 必须以END结束
3. 操作必须合法

---

总结

这道题是典型的提交答案题，解题步骤：

1. 完全理解游戏规则：实现准确的游戏模拟器
2. 设计基础策略：贪心合并、道具使用时机
3. 针对不同数据规模：小数据用搜索，大数据用启发式
4. 不断优化：根据得分反馈调整策略
5. 验证合法性：确保所有操作合法

关键点：

• 高级建筑的得分是指数级增长的，优先追求高等级
• 连锁反应能大幅提高单次操作得分
• 炸弹虽然扣分，但可以创造更好的布局
• 星星可以快速获得高等级建筑

对于NOI级别的比赛，通常需要为每个测试点设计专门的优化策略，可能需要数小时甚至更长时间来优化每个测试点的解。