ZR#331. 【18 提高 3】括号序列(栈)

题意

挺神仙的。首先$60$分暴力是比较好打的。

就是枚举左端点,看右端点能否是$0$

但是这样肯定是过不了的,假如我们只枚举一次,把得到的栈记录下来

那么若区间$(l, r)$是可行的,那么$s_{l - } = s_r$,证明自己yy一下吧。。

然后就是字符串hash乱搞了。。

#include<cstdio>
#include<algorithm>
#include<queue>
#include<cstring>
#include<map>
#define LL long long
#define ull unsigned long long 
using namespace std;
const int MAXN = 1e6 + 10, mod = 1e9 + 7;
inline LL read() {
    char c = getchar(); LL x = 0, f = 1;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
char a[MAXN], s[MAXN];
int top = 0;
ull base = 12, base2 = 233, po1[MAXN], po2[MAXN];
map<ull, LL> mp;
int main() {
    scanf("%s", a + 1);
    LL N = strlen(a + 1), ans = 0;
    ull sum = 0, sum2 = 0;
    mp[0] = 1; po1[0] = 1; po2[0] = 1;
    for(int i = 1; i <= N; i++) po1[i] = po1[i - 1] * base, po2[i] = po2[i - 1] * base2;
    for(int i = 1; i <= N; i++) {
        if(top && a[i] == s[top]) {
            top--;
            sum -= po1[top] * (a[i] - 'a' + 1);
            sum2 -= po2[top] * (a[i] - 'a' + 1);
            
        } 
        else {
            sum += po1[top] * (a[i] - 'a' + 1);
            sum2 += po2[top] * (a[i] - 'a' + 1) ;
            s[++top] = a[i];
        }
        ans += mp[(sum << 5) + sum2];
        mp[(sum << 5) + sum2]++;
     //   printf("%d\n", ans);
    }
    printf("%lld", ans);
    return 0;
}
/*
abaababababbbbbaavbaaaabbbaaaabbabbbaabbabbb
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据结构与算法

洛谷P1481 魔族密码(LIS)

16620
来自专栏程序你好

在c#中,如何序列化/反序列化一个字典对象?

.Net提供的各种序列化的类,通过使用这些类,. Net对象的序列化和反序列化变得很容易。但是字典对象的序列化并不是那么容易。为此,您必须创建一个能够序列化自身...

11710
来自专栏大内老A

yield在WCF中的错误使用——99%的开发人员都有可能犯的错误[上篇]

在定义API的时候,对于一些返回集合对象的方法,很多人喜欢将返回类型定义成IEnumerable<T>,这本没有什么问题。这里要说的是另一个问题:对于返回类型为...

18480
来自专栏康怀帅的专栏

PHP 变量与常量

本文介绍了 PHP 变量与常量。 官方文档:http://php.net/manual/zh/language.variables.php 官方文档:http:...

31140
来自专栏java一日一条

50个常见的 Java 错误及避免方法(第二部分)

System.out.println("Whatdo you want to do?");

12330
来自专栏Android相关

X86 Assemble指令--MOVS指令簇

该指令簇包括: MOVS mem16,mem16:显式指定源操作数与目的操作数 MOVSB:每次移动一个字节 MOVSW:每次移动一个字 MOVSD:每...

15720
来自专栏java工会

Spring中的9种设计模式汇总

又叫做静态工厂方法(StaticFactory Method)模式,但不属于23种GOF设计模式之一。

11920
来自专栏魂祭心

原 What Every Dev need

29480
来自专栏小樱的经验随笔

对X86汇编的理解与入门

本文描述基本的32位X86汇编语言的一个子集,其中涉及汇编语言的最核心部分,包括寄存器结构,数据表示,基本的操作指令(包括数据传送指令、逻辑计算指令、算数运算指...

33030
来自专栏黑泽君的专栏

【小知识】小例子说明Spring的核心思想之一:控制反转。

目的:改写已存在的类的某个方法或某些方法,使方法增强了。装饰设计模式(也即包装设计模式) 口诀:

19010

扫码关注云+社区

领取腾讯云代金券