Año 2025

Especialidad Maestría

Problema 1: Diferencia Máxima

Fuente: Luogu P5146. Encontrar la máxima diferencia entre dos elementos donde el menor aparece antes del mayor.

// Código optimizado para lectura
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 1e6 + 10;

ll arr[N];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    ll minVal = arr[1];
    ll res = LLONG_MIN;
    for (int i = 2; i <= n; ++i) {
        res = max(res, arr[i] - minVal);
        minVal = min(minVal, arr[i]);
    }
    cout << res << "\n";
    return 0;
}

Problema 2: Cuadrícula de Palabras

Fuente: Luogu P1101. Buscar la palabra "yizhong" en todas las direcciones dentro de una cuadrícula de letras y maracrla.

#include <bits/stdc++.h>
using namespace std;
const int N = 102;
char grid[N][N];
bool marked[N][N];
int dx[8] = {-1, 1, 0, 0, -1, -1, 1, 1};
int dy[8] = {0, 0, -1, 1, -1, 1, -1, 1};
string target = " yizhong"; // índice 1 basado

bool inside(int x, int y, int n) {
    return x >= 1 && x <= n && y >= 1 && y <= n;
}

void follow(int x, int y, int &cnt, int dir, bool flag) {
    while (inside(x, y, n) && cnt <= 7 && grid[x][y] == target[cnt]) {
        if (flag) marked[x][y] = true;
        x += dx[dir];
        y += dy[dir];
        cnt++;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j)
            cin >> grid[i][j];
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (grid[i][j] != 'y') continue;
            for (int d = 0; d < 8; ++d) {
                int x = i + dx[d], y = j + dy[d];
                int cnt = 2;
                follow(x, y, cnt, d, false);
                if (cnt == 8) {
                    marked[i][j] = true;
                    cnt = 2;
                    follow(x, y, cnt, d, true);
                }
            }
        }
    }
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= n; ++j) {
            if (marked[i][j]) cout << grid[i][j];
            else cout << '*';
        }
        cout << "\n";
    }
    return 0;
}

Problema 3: Ordenamiento de Cadenas de Matrices

Fuente: Luogu P1753. (No se incluye código, solo referencia al problema).

Problema 4: Camino más Largo

Fuente: Luogu P1807. Encontrar el camino más largo en un grafo acíclico dirigido usando SPFA con pesos negativos.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e4 + 10;
vector<pair<int, int>> graph[N];
bool inQueue[N];
ll dist[N];

void spfa(int n) {
    fill(dist, dist + n + 1, INT_MAX);
    memset(inQueue, false, sizeof inQueue);
    queue<int> q;
    q.push(1);
    inQueue[1] = true;
    dist[1] = 0;
    while (!q.empty()) {
        int u = q.front(); q.pop();
        inQueue[u] = false;
        for (auto &edge : graph[u]) {
            int v = edge.first, w = edge.second;
            if (dist[v] > dist[u] + w) {
                dist[v] = dist[u] + w;
                if (!inQueue[v]) {
                    q.push(v);
                    inQueue[v] = true;
                }
            }
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m; cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        int u, v, w; cin >> u >> v >> w;
        graph[u].push_back({v, -w});
    }
    spfa(n);
    if (dist[n] > INT_MAX / 2) cout << -1 << "\n";
    else cout << -dist[n] << "\n";
    return 0;
}

Especialidad Académica

Problema 1: Cartas de Póker

Fuente: CSP-J 2024, Luogu P11227. Contar cuántas cartas faltan para tener una baraja completa de 52 cartas.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    set<string> seen;
    for (int i = 0; i < n; ++i) {
        string card; cin >> card;
        seen.insert(card);
    }
    cout << 52 - seen.size() << "\n";
    return 0;
}

Problema 2: IPv6

Fuente: Luogu B4148. Convertir una dirección IPv6 comprimida a su representación binaria completa de 128 bits.

#include <bits/stdc++.h>
using namespace std;
string ip;
unordered_map<char, int> hexMap;
string binaryOutput;

void initMap() {
    for (char c = '0'; c <= '9'; ++c) hexMap[c] = c - '0';
    hexMap['A']=10; hexMap['B']=11; hexMap['C']=12; hexMap['D']=13; hexMap['E']=14; hexMap['F']=15;
}

void toBinary(int val) {
    for (int bit = 3; bit >= 0; --bit)
        binaryOutput += to_string((val >> bit) & 1);
}

void padZeros(int idx) {
    int missing = 4;
    for (int j = idx; j < ip.size() && ip[j] != ':'; ++j) missing--;
    for (int j = 0; j < missing; ++j) binaryOutput += "0000";
}

int countGroups() {
    int cols = 0;
    for (int i = 0; i < ip.size(); ++i) {
        if (i > 0 && ip[i]==':' && ip[i-1]==':') continue;
        if (ip[i]==':') cols++;
    }
    if (ip.front()==':' || ip.back()==':') cols--;
    return cols + 1;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    initMap();
    cin >> ip;
    int groups = countGroups();
    for (int i = 0; i < ip.size(); ++i) {
        if (ip[i] == ':') {
            if (i >= 1 && ip[i-1]==':') {
                int missingGroups = 8 - groups;
                for (int j = 0; j < missingGroups * 4; ++j) binaryOutput += "0000";
            }
            continue;
        }
        if ((i==0 && ip[i]!=':') || (i>=1 && ip[i-1]==':' && ip[i]!=':'))
            padZeros(i);
        toBinary(hexMap[ip[i]]);
    }
    cout << binaryOutput << "\n";
    return 0;
}

Problema 3: Pila (Stack)

Fuente: Luogu P1044. Contar el número de secuancias posibles de push y pop para una pila con n elementos.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 105;
ll memo[N][N];

ll dfs(int step, int inStack, int n) {
    if (step == 2 * n) return (inStack == 0) ? 1 : 0;
    ll &res = memo[step][inStack];
    if (res != -1) return res;
    ll cnt = 0;
    if (inStack < n) cnt += dfs(step+1, inStack+1, n);
    if (inStack > 0) cnt += dfs(step+1, inStack-1, n);
    return res = cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    memset(memo, -1, sizeof memo);
    cout << dfs(0, 0, n) << "\n";
    return 0;
}

Problema 4: Pares Inversos

Fuente: Luogu P1908. Contar el número de pares inversos en un arreglo usando mergesort.

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 5e5 + 10;
ll arr[N], temp[N];
ll inversions = 0;

void mergeSort(int l, int r) {
    if (l >= r) return;
    int mid = (l + r) >> 1;
    mergeSort(l, mid);
    mergeSort(mid+1, r);
    int i = l, j = mid+1, k = 0;
    while (i <= mid && j <= r) {
        if (arr[i] <= arr[j]) temp[k++] = arr[i++];
        else {
            inversions += mid - i + 1;
            temp[k++] = arr[j++];
        }
    }
    while (i <= mid) temp[k++] = arr[i++];
    while (j <= r) temp[k++] = arr[j++];
    for (i = 0; i < k; ++i) arr[l + i] = temp[i];
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> arr[i];
    mergeSort(1, n);
    cout << inversions << "\n";
    return 0;
}

Año 2024

Intercambiar Nodos en Lista Enlazada (LeetCode 1721)

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapNodes(ListNode* head, int k) {
        int len = 0;
        ListNode *p = head, *q = head;
        while (p) { len++; p = p->next; }
        p = head;
        for (int i = 0; i < len - k; ++i) p = p->next;
        for (int i = 0; i < k - 1; ++i) q = q->next;
        swap(p->val, q->val);
        return head;
    }
};

Intercambiar Pares de Nodos (LeetCode 24)

class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        ListNode *p = head, *q, *nxt;
        while (p) {
            q = p->next;
            if (!q) break;
            nxt = q->next;
            swap(p->val, q->val);
            p = nxt;
        }
        return head;
    }
};

Problema de José (Luogu P1996)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m; cin >> n >> m;
    vector<int> people;
    for (int i = 1; i <= n; ++i) people.push_back(i);
    int idx = 0;
    while (!people.empty()) {
        idx = (idx + m - 1) % people.size();
        cout << people[idx] << " ";
        people.erase(people.begin() + idx);
    }
    return 0;
}

Punto Silla (Luogu B2102)

#include <bits/stdc++.h>
using namespace std;
int mat[6][6];
bool rowMax[6][6], colMin[6][6];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    for (int i = 1; i <= 5; ++i) {
        int maxVal = INT_MIN, rx, ry;
        for (int j = 1; j <= 5; ++j) {
            cin >> mat[i][j];
            if (mat[i][j] > maxVal) {
                maxVal = mat[i][j];
                rx = i; ry = j;
            }
        }
        rowMax[rx][ry] = true;
    }
    for (int j = 1; j <= 5; ++j) {
        int minVal = INT_MAX, cx, cy;
        for (int i = 1; i <= 5; ++i) {
            if (mat[i][j] < minVal) {
                minVal = mat[i][j];
                cx = i; cy = j;
            }
        }
        colMin[cx][cy] = true;
    }
    for (int i = 1; i <= 5; ++i)
        for (int j = 1; j <= 5; ++j)
            if (rowMax[i][j] && colMin[i][j]) {
                cout << i << " " << j << " " << mat[i][j] << "\n";
                return 0;
            }
    cout << "not found\n";
    return 0;
}

N-Reinas (LeetCode 51)

class Solution {
public:
    vector<vector<string>> result;
    vector<vector<char>> board;
    vector<bool> colUsed, diag1, diag2;
    vector<string> cur;
    void backtrack(int row, int n) {
        if (row == n + 1) {
            cur.clear();
            for (int i = 1; i <= n; ++i) {
                string tmp;
                for (int j = 1; j <= n; ++j) tmp += board[i][j];
                cur.push_back(tmp);
            }
            result.push_back(cur);
            return;
        }
        for (int c = 1; c <= n; ++c) {
            if (colUsed[c] || diag1[row + c] || diag2[row - c + n]) continue;
            board[row][c] = 'Q';
            colUsed[c] = diag1[row + c] = diag2[row - c + n] = true;
            backtrack(row + 1, n);
            board[row][c] = '.';
            colUsed[c] = diag1[row + c] = diag2[row - c + n] = false;
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        board.assign(n + 2, vector<char>(n + 2, '.'));
        colUsed.assign(n + 1, false);
        diag1.assign(3 * n + 1, false);
        diag2.assign(3 * n + 1, false);
        backtrack(1, n);
        return result;
    }
};

N-Reinas Checker (Luogu P1219)

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
int n, cnt = 0;
bool col[N], diag1[3*N], diag2[3*N];
vector<int> solution;

void dfs(int row) {
    if (row == n + 1) {
        if (++cnt <= 3) {
            for (int x : solution) cout << x << " ";
            cout << "\n";
        }
        return;
    }
    for (int c = 1; c <= n; ++c) {
        if (col[c] || diag1[row + c] || diag2[row - c + n]) continue;
        col[c] = diag1[row + c] = diag2[row - c + n] = true;
        solution.push_back(c);
        dfs(row + 1);
        col[c] = diag1[row + c] = diag2[row - c + n] = false;
        solution.pop_back();
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n;
    dfs(1);
    cout << cnt << "\n";
    return 0;
}

N-Reinas con Pesos (UVA167, no enviado)

#include <bits/stdc++.h>
using namespace std;
const int N = 10;
int k, n = 8;
bool col[N], diag1[3*N], diag2[3*N];
int values[N][N];
int best, cur;

void dfs(int row) {
    if (row == n + 1) {
        best = max(best, cur);
        return;
    }
    for (int c = 1; c <= n; ++c) {
        if (col[c] || diag1[row + c] || diag2[row - c + n]) continue;
        col[c] = diag1[row + c] = diag2[row - c + n] = true;
        cur += values[row][c];
        dfs(row + 1);
        cur -= values[row][c];
        col[c] = diag1[row + c] = diag2[row - c + n] = false;
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> k;
    while (k--) {
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= n; ++j)
                cin >> values[i][j];
        best = INT_MIN; cur = 0;
        dfs(1);
        cout << best << "\n";
    }
    return 0;
}

Simulacro (1)

Ping Pong

#include <bits/stdc++.h>
using namespace std;
string input, combined;

void printScore(int limit) {
    int w = 0, l = 0;
    for (char ch : combined) {
        if (ch == 'E') break;
        if (ch == 'W') w++;
        else if (ch == 'L') l++;
        if ((w >= limit && w - l >= 2) || (l >= limit && l - w >= 2)) {
            cout << w << ":" << l << "\n";
            w = l = 0;
        }
    }
    cout << w << ":" << l << "\n\n";
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    string line;
    while (cin >> line) {
        combined += line;
        if (line.find('E') != string::npos) break;
    }
    printScore(11);
    printScore(21);
    return 0;
}

Recorrido del Caballo (Luogu P1443)

#include <bits/stdc++.h>
using namespace std;
const int N = 405;
int dist[N][N];
int n, m, sx, sy;
int dx[8] = {-2,-2,2,2,-1,1,-1,1};
int dy[8] = {-1,1,-1,1,-2,-2,2,2};
bool visited[N][N];
struct State { int x, y, steps; };

void bfs() {
    queue<State> q;
    q.push({sx, sy, 0});
    visited[sx][sy] = true;
    dist[sx][sy] = 0;
    while (!q.empty()) {
        auto [x, y, s] = q.front(); q.pop();
        for (int d = 0; d < 8; ++d) {
            int nx = x + dx[d], ny = y + dy[d];
            if (nx < 1 || nx > n || ny < 1 || ny > m || visited[nx][ny]) continue;
            dist[nx][ny] = min(dist[nx][ny], s + 1);
            q.push({nx, ny, s + 1});
            visited[nx][ny] = true;
        }
    }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    memset(dist, 0x3f, sizeof dist);
    cin >> n >> m >> sx >> sy;
    bfs();
    for (int i = 1; i <= n; ++i) {
        for (int j = 1; j <= m; ++j) {
            if (dist[i][j] > 0x3f3f3f3f / 2) cout << -1 << " ";
            else cout << dist[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

Watering Hole (USACO 2008, Luogu P1550)

#include <bits/stdc++.h>
using namespace std;
const int N = 305;
struct Edge { int u, v, w; };
bool operator<(const Edge &a, const Edge &b) { return a.w < b.w; }
vector<Edge> edges;
int parent[N];
int cost[N];

int find(int x) { return parent[x] == x ? x : parent[x] = find(parent[x]); }

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) cin >> cost[i];
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= n; ++j) {
            int x; cin >> x;
            if (i > j) edges.push_back({i, j, x});
        }
    // nodo virtual n+1 (agua natural)
    for (int i = 1; i <= n; ++i)
        edges.push_back({i, n+1, cost[i]});
    sort(edges.begin(), edges.end());
    for (int i = 1; i <= n+1; ++i) parent[i] = i;
    long long total = 0;
    for (auto &e : edges) {
        int pu = find(e.u), pv = find(e.v);
        if (pu != pv) {
            parent[pu] = pv;
            total += e.w;
        }
    }
    cout << total << "\n";
    return 0;
}

Árbol Binario con Puntuación (NOIP 2003, Luogu P1040)

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 35;
ll score[N][N];
int root[N][N];
ll val[N];

void printTree(int l, int r) {
    if (l > r) return;
    cout << root[l][r] << " ";
    if (l == r) return;
    printTree(l, root[l][r] - 1);
    printTree(root[l][r] + 1, r);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n; cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> val[i];
        score[i][i] = val[i];
        score[i][i-1] = 1;   // subárbol izquierdo vacío
        score[i+1][i] = 1;   // subárbol derecho vacío
        root[i][i] = i;
    }
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            score[i][j] = 0;
            for (int k = i; k <= j; ++k) {
                ll cur = score[i][k-1] * score[k+1][j] + val[k];
                if (cur > score[i][j]) {
                    score[i][j] = cur;
                    root[i][j] = k;
                }
            }
        }
    }
    cout << score[1][n] << "\n";
    printTree(1, n);
    return 0;
}