切糕 小白月赛45

D-切糕_牛客小白月赛45 (nowcoder.com)

今天把我做的一些括号序列的题都写一些

C. Recover an RBS edu132 div2_三木森sam的博客-CSDN博客

这个是cf里的题，多了个问号，问你是否可以通过更改问号，使其变成唯一序列

这题的主要关注点在于唯一性，所以只需要遍历一遍即可，问号用到该用的地方上，然后最后看看是否满足最后的条件即可，不需要想其他的了

 

还有一个这个题，有一点点偏思维。假设'('是1，‘)’是0

然后这里注意是合法的括号序列或者是长度至少为2的回文，注意要是前缀，之前题目读假了所以错了。括号序列10，11（1开头的全部合法）。0...0（0开头的必须再遇到一个0可以构成一个回文）删掉就可以了。然后就按照这个来删就好

代码贴一下：

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define int long long 
typedef long long ll;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5050,INF=0x3f3f3f3f,mod=1e9+7;
map<int,int> mp;
int a[N];
signed main(){
    //IOS; 
    int T;
    T=1;
    //cin>>T;
    while(T--)
    {
        int n;
        cin>>n;
        string ch;
        cin>>ch;
        string c;
        for(int i=0;isize();i++)
        {
            if(ch[i]=='(') c+='1';
            else if(ch[i]==')') c+='0';
        }
        int sum=0,s=0;
        for(int i=0;isize();)
        {
            if(i==c.size()-1) break;
            if(c[i]=='1')
            {
                i+=2;
                sum++;
                s+=2;
                continue;
            }
            if(c[i]=='0')
            {
                int pos=i+1;
                int cnt=0;
                while(possize()&&c[pos]=='1') pos++,cnt++;
                if(pos>=c.size()) break;
                cnt+=2;
                s+=cnt;
                sum++;
                i=pos+1;
            //  cout<
             
            }
        }
        cout<" "<size()-s<<"\n"; 
    }
    return 0;
}
/*
0的话得碰到下一个0
1的话就2 
*/

然后开头的这个题

题意就是给你给你一个括号串，遇到合法的串你可以选择切或者不切，问你有多少种切法

合法：左右括号的数量要是一样的，任意前缀的左括号需要大于等于右括号

这个题就是找到可切的地方，有cnt的地方，然后一个地方有两种选择（切或者不切），所以最后的答案是2^cnt。

那怎么样判断一个位置是不是可切的呢，这里令左括号为1,右括号为-1，然后求前缀

如果某一个前缀是负数，那整个序列都是不合法的所以输出-1

（我刚开始做这题想的是如果负数的怎么办，我以为负数的部分是可以量化的，也就是可以切出来的，但是其实不能，就相当于多了一个右括号，那它是没办法匹配的）

如果在最后的s[n]的位置不等于0了，就相当于也是切不出的，这题你要知道，能切出来的前提是在序列合法的情况下切出的，切只是相当于把一个合法序列切成若干的合法序列而已

然后什么时候可以开始切呢，就是在合法的时候可以切，因为s[i]>0的时候是左括号>右括号，如果等于0，那么刚好，并且可以匹配

代码贴上：

#pragma GCC optimize(1)
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")
#define IOS ios::sync_with_stdio(false), cin.tie(0);
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define int long long
typedef long long ll;
typedef pair<int,int> PAII;
const int N=2e6+10,M=5050,INF=1e18,mod=1e9+7;
int a[N],s[N];
signed main(){
    //IOS;
    int T;
    T=1;
    //cin>>T;
    while(T--)
    {	
    	string ch;
    	cin>>ch;
    	ch=" "+ch;
    	int n=0;
    	for(int i=0;isize();i++)
    	{
			if(ch[i]=='(') a[++n]=1;
			else if(ch[i]==')') a[++n]=-1;
		}
		int f=1,cnt=0;
		for(int i=1;i<=n;i++)
		{
			s[i]=s[i-1]+a[i];
			if(s[i]<0) f=0;
			if(s[i]==0&&i!=n) cnt++;
		//	cout<
		}
		if(s[n]!=0) f=0;
		if(f==0)
		{
			cout<<"-1\n";
			continue;
		}
		int res=1;
		for(int i=1;i<=cnt;i++) res=(res*2)%mod;
		cout<"\n";
    }
    return 0;
}
/*
 
*/