20pts求助
查看原帖
20pts求助
160484
cunzai_zsy0531kkksd12楼主2021/2/6 18:12
#include<iostream>
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
typedef long long ll;
const int N=2e4+13,M=5e3+13,mod=1e9+7;
int n,m,l,a[M+10][M],b[N][10],lim[N],ms[N];
ll f[N][10][10];
char s[N];
struct Stack{
	int s[N],t;
	inline void clear(){t=0;}
	inline void push(int x){s[++t]=x;}
	inline void pop(){--t;}
	inline int top(){return s[t];}
	inline bool empty(){return !t;}
};
inline int min(const int &a,const int &b){return a<b?a:b;}
inline int max(const int &a,const int &b){return a>b?a:b;}
inline void work__min(int k,int x,int y){for(int i=1;i<=n;++i) a[k][i]=min(a[x][i],a[y][i]);}
inline void work__max(int k,int x,int y){for(int i=1;i<=n;++i) a[k][i]=max(a[x][i],a[y][i]);}
inline void work_min(int k,int x,int y){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=lim[i];++j){
			int tmp1=0,tmp2=0;
			if(f[x][i][j]){
				for(int p=lim[i];p>=j;--p) tmp1+=f[y][i][p],tmp1%=mod;
				tmp1*=f[x][i][j];tmp1%=mod;
			}
			if(f[y][i][j]){
				for(int p=lim[i];p>=j;--p) tmp2+=f[y][i][p],tmp2%=mod;
				tmp2*=f[y][i][j];tmp2%=mod;
			}
			f[k][i][j]=(tmp1+tmp2)%mod;
			if(f[x][i][j]&&f[y][i][j]) f[k][i][j]-=f[x][i][j]*f[y][i][j]%mod,f[k][i][j]=(f[k][i][j]+mod)%mod;
		}
	}
}
inline void work_max(int k,int x,int y){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=lim[i];++j){
			int tmp1=0,tmp2=0;
			if(f[x][i][j]){
				for(int p=1;p<=j;++p) tmp1+=f[y][i][p],tmp1%=mod;
				tmp1*=f[x][i][j];tmp1%=mod;
			}
			if(f[y][i][j]){
				for(int p=1;p<=j;++p) tmp2+=f[x][i][p],tmp2%=mod;
				tmp2*=f[y][i][j];tmp2%=mod;
			}
			f[k][i][j]=(tmp1+tmp2)%mod;
			if(f[x][i][j]&&f[y][i][j]) f[k][i][j]-=f[x][i][j]*f[y][i][j]%mod,f[k][i][j]=(f[k][i][j]+mod)%mod;
		}
	}
}
inline void work_yih(int k,int x,int y){
	for(int i=1;i<=n;++i){
		for(int j=1;j<=lim[i];++j){
			int tmp1=0,tmp2=0,tmp3=0,tmp4=0;
			if(f[x][i][j]){
				for(int p=1;p<=j;++p) tmp1+=f[y][i][p],tmp1%=mod;
				tmp1*=f[x][i][j];tmp1%=mod;
				for(int p=lim[i];p>=j;--p) tmp2+=f[y][i][p],tmp2%=mod;
				tmp2*=f[x][i][j],tmp2%=mod;
			}
			if(f[y][i][j]){
				for(int p=1;p<=j;++p) tmp3+=f[x][i][p],tmp3%=mod;
				tmp3*=f[y][i][j];tmp3%=mod;
				for(int p=lim[i];p>=j;--p) tmp4+=f[x][i][p],tmp4%=mod;
				tmp4*=f[y][i][j];tmp4%=mod;
			}
			f[k][i][j]=((tmp1+tmp2)%mod+(tmp3+tmp4)%mod)%mod;
			if(f[x][i][j]&&f[y][i][j]) f[k][i][j]-=2*f[x][i][j]*f[y][i][j]%mod,f[k][i][j]=(f[k][i][j]+mod)%mod;
		}
	}
}
inline void solve1(){
	Stack num,op;num.clear();op.clear();
	while(!num.empty()) num.pop();while(!op.empty()) op.pop();
	int tot=m-1;bool flag=0;
	for(int i=1;i<=l;++i){
		if(s[i]>='0'&&s[i]<='9'){
			if(flag||op.empty()) num.push(s[i]-'0'),flag=0;
			else{
				int k=op.top();op.pop();int j=num.top();num.pop();
				if(!k) work__min(++tot,s[i]-'0',j);
				else work__max(++tot,s[i]-'0',j);
				num.push(tot);
			}
		}
		else if(s[i]=='(') flag=1;
		else if(s[i]!=')') op.push(s[i]=='>');
	}
	int res=num.s[1];
	if(!op.empty()){
		for(int i=1,j=2;i<=op.t;++i,++j){
			if(!op.s[i]) work__min(res,res,num.s[j]);
			else work__max(res,res,num.s[j]);
		}
	}
	ll ans=0;
	for(int i=1;i<=n;++i) ans+=a[res][i],ans%=mod;
	printf("%lld\n",ans);
}
inline void solve2(){
	for(int i=1;i<=n;++i){
		for(int j=0;j<m;++j) b[i][j+1]=a[j][i];
		sort(b[i]+1,b[i]+m+1);
		lim[i]=unique(b[i]+1,b[i]+m+1)-b[i]-1;
		for(int j=0;j<m;++j) a[j][i]=lower_bound(b[i]+1,b[i]+lim[i]+1,a[j][i])-b[i];
	}
	Stack num,op;
	while(!num.empty()) num.pop();while(!op.empty()) op.pop();
	bool flag=0;int tot=m-1;
	for(int i=0;i<m;++i)
		for(int j=1;j<=n;++j) f[i][j][a[i][j]]=1;
	for(int i=1;i<=l;++i){
		if(s[i]>='0'&&s[i]<='9'){
			if(flag||op.empty()) num.push(s[i]-'0'),flag=0;
			else{
				int j=num.top();num.pop();int k=op.top();op.pop();
				if(!k) work_min(++tot,s[i]-'0',j);
				else if(k==1) work_max(++tot,s[i]-'0',j);
				else work_yih(++tot,s[i]-'0',j);
				num.push(tot);
			}
		}
		else if(s[i]=='(') flag=1;
		else if(s[i]!=')') op.push(s[i]=='<'?0:(s[i]=='?')+1);
	}
	int res=num.s[1];
	for(int i=1,j=2;i<=op.t;++i,++j){
		if(!op.s[i]) work_min(res,res,num.s[j]);
		else if(op.s[i]==1) work_max(res,res,num.s[j]);
		else work_yih(res,res,num.s[j]);
	}
	ll ans=0;
	for(int i=1;i<=n;++i)
		for(int j=1;j<=lim[i];++j) ans=(ans+f[res][i][j]*b[i][j]%mod)%mod;
	printf("%lld\n",ans);
}
int main(){
	//freopen("expr.in","r",stdin);
	//freopen("expr.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i)
		for(int j=1;j<=n;++j) scanf("%d",&a[i][j]);
	scanf("%s",s+1);l=strlen(s+1);
	bool noyih=1;
	for(int i=1;i<=l;++i)
		if(s[i]=='?') noyih=0;
	if(noyih) solve1();
	else solve2();
	return 0;
}

RT.

这题挂掉之后直接打铁+退役。

2021/2/6 18:12
加载中...