hdu 3474 Necklace

87 阅读 0 评论 58 点赞

我是靠谱客的博主危机苗条，这篇文章主要介绍hdu 3474 Necklace，现在分享给大家，希望可以做个参考。

把C看成1，J看成-1，那么问题就转化为，有多少段以i结尾，长度为N，且任意i-n+1<=j<=i，sum[i]-sum[j]>=0的区间，由于任意，这n个式子中的最小值也必须满足大于等于0的条件，那么，我们可以对每个i维护一个长度为n的区间内的最大值k，用sum[i]-k来表示sum[i]-max{sum[j]},即min{sum[i]-sum[j]},跟hdu 3415一样的做法

代码:

复制代码

#include<iostream>
#include<memory.h>
#include<string>
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<ctime>
using namespace std;
const int MAX=2000005;
int sum[MAX],pos[MAX],id[MAX],a[MAX],cnt,n,N;
bool ok[MAX];
char s[MAX];
void solve(int k)
{
int i,head=0,tail=0;
pos[0]=0; id[0]=0;
for(i=1;i<=N;i++)
{
while(head<=tail&&i-id[head]>n)
head++;
if(i>n&&sum[i]-pos[head]>=0)
{
if(k)
{
if(n+n-i)
ok[n+n-i]=true;
else
ok[n]=true;
}
else
ok[i-n]=true;
}
while(head<=tail&&pos[tail]<=sum[i])
tail--;
pos[++tail]=sum[i];
id[tail]=i;
}
}
int main()
{
int i,j,k,T,ca;
scanf("%d",&T);
for(ca=1;ca<=T;ca++)
{
scanf("%s",s);
n=strlen(s);
sum[0]=0;
for(i=0;i<n;i++)
{
if(s[i]=='C')
a[i+1]=a[i+1+n]=1;
else
a[i+1]=a[i+1+n]=-1;
}
N=2*n;
for(i=1;i<=N;i++)
{
sum[i]=sum[i-1]+a[i];
}
cnt=0;
memset(ok,false,sizeof(ok));
solve(0);
for(i=1;i<=N;i++)
sum[i]=sum[i-1]+a[N-i+1];
solve(1);
for(i=1;i<=N;i++)
if(ok[i])
cnt++;
printf("Case %d: %dn",ca,cnt);
}
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
77
#include<iostream>
#include<memory.h>
#include<string>
#include<cstdio>
#include<algorithm>
#include<math.h>
#include<stack>
#include<queue>
#include<vector>
#include<map>
#include<ctime>
using namespace std;
const int MAX=2000005;
int sum[MAX],pos[MAX],id[MAX],a[MAX],cnt,n,N;
bool ok[MAX];
char s[MAX];
void solve(int k)
{
int i,head=0,tail=0;
pos[0]=0; id[0]=0;
for(i=1;i<=N;i++)
{
while(head<=tail&&i-id[head]>n)
head++;
if(i>n&&sum[i]-pos[head]>=0)
{
if(k)
{
if(n+n-i)
ok[n+n-i]=true;
else
ok[n]=true;
}
else
ok[i-n]=true;
}
while(head<=tail&&pos[tail]<=sum[i])
tail--;
pos[++tail]=sum[i];
id[tail]=i;
}
}
int main()
{
int i,j,k,T,ca;
scanf("%d",&T);
for(ca=1;ca<=T;ca++)
{
scanf("%s",s);
n=strlen(s);
sum[0]=0;
for(i=0;i<n;i++)
{
if(s[i]=='C')
a[i+1]=a[i+1+n]=1;
else
a[i+1]=a[i+1+n]=-1;
}
N=2*n;
for(i=1;i<=N;i++)
{
sum[i]=sum[i-1]+a[i];
}
cnt=0;
memset(ok,false,sizeof(ok));
solve(0);
for(i=1;i<=N;i++)
sum[i]=sum[i-1]+a[N-i+1];
solve(1);
for(i=1;i<=N;i++)
if(ok[i])
cnt++;
printf("Case %d: %dn",ca,cnt);
}
return 0;
}