gym103438 L. Jason ABC（思维）

本文主要是介绍gym103438 L. Jason ABC（思维），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题意：

给定长为 3n 的 ABC 字符串，每次操作可选一个区间 \([l,r]\) 和一个字符 \(c\in \{A,B,C\}\)，并把区间中的字符全变成 c。求操作次数最少的方案，使 A,B,C 的出现次数相等。

思路：

如果原字符串已经合法，那么不用操作。

只需操作1次的情况：设 \(cA[i,j]\) 为 \([i,j]\) 中 A 出现的次数，B 和 C 同理。假设把区间 \([l,r]\) 变成 A，这就要求 \(cB[1,3n]-cB[l,r]=n\) 且 \(cC[1,3n]-cC[l,r]=n\) 。用双指针找是否存在这样的 \(l,r\)。

若上述两种情况均不满足，那么一定只需操作2次，方案如下：

找最小的 p，使得 \([1,p]\) 中出现次数最多的字符恰出现了 n 次，不妨设该字符为 A。这时还需要 \(n-cB[1,p]\) 个 B，于是把 p 右边的 \(n-cB[1,p]\) 个字符变成 B，再把剩下的数变成 C。

#include <bits/stdc++.h>
using namespace std;
const int N = 9e5 + 5;
int n, m, c[3][N], p;
char s[N], pi;

bool f1(char t)
{
    int x = (t - 'A' + 1) % 3, y = (t - 'A' + 2) % 3;
    for(int l = 1, r = 1; l <= m; l++)
    {
        if(r < l) r = l;
        while((c[x][r]-c[x][l-1] < c[x][m]-n || c[y][r]-c[y][l-1] < c[y][m]-n)
              && r <= m) r++;
        if(c[x][r]-c[x][l-1] == c[x][m]-n && c[y][r]-c[y][l-1] == c[y][m]-n)
            return printf("1\n%d %d %c", l, r, t), 1;
    }
    return 0;
}

void f2()
{
    puts("2");
    int x = (pi - 'A' + 1) % 3, y = (pi - 'A' + 2) % 3;
    char X = x + 'A', Y = y + 'A';
    printf("%d %d %c\n", p+1, p+n-c[x][p], X);
    printf("%d %d %c\n", p+n-c[x][p]+1, m, Y);
}

signed main()
{
    scanf("%d%s", &n, s + 1); m = 3 * n;

    for(int i = 1; i <= m; i++) {
        for(int j = 0; j < 3; j++) c[j][i] = c[j][i-1];
        c[s[i]-'A'][i] = c[s[i]-'A'][i-1] + 1;
        if(!p && c[s[i]-'A'][i] == n) p = i, pi = s[i];
    }

    if(c[0][m] == c[1][m] && c[0][m] == n) return puts("0"), 0;

    if(f1('A') || f1('B') || f1('C')) return 0;

    f2();

    return 0;
}

这篇关于gym103438 L. Jason ABC（思维）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！