链接
https://codeforces.com/contest/1169/problem/D
题解
我尝试构造出一个不包含合法的
(
1
,
1
,
1
)
(1,1,1)
(1,1,1)三元组的序列 但是发现这样会使得
1
1
1非常稀疏 那么相对的
0
0
0就会很多 我感觉，是不是说只要某种数字的数量多那么一点点，就会使得很多三元组出现？ 对每个位置暴力往前找三元组，可以得到一个最靠后的开头位置 对这个开头位置维护前缀最大值，每个位置的前缀最大值加起来就是答案
代码
#include<bits/stdc++.h>
#define maxn 300010
#define linf (1ll<<60)
#define iinf 0x3f3f3f3f
#define eps 1e-8
#define cl(x) memset(x,0,sizeof(x))
#define mod 1000000007ll
using namespace std
;
typedef long long ll
;
ll
read(ll x
=0)
{
int c
, f
=1;
for(c
=getchar();!isdigit(c
);c
=getchar())if(c
=='-')f
=-f
;
for(;isdigit(c
);c
=getchar())x
=x
*10+c
-48;
return f
*x
;
}
ll a
[maxn
], N
, smin
[maxn
], bd
[maxn
];
vector
<ll
> pos
[2];
char s
[maxn
];
int main()
{
ll i
, N
, ans(0);
scanf("%s",s
+1);
N
=strlen(s
+1);
for(i
=1;i
<=N
;i
++)
{
a
[i
]=s
[i
]-0x30;
}
for(i
=1;i
<=N
;i
++)
{
for(auto it
=pos
[a
[i
]].rbegin();it
!=pos
[a
[i
]].rend();it
++)
{
if(*it
-(i
-*it
)>0 and a
[*it
-(i
-*it
)]==a
[i
])
{
bd
[i
]=*it
-(i
-*it
);
break;
}
}
smin
[i
]=max(smin
[i
-1],bd
[i
]);
if(smin
[i
]>0)ans
+=smin
[i
];
pos
[a
[i
]].emplace_back(i
);
}
cout
<<ans
;
return 0;
}
