[NOIP 2000 普及组] 计算器的改良

题意

给出一个合法的一元一次方程，只含整数、一个小写字母未知数、+、-、=。

要求求出这个未知数的值，并保留三位小数输出。

思路

这题直接扫描整条方程就行。

最直接的教学版写法如下：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72// brute.cpp：顺着等式扫描并分别统计未知数系数和常数项，作为教学版和对拍基准程序。
#include <bits/stdc++.h>
using namespace std;

string s;
char var_name;
double coef_sum;   // 所有未知数项移到左边后的总系数
double const_sum;  // 所有常数项移到左边后的总和

bool is_digit_char(char ch) {
    return ch >= '0' && ch <= '9';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;

    int n = (int) s.size();
    int side = 1; // 左边是 +1，右边是 -1
    int sign = 1;
    int i = 0;

    while (i < n) {
        if (s[i] == '+') {
            sign = 1;
            i++;
            continue;
        }
        if (s[i] == '-') {
            sign = -1;
            i++;
            continue;
        }
        if (s[i] == '=') {
            side = -1;
            sign = 1;
            i++;
            continue;
        }

        int value = 0;
        bool has_number = false;
        while (i < n && is_digit_char(s[i])) {
            value = value * 10 + (s[i] - '0');
            i++;
            has_number = true;
        }

        if (i < n && s[i] >= 'a' && s[i] <= 'z') {
            var_name = s[i];
            if (!has_number) {
                value = 1;
            }
            coef_sum += side * sign * value;
            i++;
        }
        else {
            const_sum += side * sign * value;
        }
    }

    double ans = -const_sum / coef_sum;
    if (fabs(ans) < 0.0005) {
        ans = 0.0;
    }

    cout << var_name << '=';
    cout << fixed << setprecision(3) << ans << '\n';
    return 0;
}

我们把等式左右两边统一移到左边。

扫描每一项时，维护：

当前项的正负号 sign
当前在等号左边还是右边 side

然后把解析出的项分成两类累计：

未知数项加到 coef_sum
常数项加到 const_sum

最后方程一定变成：

coef_sum * x + const_sum = 0

于是：

x = -const_sum / coef_sum

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71#include <bits/stdc++.h>
using namespace std;

string s;
char var_name;
double coef_sum;   // 未知数项总系数
double const_sum;  // 常数移项后的总和

bool is_digit_char(char ch) {
    return ch >= '0' && ch <= '9';
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> s;

    int n = (int) s.size();
    int side = 1; // 左边记为 +1，右边记为 -1，相当于统一移到左边
    int sign = 1;
    int i = 0;

    while (i < n) {
        if (s[i] == '+') {
            sign = 1;
            i++;
            continue;
        }
        if (s[i] == '-') {
            sign = -1;
            i++;
            continue;
        }
        if (s[i] == '=') {
            side = -1;
            sign = 1;
            i++;
            continue;
        }

        int value = 0;
        bool has_number = false;
        while (i < n && is_digit_char(s[i])) {
            value = value * 10 + (s[i] - '0');
            i++;
            has_number = true;
        }

        if (i < n && s[i] >= 'a' && s[i] <= 'z') {
            var_name = s[i];
            if (!has_number) {
                value = 1;
            }
            coef_sum += side * sign * value;
            i++;
        }
        else {
            const_sum += side * sign * value;
        }
    }

    double ans = -const_sum / coef_sum;
    if (fabs(ans) < 0.0005) {
        ans = 0.0;
    }

    cout << var_name << '=';
    cout << fixed << setprecision(3) << ans << '\n';
    return 0;
}

复杂度

时间复杂度： $O(n)$
空间复杂度： $O(1)$

总结

这题的关键是把字符串解析和代数移项结合起来：

读懂每一项；
正确处理左右两边符号；
最后统一成 kx+b=0。

一图流解析

这张图把本题的建模、关键转移、实现检查和训练方法压缩到一页，适合读完正文后复盘。

[NOIP 2000 普及组] 计算器的改良

目录

题意

思路

代码

复杂度

总结

一图流解析