1 条题解
-
0
思路与算法
把等式写成 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