P1061 · OFFICIAL SOLUTION

P1061 挑战不被发现官方题解

Gioush OJ · P1061 挑战不被发现

【题意简述】

至多反转一个区间，使字符串中 APT 的出现次数最少。

【正解】

记原串中 APT 的数量为 $C$ 。只保留所有 APT 与 TPA 事件，分别赋值 $+1$ 与 $-1$ 。反转一个区间会让区间内部的 APT 与 TPA 互换，因此减少量等于事件序列某个连续段的和。

设该 $\pm1$ 序列的最大子段和为 $M$ ，答案为

C-\max(0,M).

用 Kadane 算法在线维护最大子段和即可。

【正确性】

对任意反转区间，完全位于区间内的每个 APT 变成 TPA，每个 TPA 变成 APT，净减少量正是对应连续事件段之和；反之，任意连续事件段都可选择覆盖它且不跨越相邻事件的区间实现。因此最大可减少量恰为 $M$ 。

【复杂度】

时间复杂度 $\mathcal O(|S|)$ ，额外空间复杂度 $\mathcal O(1)$ 。

【参考代码】

1#include <algorithm>2#include <cstdio>3#include <cstring>4 5char S[1000010];6 7int main() {8    int c, T;9    scanf("%d%d", &c, &T);10    while (T--) {11        scanf("%s", S);12        int n = (int)strlen(S), Count = 0, Now = 0, Best = 0;13        for (int i = 0; i + 2 < n; ++i) {14            int Value = 0;15            if (S[i] == 'A' && S[i + 1] == 'P' && S[i + 2] == 'T') Value = 1, ++Count;16            if (S[i] == 'T' && S[i + 1] == 'P' && S[i + 2] == 'A') Value = -1;17            if (Value) Now = std::max(0, Now + Value), Best = std::max(Best, Now);18        }19        printf("%d\n", Count - Best);20    }21    return 0;22}