Codeforces Round #138 (Div. 2)

2024-10-14 09:16:05

A. Parallelepiped

枚举其中一边，计算其他两条边。

B. Array

模拟。

C. Bracket Sequence

栈。

D. Two Strings

\(pre[i]\)表示第i个参与匹配的最长前缀。
\(suf[i]\)表示\([i,n]\)能匹配的最大后缀，可以不包括位置i。
如果存在\(pre[i]==0\ or\ pre[i]+suf[i+1]<m\)，说明位置i不能够拼成串\(t\)。
\(pre[i]\)：如果\(i\)匹配了长度\(pre[i]\)，那么所有位置\(j \gt i\)且字符为\(t[pre[i]+1]\)的匹配长度至少为\(pre[i]+1\)，那么可以用线段树维护区间最值即可。
上述做法是比较麻烦的，用\(p[i][j]\)表示距离\(i\)最近的字符\(j\)的位置，可以比较方便地求，空间复杂度比较大就是。

E. Partial Sums

单独考虑每个数在每个位置的贡献即可，出现的次数为组合数。

最新文章

热门文章