Atcoder abc268

發表於 更新於 分類於 ， Disqus： 文章字數： 2.2k 所需閱讀時間 ≈ 7 分鐘
G(概率论,桶排序)Ex(SA,线段树)

https://atcoder.jp/contests/abc268/tasks

G - Random Student ID

n个学生 姓名为小写字母,互不相同

问对于所有 a-z 的排列 决定的字典序下

每个学生 的 名字排名顺序期望

范围

名字长度和 5e5

3s

1024mb

我的思路

先估计一下n

1*26+2*26**2+3*26**3+4*26**3*7 = 546234 > 5e5

n < 26+26**2+26**3+26**3*7 = 141310

显然也不能两两计算

感觉可以 基数排序 先计算每个字符串, 的每一位所在的区间大小

而排序 可以看成 首位的期望偏移 + 第二位的期望偏移 + 第三位的期望偏移

可拆!

例如首位是a, 那么 a > b 则有b的长度贡献, a > c 则有c的长度贡献, 而和b与c的大小无关

1
abcde

a: (len(b)/2+len(c)/2+len(d)/2+…)

ab: a前缀中 空 + len(a)/2 + len(c)/2 + len(d)/2+…

abc: abc前缀中 空 + len(a)/2 + len(b)/2 + len(d)/2+…

其实就是 前缀中 : 空 + (all-len(cur))/2

注意 为前缀只是长度大小导致的不等关系

似乎就AC了

代码

https://atcoder.jp/contests/abc268/submissions/35779478

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
#include <bits/stdc++.h>
#include <atcoder/modint>
using mint = atcoder::modint998244353;
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (ll i=a;i<(ll)n;i++)
ll read(){ll r;scanf("%lld",&r);return r;}

vector<string> ss;
char t[500010];

int main(){
  int n = read();
  int sz=0;
  rep(i,0,n){
    scanf("%s",t);
    sz=max(sz,(int)strlen(t));
    ss.push_back(t);
  }
  vector<mint>ans(n,1); // 1-index
  vector<vector<int>> g = {{}};
  rep(i,0,n)g[0].push_back(i);
  rep(j,0,sz){
    vector<vector<int>> nextg = {};
    for(auto &idx:g){ // idx 前j位一样, 从第j位开始比
      vector<vector<int> > ch2idx('z'-'a'+2); // 空, 'a', .. ,'z'
      for(auto i:idx){
        if((int)ss[i].size() == j) ch2idx[0].push_back(i);
        else ch2idx[ss[i][j]-'a'+1].push_back(i);
      }
      // 空 + (all-空-cur)/2 = (all+空-cur)/2
      for(auto i:idx)if((int)ss[i].size()!=j)ans[i] += mint(idx.size()+ch2idx[0].size()-ch2idx[ss[i][j]-'a'+1].size())/2;
      rep(i,0,'z'-'a'+2)if(ch2idx[i].size()>1)nextg.push_back(ch2idx[i]);
    }
    g=nextg;
  }
  for(auto v:ans)printf("%d\n",v.val());
  return 0;
}

Ex - Taboo

给小写字母字符串S, 可以选任意次 修改S中某个字符为星号

目标是,不包含小写字母$T_1\cdots T_N$ 为子字符串(连续的)

问最少需要操作几次

范围

|S| 5e5

|Ti| 长度和 5e5

4s

1024mb

我的思路

其实就是删除多少个,(然后就把字符串切开了)

剩下的都不包含T中的字符串

对于自身不是 自己的前后缀重叠的T来讲, 就是问T的出现次数

而对于自身有 前后缀重叠的, 比如

1
2
3
4
5
aba
  aba

aaa
 aaa

就不再是 出现次数了

而, 如果这样去搞 ,似乎得 n^2以上

换个角度, 直接切

dp[i] 表示 第i个切掉, 前面的最小切的次数满足条件

dp[i] = min(dp[j]) + 1, 其中j < i 且 s[j+1..i-1] 不包含任何T

显然 对于给定i, 那么 有最小的j满足[j+1..i-1] 不包含任何T , 那么 中间的这些也不包含任何T, 所以可选的j是连续的区间

换句话说,j=f(i), dp[i] = min(dp[f(i)..i-1]) + 1, 这个用数据结构可以快速算出min

如果能快速算出f(i) 就好了

再看 f(i) 显然非严格单调递增, 因为 f(i+1) 显然不小于 f(i),

问题变成 以 i-1 结尾的字符串, 最短出现在t中的长度

因为[f(i-1)..i-1] 相对于 [f(i-1)..i-2] 多出来的全是 s[i-1]结尾的字符串

一个办法是对t建立字典树, 每次去查, 显然这样 可以达到n^2

感觉需要一些字符串技巧

题解

总览

  1. 通过把 St1t2…tn拼起来后, 计算 后缀数组SA,和最长公共前缀LCP数组LA
  2. 计算从 S[i]开始的 最短出现在Ti中的字符串的长度
  3. 计算最少次数, 让[l1,r1],[l2,r2]… 至少包含一个*
  • 构建 SA和LA

例如对样例, 构建字符串

abcdefghijklmn_abcd_ijk_ghi

然后计算SA和LA

LCP 是一段区间的 LA的值, 可以segtree上求

  • 计算多少个字符从S[i]开始和Tj重复

其实就是在SA以后

1
2
3
Tj......_
...
Si......

换句话说 区间 sa[Tj..si] 这一段的最大公共长度应该大于等于Tj的长度

现在要找最小的长度

反过来, 通过tj 去找

对tj, 通过二分找 最大的位置 公共长度大于等于 |tj|, 这样 这一段sa 的min len 都等于|tj|

就是个线段树计算区间min(SA的min) + 二分搜索 + 线段树维护区间min(|tj|的min)

需要注意的是拼接,可能出现如下的情况

……..xxx#xxx#???

这样 去算SA会有问题

Ti开始的 xxx#??? 会大于S末尾的xxx#xxx#???

这样找区间会有未覆盖的S的

一个办法就是 s后面是’a’-1, t后面接’a’-2, 这样保证t如果是s前缀,则一定在s前面

最后就是一个倒着的dp 和我上面想得一样

代码

179行 1900ms

https://atcoder.jp/contests/abc268/submissions/35787022

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
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<(int)n;i++)
#define per(i,a,n) for (int i=n;i-->(int)a;)

#define SEG_ROOT 1,0,n-1
#define SEG_L (o<<1)
#define SEG_R (o<<1|1)
#define mid ((l+r)/2)
#define SEG_L_CHILD SEG_L,l,mid
#define SEG_R_CHILD SEG_R,mid+1,r

int read(){int r;scanf("%d",&r);return r;}
const int INF=0x3f3f3f3f;

// Ex

// 0-index + vector + sort
// SA 下标按照顺序排列
// RK 下标对应顺序index
// h SA 中相邻后缀 最长公共前缀 h[0] = 0; h[i] = 最长公共前缀(s[SA[i]..],s[SA[i-1]..])
template<class T>
void calc_SA_RK(vector<T>& arr, vector<int> &SA,vector<int> &RK, vector<int>&h){
  int n = arr.size();
  RK = vector<int>(n,0);
  SA = vector<int>(n,0);
  iota(SA.begin(),SA.end(), 0);
  sort(SA.begin(),SA.end(), [&](int i,int j){return arr[i] < arr[j];});
  rep(i,1,n) RK[SA[i]] = RK[SA[i-1]] + !(arr[SA[i]] == arr[SA[i-1]]);
  for(int w = 1; w < n; w *= 2) {
    auto RK0 = RK;
    auto rk = [&](int i){return i < n ? RK0[i] : -1;};
    sort(SA.begin(),SA.end(), [&](int i,int j){
        return rk(i) != rk(j) ? rk(i) < rk(j) : rk(i+w) < rk(j+w);
    });
    RK[SA[0]] = 0;
    rep(i,1,n) RK[SA[i]] = RK[SA[i-1]] + !(rk(SA[i]) == rk(SA[i-1]) && rk(SA[i]+w) == rk(SA[i-1]+w));
  }
  // height
  h = vector<int>(n,0);
  int k = 0;
  rep(i,0,n) {
    if (RK[i] == 0) continue;
    if (k) --k;
    while (arr[i + k] == arr[SA[RK[i] - 1] + k]) ++k;
    h[RK[i]] = k;
  }
}

char s[1500010];

vector<int>SA;
vector<int>RK;
vector<int>h;

// ---------- seg0 START ----------
int seg0[6000010]; // seg h

int build0(int o,int l,int r){ // seg h
  if(l==r) return seg0[o]=h[l];
  return seg0[o]=min(build0(SEG_L_CHILD),build0(SEG_R_CHILD));
}

int query0(int o,int l,int r,int st,int sz){ // min(h[st..return]) >= sz
  if(st>r) return r;
  // st <= r
  if(l==r) return seg0[o] >= sz ? l : (l-1);
  if(seg0[o]>=sz) return r;
  int ret = query0(SEG_L_CHILD,st,sz);
  return (ret!=mid)?ret:query0(SEG_R_CHILD,st,sz);
}
// ---------- seg0 END ----------

// ---------- seg1 START ----------
int minl[1500010];
pair<int,int> seg1[6000010]; // {min value,lazy value}
pair<int,int> build1(int o,int l,int r){ // seg h
  if(l==r) return seg1[o]={INF,INF};
  return seg1[o]=min(build1(SEG_L_CHILD),build1(SEG_R_CHILD));
}

void up1(int o,int v){ seg1[o] = {min(seg1[o].first,v),min(seg1[o].second,v)}; }
void down1(int o){
  int v=seg1[o].second;
  up1(SEG_L,v);
  up1(SEG_R,v);
  seg1[o].second=INF;
}
void setMin1(int o,int l,int r,int ql,int qr,int v){
  if(ql<=l&&r<=qr) return up1(o,v);
  down1(o);
  if(ql<=mid) setMin1(SEG_L_CHILD,ql,qr,v);
  if(qr> mid) setMin1(SEG_R_CHILD,ql,qr,v);
  seg1[o].first=min(seg1[SEG_L].second,seg1[SEG_R].second);
}
void applyMin1(int o,int l,int r){
  if(l==r){
    minl[l]=seg1[o].first;
    return ;
  }
  down1(o);
  applyMin1(SEG_L_CHILD);
  applyMin1(SEG_R_CHILD);
}
// ---------- seg1 END ----------

// ---------- seg2 START ----------
int seg2[2000010]; // dp[i] = min(dp[i+1...i+len[i+1]-1])+1
void build2(int o,int l,int r){
  seg2[o]=INF;
  if(l==r)return;
  build2(SEG_L_CHILD);
  build2(SEG_R_CHILD);
}
void set2(int o,int l,int r,int pos,int v){
  if(l==r){
    seg2[o]=min(seg2[o],v);
    return;
  }
  if(pos<=mid)set2(SEG_L_CHILD,pos,v);
  else set2(SEG_R_CHILD,pos,v);
  seg2[o]=min(seg2[SEG_L],seg2[SEG_R]);
}
int query2(int o,int l,int r,int ql,int qr){ // query min
  if(ql<=l&&r<=qr)return seg2[o];
  int lv=(ql<=mid?query2(SEG_L_CHILD,ql,qr):INF);
  int rv=(qr> mid?query2(SEG_R_CHILD,ql,qr):INF);
  return min(lv,rv);
}
// ---------- seg2 END ----------

int main(){
  scanf("%s",s);
  vector<pair<int,int> > off; // t[i] {start place,len}
  int N=read();
  int ns;
  int n=ns=strlen(s);
  rep(i,0,N){
    scanf("%s",s+n);
    int sz=strlen(s+n);
    off.push_back({n,sz});
    n+=sz;
    s[n++]='a'-1;
  }
  vector<char>a; // SA [0..n)
  rep(i,0,n) a.push_back(s[i]);
  calc_SA_RK(a,SA,RK,h);

  // seg0
  build0(SEG_ROOT);
  vector<tuple<int,int,int> > lrv;
  for(auto [i,sz]:off) lrv.push_back({RK[i],query0(SEG_ROOT,RK[i]+1,sz),sz});

  // seg1
  build1(SEG_ROOT);
  for(auto [l,r,v]:lrv) setMin1(SEG_ROOT,l,r,v);
  applyMin1(SEG_ROOT);

  // seg2
  n=ns+1;
  build2(SEG_ROOT);
  set2(SEG_ROOT,n-1,0);
  int r=n-1;
  per(i,0,n-1){
    set2(SEG_ROOT,i,query2(SEG_ROOT,i+1,r)+1);
    r=min(r,i+minl[RK[i]]-1);
  }
  printf("%d\n",query2(SEG_ROOT,0,r));
  return 0;
}

总结

G

没啥难的, 注意到期望可拆就行

Ex

后缀数组 SA

恩 后缀数组还是不熟, 其实应该想到dp的思路的话 正向反向是对称的

所以既然正向想到求一个位置向前字符串, 那么其实反过来就应该想到从一个位置开始向后的字符串了! 那么就自然到后缀数组了

参考

官方题解