ZigZagK的博客
[计数]Codeforces1428F【Fruit Sequences】题解
[计数]Codeforces1428F【Fruit Sequences】题解
2020年10月20日 17:47
查看标签

题目概述

CF1428F

解题报告

不是很难,但是要考虑的周全一些。

对于一块连续的 $1$(假设区间是 $[L,R]$ ),我们枚举 $[L,i](i>L)$ 和 $[j,R](j<R)$ 。

对于 $[L,i]$ ,如果想作为最大块产生贡献,那么显然不能向右扩展,只能向左扩展,且最远扩展到第一个比 $[L,i]$ 的块之前。对于 $[j,R]$ 和整个块 $[L,R]$ 同理。

但是我们发现这样会统计重复,因此我们向左扩展时,强制最远扩展到第一个不少于 $[L,i]$ 的块之前,这样就避免左右扩展时统计重复。

还有一个容易忽略的情况,如果对于连续 $1$ 的区间 $[l,r]$ ,$l-1$ 和 $r+1$ 都是 $1$ ,说明 $[l,r]$ 不能向左向右扩展,但是也需要统计。

向左向右扩展利用数据结构就行了,比如二分+ST表。

示例程序

  • 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
#include<cstdio> #include<algorithm> using namespace std; typedef long long LL; const int maxn=500000,LOG=19; int n,LS[maxn+5],RS[maxn+5];char s[maxn+5]; int RMQ[2][maxn+5][LOG+1],lg[maxn+5];LL ans; int Max(int ID,int L,int R) {int k=lg[R-L+1];return max(RMQ[ID][L][k],RMQ[ID][R-(1<<k)+1][k]);} int FindL(int l,int r,int x){ int L=1,R=r-l+1; for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) Max(1,r-mid+1,r)<=x?L=mid+1:R=mid-1; return r-R+1; } int FindR(int l,int r,int x){ int L=1,R=r-l+1; for (int mid=L+(R-L>>1);L<=R;mid=L+(R-L>>1)) Max(0,l,l+mid-1)<=x?L=mid+1:R=mid-1; return l+R-1; } int main(){ scanf("%d%s",&n,s+1); for (int i=1;i<=n;i++) if (s[i]=='1') LS[i]=LS[i-1]+1; else LS[i]=0; for (int i=n;i>=1;i--) if (s[i]=='1') RS[i]=RS[i+1]+1; else RS[i]=0; for (int i=1;i<=n;i++) RMQ[0][i][0]=LS[i],RMQ[1][i][0]=RS[i]; for (int j=1;(1<<j)<=n;j++) for (int i=1;i+(1<<j)-1<=n;i++) RMQ[0][i][j]=max(RMQ[0][i][j-1],RMQ[0][i+(1<<j-1)][j-1]), RMQ[1][i][j]=max(RMQ[1][i][j-1],RMQ[1][i+(1<<j-1)][j-1]); for (int i=2;i<=n;i++) lg[i]=lg[i>>1]+1; for (int i=1;i<=n;i++) if (s[i]=='1'){ int j=i-LS[i]+1,L=FindL(1,j-1,LS[i]-1),R=FindR(i+1,n,LS[i]); ans+=(LL)(j-L+1)*(R-i+1)*LS[i]; if (s[i-1]=='1'){ j=i+RS[i]-1;R=FindR(j+1,n,RS[i]); ans+=(LL)(R-j+1)*RS[i]; } } for (int i=1;i<=n;i++) if (s[i-1]!='1' && s[i]=='1' && RS[i]>=3) for (int j=1;j<=RS[i]-2;j++) ans+=(LL)(RS[i]-2-j+1)*j; printf("%lld\n",ans);return 0; }
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
本文写于 1624 天前,最后更新于 1624 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 Skyscape Plum - Melodic Artist
  2. 2 ほしのおとしもの ああああ
  3. 3 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  4. 4 秘匿されたフォーシーズンズ 上海アリス幻樂団
  5. 5 Ideal and the Real 小西利樹
  6. 6 Undertale Toby Fox
  7. 7 First Steps Lena Raine
  8. 8 Mirror Temple (Mirror Magic Mix) Lena Raine / 2 Mello
  9. 9 City of Tears Christopher Larkin
  10. 10 Tower Of Heaven (You Are Slaves) Feint
Skyscape - Plum - Melodic Artist
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

Loading