【bzoj3770】疯狂的限制

2014年12月8日1,0414

Description

给定k个限制条件,其中第i个条件用c[i],l[i],r[i]表示:
字符c[i]在字符串中的出现次数大等于l[i],小等于r[i]。
若一个字符串满足的限制条件的个数大等于L,小等于R,则称该串为Stenis String
给定一小写字母串s,求s有多少个子串是Steins String。

Input

第一行一个非空的小写字母串s
第二行三个整数k,L,R。
以下k行,每行1个字符和2个整数表示c[i],l[i],r[i]

Output

一个整数,表示答案

Sample Input

elpsycongroo
3 1 2
o 2 4
a 1 2
y 1 3

Sample Output

48

HINT

对于100%的数据 0<=L<=R<=k<=500,0<=l[i]<=r[i]<=|s|,|s|<=10^5

题解

枚举区间左端点l,则对于每个限制,满足该限制的区间右端点r是一个区间s-t。。。
处理每个限制的r的s-t,以及每个位置x作为右端点满足的限制个数cnt[x]
若L<=cnt[x]<=R,左端点为l的答案ans[l]++
ans=∑ ans[i]
这个算什么算法。。。

 

 

  • SkyDec2014年12月8日 上午10:51 回复

    感觉应该算暴力吧

    #1  
  • 蒟蒻2016年5月1日 下午5:38 回复

    Hack
    abaaaaaaa
    1 1 1
    b 0 0

    #2  
    • hzwer2016年5月1日 下午11:18 回复
      admin

      花了20分钟才看懂自己的代码。。。
      已改正

      #21
      • 蒟蒻2016年5月15日 下午8:42 回复

        您程序常数TLE辣

        #22