「ROI 2021 Day2」莫斯科数字 题解

题目理解

莫斯科数字是一种类似罗马数字的系统，有26个字母对应不同的数值。关键规则是：

• 如果字母右边有比它大的字母，则贡献为 负值
• 否则贡献为 正值

我们需要将模板中的问号替换为字母，使得最终数字的值最大。

关键观察

1. 贡献计算规则

对于位置 $i$ 的字母 $c_i$：

• 贡献 = $sign \times value[c_i]$
• 其中 $sign = -1$ 如果 $\exists j > i$ 使得 $value[c_j] > value[c_i]$
• 否则 $sign = +1$

2. 最大化策略

为了最大化总值：

• 正贡献的字母应该尽可能大
• 负贡献的字母应该尽可能小（因为负得少）
• 关键是要控制每个字母的符号

3. 后缀最大值的影响

一个字母的符号取决于它右边的最大值：

• 如果当前字母 < 右边最大值 → 负贡献
• 如果当前字母 ≥ 右边最大值 → 正贡献

算法思路

方法：从右向左贪心

步骤1：预处理数值映射

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

map<char, long long> value = {
    {'A', 1}, {'B', 5}, {'C', 10}, {'D', 50}, {'E', 100}, {'F', 500}, {'G', 1000},
    {'H', 5000}, {'I', 10000}, {'J', 50000}, {'K', 100000}, {'L', 500000}, {'M', 1000000},
    {'N', 5000000}, {'O', 10000000}, {'P', 50000000}, {'Q', 100000000}, {'R', 500000000},
    {'S', 1000000000}, {'T', 5000000000}, {'U', 10000000000}, {'V', 50000000000},
    {'W', 100000000000}, {'X', 500000000000}, {'Y', 1000000000000}, {'Z', 5000000000000}
};

步骤2：计算后缀最大值

从右向左处理，维护每个位置右边的最大值：

vector<char> compute_max_right(const string& s) {
    int n = s.length();
    vector<char> max_right(n + 1, 'A'); // 'A' 是最小的
    char current_max = 'A';
    
    for (int i = n - 1; i >= 0; i--) {
        if (s[i] != '?') {
            current_max = max(current_max, s[i]);
        }
        max_right[i] = current_max;
    }
    return max_right;
}

步骤3：贪心填充问号

从右向左处理，为每个问号选择最优字母：

string fill_template(const string& template_str) {
    string result = template_str;
    int n = template_str.length();
    
    vector<char> max_right = compute_max_right(result);
    
    // 从右向左填充问号
    for (int i = n - 1; i >= 0; i--) {
        if (template_str[i] == '?') {
            // 当前字母的符号取决于它和右边最大值的关系
            char right_max = max_right[i + 1];
            
            if (value[right_max] > 0) {
                // 右边有更大的字母 → 当前为负贡献
                // 选择最小的字母（负得少）
                result[i] = 'A';
            } else {
                // 右边没有更大的字母 → 当前为正贡献  
                // 选择最大的字母
                result[i] = 'Z';
            }
            
            // 更新后缀最大值
            max_right[i] = max(result[i], max_right[i + 1]);
        }
    }
    
    return result;
}

步骤4：计算数字值

long long calculate_value(const string& s) {
    int n = s.length();
    long long total = 0;
    
    // 计算后缀最大值
    vector<long long> max_val_right(n + 1, 0);
    for (int i = n - 1; i >= 0; i--) {
        max_val_right[i] = max(value[s[i]], max_val_right[i + 1]);
    }
    
    // 计算总价值
    for (int i = 0; i < n; i++) {
        if (value[s[i]] < max_val_right[i + 1]) {
            total -= value[s[i]];
        } else {
            total += value[s[i]];
        }
    }
    return total;
}

完整代码实现

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

map<char, long long> value = {
    {'A', 1}, {'B', 5}, {'C', 10}, {'D', 50}, {'E', 100}, {'F', 500}, {'G', 1000},
    {'H', 5000}, {'I', 10000}, {'J', 50000}, {'K', 100000}, {'L', 500000}, {'M', 1000000},
    {'N', 5000000}, {'O', 10000000}, {'P', 50000000}, {'Q', 100000000}, {'R', 500000000},
    {'S', 1000000000}, {'T', 5000000000}, {'U', 10000000000}, {'V', 50000000000},
    {'W', 100000000000}, {'X', 500000000000}, {'Y', 1000000000000}, {'Z', 5000000000000}
};

string fill_template(const string& template_str) {
    string result = template_str;
    int n = template_str.length();
    
    // 预处理：计算固定字母的后缀最大值
    vector<char> max_right(n + 1, 'A');
    char current_max = 'A';
    for (int i = n - 1; i >= 0; i--) {
        if (template_str[i] != '?') {
            current_max = max(current_max, template_str[i]);
        }
        max_right[i] = current_max;
    }
    
    // 从右向左填充问号
    for (int i = n - 1; i >= 0; i--) {
        if (template_str[i] == '?') {
            // 检查当前符号
            bool will_be_negative = false;
            
            // 如果右边有固定的大字母，或者我们可以选择让当前为负
            if (value[max_right[i + 1]] > 0) {
                // 存在右边字母比所有可能选择都大
                will_be_negative = true;
            }
            
            if (will_be_negative) {
                // 负贡献：选择最小的字母
                result[i] = 'A';
            } else {
                // 正贡献：选择最大的字母
                result[i] = 'Z';
            }
            
            // 更新后缀最大值
            max_right[i] = max(result[i], max_right[i + 1]);
        }
    }
    
    return result;
}

long long calculate_value(const string& s) {
    int n = s.length();
    long long total = 0;
    vector<long long> max_val_right(n + 1, 0);
    
    for (int i = n - 1; i >= 0; i--) {
        max_val_right[i] = max(value[s[i]], max_val_right[i + 1]);
    }
    
    for (int i = 0; i < n; i++) {
        if (value[s[i]] < max_val_right[i + 1]) {
            total -= value[s[i]];
        } else {
            total += value[s[i]];
        }
    }
    return total;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    
    while (t--) {
        string template_str;
        cin >> template_str;
        
        string filled = fill_template(template_str);
        long long val = calculate_value(filled);
        
        cout << val << "\n";
        cout << filled << "\n";
    }
    
    return 0;
}

算法正确性证明

贪心选择正确性

1. 负贡献情况：当字母必然为负贡献时，选择最小的字母 $A$ 使得负得最少
2. 正贡献情况：当字母可以正贡献时，选择最大的字母 $Z$ 使得正得最多
3. 从右向左处理：确保每个决策都基于准确的右边信息

边界情况处理

• 全问号：全部选 $Z$，全部正贡献
• 无问号：直接计算固定值
• 混合情况：正确处理固定字母对问号的影响

复杂度分析

• 时间复杂度：$O(S)$，其中 $S$ 是所有字符串总长度
• 空间复杂度：$O(S)$

样例验证

样例1：BBBC

• 固定字符串，直接计算
• $B=5$（负），$B=5$（负），$B=5$（负），$C=10$（正）
• 总值：$-5-5-5+10 = -5$

样例2：????

• 全部选 $Z$，全部正贡献
• 总值：$4 \times 5\times 10^{12} = 2\times 10^{13}$

样例3：A?B?C?D

• 需要巧妙选择使得尽可能多的字母获得正贡献
• 算法会选择使得每个字母都能正贡献的配置

样例4：YYYYY?

• 前5个Y可能负贡献，最后一个Y正贡献
• 但通过选择，可以让所有Y都正贡献

优化技巧

1. 提前计算：预处理所有字母的数值
2. 后缀处理：从右向左一次扫描完成所有决策
3. 懒更新：只在必要时更新后缀最大值

总结

本题的关键在于理解莫斯科数字的符号规则，并通过从右向左的贪心策略最大化总值。算法高效且正确，能够处理大规模数据。