正题

题目链接:http://noip.ybtoj.com.cn/contest/90/problem/1

---

题目大意

给出一个$01$序列，求有多少对$(l,p,r)$使得$l<p<r$且$s_p=1$且$s(l,p)=s(p,r)$（$s(l,r)$表示$l\sim r$中$1$的数量）

---

解题思路

定义$S_i$表示$1\sim i$的$1$的个数。

那么如果一个位置为$1$那么就是求有多少个位置$j$使得$S_i-S_j\ge 3$且是奇数。维护一个指针存奇偶个数即可。

如果一个是$0$那么有两种情况，一个是前面第一个$1$的答案，一个是很多个$0$夹着一个$1$。维护一下上一个$1$前$0$的数量即可。

时间复杂度$O(n)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> #define ll long long using namespace std; const ll N=1e6+10; ll idx,n,cnt,eve,odd,ans; char s[N]; int main() {freopen("puzzle.in","r",stdin);freopen("puzzle.out","w",stdout);scanf("%lld%lld",&idx,&n);scanf("%s",s+1);ll k=0,L=0,w=0,last=0,z=0;for(ll i=1;i<=n;i++){cnt+=(s[i]=='1');while(cnt-k-(s[L]=='1')>2){k+=(s[L++]=='1');if(k&1)eve++;else odd++;}if(s[i]=='1'){if(cnt&1)ans+=(w=odd);else ans+=(w=eve);last=z;z=0;}else z++,ans+=w+last;}printf("%lld",ans); }

总结

以上是生活随笔为你收集整理的YbtOJ#20063-[NOIP2020模拟赛B组Day4]古老谜题【统计】的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。