CSP-J2022-C-逻辑表达式题解

发表于 更新于 分类于

题意：给你一个由 0、1、&、|、(、) 组成的字符串，保证是一个合法的逻辑表达式。其中括号优先级最高，与运算优先级高于或运算，同级之间从左到右算。定义一次短路为，或运算的左边结果为 1，或者与运算的左边结果为 0，此时后面部分无需计算（也不统计短路）。询问该逻辑表达式的结果以及与、或运算各自的短路次数。

做法 1

我们可以先使用栈预处理出括号的匹配（分段），然后使用 DFS 来计算。

DFS 时传入当前要处理的区间，返回该区间的结果，通过 DFS 内更改全局变量统计短路次数。对于区间之间的转移，我们有以下两种处理方法：

1.1

考虑最后一次运算的位置。从最右边开始，每次往前跳一段，如果出现或运算则一定是最后一次，否则继续跳；如果没有或运算则为最后一次与运算的位置。有了这个，我们递归地计算出从开头到最后一次的位置的答案，判断是否短路。如果不短路，则递归右边计算。这个做法显然会超时，因为可能会重复地扫同层之间的与运算。所以我们传参时传入一个布尔参数 flagflag，表示是否能确定当前层没有或运算。如果 flag=1flag=1，则可以直接跳过“每次跳一段”的过程，直接得出最后一次操作的位置。复杂度显然正确。

By myself

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
#include<bits/stdc++.h>
using namespace std;
string s;
int pr[1000010],cnt1,cnt2;
bool dfs(int l,int r,bool flag) {
    if(l==r) return s[l]-'0';
    if(pr[r]==l) return dfs(l+1,r-1,0);
    int now=pr[r]-1;
    bool done=0;
    while(!flag&&now>l) {
        if(s[now]=='|') {
            done=1;
            break;
        }
        now=pr[now-1]-1;
    }
    if(done==0) flag=1,now=pr[r]-1;
    auto res=dfs(l,now-1,flag);
    if(s[now]=='|'&&res==1) cnt2++;
    else if(s[now]=='&'&&res==0) cnt1++;
    else return dfs(now+1,r,1);
    return res;
}
int main() {
    // freopen("expr.in","r",stdin);
    // freopen("expr.out","w",stdout);
    cin>>s;
    stack<int> st;
    for(int i=0;i<s.size();i++) {
        if(s[i]=='0'||s[i]=='1') pr[i]=i;
        else if(s[i]==')') pr[i]=st.top(),pr[st.top()]=i,st.pop();
        else if(s[i]=='(') st.push(i);
    }
    cout<<dfs(0,s.size()-1,0)<<endl;
    cout<<cnt1<<" "<<cnt2<<endl;
    return 0;
}

1.2

也和上个类似，寻找最后一次运算位置作为分段点。这个做法用较高的代码难度换了较低的思维难度，直接使用 ST 表来预处理分段位置。

By GD-J00096

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
73
74
75
76
77
78
79
80
81
82
83
84
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

inline void fio(string name)
{
    freopen((name+".in").c_str(),"r",stdin);
    freopen((name+".out").c_str(),"w",stdout);
}

inline long long read()
{
    long long s=0,w=1,ch=getchar();
    while(ch<'0'||ch>'9') ch=='-'?w=-1,ch=getchar():ch=getchar();
    while(ch>='0'&&ch<='9') s=(s<<1)+(s<<3)+(ch^48),ch=getchar();
    return s*w;
}

const int S=1000005;

int n;
char a[S];
int top,sta[S];
int rb[S],val[S];
int mlog[S],mn[S][25];
int cnt1,cnt2;

inline int que(int l,int r)
{
    int k=mlog[r-l+1];
    int x=mn[l][k],y=mn[r-(1<<k)+1][k];
    return val[x]<val[y]?x:y;
}

int slove(int l,int r)
{
    if(rb[l]==r) l++,r--;
    if(l==r) return a[l]-'0';
    int pos=que(l,r);
    int lft=slove(l,pos-1);
    if(lft==0&&a[pos]=='&')
    {
        cnt1++;
        return 0;
    }
    if(lft==1&&a[pos]=='|')
    {
        cnt2++;
        return 1;
    }
    int rig=slove(pos+1,r);
    if(a[pos]=='&') return lft&rig;
    else return lft|rig;
}

int main()
{
    fio("expr");
    scanf("%s",a+1);
    n=strlen(a+1);
    for(int i=1;i<=n;i++)
    {
        if(a[i]=='(') sta[++top]=i;
        else if(a[i]==')') rb[sta[top--]]=i;
        else if(a[i]!='0'&&a[i]!='1') val[i]=sta[top]*2+(a[i]=='&');
        if(a[i]!='&'&&a[i]!='|') val[i]=1e8;
    }
    mlog[0]=-1;
    for(int i=1;i<=n;i++) mlog[i]=mlog[i>>1]+1,mn[i][0]=i;
    for(int j=1;j<=mlog[n];j++)
    {
        for(int i=1;i<=n-(1<<j)+1;i++)
        {
            int x=mn[i][j-1],y=mn[i+(1<<j-1)][j-1];
            mn[i][j]=val[x]<val[y]?x:y;
        }
    }
    printf("%d\n",slove(1,n));
    printf("%d %d\n",cnt1,cnt2);
    return 0;
}

1.3

同层之间直接从左往右跳，每一段递归计算。缺点是需要处理与或的优先级问题，优点是复杂度直接就是正确的，思维难度较低。

By JS-J00401

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
#include<bits/stdc++.h>
#define N 3000005
using namespace std;
int n,m,top,ans1,ans2;
int to[N],to2[N],stk[N],cl[N],cr[N];
char str[N],s[N];
void build(int l,int r){
    if(l==r) return;
    if(str[l]=='('&&str[r]==')'&&to[l]==r){build(l+1,r-1);return;}
    build(l,to[l]);
    for(int i=to[l]+1;i<=r;i=to[i+1]+1){
        build(i+1,to[i+1]);
        if(str[i]=='&'){
            cl[to2[i-1]]++;cr[to2[i+1]]++;
            to2[to2[i+1]]=to2[i-1];
        }
    }
}
int solve(int l,int r){
    if(l==r) return s[l]-'0';
    if(s[l]=='('&&s[r]==')'&&to[l]==r) return solve(l+1,r-1);
    int val=solve(l,to[l]);
    for(int i=to[l]+1;i<=r;i=to[i+1]+1){
        if(s[i]=='&'){
            if(!val) ans1++;
            else val&=solve(i+1,to[i+1]);
        }else{
            if(val) ans2++;
            else val|=solve(i+1,to[i+1]);
        }
    }
    return val;
}
signed main(){
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    scanf("%s",str+1);n=strlen(str+1);
    for(int i=1;i<=n;i++){
        if(str[i]=='0'||str[i]=='1') to[i]=i;
        if(str[i]=='(') stk[++top]=i;
        if(str[i]==')') to[stk[top]]=i,to[i]=stk[top],top--;
    }
    memcpy(to2,to,sizeof(to));
    build(1,n);
    for(int i=1;i<=n;i++){
        while(cl[i]--) s[++m]='(';
        s[++m]=str[i];
        while(cr[i]--) s[++m]=')';
    }
    memset(to,0,sizeof(to));
    top=0;
    for(int i=1;i<=m;i++){
        if(s[i]=='0'||s[i]=='1') to[i]=i;
        if(s[i]=='(') stk[++top]=i;
        if(s[i]==')') to[stk[top]]=i,to[i]=stk[top],top--;
    }
    printf("%d\n",solve(1,m));
    printf("%d %d\n",ans1,ans2);
    return 0;
}

1.4

考虑暴力分层，对于每层直接建一个段跳跃的链表，每层之间递归处理，简化思维难度。

By GD-J01245

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
#include<cstdio>
#include<cstring>
const int N=1e6+9;
char s[N];int u,n,top,t[N],nx1[N],nx2[N],head[N],c1,c2,b[N];
int gans(int l,int r)
{
//	printf("%d %d\n",l,r);
    if(l==r) return (int)(s[l]-'0');
    if(s[l]=='('&&b[l]==r) return gans(l+1,r-1);
    if(nx1[r]>l)
    {
        int a=gans(l,nx1[r]-1);
        if(a==1){c1++;return 1;}
        return gans(nx1[r]+1,r);
    }
    int a=gans(l,nx2[r]-1);
    if(a==0){c2++;return 0;}
    return gans(nx2[r]+1,r);
}
int main()
{
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    scanf("%s",s+1);n=strlen(s+1);
    for(int i=1;i<=n;++i)
    {
        if(s[i]=='(') top++,t[top]=i;
        if(s[i]==')') b[t[top]]=i,top--;
    }
    for(int i=0;i<=n+1;++i) head[i]=0;
    for(int i=1;i<=n;++i)
    {
        if(s[i]=='(') u++;
        if(s[i]==')') u--;
        if(s[i]=='|') head[u]=i;
        nx1[i]=head[u];
    }
    u=0; for(int i=0;i<=n+1;++i) head[i]=0;
    for(int i=1;i<=n;++i)
    {
        if(s[i]=='(') u++;
        if(s[i]==')') u--;
        if(s[i]=='&') head[u]=i;
        nx2[i]=head[u];
    }
    int anss=gans(1,n);
    printf("%d\n",anss);
    printf("%d %d\n",c2,c1);
}

做法 2

考虑直接从左到右扫，实时维护。具体维护上，也有两种方法：

2.1

预处理的加强版。此做法预处理的不仅是括号的匹配，还有计算顺序的匹配，即完整地分段。例如，0&1|1&(1|1&1) 会将 0&1、1&(1|1&1) 分别在首尾匹配上（相当于暴力加括号，但并不会真的加上而是维护匹配），此时再从左往右扫即可不分优先级地处理答案。

By JS-J00426

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
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+5;
string s;
int sum,sun,to[N],stk[N],stkid,now;
char la;
stack<int>r[N/2];
int main()
{
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    cin>>s;
    int n=s.size();
    for(int i=n-1;i>=0;i--) s[i+1]=s[i];
    for(int i=1;i<=n;i++) to[i]=i+1;
    for(int i=1;i<=n;i++){
        if(s[i]=='(') stk[++stkid]=i-1;
        if(s[i]==')') to[stk[stkid--]]=i;
    }
    for(int i=1;i<=n;i++){
        if(s[i]=='|'){
            if(r[now].size()){
                int TOP=r[now].top();
                r[now].pop();
            	to[TOP]=i-1;
        	}
        	r[now].push(i);
    	}
        if(s[i]=='(') now++;
        if(s[i]==')'){
            if(r[now].size()){
                int TOP=r[now].top();
                r[now].pop();
            	to[TOP]=i;
        	}
            now--;
        }
    }
    if(r[now].size()) to[r[now].top()]=n+1;
    //for(int i=1;i<=n;i++) cout<<to[i]<<' ';cout<<endl;
    for(int i=1;i<=n;i++){
        if(s[i]=='('||s[i]==')') continue;
        if(s[i]=='|'){
            if(la=='1') {sun++;i=to[i];}
        }
        else if(s[i]=='&'){
            if(la=='0') {sum++;i=to[i];}
        }
        else{
            la=s[i];
        }
    }
    cout<<la<<endl<<sum<<' '<<sun;
    return 0;
}

2.2

此做法不需要预处理，甚至不需要开栈。考虑从左往右扫，直接维护答案。如果发生短路，则暴力跳过后面的一段。这个做法的关键在于，只要不发生短路，答案一定取决于后面而与前面完全无关。这个做法中甚至几乎不用处理括号和优先级，因为括号和优先级仅起到分割块的作用，在暴力跳一段时才需要考虑。

By JS-J00837

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
#include<bits/stdc++.h>
#define REP(i,a,n) for(int i=(a);i<(int)(n);++i)
#define pb push_back
using namespace std;
string s;
int tp1,tp2;
int main(){
    freopen("expr.in","r",stdin);
    freopen("expr.out","w",stdout);
    cin>>s;
    int cnt1=0,cnt2=0,ans=0;
    REP(i,0,s.size()){
        if(s[i]=='1'||s[i]=='0')ans=s[i]-'0';
        else if(s[i]=='&'){
            if(ans==0){
                ++cnt1;
                int res=0;
                for(int j=i+1;j<(int)(s.size());++j){
                    if(s[j]=='(')++res;
                    else if(s[j]==')')--res;
                    if((!res)&&s[j]!='&'&&s[j]!='|'){
                        i=j;
                        break;
                    }
                }
            }
        }else if(s[i]=='|'){
            if(ans==1){
                ++cnt2;
                int res=0;
                for(int j=i+1;j<(int)(s.size());++j){
                    if(s[j]=='(')++res;
                    else if(s[j]==')')--res;
                    if(j!=(int)(s.size()-1)&&s[j+1]=='&')continue;
                    if((!res)&&s[j]!='&'&&s[j]!='|'){
                        i=j;
                        break;
                    }
                }
            }
        }
    }
    cout<<ans<<endl;
    cout<<cnt1<<' '<<cnt2<<endl;
    return 0;
}