Problema das Fotografias Solitárias

Este problema envolve uma linha de N vacas, onde cada vaca é classificada como Guernsey (G) ou Holstein (H). Para cada subsequence contígua de pelo menos três vacas, tiramos uma fotografia.дна фотографія.

Uma fotografia é considerada "solitária" se contém apenas uma vaca G ou apenas uma vaca H. Nosso objetivo é contar quantas fotografias solitárias serão descartadas.

Observação do Padrão

Para entender melhor, considere uma fotografia contendo uma vaca específico do tipo H. Para que esta fotografia seja solitária, ela deve ter exatamante uma vaca H e pelo menos duas vagas para vacas G.

Analisando os padrões possíveis para长度 3:

• GGH
• GHG
• HGG

Para comprimento 4, os padrões são:

• GGGH
• GGHG
• GHGG
• HGGG

Percebemos que o número de fotografias solitárias está relacionado à quantidade de vagas G disponíveis em ambos os lados de cada vaca.

Abordagem: Método de Contribuição

A estratégia consiste em analisar cada vaca individualmente e calcular quantas fotografías solitárias ela "contribui". Para cada posição i, precisamos saber:

• Quantas vagas G estão imediatamente à esquerda (esquerda[i])
• Quantas vagas G estão imediatamente à direita (direita[i])

A fórmula de contribuição para cada vaca é:

contribuição = esquerda[i] * direita[i] + max(0, esquerda[i] - 1) + max(0, direita[i] - 1)

Onde:

• esquerda[i] * direita[i]: A vaca H fica no meio, combinendo esquerda[i] escolhas da esquerda com direita[i] escolhas da direita
• max(0, esquerda[i] - 1): A vaca fica no extremo direito, necessitando pelo menos uma vaga à esquerda
• max(0, direita[i] - 1): A vaca fica no extremo esquerdo, necessitando pelo menos uma vaga à direita

Implementação

Cálculo dos Arrays auxiliares

Primeiro, percorremos da esquerda para a direita, calculando quantas vagas G 연속uo existem antes de cada posição.

Depois, percorremos da direita para a esquerda, calculando quantas vagas G contínuas existem depois de cada posição.

Código em C++

#include <iostream>
using namespace std;

const int MAXN = 500005;
typedef long long ll;

int n;
char str[MAXN];
int esquerda[MAXN], direita[MAXN];

int main() {
    cin >> n;
    scanf("%s", str);
    
    // Passada da esquerda para a direita
    int contH = 0, contG = 0;
    for (int i = 0; i < n; i++) {
        if (str[i] == 'H') {
            esquerda[i] = contG;
            contH++;
            contG = 0;
        } else {
            esquerda[i] = contH;
            contG++;
            contH = 0;
        }
    }
    
    // Passada da direita para a esquerda
    contH = 0;
    contG = 0;
    for (int i = n - 1; i >= 0; i--) {
        if (str[i] == 'H') {
            direita[i] = contG;
            contH++;
            contG = 0;
        } else {
            direita[i] = contH;
            contG++;
            contH = 0;
        }
    }
    
    // Cálculo da resposta
    ll resposta = 0;
    for (int i = 0; i < n; i++) {
        resposta += (ll)esquerda[i] * direita[i];
        resposta += max(0, esquerda[i] - 1);
        resposta += max(0, direita[i] - 1);
    }
    
    cout << resposta << endl;
    return 0;
}

Exemplo de Execução

Para a entrada:

5
GHGHG

As subsequence de comprimento 3 são: GHG, HGH, GHG. Cada uma contém exatamente uma vaca de um tipo, tornando-as fotografias solitárias. O resultado é 3.

Complexidade

O algoritmo executa três passadas pela-string de tamanho N, resultando em complexidade O(N) de tempo e O(N) de memória.