简答题
偏难
#22110
逻辑表达式(expr)
逻辑表达式(expr)



答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1
#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;
}</pre><pre class="brush:cpp;toolbar:false">//参考代码2
#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;
}</pre><pre class="brush:cpp;toolbar:false">//参考代码3
#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;
}</pre><pre class="brush:cpp;toolbar:false">//参考代码4
#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;
}</pre><p></p>
这道题暂未补解析。