Ordenação e Seleção Ótima

Tema: Algoritmos de ordenação, enumeração e estratégias gananciosas

Abordagem: Utilizaremos ordenação para organizar os elementos por tamanho, seguida por enumeração para identificar qual elemento oferece o melhor resultdao quando posicionado estrategicamente.

Código Implementado

#include <iostream>
#include <vector>
#include <algorithm>
#define int long long

struct Elemento {
    int tamanho;
    int identificador;
};

bool comparador(Elemento a, Elemento b) {
    if (a.tamanho != b.tamanho) {
        return a.tamanho < b.tamanho;
    }
    return a.identificador < b.identificador;
}

void resolver() {
    int quantidade = 0;
    std::cin >> quantidade;
    
    std::vector<Elemento> elementos(quantidade + 1);
    for (int i = 1; i <= quantidade; i++) {
        std::cin >> elementos[i].tamanho;
        elementos[i].identificador = i;
    }
    
    std::sort(elementos.begin() + 1, elementos.end(), comparador);
    
    int maximo = 0;
    int posicao = 0;
    
    for (int i = 1; i <= quantidade; i++) {
        int valor_atual = elementos[i].tamanho * (quantidade - i + 1) * (quantidade - i + 1);
        if (valor_atual > maximo) {
            maximo = valor_atual;
            posicao = i;
        }
    }
    
    std::cout << quantidade - posicao + 1 << std::endl;
    
    std::vector<int> selecionados;
    for (int i = posicao; i <= quantidade; i++) {
        selecionados.push_back(elementos[i].identificador);
    }
    
    std::sort(selecionados.begin(), selecionados.end());
    
    for (int item : selecionados) {
        std::cout << item << " ";
    }
    std::cout << std::endl;
}

Contagem de Representações Numéricas

Tema: Programação dinâmica e enumeração de possibilidades

Abordagem: Dado o escopo limitado, podemos analisar cada indivíduo separadamente. Utilizaremos uma abordagem de programação dinâmica onde dp[i][j] representa o número de maneiras de alcançar o valor j com os primeiros i indivíduos. Como os números podem ser negativos, implementaremos um deslocamento (offset) para lidar com índices negativos.

Código Implementado

#include <iostream>
#include <vector>
#define int long long

const int MOD = 1e9 + 7;
const int DESLOCAMENTO = 1e3;
const int MAX_VALOR = 2020;

int possibilidades[110][MAX_VALOR];
int coeficientes[11] = {0, 9, 8, 7, 6, 5, 6, 5, 4, 3, 2};

void adicionar_estado(int passo, int valor, int peso) {
    if (valor + peso >= 0 && valor + peso <= 2 * DESLOCAMENTO) {
        possibilidades[passo][valor] = (possibilidades[passo][valor] + possibilidades[passo-1][valor + peso]) % MOD;
    }
}

void resolver() {
    int alvo = 0, passos = 0;
    std::cin >> alvo >> passos;
    
    possibilidades[0][DESLOCAMENTO] = 1;
    
    for (int i = 1; i <= passos + 1; i++) {
        for (int j = 0; j <= 2 * DESLOCAMENTO; j++) {
            for (int k = 1; k <= 10; k++) {
                adicionar_estado(i, j, k);
                adicionar_estado(i, j, -k); 
            }
            
            for (int k1 = 1; k1 <= 5; k1++) {
                for (int k2 = 1; k2 <= 5; k2++) {
                    adicionar_estado(i, j, k1 + k2);
                    adicionar_estado(i, j, k1 - k2);
                    adicionar_estado(i, j, -k1 - k2);
                    adicionar_estado(i, j, -k1 + k2);
                }
            }
        }
    }
    
    std::cout << possibilidades[passos + 1][alvo + DESLOCAMENTO] << std::endl;
}

Análise de Árvores Genéticas com Operações Bitwise

Tema: Algoritmos de busca em profundidade, operações bitwise e manipulação de strings

Abordagem: O problema pode ser simplificado usando a propriedade de que D(i,j) = D(1,i) XOR D(1,j). A expressão complexa pode ser transformada em uma contagem de ocorrências de cada elemento. Após análise, observamos que os elementos extremos (primeiro e último) aparecem m-2 vezes, enquanto os outros aparecem m-3 vezes. Dependendo se m é par ou ímpar, o resultado final será diferente.

Código Implementado

#include <iostream>
#include <vector>
#include <string>
#define int long long

std::vector<int> arvore[100005];
std::string distancias[100005];
int n = 0, m = 0, L = 0;

std::string operar_xor(std::string s, std::string t) {
    std::string resultado(L, '0');
    for (int i = 0; i < L; i++) {
        if (s[i] == t[i]) {
            resultado[i] = '0';
        } else {
            resultado[i] = '1';
        }
    }
    return resultado;
}

void dfs(int no) {
    for (int i = 0; i < arvore[no].size(); i++) {
        int filho = arvore[no][i];
        distancias[filho] = operar_xor(distancias[filho], distancias[no]);
        dfs(filho);
    }
}

void resolver() {
    std::cin >> n >> m >> L;
    int u = 0, v = 0;
    for (int i = 1; i <= n - 1; i++) {
        std::cin >> u >> v >> distancias[v];
        arvore[u].push_back(v);
    }
    
    std::vector<int> identificadores(m + 1, 0);
    for (int i = 1; i <= m; i++) {
        std::cin >> identificadores[i];
    }
    
    distancias[1] = std::string(L, '0');
    dfs(1);
    
    if (m & 1) {
        std::cout << operar_xor(distancias[identificadores[1]], distancias[identificadores[m]]) << std::endl;
    } else {
        std::string resposta(L, '0');
        for (int i = 2; i <= m - 1; i++) {
            resposta = operar_xor(resposta, distancias[identificadores[i]]);
        }
        std::cout << resposta << std::endl;
    }
}

Otimização com Bitset

Tema: Estruturas de dados bitwise e otimização de operações

Abordagem: Podemos utilizar a estrutura de dados bitset para realizar operações XOR de forma mais eficiente, reduzindo a complexidade e o tempo de execução.

Código Implementado

#include <iostream>
#include <vector>
#include <bitset>
#define int long long

std::vector<int> arvore[100005];
std::bitset<100> distancias[100005];
std::bitset<100> resposta;
int n = 0, m = 0, L = 0;

void dfs(int no) {
    for (int i = 0; i < arvore[no].size(); i++) {
        int filho = arvore[no][i];
        distancias[filho] ^= distancias[no];
        dfs(filho);
    }
}

void resolver() {
    std::cin >> n >> m >> L;
    int u = 0, v = 0;
    for (int i = 1; i <= n - 1; i++) {
        std::cin >> u >> v >> distancias[v];
        arvore[u].push_back(v);
    }
    
    std::vector<int> identificadores(m + 1, 0);
    for (int i = 1; i <= m; i++) {
        std::cin >> identificadores[i];
    }
    
    dfs(1);
    
    if (m & 1) {
        resposta = distancias[identificadores[1]] ^ distancias[identificadores[m]];
    } else {
        for (int i = 2; i <= m - 1; i++) {
            resposta ^= distancias[identificadores[i]];
        }
    }
    
    std::string resultado = resposta.to_string().substr(100 - L, L);
    std::cout << resultado << std::endl;
}