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

题意:给你一个由 01&|() 组成的字符串,保证是一个合法的逻辑表达式。其中括号优先级最高,与运算优先级高于或运算,同级之间从左到右算。定义一次短路为,或运算的左边结果为 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&11&(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;
}