CF Educational Round70 题解

Educational Round,顾名思义,教育做人专场

这场比赛巧妙地教育了一个初出茅庐的萌新Oier(我)到底该如何做人(哭晕)。

比赛链接:

$~A$

题意:给你两个二进制字符串$x$和$y$,将$y$左移$k$位,再与$x$相加,得到字符串$s_k$,最后将其反转得到$res_k$。求当$res_k$字典序最小时的$k$。


诡异的贪心……

实不相瞒我想了整整半个多小时(中间伴有间歇性走神)……

其实就是转化的思想,求反串的字典序最小,就是要把正串里面的低位1们尽量消掉。又因为题目里面限制了$x>y$,所以一定存在$x$的二进制表示中至少一个$1$比$y$的最低位$1$靠左。考虑贪心的思想,$x$被消掉的$1$越靠右,反串字典序就越小。所以说我们要找的就是$\boldsymbol{x}$中能被$\boldsymbol{y}$消掉的最靠右的那个$\boldsymbol{1}$的位置

于是扫一遍。

1
2
3
4
5
6
7
8
9
10
11
12
cin >> T ;
while (T --){
int i, posa = 0 , posb = 0 ;
scanf("%s", A + 1) ;scanf("%s", B + 1) ;
int La = strlen(A + 1), Lb = strlen(B + 1) ;
for (i = 1 ; i <= Lb ; ++ i)
if (B[i] == '1') posb = i ; posb = Lb - posb + 1 ;
for (i = 1 ; i <= La ; ++ i)
if (A[i] == '1') if (La - i + 1 >= posb) posa = La - i + 1 ;
// cout << posa << " " << posb << endl ;
printf("%d\n", posa - posb) ;
}

$\it{B}$

题意:给定一个计数器$(x-y)$,对于每次引进的常数$z$,可以选择$\text{((+=x)mod=10)}$ 或者$\text{((+=y)mod=10)}$($\text{mod=}$就是%=)然后把结果再丢到运算里面继续运算。现在给定一个残缺的$z$序列(省略了中间的某些结果),求$0\text{~}9$两两组合的计数器分别至少需要多少步才能还原这个串的运算。


草,我这最短路又是白学了。

首先我们考虑一个显然的$10^4\cdot \Omega(1)$的预处理,就是令$(i-j)$为计数器,从$k$到$o$的最短距离,这玩意儿显然可以BFS,由于是对$10$取模所以大概循环节也在下界为$\Theta(1)$左右酱紫。之后对于询问直接暴力枚举就好了,复杂度大概是$100\cdot O(|S|)\leq 100\times 2,000,000=2e8$……梦想算法……但其实显然那个$100$可以只做$50+$的样子,毕竟是对称的……不过还是梦想算法233

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
int main(){
int i, j, k, o ;
for (i = 0 ; i < 10 ; ++ i)
for (j = 0 ; j < 10 ; ++ j)
for (k = 0 ; k < 10 ; ++ k)
for (o = 0 ; o < 10 ; ++ o){
bool mark[200] ;
dis[i][j][k][o] = -1 ;
memset(mark, 0, sizeof(mark)) ;
q.push((wk){k, 0}) ;
while (!q.empty()){
wk now = q.front() ; q.pop() ;
if (now.num == o && now.cnt){
dis[i][j][k][o] = now.cnt ; break ;
}
if (mark[now.num]) continue ;mark[now.num] = 1 ;
q.push((wk){ (now.num + i) % 10, now.cnt + 1}) ;
q.push((wk){ (now.num + j) % 10, now.cnt + 1}) ;
}
while (!q.empty()) q.pop() ;
}
/*for (i = 0 ; i < 10 ; ++ i)
for (j = 0 ; j < 10 ; ++ j)
for (k = 0 ; k < 10 ; ++ k)
for (o = 0 ; o < 10 ; ++ o)
cout << dis[i][j][k][o] << " " ;*/
cin >> (In + 1) ; int ans = 0, N = strlen(In + 1) ;
for (i = 1 ; i <= N ; ++ i) base[i] = In[i] - '0' ;
for (i = 0 ; i < 10 ; ++ i, puts(""))
for (j = 0 ; j < 10 ; ++ j){ /*qwqwq*/
for (ans = 0, k = 2 ; k <= N ; ++ k){
if (dis[i][j][base[k - 1]][base[k]] == -1) {
printf("-1 "), ans = -1 ; break ;
}
ans += dis[i][j][base[k - 1]][base[k]] ;
}
if (ans > -1) printf("%d ", ans - N + 1) ;
}
}

(代码渲染会自动把tab映射成force-tab我也懒得管了= =)

$\mathcal{C}$

题意:给定一段某个机器人的操作序列WSAD,可以添加一个字符,求最终机器人的最小活动区域面积。


首先显然是行列无关的,所以分开考虑;接着发现最优策略肯定是让某一步相当于没走,但是假设$x_{min}$和$x_{max}$均在这次改动操作的后面,那么缩小$x_{max}$的时候也会缩小$x_{min}$,相当于没缩——所以应找到一个界点,所有的最大值都在左/右边,对应的所有最小值都在右/左边。

由于每一步操作都是有后效性的,所以考虑直接前缀和上求出$min$和$max$就好。

但是考虑无论怎么移动,都不能越过预处理出来的$x_{min}$、$x_{max}$这个界(否则会出现越贪越大)。也就是说假设有一个$x_{max}$,接着过了一会儿有一个$x_{min}$,为了“拔高”$x_{min}$我们必须要添加一个$W$,所以我们必须要保证任何时刻不会出现$x_{max}$在放上一个$W$之后越界的情况,也就是说$x_{min}$和$x_{max}$出现的位置之间必须要一个$S$才能用来抵消掉我们$W$,需要特判。

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
using namespace std ; LL ans ; 
int fhm, fhn, fwm, fwn, pos[2][5], i ;
int T, N, Sw[MAXN], Sh[MAXN] ; char S[MAXN] ;

int main(){
cin >> T ;
while (T --){
fhm = fwm = -Inf, fhn = fwn = Inf ;
scanf("%s", S + 1), N = strlen(S + 1) ;
for (i = 1 ; i <= N ; ++ i){
Sh[i] = Sh[i - 1], Sw[i] = Sw[i - 1] ;
if (S[i] == 'W') Sh[i] = Sh[i - 1] + 1 ;
else if (S[i] == 'S') Sh[i] = Sh[i - 1] - 1 ;
else if (S[i] == 'D') Sw[i] = Sw[i - 1] + 1 ;
else if (S[i] == 'A') Sw[i] = Sw[i - 1] - 1 ;
}//前缀和 : w x h
for (i = 0 ; i <= N ; ++ i) fwm = max(Sw[i], fwm), fwn = min(Sw[i], fwn) ;
for (i = 0 ; i <= N ; ++ i) fhm = max(Sh[i], fhm), fhn = min(Sh[i], fhn) ;
for (i = N ; ~i ; -- i) if (Sh[i] == fhn) { pos[0][4] = i ; break ; } //last_min h
for (i = N ; ~i ; -- i) if (Sw[i] == fwn) { pos[1][4] = i ; break ; } //last_min h
for (i = 0 ; i <= N ; ++ i) if (Sh[i] == fhm) { pos[0][1] = i ; break ; } //first_max h
for (i = 0 ; i <= N ; ++ i) if (Sw[i] == fwm) { pos[1][1] = i ; break ; } //first_max w
for (i = N ; ~i ; -- i) if (Sh[i] == fhm) { pos[0][3] = i ; break ; } //last_max h
for (i = N ; ~i ; -- i) if (Sw[i] == fwm) { pos[1][3] = i ; break ; } //last_max h
for (i = 0 ; i <= N ; ++ i) if (Sh[i] == fhn) { pos[0][2] = i ; break ; } //first_min h
for (i = 0 ; i <= N ; ++ i) if (Sw[i] == fwn) { pos[1][2] = i ; break ; } //first_min w
ans = 1ll * (fwn - fwm - 1) * (fhn - fhm - 1) ; //cout << ans << endl ;
if (pos[0][3] < pos[0][2] && Sh[pos[0][3]] - Sh[pos[0][2]] > 1)
ans = min(ans, 1ll * (fhm - fhn) * (fwm - fwn + 1)) ;
if (pos[1][3] < pos[1][2] && Sw[pos[1][3]] - Sw[pos[1][2]] > 1)
ans = min(ans, 1ll * (fhm - fhn + 1) * (fwm - fwn)) ;
if (pos[0][4] < pos[0][1] && Sh[pos[0][4]] - Sh[pos[0][1]] < -1)
ans = min(ans, 1ll * (fhm - fhn) * (fwm - fwn + 1)) ;
if (pos[1][4] < pos[1][1] && Sw[pos[1][4]] - Sw[pos[1][1]] < -1)
ans = min(ans, 1ll * (fhm - fhn + 1) * (fwm - fwn)) ;
cout << ans << endl ;
pos[0][1] = pos[1][1] = pos[0][2] = pos[1][2] = Inf ;
pos[0][3] = pos[1][3] = pos[0][4] = pos[1][4] = -Inf ;
}
}

emmmm好像当时debug了好久的样子。

$\rm{D}$

题意:构造一个含有1/3/7的串,使得子序列1337的数量恰好为$x$。


这特么就是一个智商题。就是考虑一个最简单的构造133..3337这种,但是不是每一个$x$都可以表示成$\frac{p(p-1)}{2}$这种形式的……所以考虑找出最大的$p~\rm{s.t.}$ $p(p-1)\leq 2x$,然后拼命地向第一组33后面添加7就好了。这样总长度是上限是$2\sqrt x$的,挺稳。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main(){
cin >> T ;
while (T --){
cin >> N ; int p = sqrt(2*N);
for (int i = p ; i <= 2*N ; ++ i){
if (i * (i - 1) > 2 * N) break ;
L1 = i * (i - 1) / 2, L2 = N - L1, L1 = i ;
}
printf("133") ;
for (int i = 1 ; i <= L2 ; ++ i) putchar('7') ;
for (int i = 1 ; i <= L1 - 2 ; ++ i) putchar('3') ;
printf("7\n") ;
}
}

$\mathbb{E}$

题意:给定$N~(\leq 1e5)$个模板串$s_i$和一个文本串$T$,求所有的$s_i+s_j~(i\not=j)$在$T$中出现的次数之和。


嗯,顺带复习了一下$AC$自动机。

思路其实也很简单,就是建俩$AC$自动机,一个跑正串,一个跑反串,然后枚举每个合法的i作为中间的结合位点,乘法原理就好了……但其实这种结论能轻易得出还是建立在$AC$自动机掌握十分扎实的基础上啊。

哦对,似乎对于AC自动机的题目,树形dp才是正确的打开方式。每次重新跳fail根本吃不消。。(CF真的有数据去卡这东西,aaa..aa这种……)

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
char S[MAXN], In[MAXN] ; int N ; 
struct ACm{
queue <int> q ; int cnt ;
int tr[MAXN][27], res[MAXN] ;
int fail[MAXN], ans[MAXN], e[MAXN] ;
#define v(x) tr[rt][x]
void insert(char *s, int Id){
int i, j = strlen(s), k, rt = 0 ;
for (i = 0 ; i < j ; ++ i){
k = s[i] - 'a' ;
if (!v(k)) v(k) = ++ cnt ;
rt = v(k) ;
}
e[rt] ++ ;
}
void build(){
int i, rt = 0 ;
for (i = 0 ; i < 26 ; ++ i) if (v(i)) q.push(v(i)) ;
while (!q.empty()){
rt = q.front(), q.pop() ;
for (i = 0 ; i < 26 ; ++ i){
if (!v(i)) v(i) = tr[fail[rt]][i] ;
else fail[v(i)] = tr[fail[rt]][i], q.push(v(i)) ;
// if (e[fail[v(i)]]) last[v(i)] = fail[v(i)] ; else last[v(i)] = last[fail[v(i)]] ;
}
}
}/*
void work(char *s){
int i, j = strlen(s), p, rt = 0 ;
for (i = 0 ; i < j ; ++ i){
rt = v(s[i] - 'a'), p = rt ;
while(p) res[i] += e[p], p = fail[p] ;
}
}*/
int dfs(int rt){
if (!rt) return 0 ;
if (res[rt] != -1) return res[rt] ;
return res[rt] = e[rt] + dfs(fail[rt]) ;
}
void work(char *s){
memset(res, -1, sizeof(res)) ;
int i, j = strlen(s), p, rt = 0 ;
for (i = 0 ; i < j ; ++ i) rt = v(s[i] - 'a'), ans[i] = dfs(rt) ;
}
}P, Q ; LL ans ;

int main(){
cin >> S >> N ; int i, j ;
for (i = 1 ; i <= N ; ++ i){
scanf("%s", In), P.insert(In, i) ;
j = strlen(In), reverse(In, In + j), Q.insert(In, i) ;
}
P.build(), Q.build() ; j = strlen(S) ;
P.work(S), j = strlen(S) ; reverse(S, S + j) ; Q.work(S) ;
// for (i = 0 ; i < j ; ++ i) cout << P.res[i] << " " ; puts("") ;
// for (i = 0 ; i < j ; ++ i) cout << Q.res[i] << " " ;
for (i = 0 ; i < j ; ++ i) ans += 1ll * P.ans[i] * Q.ans[j - 2 - i] ;
cout << ans << endl ; return 0 ;
}

$\mathfrak{F}$

题意:给定大写字母$A$和$B$的数量,求可以组成多少种不同的最短周期。其中周期的定义式不完全的,即只需要满足$\forall i,s[i]=s[i~\bmod~k]$,$k$就是周期。


这真是神仙题……

下文中用$a,b$表示输入的那俩值。

考虑对于一个合法的$k$而言,假设在这个$k$满足$k=\lfloor n/p\rfloor,p\in \mathbb{N}$,那么$p$就是循环节的数量。现在我们假设有$q_a+q_b=k$,即每一段循环节中$A$的数量和$B$的数量。那么一定需要满足的是$q_a\cdot p\leq a$并且$q_b\cdot p\leq b$。

同时考虑一定会有
$$
q_a \leq \lfloor\frac{a}{p}\rfloor, q_b \leq \lfloor\frac{b}{p}\rfloor
$$
但同时还有一个条件,就是虽然实际上多出去一堆下脚料,但$a_{rest},b_{rest}$必须小于等于$q_a$和$q_b$。也就是说需要有
$$
(p+1)\cdot q_a \geq a,(p+1)\cdot q_b\geq b
$$

美化一下就是

$$
\lceil \frac{a}{p+1} \rceil \leq q_a\leq \lfloor \frac{a}{p} \rfloor \\\
\lceil \frac{b}{p+1} \rceil \leq q_b\leq \lfloor \frac{b}{p} \rfloor
$$

就可以通过从$1$到$n$枚举$p$来求得$q_a$和$q_b$,那么根据定义,$q_a$和$q_b$是一段循环节中的$A$和$B$的数量,所以$q_a+q_b$对$k$产生贡献。

还有一个小问题,就是如何保证一定是最小的$k$。这个其实也很简单。假设对于每一段完整的循环节他同时也自循环,段和段之间$A$和$B$个数一定相同,所以可以考虑直接把每一段的$A$丢到前面,$B$丢到后面,就避免了自循环这种情况。

然后这东西显然是可以数论分块的,所以我们分一下块就做完了.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#define LL long long
#define Mod 1000000007

using namespace std ;
int N, M, L ; LL Ans ;

int main(){
cin >> N >> M, L = N + M ;
for (int g, l = 1, r ; l <= L ; l = r + 1){
g = L / l, r = L / g ;
if (N < g || M < g) continue ;
int ln = (N + g) / (g + 1), hn = N / g ;
int lm = (M + g) / (g + 1), hm = M / g ;
if (hn >= ln && hm >= lm)
Ans += max(0ll, 1ll * (min(hn + hm, r) - max(l, lm + ln) + 1)) ;
}
cout << Ans << endl ; return 0 ;
}

完结撒🌹fa~