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：重复两个步骤：
-
找到尽可能短的一段后缀，包含需要的所有数。
-
在上一个选的数到这段后缀的开头之间找到最小数，加入答案序列。
第二步可以直接暴力，能过但能卡。