本文共 4959 字，大约阅读时间需要 16 分钟。

代码forces参赛经历与思考

回文字符串问题

题意

给你一个字符串，要求插入一个字符‘a’，使其成为非回文字符串。

思路

代码示例

#include 
   
    using namespace std;bool isS(const string &str) {    if (str.empty()) return true;    if (str[0] != 'a') return false;    for (int i = 0; i < str.size() - 1; ++i) {        if (str[i] != str[i+1]) return false;    }    return true;}int main() {    int T;    cin >> T;    while (T--) {        string s;        int n = s.size();        bool is_possible = true;        for (int i = 0; i < n; ++i) {            if (s[n - i - 1] != 'a' && !is_possible) {                s.insert(n - i, 'a');                is_possible = false;            }        }        if (is_possible) {            cout << "NO\n";            continue;        }        cout << "YES\n";        for (int i = 0; i < n; ++i) {            if (s[n - i - 1] != 'a') {                s.insert(n - i, 'a');                break;            }        }        cout << s << endl;    }    return 0;}
   

01串转换问题

题意

将给定01串转换为另一个01串，允许每次操作选择前缀取反，且每次操作后01的数量保持不变。

思路

代码示例

#include 
   
    using namespace std;int main() {    int T;    cin >> T;    while (T--) {        string s;        int n = s.size();        vector
    
      cnt0(n + 1, 0), cnt1(n + 1, 0);        for (int i = 1; i <= n; ++i) {            cnt0[i] = (s[i-1] == '0') ? cnt0[i-1] + 1 : cnt0[i-1];            cnt1[i] = (s[i-1] == '1') ? cnt1[i-1] + 1 : cnt1[i-1];        }        string ans1(n, ' '), ans2(n, ' ');        bool possible = true;        for (int i = n; i >= 0; --i) {            if (ans1[i-1] != (s[i-1] == '0' ? '(' : ')')) {                if (cnt0[i] != cnt1[i]) possible = false;                if (!possible) break;            }            if (ans2[i-1] != (s[i-1] == '0' ? ')' : '(')) {                if (cnt0[i] != cnt1[i]) possible = false;                if (!possible) break;            }            if (possible) {                ans1[i-1] = (s[i-1] == '0' ? '(' : ')');                ans2[i-1] = (s[i-1] == '0' ? ')' : '(');            }        }        if (!possible) {            if (isS(s)) {                cout << "NO\n";            } else {                cout << "YES\n";                cout << s << "a\n";            }        } else {            cout << "YES\n";            for (int i = 0; i < n; ++i) {                cout << ans1[i];            }            cout << "\n";            for (int i = 0; i < n; ++i) {                cout << ans2[i];            }            cout << "\n";        }    }    return 0;}
    
   

平衡括号字符串构造

题意

构造两个平衡括号字符串，满足：

• 位置1相同，位置0不同。
• 平衡括号可以通过插入“+”和“1”形成合法表达式。

思路

代码示例

#include 
   
    using namespace std;bool ok() {    if (n % 2) return false;    vector
    
      zero_pos, one_pos;    for (int i = 0; i < n; ++i) {        if (s[i] == '0') {            if (i == 0 || i == n - 1) return false;            zero_pos.push_back(i);        } else {            one_pos.push_back(i);        }    }    if (zero_pos.size() % 2) return false;    for (int i = 0; i < zero_pos.size(); i += 2) {        ans1[zero_pos[i]] = '(';        ans1[zero_pos[i+1]] = ')';        ans2[zero_pos[i]] = ')';        ans2[zero_pos[i+1]] = '(';    }    int mid = one_pos.size() / 2;    for (int i = 0; i < mid; ++i) {        ans1[one_pos[i]] = '(';        ans1[one_pos[mid - i - 1]] = ')';        ans2[one_pos[i]] = '(';        ans2[one_pos[mid - i - 1]] = ')';    }    return true;}int main() {    int T;    cin >> T;    while (T--) {        int n;        string s;        string ans1(n, ' '), ans2(n, ' ');        if (!ok()) {            cout << "NO\n";        } else {            cout << "YES\n";            for (int i = 0; i < n; ++i) {                cout << ans1[i];            }            cout << "\n";            for (int i = 0; i < n; ++i) {                cout << ans2[i];            }            cout << "\n";        }    }    return 0;}
    
   

城市权重问题

题意

给定n个城市，每个城市有权值a_i或c_i，求从i到j的最短路径权重。

思路

代码示例

#include 
   
    using namespace std;int main() {    int n;    cin >> n;    vector
    
     
      > cities(n);    for (int i = 0; i < n; ++i) {        int a, c;        cin >> a >> c;        cities[i] = make_pair(a, c);    }    vector
      
        arr(n);    for (int i = 0; i < n; ++i) {        int a, c;        cin >> a >> c;        cities[i] = make_pair(a, c);        arr[i] = cities[i].first + cities[i].second;    }    sort(cities.begin(), cities.end());    ll ans = 0;    int maxx = cities[0].first + cities[0].second;    for (int i = 1; i < n; ++i) {        ans += max(0ll, cities[i].first - maxx);        maxx = max(maxx, cities[i].first + cities[i].second);    }    cout << ans << endl;    return 0;}
      
     
    
   

总结

通过反复练习和梳理思路，逐步掌握了多个Codeforces题目的解法。虽然在比赛中遇到过思路混乱和细节错误的问题，但通过赛后反思和优化，最终实现了正确解答。希望未来能继续保持学习热情，不断提升代码写作和问题解决能力。