简答题 偏难
#22110

逻辑表达式(expr)

逻辑表达式(expr)


未登录也能判分,登录后才会记录
答案与解析
正确答案:<pre class="brush:cpp;toolbar:false">//参考代码1 #include &lt;iostream&gt; #include &lt;algorithm&gt; #include &lt;cstdio&gt; #include &lt;cstring&gt; 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&lt;'0'||ch&gt;'9') ch=='-'?w=-1,ch=getchar():ch=getchar(); while(ch&gt;='0'&amp;&amp;ch&lt;='9') s=(s&lt;&lt;1)+(s&lt;&lt;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&lt;&lt;k)+1][k]; return val[x]&lt;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&amp;&amp;a[pos]=='&amp;') { cnt1++; return 0; } if(lft==1&amp;&amp;a[pos]=='|') { cnt2++; return 1; } int rig=slove(pos+1,r); if(a[pos]=='&amp;') return lft&amp;rig; else return lft|rig; } int main() { fio("expr"); scanf("%s",a+1); n=strlen(a+1); for(int i=1;i&lt;=n;i++) { if(a[i]=='(') sta[++top]=i; else if(a[i]==')') rb[sta[top--]]=i; else if(a[i]!='0'&amp;&amp;a[i]!='1') val[i]=sta[top]*2+(a[i]=='&amp;'); if(a[i]!='&amp;'&amp;&amp;a[i]!='|') val[i]=1e8; } mlog[0]=-1; for(int i=1;i&lt;=n;i++) mlog[i]=mlog[i&gt;&gt;1]+1,mn[i][0]=i; for(int j=1;j&lt;=mlog[n];j++) { for(int i=1;i&lt;=n-(1&lt;&lt;j)+1;i++) { int x=mn[i][j-1],y=mn[i+(1&lt;&lt;j-1)][j-1]; mn[i][j]=val[x]&lt;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&lt;bits/stdc++.h&gt; #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]=='('&amp;&amp;str[r]==')'&amp;&amp;to[l]==r){build(l+1,r-1);return;} build(l,to[l]); for(int i=to[l]+1;i&lt;=r;i=to[i+1]+1){ build(i+1,to[i+1]); if(str[i]=='&amp;'){ 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]=='('&amp;&amp;s[r]==')'&amp;&amp;to[l]==r) return solve(l+1,r-1); int val=solve(l,to[l]); for(int i=to[l]+1;i&lt;=r;i=to[i+1]+1){ if(s[i]=='&amp;'){ if(!val) ans1++; else val&amp;=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&lt;=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&lt;=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&lt;=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&lt;bits/stdc++.h&gt; 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&lt;int&gt;r[N/2]; int main() { freopen("expr.in","r",stdin); freopen("expr.out","w",stdout); cin&gt;&gt;s; int n=s.size(); for(int i=n-1;i&gt;=0;i--) s[i+1]=s[i]; for(int i=1;i&lt;=n;i++) to[i]=i+1; for(int i=1;i&lt;=n;i++){ if(s[i]=='(') stk[++stkid]=i-1; if(s[i]==')') to[stk[stkid--]]=i; } for(int i=1;i&lt;=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&lt;=n;i++) cout&lt;&lt;to[i]&lt;&lt;' ';cout&lt;&lt;endl; for(int i=1;i&lt;=n;i++){ if(s[i]=='('||s[i]==')') continue; if(s[i]=='|'){     if(la=='1') {sun++;i=to[i];} } else if(s[i]=='&amp;'){ if(la=='0') {sum++;i=to[i];} } else{     la=s[i]; } } cout&lt;&lt;la&lt;&lt;endl&lt;&lt;sum&lt;&lt;' '&lt;&lt;sun; return 0; }</pre><pre class="brush:cpp;toolbar:false">//参考代码4 #include&lt;bits/stdc++.h&gt; #define REP(i,a,n) for(int i=(a);i&lt;(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&gt;&gt;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]=='&amp;'){ if(ans==0){ ++cnt1; int res=0; for(int j=i+1;j&lt;(int)(s.size());++j){ if(s[j]=='(')++res; else if(s[j]==')')--res; if((!res)&amp;&amp;s[j]!='&amp;'&amp;&amp;s[j]!='|'){ i=j; break; } } } }else if(s[i]=='|'){ if(ans==1){ ++cnt2; int res=0; for(int j=i+1;j&lt;(int)(s.size());++j){ if(s[j]=='(')++res; else if(s[j]==')')--res; if(j!=(int)(s.size()-1)&amp;&amp;s[j+1]=='&amp;')continue; if((!res)&amp;&amp;s[j]!='&amp;'&amp;&amp;s[j]!='|'){ i=j; break; } } } } } cout&lt;&lt;ans&lt;&lt;endl; cout&lt;&lt;cnt1&lt;&lt;' '&lt;&lt;cnt2&lt;&lt;endl; return 0; }</pre><p></p>
这道题暂未补解析。