「BZOJ3770」疯狂的限制

给定k个限制条件，其中第i个条件用c[i],l[i],r[i]表示：

字符c[i]在字符串中的出现次数大等于l[i]，小等于r[i]。

若一个字符串满足的限制条件的个数大等于L，小等于R，则称该串为Stenis String

给定一小写字母串s，求s有多少个子串是Steins String。

第一行一个非空的小写字母串s

第二行三个整数k,L,R。

以下k行，每行1个字符和2个整数表示c[i],l[i],r[i]

一个整数，表示答案

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

48

对于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]

这个算什么算法。。。

#include<queue>
#include<cstdio>
#include<cstring>
#include<iostream>
#define inf 1000000000
#define pa pair<int,int>
#define ll long long 
using namespace std;
int read()
{
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9')ch=getchar();
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x;
}
ll ans;
char ch[100005];
int K,L,R,n,now;
int sum[26][100005],cnt[100005];
int c[505],x[505],y[505];
int l[505],r[505];
void solve(int p)
{
	for(int i=1;i<=K;i++)
    {
		while((r[i]<n&&sum[c[i]][r[i]+1]-sum[c[i]][p-1]<=y[i])||r[i]<p)
		{
			r[i]++;
            if(sum[c[i]][r[i]]-sum[c[i]][p-1]<=y[i])
            {
                cnt[r[i]]++;            
                if(cnt[r[i]]==R+1)now--;
                if(cnt[r[i]]==L)now++;
            }
		}
		while((l[i]<=n&&sum[c[i]][l[i]]-sum[c[i]][p-1]<x[i])||l[i]<p)
		{
            if(l[i]&&sum[c[i]][l[i]]-sum[c[i]][p-1]<x[i])
                {
                    cnt[l[i]]--;
                    if(cnt[l[i]]==L-1)now--;
                    if(cnt[l[i]]==R)now++;
                }
			l[i]++;
		}
	}
}
int main()
{
	scanf("%s",ch+1);
	K=read();L=read();R=read();
	char t[5];
	for(int i=1;i<=K;i++)
	{
		scanf("%s",t);
		c[i]=t[0]-'a';
		x[i]=read(),y[i]=read();
	}
	n=strlen(ch+1);
	for(int i=1;i<=n;i++)
	{
		for(int j=0;j<26;j++)
			sum[j][i]=sum[j][i-1];
		sum[ch[i]-'a'][i]++;
	}
	if(L==0)now=n;
	solve(1);
	for(int i=1;i<=n;i++)
	{
		ans+=now;
		if(i+1<=n)solve(i+1);
		if(cnt[i]<=R&&cnt[i]>=L)now--;
	}
	printf("%lld\n",ans);
	return 0;
}

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

#include<queue>

#include<cstdio>

#include<cstring>

#include<iostream>

#define inf 1000000000

#define pa pair<int,int>

#define ll long long

using namespace std;

int read()

{

int x=0;char ch=getchar();

while(ch<'0'||ch>'9')ch=getchar();

while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

return x;

}

ll ans;

char ch[100005];

int K,L,R,n,now;

int sum[26][100005],cnt[100005];

int c[505],x[505],y[505];

int l[505],r[505];

void solve(int p)

{

for(int i=1;i<=K;i++)

{

while((r[i]<n&&sum[c[i]][r[i]+1]-sum[c[i]][p-1]<=y[i])||r[i]<p)

{

r[i]++;

if(sum[c[i]][r[i]]-sum[c[i]][p-1]<=y[i])

{

cnt[r[i]]++;

if(cnt[r[i]]==R+1)now--;

if(cnt[r[i]]==L)now++;

}

while((l[i]<=n&&sum[c[i]][l[i]]-sum[c[i]][p-1]<x[i])||l[i]<p)

{

if(l[i]&&sum[c[i]][l[i]]-sum[c[i]][p-1]<x[i])

{

cnt[l[i]]--;

if(cnt[l[i]]==L-1)now--;

if(cnt[l[i]]==R)now++;

}

l[i]++;

}

int main()

{

scanf("%s",ch+1);

K=read();L=read();R=read();

char t[5];

for(int i=1;i<=K;i++)

{

scanf("%s",t);

c[i]=t[0]-'a';

x[i]=read(),y[i]=read();

}

n=strlen(ch+1);

for(int i=1;i<=n;i++)

{

for(int j=0;j<26;j++)

sum[j][i]=sum[j][i-1];

sum[ch[i]-'a'][i]++;

}

if(L==0)now=n;

solve(1);

for(int i=1;i<=n;i++)

{

ans+=now;

if(i+1<=n)solve(i+1);

if(cnt[i]<=R&&cnt[i]>=L)now--;

}

printf("%lld\n",ans);

return 0;

}

hzwer.com _ Home | http://hzwer.com

Description

Input

Output

Sample Input

Sample Output

HINT

题解

分类目录

热门文章

Myfriends

近期评论