本文最后更新于:2020年10月8日 早上

题意简述

  • 定义两个长度都为 $w$ 的二进制串 $m,n$ 相似的条件为 $\exists i\in [1,w]$ 使得 $m_i=n_i$ 。这里「相似」记作 $\sim$。

  • 现在给定一个 $n\in \mathbb{Z}$ 于一个长度为 $2n-1$ 的二进制串 $s$,求出一个长度为 $n$ 的二进制串 $ans$,使得对于 $s$ 中长度为 $n$ 的所有连接字串构成的集合 $A$ 中,$\forall A_i \sim ans$。如果有多个答案,输出其中一个。

题目分析

正解:$O(n)$

这道题有很多的乱搞做法。我们现在先来分析一下正解。

要使 $ans$ 满足 $\forall A_i \sim ans$,不难发现最简单的方法是将 $s$ 中的 $\dfrac{1}{2}$ 的元素存入 $ans$,这样能确保结果成立。

重要代码:

for (int i = 0; i < int(S.size()); i += 2)
        ans += S[i];

这个算法的时间复杂度为 $O(n)$,由于 $n$ 取值范围小,所以这应该是这道题的正解。并且这道题不会有 $O(1)$ 算法。

下面给出一些其他方法。

更容易理解的 $O(n^2)$ 算法

要使$ans$ 满足 $\forall A_i \sim ans$,我们可以对于 $A_i$,将它的第 $i$ 项存入 $ans$ 中。则首先需要循环求出 $A$,还需要循环依次存入 $ans$ 串中,每次就输出 $ans_i$ 即可。

重要代码:

for (int i = 0; i < n; i++) {
           for (int j = 0; j <= n; j++) {
               temp += a[i + j];
           }
           putchar(temp[i]);
           temp = "";
       }
       putchar('\n');

整体时间复杂度 $O(n^2)$。

最乱搞的做法

直接获得一个随机的二进制串 $q$,然后反复验证其相似性。验证相似性需要的时间复杂度为 $O(n^2)$,而随机生成的二进制串 $q$ 不满足条件的概率是 $\dfrac{1}{2^n}$,设重试 $cnt$ 次,故最终的时间复杂度为 $O(cnt\times n^2)$ 由于 $cnt,n$ 都很小,所以该解法仍然可以通过此题。

重要代码:

 while (true) {
        for (int i = 0; i < N; i++)
            ans[i] = char('0' + rng() % 2);
 
        bool valid = true;
 
        for (int start = 0; start < N; start++) {
            bool match = false;
 
            for (int i = 0; i < N; i++)
                match = match || ans[i] == S[start + i];
 
            valid = valid && match;
        }
 
        if (valid)
            break;
    }
 
    cout << ans << '\n';
}

总结

这道题作为 A 题还是挺有思维难度的。


本文在 CC BY-NC-ND 4.0( https://creativecommons.org/licenses/by-nc-nd/4.0/deed.zh )协议 的前提下,禁止超过文章30%字数的摘录(对于不超过文章30%字数的摘录,要求在醒目位置注明原文作者与原文链接),同时,在未经作者本人手写签名许可的情况下,禁止任何形式的全文转载,禁止发布任何基于本文的再创作。

题解【LGR-(-11)】CSP 2020 第一轮(初赛)模拟 上一篇
CF1405A 题解 下一篇
本博客采用 xCss 的 Valine 评论系统,搭配了 Valine-Admin,垃圾评论将会被过滤。所以在评论的时候,请注意您的语言。如果您的评论被过滤但并非垃圾评论,请发邮件到 luosiweimail@gmail.com 进行申诉。