AtCoder比赛记录（二）

这里记录的是这个账号的比赛情况。

ABC300

2023-4-29

Solved:7/8

0->1200

F(Medium-,1846)

给定由o和x组成的字符串\(S\)。将\(S\)复制\(m\)遍，然后将其中\(k\)个x改成o，求改完之后连续的o最多可能有多少个。

Solution：贪心。设最多能改完\(t\)个完整的\(S\)，考虑三类情况：

• 最长连续o段包含了\(t\)个完整的\(S\)

• 最长连续o段包含了\(t-1\)个完整的\(S\)

• 最长连续o段不包含完整的\(S\)

三种情况都可以预处理前缀和，后缀和，然后用双指针处理。注意判断\(m\)能否使上述情况出现。

G(Medium-,2343)

求不超过\(n\)的数中所有质因子都不超过\(k\)的数的个数。\(k \le 100\)。

Solution：双向搜索。将小于\(k\)的（不超过25个）素数分成两组。先dfs第一组素数能拼出的所有数，记录在一个vector里。然后dfs第二组素数能拼出的所有数，在第一个vector中二分查找即可。

ABC299

2023-4-22

Solved:6/8

Unrated

F(Hard-,2366)

给定字符串 \(S\)，求字符串 \(T\) 的数目，使字符串 \(TT\) 是 \(S\) 的字串。

Solution：首先可以想到要尽可能向左边取，才可以使 \(T\) 不重复。

枚举中间的分界点，然后 \(DP\)：\(dp_{i,j}\) 表示两个 \(T\) 的结尾分别是 \(i,j\)。转移方程很好写。

这道题的难点在于状态定义。

G(Medium,2088)

给定一个数组，值域为 \(\{1,2,...,m\}\)，求它的一个子序列，其是 \(1,2,...,m\) 的一个排列，且字典序最小。

Solution：重复两个步骤：

• 找到尽可能短的一段后缀，包含需要的所有数。

• 在上一个选的数到这段后缀的开头之间找到最小数，加入答案序列。

第二步可以直接暴力，能过但能卡。