Programação Competitiva

Exercícios de programação competitivas tirados de vjudge.net

docker run --name myvjudge -it -v  C:/Users/wvita/Source/Repos/RalphVita/ProgramacaoCompetitiva:/home/pc ubuntu:vjudge bash

ou

docker container exec -it myvjudge /bin/bash

Bibliotecas

algorithm

http://www.cplusplus.com/reference/algorithm/

Estruturas

• Grafo
• Union-Find/Disjoint Sets
• Segment Tree
• Fenwick Tree

Grafo

Armazena informação de conectividade entre vértices

    int AdjMat[V][V]

Ou

    vector<vector<pair<int, int>>>

Union-Find/Disjoint Sets

• Encontrar o conjunto que um elemento pertence

    UF.findSet(i)

• Testar se dois elementos pertencem ao mesmo conjunto

    UF.isSameSet(a, b)

• Fazer a união de dois conjuntos

    //Coloca os elementos do conjunto em que a está, no conjunto em que b está.
    UF.unionSet(a, b);

Segment Tree

• Encontrar o índice do menor elemento no intervalo [i…j]

    RMQ(i, j) 

• Para retornar o máximo é só multiplicar a entrada por -1.

    st.update(k, k, -x);
    -RMQ(i, j)

Fenwick Tree

• Quantas vezes os inteiros entre a e b aparecem em um array?

    RSQ(a, b) 

• Para retornar a soma, é só entrar com os valores, em vez da quantidade de vezes que eles aparacem.