Problema A: Verificação de Ano Bissexto

Conceito: Estruturas condicionais básicas.

O objetivo é determinar se um determinado ano é bissexto. A regra padrão exige que o ano seja divisível por 4, mas não por 100, a menos que também seja divisível por 400.

bool ehBissexto(int ano) {
    return (ano % 4 == 0 && ano % 100 != 0) || (ano % 400 == 0);
}

Problema B: Contagem de Ocorrências em String

Conceito: Manipulação de strings e travessia linear.

Dada uma string, o problema pede a contagem de um caractere específico. A solução envolve iterar sobre cada caractere da string e incrementar um contador quando a condição é satisfeita.

int contarCaractere(const std::string& texto, char alvo) {
    int contador = 0;
    for (char c : texto) {
        if (c == alvo) contador++;
    }
    return contador;
}

Problema C: Jogo de Minimização e Maximização em Árvore

Conceito: Árvores, DFS, Programação Dinâmica (DP).

Dois jogadores movem uma peça a partir da raiz de uma árvore ponderada. O primeiro jogador deseja maximizar a soma dos pesos do caminho, enquanto o segundo deseja minimizá-la. Como a profundidade alterna a cada movimento, os nós em profundidade ímpar são controlados pelo primeiro jogador (maximização) e os de profundidade par pelo segundo (minimização).

A relação de recorrência para o valor ótimo $f[p]$ no nó $p$ é:

$$f[p] = \max_{q \in filhos(p)} (f[q] + w_q) \text{ se a profundidade de } p \text{ for ímpar}$$

$$f[p] = \min_{q \in filhos(p)} (f[q] + w_q) \text{ se a profundidade de } p \text{ for par}$$

long long calcularValorOtimo(int no, int pai, int profundidade, const vector<vector<pair<int, long long>>>& adj) {
    bool maximizar = (profundidade % 2 != 0);
    long long resultado = maximizar ? -1e18 : 1e18;
    
    if (adj[no].size() == 1 && no != 1) return 0;
    
    for (auto& [vizinho, peso] : adj[no]) {
        if (vizinho == pai) continue;
        long long valFilho = calcularValorOtimo(vizinho, no, profundidade + 1, adj) + peso;
        if (maximizar) resultado = max(resultado, valFilho);
        else resultado = min(resultado, valFilho);
    }
    return resultado;
}

Problema D: Atribuição de Valores em Intervalos

Conceito: Conjuntos Disjuntos (DSU), Processamento Offline.

O problema requer aplicar operações de atribuição de 0 ou 1 em intervalos. O estado final de cada posição depende exclusivamente da última operação que a cobriu. Processando as operações de forma offline (da última para a primeira), podemos usar um DSU para pular eficientemente posições já preenchidas.

int pai[1000005];
int encontrar(int x) {
    return pai[x] == x ? x : pai[x] = encontrar(pai[x]);
}

void processarOperacoes(int n, int m, vector<tuple<int, int, int>>& ops, vector<int>& res) {
    for (int i = 1; i <= n + 1; i++) pai[i] = i;
    
    for (int i = m; i >= 1; i--) {
        auto [tipo, l, r] = ops[i];
        int pos = encontrar(l);
        while (pos <= r) {
            res[pos] = tipo;
            pai[pos] = pos + 1;
            pos = encontrar(pos + 1);
        }
    }
}

Problema E: Simulação de Jogo de Cartas

Conceito: Simulação, Algoritmo Guloso.

O problema exige a simulação de um jogo de cartas onde os jogadores devem avaliar suas mãos e jogar de forma gulosa. A estratégia envolve classificar as combinações de cartas em ordem decrescente de força e, em cada turno, selecionar a maior combinação possível que possa vencer a mesa ou descartar cartas para otimizar o estado final.

Problema F: Equação XOR (Versão Simples)

Conceito: Propriedades da operação XOR.

Dados inteiros não negativos $A, B, C$, deve-se encontrar $X \ge 0$ tal que $(A \oplus X) + B = C$. Isolando $X$, temos $A \oplus X = C - B$. Aplicando XOR com $A$ em ambos os lados, obtemos $X = (C - B) \oplus A$. A solução é válida se $C \ge B$.

Problema G: Equação XOR (Versão Intermediária)

Conceito: Programação Dinâmica Bit a Bit.

A equação é $(A \oplus X) + (B \oplus X) = C$. Como a adição envolve transporte (carry) entre bits, resolvemos bit a bit usando DP. O estado $dp[i][carry]$ indica se é possível processar os primeiros $i$ bits com um carry específico para o próximo bit.

bool resolverEquacaoXOR(long long a, long long b, long long c) {
    bool dp[65][2] = {false};
    dp[0][0] = true;
    
    for (int i = 0; i < 62; i++) {
        int bitA = (a >> i) & 1;
        int bitB = (b >> i) & 1;
        int bitC = (c >> i) & 1;
        
        for (int x = 0; x < 2; x++) {
            for (int carry = 0; carry < 2; carry++) {
                if (!dp[i][carry]) continue;
                int soma = (x ^ bitA) + (x ^ bitB) + carry;
                if ((soma & 1) == bitC) {
                    dp[i + 1][soma >> 1] = true;
                }
            }
        }
    }
    return dp[62][0];
}

Problema H: Equação XOR (Versão Avançada)

Conceito: Programação Dinâmica Bit a Bit.

A equação é $(A \oplus X) + (B \oplus X) = C \oplus X$. A abordagem é idêntica à do Problema G, alterando apenas a verificação do bit alvo na transição de estado. A condição de paridade torna-se $(bitX \oplus bitA + bitX \oplus bitB + carry) \pmod 2 == bitC \oplus bitX$.

Problema I: Maior Componente Conexo

Conceito: Busca em Profundidade (DFS), Grafos.

O objetivo é encontrar o tamanho do maior componente conexo em um grafo não direcionado. A solução padrão utiliza DFS ou BFS para traversar o grafo, marcando os nós visitados e calculando o tamanho de cada componente desconectado, retornando o máximo valor encontrado.

int maiorComponente(int n, const vector<vector<int>>& adj) {
    vector<bool> visitado(n + 1, false);
    int maxTam = 0;
    
    for (int i = 1; i <= n; i++) {
        if (!visitado[i]) {
            int tam = 0;
            stack<int> pilha;
            pilha.push(i);
            visitado[i] = true;
            
            while (!pilha.empty()) {
                int no = pilha.top();
                pilha.pop();
                tam++;
                for (int viz : adj[no]) {
                    if (!visitado[viz]) {
                        visitado[viz] = true;
                        pilha.push(viz);
                    }
                }
            }
            maxTam = max(maxTam, tam);
        }
    }
    return maxTam;
}

Problema J: Ordenação por Reversão de Sufixos

Conceito: Algoritmo Guloso.

Para ordenar uma string binária revertendo sufixos, devemos eliminar todas as transições entre 0 e 1. A quantidade mínima de operações é determinada pelo número de blocos contíguos de caracteres alternados. Basta contar as transições de caractere e ajustar para casos onde a string começa com '1' ou é composta apenas por '1's.

int minimoReversoes(const std::string& s, int qtdZeros) {
    int operacoes = 0;
    int n = s.length();
    for (int i = 0; i < n - 1; i++) {
        if (i + 1 == qtdZeros) {
            if (s[i] == s[i + 1]) operacoes++;
        } else {
            if (s[i] != s[i + 1]) operacoes++;
        }
    }
    if (s[0] == '1' && qtdZeros > 0) operacoes++;
    return operacoes;
}

Problema K: Contagem de Picos Locais com Atualizações em Intervalo

Conceito: Árvore de Segmentos (Segment Tree) com Lazy Propagation.

O problema exige adicionar 1 a um intervalo e contar quantos elementos são estritamente maiores que seus vizinhos imediatos (picos locais). A árvore de segmentos deve manter a contagem de picos no intervalo, além dos dois maiores valores nas bordas esquerda e direita de cada nó para verificar a formação de novos picos durante a fusão de intervalos.

struct No {
    int esq, dir;
    int valEsq[2], valDir[2];
    int lazy, picos;
};

void atualizarNo(No& no, const No& filhoEsq, const No& filhoDir) {
    no.picos = filhoEsq.picos + filhoDir.picos;
    no.esq = filhoEsq.esq;
    no.dir = filhoDir.dir;
    
    if (filhoDir.dir > filhoDir.esq && filhoDir.valEsq[0] > filhoDir.valEsq[1] && filhoDir.valEsq[0] > filhoEsq.valDir[0]) {
        no.picos++;
    }
    if (filhoEsq.dir > filhoEsq.esq && filhoEsq.valDir[0] > filhoEsq.valDir[1] && filhoEsq.valDir[0] > filhoDir.valEsq[0]) {
        no.picos++;
    }
    
    no.valEsq[0] = filhoEsq.valEsq[0];
    no.valEsq[1] = filhoEsq.valEsq[1];
    no.valDir[0] = filhoDir.valDir[0];
    no.valDir[1] = filhoDir.valDir[1];
    
    if (filhoEsq.esq == filhoEsq.dir) no.valEsq[1] = filhoDir.valEsq[0];
    if (filhoDir.esq == filhoDir.dir) no.valDir[1] = filhoEsq.valDir[0];
}

Problema L: Correspondência de Strings com Hashing

Conceito: Hash de Strings (String Hashing).

Dadas as strings $s$ e $t$, deve-se verificar se é possível alterar no máximo um caractere em $s$ para que ele se torne um deslocamento cíclico de $t$. A solução consiste em duplicar $t$ e calcular os hashes de todos os seus substrings de tamanho $|s|$. Em seguida, identifica-se o caractere que precisa ser alterado em $s$ (baseado na diferença de frequência de caracteres) e testa-se a substituição calculando o hash em tempo $O(1)$.

typedef long long ll;
const ll BASE = 313;
const ll MOD = 1e9 + 7;

ll calcularHash(const string& str, int inicio, int fim, const vector<ll>& pref, const vector<ll>& pot) {
    ll h = (pref[fim] - pref[inicio - 1] * pot[fim - inicio + 1]) % MOD;
    return (h + MOD) % MOD;
}

bool verificarCorrespondencia(const string& s, const string& t) {
    int n = s.length();
    string tDup = " " + t + t;
    string sExt = " " + s;
    
    vector<ll> prefT(2 * n + 2, 0), pot(n + 2, 1);
    for (int i = 1; i <= 2 * n; i++) {
        prefT[i] = (prefT[i - 1] * BASE + tDup[i]) % MOD;
        if (i <= n) pot[i] = (pot[i - 1] * BASE) % MOD;
    }
    
    set<ll> hashesT;
    for (int i = 1; i <= n; i++) {
        hashesT.insert(calcularHash(tDup, i, i + n - 1, prefT, pot));
    }
    
    vector<ll> prefS(n + 2, 0);
    for (int i = 1; i <= n; i++) {
        prefS[i] = (prefS[i - 1] * BASE + sExt[i]) % MOD;
    }
    
    if (hashesT.count(calcularHash(sExt, 1, n, prefS, pot))) return true;
    
    char alvo = 'a'; 
    for (int i = 1; i <= n; i++) {
        ll hashModificado = (prefS[i - 1] * pot[n - i + 1] + alvo * pot[n - i] + prefS[n] - prefS[i] * pot[n - i]) % MOD;
        hashModificado = (hashModificado + MOD) % MOD;
        if (hashesT.count(hashModificado)) return true;
    }
    return false;
}