Array

Declaration

int tab[MAX];

Declaration + initialisation a 0

int tab[MAX]={0};

Trier

sort(tab, tab+MAX)

Taille maximale

si MAX == 1e9 => TLE Si MAX == 1e8 ok

Remarque

Si tab est declare hors du main, alors il est initialise a 0. Sinon, c’est aleatoire. [Est ce du au compilateur ou au langage et trouver une reference]

Bitwise

les puissances de 2

1<<n;
1ll<<n; // a partir de n=31

multiplication par 2**n

x << n; //attention : cout << x << n; il faut des parentheses.

&

x & y ;

|

x | y;

cas remarquables

p<<1 == 2*p
p<<1|1 == 2*p +1
p>>1 == p/2
p&1 == p%2
p^1 == p+1 si p pair sinon p-1

Disjoint Sets Union

On s’inspire de Tarjan.

const int MAX = 1000;
int p[MAX], r[MAX];

Makeset

void makeset(int x)
{
    p[x]=x;
}

Find naive

int find(int x)
{
    if(x==p[x]) return x;
    return find(p[x]);
}

L’heuristique de compression

int find(int x)
{
    if(x!=p[x]) p[x]=find(p[x]);
    return p[x];
}

On suppose que x = p[x] et y=p[y]

int link(int x, int y)
{
    p[x]=y;
    return y;
}
void makeset(int x){p[x]=x; r[x]=0;}
int link(int x, int y)
{
    if(r[x] > r[y]) swap(x,y);
    else if(r[x] == r[y]) 
        rank(y)++;
    p[x]=y;
    return y;
}

Geometry

Hypotenuse

double a = 3, b =4;
double c = hypot(a,b); //c == 5

Graphs

Notations

n nombre de sommets m nombre d’aretes

u, v, w vertices

uv an edge

void dfs(int v)
{
    color[v]='b';
    for(auto w: adj[v]) if(color[w]=='w') dfs(w);
}

void visit(int v)
{
    for(auto u: adj[v])
        if(color[u] == 'w')
        {
            color[u] = 'b';
            visit(u);
        }
}
void dfs()
{
    for(auto v: vertices) color[v] = 'w';
    for(auto v: vertices)
        if(color[v] == 'w') visit(v);
}

Faisons quelques remarques :

void bfs(int v)
{
    fill(color+1, color+nv+1, 'w');
    queue<int> q;
    q.push(v);
    while(!q.empty())
    {
        auto u = q.front();
        q.pop();
        for(auto w: adj[u])
            if(color[w] == 'w')
            {
                color[w] = 'b';
                q.push(w);
            }
    }
}

Tri topologique

Il faut absolument colorier en gris avant de colorier en noir.

list<int>ltri;
bool iscyclic = false;
void visit(v)
{
    color[v] = 'g';
    for(auto u: adj[v])
    {
        if(color[u] == 'w')
        {
            color[u] = 'b';
            visit(u);
        }
        else if(color[u] == 'g')
            iscyclic = true;
    }
    ltri.push_back(v);
}
void dfs()
{
    fill(color, color+MAX+1, 'w');
    for(auto v: ver)
        if(color[v] == 'w') visit(v);
}
void tritop()
{
    fill(color+1, color+nver+1, 'w');
    dfs();
    if(!iscyclic)
        affiche(ltri)
}

Chemin le plus court : BFS

Si on a un graphe non pondere, un parcours en largeur permet de determiner le chemin le plus court.

fill(parent, parent+MAX+1, -1)
void bfs()
{
    queue q;
    q.push(v);
    while(!q.empty())
    {
        auto w = q.pop();
        for(auto x:adj[w])
            if(color[x]=='w')
            {
                parents[x] = w;
                color[x] = 'b';
                q.push(x);
            }
    }
}

Tour d’Euler

Il s’agit de dire si un graphe admet un circuit Eulerien ; et si oui le determiner.

Existence

On construit un tableau comptenant le nombres d’aretes pour chaque sommet int nedge[MAX];. Puis on verifie la parite :

bool iseuler()
{
        for(auto v:vertices)
                if(nedge[v]%2 == 1)
                        return false;
        return true;
}
Construction

L’idee est de faire un parcours en profondeur et de supprimer les aretes.

void dfs(int v)
{
        while(!adj[v].empty())
        {
                auto is = adj[v].begin();
                auto u = *is;
                if(nedge[u] > 0)
                {
                        erase(u, v);
                        nedge[u]--;
                        nedge[v]--;
                        auto it = find (solution.begin(), solution.end(), v);
                        solution.insert(it, u);
                        dfs(u);
                }
        }
}

Integer

Convertir 3,14 en 3.14

string s = "3,14";
replace(s.begin(),s.end(),',','.');

Pour avoir une precision dans un double

Ne pas utiliser

cout << x;

mais

printf("%.10f", x);
cout <<setprecision(10)<<x;

long long

long long n;
scanf("%lld", &n);

Is

isalpha isdigit

List

declaration

list<int>l;

taille

l.size()

premier element

l.front()

dernier element

l.back()

inserer dernier

l.push_back(x)

inserer devant

l.push_front(x)

supprimer devant

l.pop_front()

supprimer dernier

l.pop_back()

tester vide

l.empty()

tester si un element est dans une liste

find(l.begin(),l.end(), x)!=l.end()

sort

l.sort();
l.sort(greater<int>());

Map

Clear

m.clear();

Declaration

map<string, int>m;

Insertion

m.insert(make_pair("hello", 1));
m.insert(make_pair("hello", 1));

Divers

m["hello"]++;

Parcourir

map<int, int>m{{'a', 11}, {'b', 22}};
for(auto i = m.begin(); i != m.end(); i++)
    cout << i->first << " "<< i->second << endl;

Size

m.size();

Miscellaneous

Minimal c++ program

#include<bits/stdc++.h>
using namespace std;
int main()
{
}

Lire une matrice / tableau

Si k est le kieme element, alors il se trouve a la ligne k/5 et a la colonne k%5 (en comptant a partir de 0)

Initialiser a 0 un entier

int k{};

Parite

n%2 // return 1 si impair
n&1 // idem

“When in doubt, use brute force.” - Ken Thompson

auto

Convertir char to in

char a = 'a';
int ia = (int)a;

Multiset

Il s’agit d’une generalisation des ensembles : m = {{1, 2, 2, 3, 3, 3}} est un multiensemble.

Declaration

multiset<int>m;
multiset<int>m{1,2,2,3,3,3};

Insertion

m.insert(4);

Taille

m.size();

Premier element

auto it = m.begin(); cout << *it;

Dernier element

auto it = m.rbegin(); cout << *it;

Effacer les 3

m.erase(3)

Effacer un 3

m.erase(tab.find(3))

Number Theory

GCD

D’apres bmerry

template<class T> T gcd(T a, T b) { return b ? gcd(b, a % b) : a; }

Pair

Declaration

pair<int, int> v

Une pair

v = {1, 2}  
v = make_pair(1,2) // equivalent

Le premier, le second

v.first
v.second

vector pair

Pour changer une valeur d’une pair dans un vector

for(auto& p:v)

et non

for(auto p:v)

Priority Queue

Declaration

priority_queue<int>pq;

Push

pq.push(37);

Top

pq.top();

Pop

pq.pop();

Empty et size

pq.empty()
pq.size()

Queue

aka fifo

Declaration

queue<int>q;
queue<int>q{37}; //non

Taille

q.size()

Insertion

q.push(x)

Premier element

q.front()

Dernier element

q.back()

Supprimer le premier element

q.pop()

Tester si vide

q.empty()

Vider

queue<int>vide;
swap(vide,q);

Remarque

il est impossible de faire

for(auto x:q) ...

Random Number

Random number engines

random_device r;
knuth_b g(r());

Random number distributions

uniform_int_distribution<> x(1,37);
cout << x(g) ; // affiche un nombre aleatoire entre 1 et 37 inclus

Set

Declaration

set<int> s; // ensemble vide
set<char> s{'h','e','l','o'};

Taille

s.size();

Insertion

s.insert(x);

Test si c’est vide

s.empty();

Pour tout effacer

s.clear();

Test l’appartenance

s.count(x); //return 1 if x in s; 0 otherwise

Suppression

s.erase(x);

Union

Intersection

Shortest Paths

SPFA

void spfa(int v)
{
    for(int u:vertices) d[i] = inf;
    d[v] = 0;
    queue<int> q;
    q.push(v);
    while(!q.empty())
    {
        int u = q.front();
        q.pop();
        for(auto i:adj[u])
        {
            if(d[i] > d[u] + w(u,i))
            {
                d[i] = d[u] + w(u,i);
                if(i is not in q)
                    q.push(i)
            }
        }
    }
}

Floyd Warshal = shortest path for all pair(u,v)

int d[MAX][MAX];
int adj[MAX][MAX];
void floyd_warshal(){
    for(auto v:vertices)for(auto u:vertices)
    {
        if(adj[u][v]!=0)d[u][v]=d[v][u]=adj[u][v];
        else if(u!=v) d[u][v]=1e8;
    }
    for(auto k:vertices)for(auto i:vertices)for(auto j:vertices)
          d[i][j]=min(d[i][j], d[i][k]+d[k][j]);
};

Bellman Ford = shortest path with negative weight

for(int v = 1; v <= N; ++v) d[v]=1e8;
    d[1] = 0;
    for(int k = 1; k < N; ++k)
    {
        for(auto uvw:edges)
        {
            int u = get<0>(uvw);
            int v = get<1>(uvw);
            int w = get<2>(uvw);
            d[v]=min(d[v], d[u]+w);
        }
    }
    for(auto uvw:edges)
    {
        int u = get<0>(uvw);
        int v = get<1>(uvw);
        int w = get<2>(uvw);
        if(d[u]+w < d[v])
        {
            printf("ERREUR\n");
            return 0;
        }
    }
    printf("%d\n",d[N]);

Stack

aka lifo

Declaration

stack<int> p;

Taille

p.size();

Insertion

p.push(x);

String

Declaration

C++

string s; // s=="";
string s=""; //equivalent

C

char s[MAX]; // chaine quelconque
char s[]="hello world";

Lecture

La premiere version C++ permet de lire jusqu’au premier blanc ou fin de ligne.

string s;
cin >> s;

Pour lire toute une ligne :

string s;
getline(cin, s);

La version C permet de lire jusqu’au premier blanc ou fin de ligne

char s[MAX];
scanf("%s", s);

Ecriture

La version C++

string s;
cout << s;

La version C, ne marche pas si s string

printf("%s", s);

ou plus simplement

print(s);

Si on souhaite mettre une fin de ligne

puts(s);

Concatenation

string s = "hello";
s += "world"; //s == "helloworld"

Convertion string to int

Attention a la limite pour l’entier.

string s = "37";
int x = stoi(s); // x == 37

Convertion int to string

int x = 37;
string s = to_string(x);

Taille

La version C++

string s="hello";
s.size(); //5

La version C

char s[MAX];
strlen(s);

Erreurs classiques

string s = '1'; // ne marche pas
string s = "1"; // marche

int n; cin >>n;
string s; getline(cin, s);

Initialisation d’une chaine

string s ="hello world"; // oui
string s ='hello world'; // non

Changer un caractere d’une chaine

string s="hello world";
s[0]='H'; // oui
s[0]="H"; // non

Comparaison lexicographique

string s, t;
if(s < t) ...
ou
if(s.compare(t))

Comment mettre une lettre petites

string s = "Hello World";
tolower(s[0]); //non
s[0] = tolower(s[0]); // oui

Comment mettre toutes les lettres petites

string s = "AbC";
transform(s.begin(), s.end(), s.begin(), ::tolower);

Sous chaine

string s = "hello world";
cout <<s.substr(0,5); //affiche "hello", 5 pour 5 lettres

Pour convertir un entier en sa representation binaire

int x = 5;
bitset<3> y(x); // 101
y.to_string(); // chaine de caractere 101

Parcourir une chaine

string s;
for(auto c:s)

char s[MAX];
for(int i = 0; s[i]; ++ii)

Renverser une chaine

string s="hello";
reverse(s.begin(),s.end()); //s=="olleh"

L’ensemble des lettres d’un string

string x = "hello";
set<char>s{x.begin(),x.end()}; // s == {ehlo}

La liste de toutes les lettres

string x = "hello";
list<char>l{x.begin(),x.end()}; // l == ['h', 'e', 'l', 'l', 'o']

Trier

string s = "hello";
sort(s.begin(),s.end()); // s=="ehllo"

Find

string s = "hello world";
int n = s.find("world"); // n == 6

Replace

string s = "hello world";
s.replace(6,5,"monde"); // s== hello monde

Convertir 3,14 en 3.14

string s = "3,14";
replace(s.begin(),s.end(),',','.');

Count

string s = "hello";
count(s.begin(),s.end(),'l'); //2

Split

string line, word;
istringstream iss(line);
while(iss >>word)
{

}

char to string

string(5,'a'); // <=> "aaaaa"

Tree

Size of subtree

Input: T tree, v vertice

Output: sz[v] size of subtree from v

int sz[MAX];
void getsz(int v, int p)
{
    sz[v] = 1;
    for(auto w: adj[v])
        if(u != p)
        {
            getsz(u,v);
            sz[v] +=sz[u];
        }
}

Tuple

il s’agit d’une generalisation de pair

tuple<int,int,int> v

v = make_tuple(1,4,3);

ou

get<0>(v) = 1; get<1>(v) = 4; get<2>(v) = 3;

ce qui suit ne marche pas: v={1,4,3} cout << v.first << v.second

Capture the tuple by reference:

for (tuple<int, int> &tup : vector){
        if (get<0>(tup) == k){
            get<1>(tup) = v;
        }
}

Vector

Clear

v.clear();

Declaration

vector<int>v;
vector<int>v{1,2,3,4,5};
vector<int>v(5,1) // v == 1 1 1 1 1

Copy

vecot<int>v ...
vecot<int>w ...
v = w; // maintenant v = w;

Declaration + initialisation a 0

vector<int>v(3) // 0 0 0

Declaration + init a _

vector<string>v(3) // _ _ _

Inserer

v.push_back(x)

Supprimer le dernier

v.pop_back()

Le dernier

v.back();

Taille

v.size();

Insertion

v.insert(v.begin()+k, x);

Erase

v.erase(v.begin()+k)

Afficher

for(auto x:v)cout << x << endl; cout << endl;

Trier

sort(v.begin(), v.end());

Trier sens inverse

sort(v.begin(), v.end(), greater<int>());

Reverse

reverse(v.begin(), v.end());

Maximum - Minimum

*max_element(v.begin(),v.end());
*min_element(v.begin(),v.end());

Sous Vector

vector<int>v{1,2,3,4,5}
vector<int>w(v.begin()+1, v.begin()+3); // w == {2,3}

Concatenation

vector<int>v,w;
v.insert(v.end(), w.begin(), w.end());

Swap

v.swap(w);