P8793 题解

Register_int · 2023-04-18 22:38:51 · 题解

之前两个变量打错了，谢罪。

先暴论一下题解区全是水过去的，再锐评一下数据水的要死乱搞都能过。

首先字符串内部的先不管，手动统计一下即可。接下来能拼接的也只有这几类：

• 前缀为 o 的：

  • 前缀为 o，后缀为 o。
  • 前缀为 o，后缀为 ow。
  • 前缀为 o，后缀为 ww。

• 前缀为 wo 的：

  • 前缀为 wo，后缀为 o。
  • 前缀为 wo，后缀为 ow。
  • 前缀为 wo，后缀为 ww。

• 前缀为 ww 的：

  • 前缀为 ww，后缀为 o。
  • 前缀为 ww，后缀为 ow。
  • 前缀为 ww，后缀为 ww。（由于两端封死可以不需要计数）

• 单独一个 w。

由于匹配 w 需要用两个字符串，显然是不优的，所以在动态加入字符串时应单独储存该类字符串数量，最后再单独计算。

显然，我们关心的只是字符串能进行合并的次数，而将新加入的字符串接在已匹配的字符串之前或之后都没有区别。因此，可以直接考虑默认往字符串两端合并。然而合并的优先级仍需继续讨论。

维护每种字符串的个数，加入时讨论该字符串的前后两端即可。具体分讨实现需要注意以下细节：

• 先处理 o-o 与 o-ow、wo-o 可以连成一串。

• 之后处理 o-ow、wo-o 与一端封死的情况合并。

• 接着处理 o-o、wo-ow 与一端封死的情况合并。

• 再处理一端封死的情况相互合并，如 ww-ow 与 o-ww 合并、ww-o 和 wo-ww 合并。

• 然后处理 o-o 与 wo-ow 合并。

• 最后处理 ?-o、w 与 o-? 合并，以及 o-o 与 w 合并。

详见代码。

AC 代码

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int MAXN = 1e6 + 10;

int cnt[9], t[9], ans;

/*
0: o-o
1: o-ow
2: o-ww

3: wo-o
4: wo-ow
5: wo-ww

6: ww-o
7: ww-ow
8: ww-ww 不用管 

w: w
*/

inline 
int merge() {
    int k = 0, res = 0;
    for (int i = 0; i < 9; i++) t[i] = cnt[i];

    // o-o, wo-ow

    if (t[0] || t[4]) res += t[1] + t[3], t[1] = t[3] = 0;

    // o-ow, wo-o

    if (t[1] && (t[2] || t[7])) res += t[1], t[1] = 0;
    if (t[3] && (t[5] || t[6])) res += t[3], t[3] = 0;

    // 2:o-ww, 5:wo-ww

    if (t[0] && t[5]) k = min(t[0], t[4]), res += k << 1, t[0] -= k, t[4] -= k;
    k = min(t[0], t[5]), res += k, t[0] -= k, t[5] -= k, t[2] += k;

    if (t[2] && t[4]) k = min(t[0], t[4]), res += k << 1, t[0] -= k, t[4] -= k;
    k = min(t[2], t[4]), res += k, t[2] -= k, t[4] -= k, t[5] += k;

    k = min(t[0], t[5]), res += k, t[0] -= k, t[5] -= k, t[2] += k;

    // 6:ww-o, 7:ww-ow

    if (t[0] && t[7]) k = min(t[0], t[4]), res += k << 1, t[0] -= k, t[4] -= k;
    k = min(t[0], t[7]), res += k, t[0] -= k, t[7] -= k, t[6] += k;

    if (t[4] && t[6]) k = min(t[0], t[4]), res += k << 1, t[0] -= k, t[4] -= k;
    k = min(t[4], t[6]), res += k, t[4] -= k, t[6] -= k, t[7] += k;

    k = min(t[0], t[7]), res += k, t[0] -= k, t[7] -= k, t[6] += k;

    // 2:o-ww, 5:wo-ww, 6:ww-o, 7:ww-ow

    k = min(t[2], t[7]), res += k, t[2] -= k, t[7] -= k;
    k = min(t[5], t[6]), res += k, t[5] -= k, t[6] -= k;

    // o-ow, wo-o

    if (t[1]) res += t[1] - 1, t[1] = 1;
    if (t[3]) res += t[3] - 1, t[3] = 1;

    // o-o, wo-ow

    k = min(t[0], t[4]);
    if (k && t[0] == t[4]) res--, t[1] < t[3] ? t[1]++ : t[3]++;

    // o-o + wo-ow : wo-ow + o-o

    t[0] -= k, t[4] -= k, res += k << 1;

    // ?-o + w + o-?, o-o + w + o-o + ... 

    int pre = t[3] + t[6], suf = t[1] + t[2];

    k = min({ pre, suf, t[8] }), pre -= k, suf -= k, t[8] -= k, res += k;
    if (!(k | pre | suf)) t[0] = max(t[0] - 1, 0); // 需要一个 ?-o 或 o-? 
    return res + min(t[0], t[8]);
}

int n, m; char s[MAXN];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        scanf("%s", s), m = strlen(s);
        for (int i = 0; i <= m - 3; i++) if (s[i] == 'o' && s[i + 1] == 'w' && s[i + 2] == 'o') ans++;
        // w
        if (m == 1 && *s == 'w') cnt[8]++;
        // o-?
        else if (*s == 'o' && s[m - 1] == 'o') cnt[0]++;
        else if (*s == 'o' && s[m - 2] == 'o' && s[m - 1] == 'w') cnt[1]++;
        else if (*s == 'o' && s[m - 2] == 'w' && s[m - 1] == 'w') cnt[2]++;
        // wo-?
        else if (*s == 'w' && s[1] == 'o' && s[m - 1] == 'o') cnt[3]++;
        else if (*s == 'w' && s[1] == 'o' && s[m - 2] == 'o' && s[m - 1] == 'w') cnt[4]++;
        else if (*s == 'w' && s[1] == 'o' && s[m - 2] == 'w' && s[m - 1] == 'w') cnt[5]++;
        // ww-?
        else if (*s == 'w' && s[1] == 'w' && s[m - 1] == 'o') cnt[6]++;
        else if (*s == 'w' && s[1] == 'w' && s[m - 2] == 'o' && s[m - 1] == 'w') cnt[7]++;

        printf("%d\n", ans + merge());
    }
}