题目详情题解（0）讨论（0）提交记录（0）

AT_qupc2018_j.Repeat Strings

省选/NOI-

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个由字符 a 和 b 组成的字符串 SS，你可以依次进行若干次以下操作：

  • 从字符串 SS 中选择一个连续的区间 [l,r][l, r]。对于该区间内满足 l≤k≤rl \leq k \leq r 的每个位置 kk，如果 SkS_k 是 a，就将其变为 b；如果 SkS_k 是 b，就将其变为 a。

接下来，有 QQ 个字符串 TiT_i，每个也是由 a 和 b 构成。将每个 TiT_i 重复 1010010^{100} 次，截取长度为 ∣S∣+1|S| + 1 的前缀，得到一个新的字符串 Ti′T'_i。

你的任务是，对于每一个字符串 Ti′T'_i，计算将字符串 SS 变为 Ti′T'_i 最少需要多少次操作。

输入格式

输入以如下格式给出：

$ S $ $ Q $ $ T_1 $ $ T_2 $ ... $ T_Q $

输出格式

输出 QQ 行。每行包含一个整数，表示将 SS 变为 Ti′T'_i 所需的最小操作次数。

数据范围

  • 1≤∣S∣≤2×1051 \leq |S| \leq 2 \times 10^5
  • 1≤Q≤2×1051 \leq Q \leq 2 \times 10^5
  • 1≤∣Ti∣≤2×1051 \leq |T_i| \leq 2 \times 10^5
  • 所有 TiT_i 的长度总和不超过 2×1052 \times 10^5
  • SS 和 TiT_i 仅包含字符 a 和 b

示例解释

对于每个 Ti′T'_i 的具体表现如下：

  • $T'_1 = $ abababababa
  • $T'_2 = $ bbbbbbbbbbb
  • $T'_3 = $ babaabbabab
  • $T'_4 = $ aaaaaaaaaaa

例如，将字符串 SS 变为 T1′T'_1 需要最少 22 次操作。可以按以下步骤实现：babaabbabab → ababbaababa → abababababa。

本翻译由 AI 自动生成

输入输出样例

  • 输入#1

    babaabbabab
4
abab
b
babaabba
aaaaaaaaaaab

    输出#1

    2
4
0
5

输入解题思路，AI测评打分。不知道怎么写?

首页