P8815 [CSP-J 2022] 逻辑表达式

· · 题解

0.前言

T1太水，T2的blog不想写（简单的数学题而已，只不过前置知识把我狠狠坑了一把，详见我的游寄），因此直接写写T3吧。

我在考场上利用s=3和s=5的特殊情况作了特判，但可能因为特判时的失误或对题目并没有完全理解，最后只拿到了10分。但这10分确实是救了我一命的分数，详见游寄。

其实本题也就是大模拟。但是在第一篇题解的帮助下，我的AC代码只有53行，实在愧为大模拟。

不过这个思路确实很强啊。

1.思路

题解将思路写得很清晰，但对于这个思路，我有自己的理解，也想分享一下。

我的敲代码过程是跟着题解来的，因此也同样敲了一下优化前的代码（同时明确了思路）。

我对于本题核心思路的理解是：取出优先级最低的运算符，然后取出它的左侧判断是否有短路，若没有则计算右侧。递归此过程，直到得出最终答案。

在表达式未全部被括号括起来的情况下，优先级最低的运算符首先要保证不在括号内，其次由于or的优先级低于and，应先考虑or。反之，去掉括号并递归下去即可。

事实上“取出优先级最低的运算符”即为“找到这一层不在括号里的最后一个运算级最低的运算符”“整个算式都被括号包起来了，此时我们把括号去掉就行了”，而“计算”则可以理解为递归的过程以及在没有运算符的情况下的终止递归。

我对这个思路的评价是：非常简洁，非常完美。只是不太好想。

先看一下50分代码（即优化前的代码），也许会对这个思路有更深刻的理解。

#include<bits/stdc++.h>
using namespace std;
char s[1000010];
int len,ans,ansor,ansand;
int dfs(int l,int r){
  //取出优先级最低的运算符
    int x=0,orr=0,andd=0;
    for (int i=l;i<=r;i++){
        if (s[i]=='('){
            x++;
        }
        else if (s[i]==')'){
            x--;
        }
        else if (!x){
            if (s[i]=='|'){
                orr=i;
            }
            else if (s[i]=='&'){
                andd=i;
            }
        }
    }
    //取出后的计算
    //先判断有没有or
    if (orr){
        int lef=dfs(l,orr-1);//左侧，判断是否有短路
        if (lef==1){//有短路
            ansor++;
            return 1;
        }
        int rig=dfs(orr+1,r);//没有，计算右侧
        return (lef|rig);
    }
    if (andd){//与or同理
        int lef=dfs(l,andd-1);
        if (lef==0){
            ansand++;
            return 0;
        }
        int rig=dfs(andd+1,r);
        return (lef&rig);
    }
    if (s[l]=='('&&s[r]==')'){//被括号括起来
        return dfs(l+1,r-1);
    }
    return s[l]-'0';//在这种情况下l==r，很容易想出原因，请读者自证。
}
int main()
{
    cin>>s+1;
    len=strlen(s+1);
    ans=dfs(1,len);
    cout<<ans<<endl<<ansand<<" "<<ansor;
    return 0;
}

2.优化

但是很容易发现这样的时间复杂度为O(n^2)，会TLE。

因此我们的优化策略是：预处理每个字符左侧离它最近且优先级相同的运算符，这样我们直接取出和右边界优先级相同的运算符（在这个表达式内优先级最低）即可。若此运算符在左边界的左侧，则这一层不存在括号外的运算符，只有两种情况：整个表达式都在括号内或左边界等于右边界。

那我们该如何预处理呢？

我们可以从左到右遍历并更新每一优先级的最后一个运算符位置。由于遍历的顺序，对于遍历到的每个字符，目前所记录的与它优先级相同的运算符即为其左侧离它最近且优先级相同的运算符。

实现并不复杂。

有了这样的优化，我们就可以放心大胆地删去递归函数中的取出部分，并直接用主函数内的预处理取而代之。这样的话，时间复杂度就可以被降低为O(n)。

事实上优化对原程序的改动并不大，但对程序效率的确有了显著的提升。

%%%题解原作者。

3.AC代码

#include<bits/stdc++.h>
using namespace std;
char s[1000010];
int len,ans,ansor,ansand;
int cor[1000001],cand[1000001],lor[1000001],land[1000001];
int dfs(int l,int r){
    if (cor[r]>=l){
        int lef=dfs(l,cor[r]-1);
        if (lef==1){
            ansor++;
            return 1;
        }
        int rig=dfs(cor[r]+1,r);
        return (lef|rig);
    }
    if (cand[r]>=l){
        int lef=dfs(l,cand[r]-1);
        if (lef==0){
            ansand++;
            return 0;
        }
        int rig=dfs(cand[r]+1,r);
        return (lef&rig);
    }
    if (s[l]=='('&&s[r]==')'){
        return dfs(l+1,r-1);
    }
    return s[l]-'0';
}
int main()
{
    cin>>s+1;
    len=strlen(s+1);
    for (int i=1,x=0;i<=len;i++){
        if (s[i]=='('){
            x++;
        }
        else if (s[i]==')'){
            x--;
        }
        else if (s[i]=='|'){
            lor[x]=i;
        }
        else if (s[i]=='&'){
            land[x]=i;
        }
        cor[i]=lor[x];
        cand[i]=land[x];
    }
    ans=dfs(1,len);
    cout<<ans<<endl<<ansand<<" "<<ansor;
    return 0;
}

撒花。