题解：P12096 [NERC2024] Expression Correction

luuia · 2025-04-10 17:00:14 · 题解

Solution

模拟题，按照题意模拟即可。具体模拟一下表达式的计算和单个字符的转移就行了，O(n^3)、O(n^4) 都能过。

要注意一些 corner case，例如单个 0 是合法的，首位为 0 是不合法的。

Code

/**
 *    author: luuia
 *    created: 2025.04.10 14:59:02
 **/
#include <bits/stdc++.h>
using ll = long long;
#define For(i, j, k) for (int i = j; i <= k; i++)
#define Rep(i, j, k) for (int i = j; i >= k; i--)
#define pb push_back
using namespace std;
const int N = 1e6 + 10;
string s, t;
ll n;
ll tu(string s)
{
    ll o = 0, f = 1;
    if (s[0] == '-')
        f = -1;
    for (auto ch : s)
        if (ch != '-')
            o = o * 10 + ch - 48;
    return o * f;
}
bool ck(string s)
{
    if ((s[0] != '-' && s.size() > 10) || (s[0] == '-' && s.size() > 11))
        return 1;
    if (s != "0" && ((s[0] == '-' && s[1] == '0') || s[0] == '0'))
        return 1;
    return 0;
}
bool chk(string s)
{
    string t;
    vector<string> vec;
    bool f = 1;
    For(i, 1, s.size() - 1) if (!isdigit(s[i]) && !isdigit(s[i - 1])) return 0;
    for (auto ch : s)
    {
        if (ch == '=')
            vec.pb(f ? t : "-" + t), t = "", vec.pb("###"), f = 1;
        else if (ch == '+')
            vec.pb(f ? t : "-" + t), t = "", f = 1;
        else if (ch == '-')
            vec.pb(f ? t : "-" + t), t = "", f = 0;
        else
            t += ch;
    }
    if (t != "")
        vec.pb(f ? t : "-" + t);
    bool fl = 0;
    vector<string> ct1, ct2;
    for (auto x : vec)
    {
        if (ck(x) || x == "")
            return 0;
        if (x == "###")
        {
            fl = 1;
            continue;
        }
        (fl ? ct2 : ct1).pb(x);
    }
    if (!ct1.size() || !ct2.size() || !isdigit(s.back()) || !isdigit(s[0]))
        return 0;
    ll o1 = 0, o2 = 0;
    for (auto x : ct1)
        o1 += tu(x);
    for (auto x : ct2)
        o2 += tu(x);
    return o1 == o2;
}
void sol()
{
    cin >> s, n = s.length();
    if (chk(s))
    {
        cout << "Correct\n";
        return;
    }
    For(i, 0, n - 1)
    {
        if (!isdigit(s[i]))
            continue;
        For(j, 0, n)
        {
            string t, t1, t2;
            if (i == 0)
                t1 = "", t2 = s.substr(1, n - 1);
            else if (i == n - 1)
                t1 = s.substr(0, n - 1), t2 = "";
            else
                t1 = s.substr(0, i), t2 = s.substr(i + 1, n - i - 1);
            t = t1 + t2;
            if (j < n)
                t.insert(j, 1, s[i]);
            else
                t += s[i];
            if (chk(t))
            {
                cout << t << '\n';
                return;
            }
        }
    }
    cout << "Impossible\n";
}
int main()
{
    // freopen("input.in","r",stdin);
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    ll T = 1;
    while (T--)
        sol();
    return 0;
}