我们可以这么想：考虑DP。 f[i]表示以ii为左端点的合法区间个数。令pos[i]表示以ii为左端点，最靠左的合法右端点。那么有如下转移： f[i]=f[pos[i]+1]+1. 后面的“+1”表示[i……pos[i]]这段合法区间，f[pos[i]+1]表示在这段合法区间的基础上，还可以在后面拼接更多合法区间。那么我们的目的就是求pos[i], 考虑一段区间为什么合法？我们令左括号为1，右括号为-1，然后对于每一行单独求前缀和。那么对于每行单独考虑，一个区间[l,r]需要满足2个限制： sum[r]−sum[l−1]=0 区间中任意一点i满足sum[i]−sum[l−1]>=0 我们考虑分开处理这2个限制。对于每个左端点i，处理出使得区间前缀为负的第一个点，那么只要右端点不超过这个点，就满足第二点限制。对于同一列的每一行都求出这个值，然后取min，得到值t,表示第i列的右端点只要不超过t就可以对k行都满足第二点限制。那么令这个最小的，令左端点i不满足第二点限制的右端点为lim[i] 那么继续思路：然后从大到小枚举列i，那么我们要处理的就是第一点限制。只需要查询最近的一个右端点满足当前列的k行与第i−1列的k行相同即可，如果这个最近的右端点都大于等于lim[i],那么对于这个左端点就没有合法方案了。否则我们就找到了pos[i]. 那么这两个东西应该如何求呢？求lim[i]: 先对每一行求出对应的右端点，然后取min即可，接下来讲如何对于每行求这个右端点。如果有右端点满足使得以i为左端点的区间前缀和为负，那么肯定会有一个右端点最先满足这个东西，也就是sum[j]−sum[i−1]=−1.那么我们查询满足sum[j]=sum[i−1]−1的最小值即可。这个我们从大到小枚举i,用minn[i]表示到当前为止，值为i的点的最小下标是多少，然后就可以直接得到了。求pos[i]: 用和上面类似的方法，只不过我们这次是要找一个使得k元组相等的最小j。因为k很小，所以可以把k个值都存到map里暴力找。 code ```cpp /* Name: luogu P3059 [USACO12NOV]同时平衡线Concurrently Balanced Strings Copyright: 网络题解、ccsc Author: ccsc Date: 15-10-19 14:45 Description: */ #include using namespace std; #define ri register int #define ll long long #define inf 2139062143 ll ans,f[100100]; int lim[100100],minn[100100],n,m; char s[100100]; map M; struct node{ int s[12];signed ll opt; friend bool operator ==(node a,node b) { for(ri i=1;i<=m;i++)if(a.s[i]!=b.s[i]) return false; return true; } }sum[100100]; inline void upmax(int &a,int b){if(b>a)a=b;} inline void upmin(int &a,int b){if(b'9'){ if(ch=='-')f=1; ch=getchar(); } while(ch<='9'&&ch>='0'){ x=(x<<3)+(x<<1)+(ch^48); ch=getchar(); } return f?-x:x; } int main() { m=read(); n=read(); for(ri i=1;i<=m;i++) { scanf("%s",s+1); for(ri j=1;j<=n;j++) sum[j].s[i]=sum[j-1].s[i]+((s[j]==')')?-1:1); } for(ri i=1;i<=n;i++) lim[i]=inf; for(ri i=1;i<=m;i++) { memset(minn,127,sizeof(minn)); for(ri j=n;j;j--)//对于每行的每个点找右边的，最近的，区间和为-1的点(比当前前缀小1 { upmin(minn[(sum[j].s[i]+50000)],j);//先加入，防止第一个括号是右括号 upmin(lim[j],minn[(sum[j-1].s[i]-1+50000)]);//判断[l, r]=0,需要用到sum[l - 1]和sum[r] } } for(ri i=1;i<=n;i++) for(ri j=1;j<=m;j++) sum[i].opt=sum[i].opt*13+sum[i].s[j]; for(ri i=n;i;i--) { int pos=M[sum[i-1].opt];//找最小的和当前l - 1前缀相同的前缀 if(pos&&pos

A21283.并发平衡字符串

题目描述

输入格式

输出格式

输入输出样例