首页 > 其他分享 >CSP-J2022-C-逻辑表达式题解

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

时间：2023-03-01 15:55:05浏览次数：46  
标签：include return 运算 int 题解 J2022 freopen now CSP

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

做法 1

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

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

1.1

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

By myself

#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

#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

#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

#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

#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

#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;
}

标签：include,return,运算,int,题解,J2022,freopen,now,CSP
From： https://www.cnblogs.com/cxm1024/p/17168435.html

相关文章

  • Gym100078H-History-of-Football题解
    题目传送门题意：有\(n\)支球队，每两支球队之间都会进行一场较量，赢者积\(3\)分，输者积\(0\)分，如果平局则各积\(1\)分。给出每支球队的最终积分，求方案数。\(n\le8\)......
  • Gym100753D-Carpets题解
    题目传送门题意：有一个\(H\timesW\)的地板和\(n\)个矩形地毯，问是否能不重不漏地填满地板。\(H,W\le100,n\le7\)。考虑朴素的搜索，每次考虑最左上角的没填的位置，枚......
  • Gym100825C-KenKen-You-Do-It题解
    题目传送门题意：在一个矩阵上选中了若干个格子，保证连通。你需要在这些格子中填数，使得：每行每列不能重复，且这些数进行给定运算（可以认为只有加法和乘法）的结果为给定的数值。......
  • Gym100959I-Robots题解
    题意：平面直角坐标系上有\(n\)个机器人，每个机器人有一个上下左右之一的方向，初始所有机器人静止。在第\(0\)秒，你让第一个机器人开始朝它的方向移动，速度为每秒一个单位。......
  • Gym101252B-Kakuro题解
    题目传送门题意：有一个矩阵，每个格子为黑色或白色。你需要向白色格子中填\(1\sim9\)的整整睡。从某一个黑色格子的右侧往右连续的一段极长的白色格子被称为一个run，往下......
  • C#、IIS获取时间带星期或日期问题解决
    ，获取时间老是带星期，如:2018-8-8星期日12:00:00，造成写入数据库时无法识别为时间格式报错。试了修改区域语言和修改指定注册表均无效。   解决方法一：在代码里处理时......
  • SPOJ Query On A Tree IV 题解
    SPOJQueryOnATreeIV题解一个边分治套线段树套堆的题目比较难写但是有不小的启发思路来源和代码都抄自[SPOJ-QTREE4]QUERYONATREEIV题解|KSKUN'sBlog简......
  • [CF282D] Yet Another Number Game 题解
    [CF282D]YetAnotherNumberGame传送门这题可以分三种情况讨论\(n\)的取值。n=1显然，当\(a1\neq0\)时先手可以一下全部取完，后手必败，否则后手必胜。n=2有......
  • AtCoder Beginner Contest 275 A-F 题解
    比赛链接砳赫賏，看懂扣1(A-FindTakahashi模拟。#include<cstdio>#include<algorithm>usingnamespacestd;intn,mx,id=1;intmain(){ intx; scanf("%d......
  • Codeforces Round #854 by cybercats (Div. 1 + Div. 2) A-B题解
    比赛链接A可以发现，每次出去的顺序一定是按照\(n->1\)的顺序。因为新加入的东西只会放在最前面。相应的，如果其已在序列中，则这个操作不会对\(1~n\)的信息产生影响。......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99