Relatório de Soluções para P11323 - Cartas Felizes

Análise do Problema

O objetivo deste problema é minimizar o número de jogadas para descartar todas as cartas. Temos n tipos de cartas, cada um com quantidade v_i. As jogadas possíveis são: - Carta única: 1 carta, 1 jogada. - Par: 2 cartas iguais, 1 jogada. - Trio com acompanhante: 3 cartas iguais + 1 carta qualquer, 1 jogada. - Explosão: 4 cartas iguais, 1 jogada.

A estratégia ótima consiste em maximizar jogadas que utilizam 4 cartas, pois são as mais eficientes. Observamos que "explosão" pode ser vista como um caso especial de "trio com acompanhante" (3 cartas X + a própria X como acompanhante). Assim, podemos unificar o problema para maxmiizar o número de "trios com acompanhante".

Conceito Central

Cada "trio com acompanhante" consiste em um componente de "trio" (X,X,X) e um "acompanhante" (Y). A solução envolve: 1. Maximziar a formação de trios a partir das cartas disponíveis. 2. Usar cartas remanescentes como acompanhantes. 3. Tratar cartas que não puderem formar essas estruturas.

Algoritmo Guloso

Dividimos cada tipo de carta em: - Trios: floor(v_i / 3) trios por tipo. - Resto: v_i mod 3 cartas (0, 1 ou 2).

Estatísticas: - total_trios: número total de trios formados. - resto_um: quantidade de tipos com 1 carta remanescente. - resto_dois: quantidade de tipos com 2 cartas remanescentes.

Em seguida, realizamos o pareamento: 1. Priorizamos usar as cartas com resto 1 como acompanhantes para trios. 2. Usamos cartas com resto 2 como acompanhantes, esgotando-as em pares. 3. Se sobrarem trios sem acompanhantes, podemos combiná-los entre si (dois trios consomem 2 jogadas).

Implementação

#include <cstdio>
#include <algorithm>

using ll = long long;

void resolver() {
    int n;
    scanf("%d", &n);
    ll soma_trios = 0, cnt_um = 0, cnt_dois = 0;
    
    for (int i = 0; i < n; ++i) {
        ll quantidade;
        scanf("%lld", &quantidade);
        soma_trios += quantidade / 3;
        if (quantidade % 3 == 1) cnt_um++;
        if (quantidade % 3 == 2) cnt_dois++;
    }
    
    ll trios_iniciais = soma_trios;
    ll parcial;
    
    parcial = std::min(cnt_um, soma_trios);
    cnt_um -= parcial;
    soma_trios -= parcial;
    
    parcial = std::min(cnt_dois * 2, soma_trios);
    cnt_dois -= parcial / 2;
    soma_trios -= parcial;
    
    printf("%lld\n", trios_iniciais + cnt_um + cnt_dois);
}

int main() {
    int casos;
    scanf("%d", &casos);
    while (casos--) resolver();
    return 0;
}
</algorithm></cstdio>

Relatório de Soluções para P11324 - Orador

Análise do Problema

Precisamos maximizar o lucro diário, dado por: receita das três cidades menos a distância percorrida. Para consultas (x, y), devemos encontrar a cidade z que maximize:

Lucro = c_x + c_y + c_z - dist(x,z) - dist(z,y)

Transformação da Equação

Notando que dist(x,z) + dist(z,y) = dist(x,y) + 2 * dist(z, caminho(x,y)), reescrevemos:

Lucro = c_x + c_y - dist(x,y) + max_z { c_z - 2 * dist(z, caminho(x,y)) }

Definimos D[u] = max_v { c_v - 2 * dist(u,v) }. A resposta torna-se:

Lucro = c_x + c_y - dist(x,y) + max_{u no caminho} D[u]

Implementação com DP de Re-Raiz e LCA

A solução envolve: 1. Cálculo de D[u] para todos os nós usando DP de re-raiz (cima-baixo e baixo-cima). 2. Preparação de estruturas para consultas de caminho máximo (LCA com tabela de potências de 2).

// Código adaptado para brevidade - estrutura mantida
// Funções principais:
// - dfs1: calcula down1, down2 para subárvores
// - dfs2: calcula up para o restante da árvore
// - consulta_caminho: obtém max D[u] no caminho

Relatório de Soluções para P11325 - Fila Monotônica

Análise do Problema

O objetivo é maximizar a soma das contribuições ao longo de consultas. Cada contribuição ocorre quando uma carta é removida da fila por uma carta maior. A condição para que a carta i contribua é que a posição R[i] (primeira carta maior à direita) seja acessada.

Modelagem com Programação Dinâmica

A transformação leva a maximizar a soma de c_i para quaisquer sequências r'_1 ≤ r'_2 ≤ ... ≤ r'_n com r'_i ≥ R[i]. A DP dp[i][j] representa a soma máxima até a posição i com r'_i = j.

Otimização com Segment Tree

A transição dp[i][j] = ([j ≥ R[i]] * c_i) + max_{k≤j} dp[i-1][k] pode ser otimizada usando uma árvore de segmentos com operações de intervalo (adição e atribuição condicional). O algoritmo final opera em O(n log n).

Relatório de Soluções para P11326 - Jogo XA

Análise do Problema

Alice (XOR) e Bob (AND) alternam jogadas. Alice vence se o bit final for 1. A análise de paridade e estrutura da sequência 01 leva às condições de vitória: 1. Os zeros devem aparecer em um bloco contínuo. 2. A paridade do número de uns deve satisfazer: C % 2 != floor((n-1)/2) % 2.

Contagem com Matrizes de Transição

Modelamos o problema com DP de estados (fase, paridade) e matriz de transição 6x6. Para sequências longas, usamos exponenciação rápida de matrizes. As restrições de Bob são tratadas como pontos fixos, dividindo a sequência em segmentos livres.

Otimização com Exponenciação de Matrizes por Partes

Para tempos limitados, pré-calculamos potências da matriz de transição usando uma técnica similar à exponenciação rápida por blocos, reduzindo a complexidade das consultas.