P1054题解

MasterArcherSkeleton · 2025-02-01 21:07:27 · 题解

在 2025 年 3 月 29 日，我发现自己的题解中的【如果可能有负数怎么办？】的部分有很大的问题，现已纠正。
在 2025 年 8 月 11 日，我发现代码贴错了（很抱歉），现已纠正。
在 2025 年 11 月 30 日，经过巨佬 @shiyilang0910 的提醒，发现代码中有几处关键错误，现已纠正。

题意简化

给出一个表达式和其它 n(2 \le n \le 26) 个表达式（本文中，若只提到“表达式”，无“前缀”或“后缀”说明，则默认为中缀表达式），依次对应选项标号 A,B,C,\cdots（按大写字母顺序），求与原表达式等价的其它所有表达式的标号（按顺序从前至后）。
关于表达式的细节，大家可以看看题目：P1054 [NOIP 2005 提高组] 等价表达式 ，这里就不再进一步叙述了。

暴力（30pts）

注意到 30\% 的数据中“表达式中只可能出现两种运算符 + 和 -”，我们可以将每个表达式都转变成 xa+y 的形式。具体而言，用两个变量分别记录 x 与 y（这里就用 x 与 y 做变量名），初值为零。当遇到加（减）变量 a 时，就用 x 加（减） 1；当遇到加（减）一个常数 u 时，就用 y 加（减） u。最后只需要用每个表达式的 x 和 y 与原表达式的 x 和 y 作比较，都相等就表明该表达式与原表达式等价，否则不等价。只要注意细节，这 30 分是能够拿到的。

正解思路

拿到这道题，很容易就能够想到：把所有表达式都转变成只含 a 的多项式，再与原表达式进行比较，如果对应项系数都相等，就表明该表达式与原表达式等价，否则不等价。可是，如何把一个表达式转变成只含 a 的多项式呢？不仅操作实践难，还容易出错。况且，a 的最高次数也是很大的，不仅如此，每个多项式的系数与次数也可能很大，得用高精度来存储，就算取模也不好做（也不是精确算法）。所以，这种做法基本上是不行了。
那么怎么办呢？如何判断两个表达式等价呢？首先，若对于每个 a 代入原表达式与（其它表达式中的一个）进行求值后比较都相等，则必然这两个表达式等价，否则不等价。所以可以想到，只尝试 a 的一个取值，两个等价的表达式必然满足将这个 a 的取值代入后的结果相等。但是，将这个 a 的取值代入后的结果相等并不意味着这两个表达式一定等价。这怎么办呢？没关系，因为这表明这两个表达式大概率等价。 现在还是有一些问题，其中一个就是：最后的结果可能很大，是不是要用高精度呢？一旦用了高精度，所有运算的时间复杂度都会变大。但是其实并不需要用高精度，一边运算一边对结果取模就可以了。
所以，大体的思路基本上就有了。给 a 一个取值，分别代入到每个表达式中求值（对一个数取模的结果，一边运算一边取模），再将原表达式的结果与其他表达式的结果一一比较，得出结果（大概率正确）。

实现方法（细化）

补充：中缀表达式求值（同级运算从左至右）

第一步：输入

输入其实也是一个细节，需要根据不同的情况选择不同的读入方式。可以整体读入，没有空格时可以用 cin 或者 scanf 整体读入，遇到可能有空格的时候可以用 getline（最好不要用 gets 函数，可能不安全）；也可以单个字符读入（通常用 getchar 函数）。但是最好不要混用！

第二步：中缀表达式转后缀表达式

假设已经得到一个字符串 str，表示这个中缀表达式。直接对中缀表达式求值并不方便，可以先把中缀表达式转成后缀表达式。
先建一个字符串（后缀表达式）和一个符号栈。再从左往右扫描字符串（中缀表达式），一边扫一边分离（数字和 其它符号），得到一个元素（数字与其它符号，可以用 string 形式）后进行如下操作：

• 若该元素为数字，则将其拼接在后缀表达式后。
• 若该元素为运算符（括号不算），则一直将符号栈栈顶元素弹出并将其拼接在后缀表达式后，直到符号栈栈空或栈顶为左括号或该元素的优先级大于栈顶元素的优先级。
• 若该元素为左括号，则直接将该元素入符号栈。
• 若该元素为右括号，则一直将符号栈栈顶元素弹出并将其拼接在后缀表达式后，直到符号栈栈空或栈顶为左括号（如果直到栈空都没有找到左括号，就说明这个表达式的括号不匹配，所以如果表达式一定匹配就不需要判断栈空）。然后，再将符号栈栈顶元素弹出（当然，如果这个表达式的括号匹配的话，一定是左括号）。

扫描完了之后，最后再做一件事：一直将符号栈栈顶元素弹出并将其拼接在后缀表达式后，直到符号栈栈空（当然，如果遇到左括号，就说明这个表达式的括号不匹配，忽略该选项）。
这样，就成功地把一个中缀表达式转成后缀表达式。

第三步：后缀表达式求值

接下来，只要对这个后缀表达式求值，就能够求出原中缀表达式的值了。
建一个数字栈。先从左往右扫描字符串（后缀表达式），一边扫一边分离（同上）。得到一个元素后进行如下操作：

• 若该元素为数字，则将其入数字串。
• 若该元素为运算符（不可能是括号），令 t_1 为数字栈栈顶元素，再将数字栈栈顶元素岀栈；令 t_2 为数字栈栈顶元素，再将数字栈栈顶元素岀栈（如果表达式合法，就不可能中间栈空）。然后：
  • 若该元素为 +，则将 t_2 + t_1 的结果入栈。
  • 若该元素为 -，则将 t_2 - t_1 的结果入栈。
  • 若该元素为 *，则将 t_2 \times t_1 的结果入栈。
  • 若该元素为 ^，则将 {t_2} ^ {t_1} 的结果入栈。

扫描完了之后，数字栈中一定恰好剩余一个数字（如果表达式合法的话），那么这个数就是后缀表达式的结果。
当然，具体求 {t_2} ^ {t_1} 的时候，用快速幂还是循环 t_1 次就随便了，因为本题数据比较小，但是我个人倾向于写快速幂。

关于其他问题

如果可能有负数怎么办？

首先，因为负号与减号在中缀表达式中都是 -，所以需要将它们区别开来。
如何区别呢？注意到负号要么在表达式的最前面，要么前面是左括号；而减号要么在数字的后面，要么在右括号的后面。所以，同样是 -，我们就可以通过找它前面的字符（注意，有可能在最前面）来判断它是负号，还是减号。如果是减号，那么就把它当作运算符，否则把它当作它后面的数的一部分。定义一个变量（比如说 w），刚开始（扫描前）赋值为 1。当扫描到运算符时，判断是否是负号。如果是，则将 w 取相反数赋值后 continue，否则按运算符处理。当扫描到数时，就在入栈前将这个数的结果乘上 w，并将 w 赋值为 1。
可是，这样做对吗？
有一组 hack 就是 -(2-3)，如果按照刚才的方法计算，它会先将 2 取反，再减去 3。然而，括号的作用就没有了。所以，这样的方法是错的。
那怎么办呢？因为 -a 表示的就是 0 - a，所以可以把 -a 转换成 0 - a，也就是如果有一个负号，可以先在数字栈中加入 0，然后再用之前的方法在符号栈中加入一个 - 即可。

能否将多个步骤合并？

注意到在第二步中，后缀表达式是从左至右转换出来的，而第三步的时候，后缀表达式也是从左至右地扫描的。所以，可以把第三步与第二步合并。将第二步中“若该元素为运算符”的部分替换为第三步中“若该元素为运算符”的部分，第三步就不需要了（答案就是数字栈里唯一的数）。
如果输入使用的是单个字符读入的方式，可以一边输入一边进行第二步的操作。当然，可以叠加上面的第二、三步的合并。

贴代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
char ch, ch2, stk2[100010];
int w, temp, top1, top2, stk1[100010];
bool flag;
int Pow(int x, int y) {//快速幂
    if(!y) return 1;
    int tmp = Pow(x, y >> 1);
    tmp *= tmp;
    if(y & 1) tmp *= x;
    return tmp;
}
void Op(char op) {//计算表达式的值
    int temp = stk1[top1--];
    if(op == '+') stk1[top1] += temp;
    if(op == '-') stk1[top1] -= temp;
    if(op == '*') stk1[top1] *= temp;
    if(op == '^') stk1[top1] = Pow(stk1[top1], temp);
}
int F(char op) {//给出一个运算符的优先级
    if(op == '+' || op == '-') return 1;
    if(op == '*') return 2;
    if(op == '^') return 3;
    return 0;//括号
}
signed main()
{
    ch2 = ' ';//赋初值，用于判断负号
    w = 1;//正负标记变量
    ch = getchar();
    while(ch != '\n' && ch != '\r') {
        temp = 0;
        flag = false;
        while(ch >= '0' && ch <= '9') {
            temp = temp * 10 + (ch - '0');
            ch2 = ch;
            ch = getchar();
            flag = true;
        }
        if(flag) {
            stk1[++top1] = temp * w;
            w = 1;
        }
        if(ch == '\n' || ch == '\r') {
            break;
        }
        if(ch == ' ') {
            ch = getchar();
            continue;
        }
        if(ch == '(') {
            stk2[++top2] = '(';
        }
        else if(ch == ')') {
            while(top2 && stk2[top2] != '(') {
                Op(stk2[top2--]);
            }
            if(!top2) {
                cout << "ERROR";//右括号左边没有匹配的左括号
                return 0;
            }
            --top2;
        }
        else if(ch == '+' || ch == '-' || ch == '*' || ch == '^') {
            if(ch == '-' && (ch2 == ' ' || ch2 == '(')) {//判负号
                w = -w;
            }
            else {
                while(top2 && F(ch) <= F(stk2[top2])) {
                    Op(stk2[top2--]);
                }
                stk2[++top2] = ch;
            }
        }
        ch2 = ch;
        ch = getchar();
    }
    while(top2) {//倒着拼接在后缀表达式后并计算
        if(stk2[top2] == '(') {
            cout << "ERROR";//左括号右边没有匹配的右括号
            return 0;
        }
        Op(stk2[top2--]);
    }
    cout << stk1[1];
    return 0;
}

该代码时候情况为：

• 仅存在 +、-、*、^ 作为运算符（括号为 ( 和 )，- 可以作为负号），数字都是整数。
• 所有幂指数为非负整数，不存在要求计算 0^0。
• 所有同级运算都是从左至右进行计算（包括幂运算）。
• 不论是计算中还是初值或最终答案，都在 64 位 long long 的范围内。
• 表达式可能不合法，需要输出 ERROR。但是只存在括号不匹配导致表达式不合法的情况。
• 表达式长度不超过 10^5。
• 可能出现负数，但是保证负号要么出现在最前面，要么出现在 ( 的后面。

当然了，这一段文字可以当作一段补充。代码仅供参考，不喜勿喷。

代入原题

将上面的部分（【补充：中缀表达式求值】）代入到原题中时，要注意：在快速幂和上述函数 Op 中都要进行取模。那么，尤其要注意的就是在做减法的时候取模，一定要加上模数再取模！
当然，原题中有一个变量 a，就需要加一个判断，但是其实 a 也是一个数，就相当于输入了一个数，这个数是你要给 a 的取值，不过整体思路还是一样的，没有什么大的改动。
原题中，没有负数的存在。所以，并不需要上面【补充：中缀表达式求值】的代码那些关于判负号的语句。
当然，可以将中缀表达式求值的语句封装成一个函数，每次调用这个函数即可。注意要将一些变量初始化。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
char ch, stk2[51];
int n, temp, top1, top2, ans, A = 100007, Mod = 1000000007, stk1[51];
bool flag, flg;
int Pow(int x, int y) {
    if(!y) return 1;
    int tmp = Pow(x, y >> 1);
    (tmp *= tmp) %= Mod;
    if(y & 1) (tmp *= x) %= Mod;
    return tmp;
}
void Op(char op) {
    int temp = stk1[top1--];
    if(op == '+') (stk1[top1] += temp) %= Mod;
    if(op == '-') ((stk1[top1] += Mod) -= temp) %= Mod;
    if(op == '*') (stk1[top1] *= temp) %= Mod;
    if(op == '^') stk1[top1] = Pow(stk1[top1], temp);
}
int F(char op) {
    if(op == '+' || op == '-') return 1;
    if(op == '*') return 2;
    if(op == '^') return 3;
    return 0;
}
int Calc()
{
    flg = true;
    top1 = top2 = 0;
    ch = getchar();
    while(ch != EOF && (ch == '\n' || ch == '\r')) ch = getchar();//过滤上面没有读入的换行符
    if(ch == EOF) return -1;//空表达式
    while(ch != EOF && ch != '\n' && ch != '\r') {
        temp = 0;
        flag = false;
        while(ch >= '0' && ch <= '9') {
            temp = (temp * 10 + (ch - '0')) % Mod;
            ch = getchar();
            flag = true;
        }
        if(flag) stk1[++top1] = temp;
        if(ch == EOF || ch == '\n' || ch == '\r') break;
        if(ch == 'a') stk1[++top1] = A;
        else if(ch == '(') stk2[++top2] = '(';
        else if(ch == ')') {
            while(top2 && stk2[top2] != '(') Op(stk2[top2--]);
            if(!top2) {
                flg = false;//忽略这个选项
                while(ch != EOF && ch != '\n' && ch != '\r') ch = getchar();//将剩余的字符读入
                break;
            }
            --top2;
        }
        else if(ch == '+' || ch == '-' || ch == '*' || ch == '^') {
            while(top2 && F(ch) <= F(stk2[top2])) Op(stk2[top2--]);
            stk2[++top2] = ch;
        }
        ch = getchar();
    }
    if(!flg) return -1;
    while(top2) {
        if(stk2[top2] == '(') return -1;
        Op(stk2[top2--]);
    }
    if(!top1) return -1;//没有数字
    return stk1[1];
}
signed main()
{
    ans = Calc();
    if(ans < 0) return 0;//标准表达式不合法
    ch = getchar();
    while (ch != EOF && (ch == '\n' || ch == '\r')) (n *= 10) += signed(ch - '0');
    while (ch != EOF && ch >= '0' && ch <= '9') {
        n = n * 10 + (ch - '0');
        ch = getchar();
    }
    for(int i = 0; i < n; i ++) {
        if(Calc() == ans) cout << char('A' + i);
    }
    return 0;
}

最后说的话

文中所有代码都仅供参考。
如果文中有错误，欢迎指正。
此题代码不难，自己将每一步理解后写出来就可以了，千万不要抄代码！
最后祝愿大家 AC 本题！