Good Bye 2019

發表於 更新於 分類於 ， Disqus： 文章字數： 884 所需閱讀時間 ≈ 3 分鐘
F (分块算法)

F

原题链接

2600评分

大意

0/1构成的字符串, 如果s[l,r]长度为len,其中1的个数为n(n>0)且len%n == 0,那么这个子字符串为awesome

求awesome子字符串的个数

范围

原字符串长度[1,200'000]

官方题解

https://codeforces.com/blog/entry/72611

题解

首先 想到的就是前缀和+暴力

预处理O(n),计算每个[l->r],只需要O(1)

总的时间代价O(n^2)

显然过不了,然后我赛内想来想去没想到方法了

pref表示前缀和

如果 $r - l + 1 = k \cdot (pref[r] - pref[l - 1])$,那么就是awesome的

变形 $r - k \cdot pref[r] = l - 1 - k \cdot pref[l - 1]$

所以对于k=1->n,计算上面成立有多少对

假设取一个给定的值T

对于 k>T, $r - k \cdot pref[r] = l - 1 - k \cdot pref[l - 1]$ , 也就是这类成立的子字符串包含1的个数比较少,我们遍历 前缀，然后找比它1个数大的值小于等于n/T的，对于所有k>T，总时间代价为O(n * n/T)

对于 k<=T , $-nT \le i - k \cdot pref[i] \le n$ , 对于给定k，遍历O(n) ，总时间代价O(nT)

所以理论上 T=sqrt(n)时，总的时间代价为O(n^(3/2))

代码

这里T取的死值300,没有取sqrt

6224 ms

我自闭了这个TLE11: https://codeforces.com/contest/1270/submission/68136316

然后这个过了: https://codeforces.com/contest/1270/submission/68136440

点compare就换了一下map的位置

另外 我把T设置为450(sqrt(200'000)=447.21359549995793)也TLE11: https://codeforces.com/contest/1270/submission/68136641

这个慢的是后一部分，原因基本就是(map/unordered_map)的代价,优化方案 例如有 数组+pair,最后 sort一下统计(没写)

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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
#define INF 0x3f3f3f3f3f3f3f3f
#define MOD 1000000007
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define foreach(i, v) for (__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++ i)
const double pi = acos(-1.0);
 
// len % (num of 1) == 0
 
// fft?
 
// 10010010
// n/1 has only 1
// n-1 has only 2 of 1
 
// kmp?
 
char s[200010]; // 0->n-1
 
int onecnt = 0;
int onepos[200010]; // 0->n-1
unordered_map<int,int> v2cnt;
 
int n;
int main(){
  scanf("%s",s);
  n = strlen(s);
  rep(i,0,n){
    if(s[i]=='1'){
      onepos[onecnt++]=i;
    }
  }
  int T = 300;
  if(onecnt == 0){
    printf("0\n");
    return 0;
  }
  ll ans = 0;
  int stj = 0;
 
  // ans ==15612){ // n =1000
  //
  // k>T -> precnt <= n/T
  rep(i,0,n){
    int cnt = 0;
    rep(j,stj,onecnt){
      cnt++;
      if(!(cnt<=n/T))break; // 注意 这个是上界，不是精确范围，
      // 0-index
      // i 010 pos 01100 posnext
      // [i -> [pos -> posnext-1] ]
      int pos = onepos[j];
      int posnext = 0;
      if(j == onecnt -1){
        posnext = n;
      }else{
        posnext = onepos[j+1];
      }
      // [lenst+1->lenend] = lenend/cnt-lenst/cnt
      int lenst = pos-i;
      int lenend = posnext-i;
      // printf("%d,[%d,%d]=%d , len:[%d->%d] \n",i,pos,posnext,cnt,lenst,lenend);
      if( (lenend/cnt) >= T){ // 精确的范围
        ans+=(lenend/cnt)- max((lenst/cnt),T);
      }
      // printf("ans=%lld\n",ans);
    }
 
    if(stj < onecnt && onepos[stj] <= i){
      stj++;
    }
  }
  //  cout<<"            ans="<<ans<<endl;
  // k<=T, k=1->T,i=0->n
  rep(k,1,min(T,n)+1){
    v2cnt.clear();
    // i - k * pre[i];
    v2cnt[0]++;
    ll cnt = 0;
    rep(i,0,n){
      cnt+=(s[i] == '1');
      v2cnt[i+1-k*cnt]++;
    }
    for(auto item:v2cnt){
      ll c = item.second;
      ans+=c*(c-1)/2;
      // if(c>1){
      //   printf("k=%d: [%lld,%lld]\n",k,v,c);
      // }
    }
  }
  // ans
  printf("%lld\n",ans);
  return 0;
}

总结

这种分块 首先要看出是分块

然后分块除了实现和算法本身，一个需要注意的就是划分边界的处理，做到不重不漏,不要把理论最大最小上下界当成精确边界，另外因为实现是分块，所以理论上改变划分界限，代码应该有相同输出，可以作为测试方法。