1 条题解

  • 0
    @ 2026-10-27 5:41:08

    思路与算法

    把等式写成 K·x+C=0。扫描时维护当前位于等号哪一侧,左侧乘+1、右侧乘−1;每个项再乘自己的正负号。含字母的项加入 K,其余项加入 C。单独字母的系数是1,−x 的系数是−1。题目保证唯一实数解,因此 K≠0,解为−C/K。标程以十进制大整数精确累加,把分子乘1000后长除法决定三位小数。

    正确性说明

    移项只是在等式两侧同时加减同一项,因此不改变解集。每个原始项恰被扫描一次,其符号由项自身正负与等号侧别共同决定,所以最后得到的 K、C 正是原式移项后的系数与常数。K 非零时线性方程唯一解必为−C/K。整数商与余数直接决定缩放解最接近的整数,格式化不会引入中间浮点误差。

    复杂度

    设输入长度为 L,累计系数、常数与输出中最大数位为 D。词法扫描 O(L),大整数逐项加减总计不超过 O(LD),最终长除法 O(D²)。总时间 O(LD+D²),存储输入与整数共 O(L+D);初始化仅为常数个零整数。

    易错点

    等号右边整侧都要变号,不能只改变紧靠等号的项。不要遗漏隐含系数1、开头负号、零常数或两侧重复的未知数项。输入保证合法且唯一,不必自行定义无解和无限解的输出。负数舍入到0时不输出负零。

    参考代码(C++11)

    #include <bits/stdc++.h>
    using namespace std;
    struct cpp_int {
        string s;
        bool neg;
        cpp_int(long long v = 0) : s(to_string(v)), neg(v < 0) {
            if (neg)
                s.erase(s.begin());
        }
        void norm() {
            auto p = s.find_first_not_of('0');
            s = p == string::npos ? "0" : s.substr(p);
            if (s == "0")
                neg = false;
        }
        static int cmpabs(const cpp_int &a, const cpp_int &b) {
            if (a.s.size() != b.s.size())
                return a.s.size() < b.s.size() ? -1 : 1;
            return a.s == b.s ? 0 : a.s < b.s ? -1 : 1;
        }
        friend bool operator<(const cpp_int &a, const cpp_int &b) {
            if (a.neg != b.neg)
                return a.neg;
            int c = cmpabs(a, b);
            return a.neg ? c > 0 : c < 0;
        }
        friend bool operator==(const cpp_int &a, const cpp_int &b) {
            return a.neg == b.neg && a.s == b.s;
        }
        friend bool operator!=(const cpp_int &a, const cpp_int &b) {
            return !(a == b);
        }
        friend bool operator>(const cpp_int &a, const cpp_int &b) {
            return b < a;
        }
        friend bool operator<=(const cpp_int &a, const cpp_int &b) {
            return !(b < a);
        }
        friend bool operator>=(const cpp_int &a, const cpp_int &b) {
            return !(a < b);
        }
        cpp_int operator-() const {
            cpp_int r = *this;
            if (r.s != "0")
                r.neg = !r.neg;
            return r;
        }
        friend cpp_int operator+(const cpp_int &a, const cpp_int &b) {
            cpp_int r;
            r.s.clear();
            int carry = 0;
            if (a.neg == b.neg) {
                int i = (int)a.s.size() - 1, j = (int)b.s.size() - 1;
                while (i >= 0 || j >= 0 || carry) {
                    int v = carry + (i >= 0 ? a.s[i--] - '0' : 0) + (j >= 0 ? b.s[j--] - '0' : 0);
                    r.s += char('0' + v % 10);
                    carry = v / 10;
                }
                r.neg = a.neg;
            } else {
                const cpp_int *x = &a, *y = &b;
                if (cmpabs(a, b) < 0)
                    swap(x, y);
                int i = (int)x->s.size() - 1, j = (int)y->s.size() - 1;
                while (i >= 0) {
                    int v = x->s[i--] - '0' - carry - (j >= 0 ? y->s[j--] - '0' : 0);
                    carry = v < 0;
                    if (carry)
                        v += 10;
                    r.s += char('0' + v);
                }
                r.neg = x->neg;
            }
            reverse(r.s.begin(), r.s.end());
            r.norm();
            return r;
        }
        friend cpp_int operator-(const cpp_int &a, const cpp_int &b) {
            return a + (-b);
        }
        friend cpp_int operator*(const cpp_int &a, int b) {
            cpp_int r;
            r.s.clear();
            long long carry = 0;
            long long z = b;
            if (z < 0)
                z = -z;
            for (int i = (int)a.s.size() - 1; i >= 0; i--) {
                carry += (a.s[i] - '0') * z;
                r.s += char('0' + carry % 10);
                carry /= 10;
            }
            while (carry) {
                r.s += char('0' + carry % 10);
                carry /= 10;
            }
            reverse(r.s.begin(), r.s.end());
            r.neg = a.neg ^ (b < 0);
            r.norm();
            return r;
        }
        friend cpp_int operator/(const cpp_int &a, int b) {
            cpp_int r;
            r.s.clear();
            long long rem = 0, z = b;
            if (z < 0)
                z = -z;
            for (char c : a.s) {
                rem = rem * 10 + c - '0';
                r.s += char('0' + rem / z);
                rem %= z;
            }
            r.neg = a.neg ^ (b < 0);
            r.norm();
            return r;
        }
        cpp_int &operator+=(const cpp_int &b) {
            *this = *this + b;
            return *this;
        }
        cpp_int &operator-=(const cpp_int &b) {
            *this = *this - b;
            return *this;
        }
        cpp_int &operator*=(int b) {
            *this = *this * b;
            return *this;
        }
        friend istream &operator>>(istream &in, cpp_int &a) {
            string v;
            if (in >> v) {
                a.neg = v[0] == '-';
                if (v[0] == '-' || v[0] == '+')
                    v.erase(v.begin());
                a.s = v;
                a.norm();
            }
            return in;
        }
        friend ostream &operator<<(ostream &out, const cpp_int &a) {
            if (a.neg)
                out << '-';
            return out << a.s;
        }
    };
    
    cpp_int fromString(string s) {
        cpp_int a;
        a.neg = !s.empty() && s[0] == '-';
        if (!s.empty() && (s[0] == '-' || s[0] == '+'))
            s.erase(s.begin());
        a.s = s;
        a.norm();
        return a;
    }
    cpp_int absBig(cpp_int a) {
        a.neg = false;
        return a;
    }
    cpp_int pow10(size_t n) {
        cpp_int a;
        a.s = "1" + string(n, '0');
        return a;
    }
    cpp_int operator*(const cpp_int &a, const cpp_int &b) {
        vector<long long> d(a.s.size() + b.s.size());
        for (int i = (int)a.s.size() - 1; i >= 0; --i)
            for (int j = (int)b.s.size() - 1; j >= 0; --j)
                d[i + j + 1] += (a.s[i] - '0') * (b.s[j] - '0');
        for (int i = (int)d.size() - 1; i > 0; --i) {
            d[i - 1] += d[i] / 10;
            d[i] %= 10;
        }
        cpp_int c;
        c.s.clear();
        for (auto x : d)
            c.s += char('0' + x);
        c.neg = a.neg != b.neg;
        c.norm();
        return c;
    }
    pair<cpp_int, cpp_int> divmod(cpp_int a, cpp_int b) {
        bool sign = a.neg != b.neg, negrem = a.neg;
        a.neg = b.neg = false;
        cpp_int q, rem;
        q.s.clear();
        cpp_int mul[10];
        for (int i = 0; i < 10; ++i)
            mul[i] = b * i;
        for (char z : a.s) {
            rem = rem * 10 + (z - '0');
            int lo = 0, hi = 9;
            while (lo < hi) {
                int mi = (lo + hi + 1) / 2;
                if (mul[mi] <= rem)
                    lo = mi;
                else
                    hi = mi - 1;
            }
            q.s += char('0' + lo);
            rem -= mul[lo];
        }
        q.neg = sign;
        q.norm();
        rem.neg = negrem;
        rem.norm();
        return {q, rem};
    }
    cpp_int floorDiv(cpp_int a, const cpp_int &b) {
        auto z = divmod(a, b);
        if (a.neg && z.second != 0)
            z.first -= 1;
        return z.first;
    }
    cpp_int rootBig(const cpp_int &a) {
        cpp_int root, rem;
        string s = a.s;
        if (s.size() % 2)
            s = "0" + s;
        for (size_t i = 0; i < s.size(); i += 2) {
            rem = rem * 100 + (s[i] - '0') * 10 + s[i + 1] - '0';
            int x = 9;
            while ((root * 20 + x) * x > rem)
                --x;
            rem -= (root * 20 + x) * x;
            root = root * 10 + x;
        }
        return root;
    }
    string fixedBig(cpp_int rounded, int digits) {
        bool neg = rounded.neg;
        string s = rounded.s;
        while (s.size() <= (size_t)digits)
            s = "0" + s;
        if (digits)
            s.insert(s.size() - digits, ".");
        return (neg ? "-" : "") + s;
    }
    cpp_int roundedRational(cpp_int a, cpp_int b) {
        bool neg = a.neg != b.neg;
        a.neg = b.neg = false;
        auto q = divmod(a, b);
        if (q.second * 2 >= b)
            q.first += 1;
        q.first.neg = neg && q.first != 0;
        return q.first;
    }
    
    int main() {
        ios::sync_with_stdio(false);
        cin.tie(nullptr);
        string s;
        cin >> s;
        cpp_int coef, constant;
        char variable = 'x';
        int side = 1;
        for (size_t i = 0; i < s.size();) {
            if (s[i] == '=') {
                side = -1;
                ++i;
                continue;
            }
            int sign = 1;
            if (s[i] == '+' || s[i] == '-') {
                if (s[i] == '-')
                    sign = -1;
                ++i;
            }
            size_t begin = i;
            while (i < s.size() && isdigit(s[i]))
                ++i;
            bool has = i > begin;
            cpp_int v = has ? fromString(s.substr(begin, i - begin)) : cpp_int(1);
            v = v * (sign * side);
            if (i < s.size() && isalpha(s[i])) {
                variable = s[i++];
                coef += v;
            } else
                constant += v;
        }
        cpp_int answer = roundedRational((-constant) * 1000, coef);
        cout << variable << '=' << fixedBig(answer, 3) << '\n';
    }
    
    • 1

    信息

    ID
    2011
    时间
    1000ms
    内存
    64MiB
    难度
    普及
    标签
    递交数
    0
    已通过
    0
    上传者