题解：AtCoder Beginner Contest AT_abc380_d ABC380D Strange Mirroring

题目大意

给定一个字符串 $S$，执行 $10^{100}$ 次以下操作：

• 首先，令字符串 $T$ 为字符串 $S$ 中所有大写字母变为小写字母，小写字母变为大写字母的结果。
• 其次，将 $T$ 拼接在 $S$ 后面。

接下来，有一些询问：

• 请输出在所有操作执行完成之后 $S$ 的第 $K$ 个字母。

思路

乍一看，好大的数据范围！这题真难！

仔细思考一番发现，我们可以令原始的 $S$ 为一号串，刚开始$T$ 为二号串，然后每一次操作完的字符串就是一号串和二号串的组合。

于是，这题是……找规律？

以下内容为考场上研究的内容：

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 60 61 62 63 64
1  2  2  1  2  1  1  2  2  1  1  2  1  2  2  1  2  1  1  2  1  2  2  1  1  2  2  1  2  1  1  2  2  1  1  2  1  2  2  1  1  2  2  1  2  1  1  2  1  2  2  1  2  1  1  2  2  1  1  2  1  2  2  1

1           2           3           4           5           6           7           8           9           10          11          12          13          14          15          16
1           2           2           1           2           1           1           2           2           1           1           2           1           2           2           1

1                                               2                                               3                                               4                                     
1                                               2                                               2                                               1                                     

解释一下，这堆东西每两行为一组，每组中第一行为位置，第二行为编号（一或二）。第一组是刚才说的一号二号串的组合，第二组就是把第一组中的 1 2 2 1 看作一号串，2 1 1 2 看作二号串，第三组同理。

规律的话嘛，就是可以发现每一层的规律都一样，最后一层就是 1 2 2 1。当然不能直接计算出来了，不过可以递归。单次查询的时间复杂度不高，递归调用的时间复杂度较为合理。$dfs(x)$ 的时间复杂度为 $O(lo{g}_{4}x)$，可以解决本题。

代码

Submission #59860658

原文地址：https://blog.csdn.net/ArmeriaLeap/article/details/143823755

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！