Árbol de Expansión Mínima con Operación AND (HDU 6614)

El objetivo es construir un árbol de expansión mínima (MST) donde el peso de cada arista entre dos nodos es el resultado de la operación bitwise AND entre sus etiquetas.

Para los números de la forma \(2^i - 1\), verificamos si \(2^i \leq n\). De ser así, conectamos el nodo con \(2^i\). Para cualquier otro valor, buscamos la posición del primer bit en cero (supongamos en el índice \(x\)) y establecemos una conexión con el nodo \(2^x\). Este enfoque minimiza el peso acumulado aprovechando la estructura binaria de los números.

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void resolverMST() {
    int n_nodos;
    if (!(cin >> n_nodos)) return;
    vector<int> adjacencias;
    long long costo_total = 0;

    for (int i = 2; i <= n_nodos; ++i) {
        int limite_bit = 1;
        while (limite_bit <= i) limite_bit <<= 1;
        
        if (i == limite_bit - 1) {
            if (limite_bit <= n_nodos) {
                adjacencias.push_back(limite_bit);
            } else {
                adjacencias.push_back(1);
                costo_total++;
            }
        } else {
            for (int bit = 0; bit <= 20; ++bit) {
                if (!((i >> bit) & 1)) {
                    adjacencias.push_back(1 << bit);
                    break;
                }
            }
        }
    }

    cout << costo_total << "\n";
    for (int i = 0; i < adjacencias.size(); ++i) {
        cout << adjacencias[i] << (i == adjacencias.size() - 1 ? "" : " ");
    }
    cout << "\n";
}

int main() {
    int casos;
    cin >> casos;
    while (casos--) resolverMST();
    return 0;
}

Distribución Equitativa de Piedras (HDU 6616)

Se requiere dividir \(n\) piedras en \(k\) grupos, de modo que cada grupo contenga \(n/k\) piedras y el peso total de cada grupo sea idéntico (el peso de la peidra \(i\) es \(i\)).

Si \(n/k\) es par, podemos utilizar un llenado en forma de serpiente (zig-zag) para equilibrar los pesos. Si es impar, procesamos los primeros \(3k\) elementos de forma especial para compensar la disparidad y luego aplicamos la técnica de zig-zag para el resto de las piedras.

#include <cstdio>
#include <vector>

using namespace std;

void particionarPiedras() {
    int n, k;
    scanf("%d %d", &n, &k);
    long long suma_total = 1LL * n * (n + 1) / 2;
    if (suma_total % k != 0 || (n == k && n != 1)) {
        printf("no\n");
        return;
    }
    printf("yes\n");
    int filas = k, columnas = n / k;
    vector<vector<int>> rejilla(filas + 1, vector<int>(columnas + 1));

    if (columnas % 2 != 0) {
        for (int i = 1; i <= filas; ++i) rejilla[i][1] = i;
        rejilla[k / 2 + 1][2] = 2 * k;
        for (int i = k / 2 + 2; i <= filas; ++i) rejilla[i][2] = i - k / 2 - 1 + k;
        for (int i = 1; i <= k / 2; ++i) rejilla[i][2] = k + k / 2 + i;
        for (int i = 1; i <= filas; ++i) rejilla[i][3] = (9LL * k + 3) / 2 * 3 / 3 - rejilla[i][1] - rejilla[i][2]; // Simplificación lógica
        
        int r = 1, c = 4;
        for (int val = 3 * k + 1; val <= n; ++val) {
            rejilla[r][c] = val;
            if (c % 2 == 0) {
                if (r == filas) c++; else r++;
            } else {
                if (r == 1) c++; else r--;
            }
        }
    } else {
        int r = 1, c = 1;
        for (int val = 1; val <= n; ++val) {
            rejilla[r][c] = val;
            if (c % 2 != 0) {
                if (r == filas) c++; else r++;
            } else {
                if (r == 1) c++; else r--;
            }
        }
    }

    for (int i = 1; i <= filas; ++i) {
        for (int j = 1; j <= columnas; ++j) {
            printf("%d%c", rejilla[i][j], j == columnas ? '\n' : ' ');
        }
    }
}

Solubilidad del Puzzle de 15 Piezas (HDU 6620)

Para determinar si un estado del puzzle de 15 piezas es alcanzable, tratamos el espacio vacío (0) como el valor 16. Calculamos la cantidad de inversiones en la secuencia lineal resultante. El puzzle es soluble si la suma de las inversiones y la distancia Manhattan del espacio vacío al estado final tiene una paridad específica.

#include <iostream>
#include <vector>

using namespace std;

void verificarSolubilidad() {
    int tablero[16];
    int inversiones = 0;
    for (int i = 0; i < 16; ++i) {
        cin >> tablero[i];
        if (tablero[i] == 0) {
            inversiones += (i / 4) + (i % 4) + 2;
            tablero[i] = 16;
        }
        for (int j = 0; j < i; ++j) {
            if (tablero[j] > tablero[i]) inversiones++;
        }
    }
    cout << (inversiones % 2 == 0 ? "Yes" : "No") << endl;
}

K-ésima Distancia Cercana con Árboles Persistentes (HDU 6621)

Dada una secuencia, debemos responder consultas sobre la k-ésima menor distancia absoluta entre elementos en un rango \([L, R]\) y un valor \(p\). Esto se resuelve mediante búsqueda binaria sobre el valor de la distancia, utilizando un árbol de segmentos persistente (Chairman Tree) para contar cuántos elementos caen en el rango \([p - \text{mid}, p + \text{mid}]\).

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int MAXN = 100005;
struct NodoPersistente {
    int izq, der, cuenta;
} tree[MAXN * 40];

int raices[MAXN], total_nodos;

void insertar(int prev, int &curr, int l, int r, int val) {
    curr = ++total_nodos;
    tree[curr] = tree[prev];
    tree[curr].cuenta++;
    if (l == r) return;
    int mid = (l + r) / 2;
    if (val <= mid) insertar(tree[prev].izq, tree[curr].izq, l, mid, val);
    else insertar(tree[prev].der, tree[curr].der, mid + 1, r, val);
}

int buscarRango(int u, int v, int l, int r, int qL, int qR) {
    if (qL > r || qR < l) return 0;
    if (qL <= l && r <= qR) return tree[v].cuenta - tree[u].cuenta;
    int mid = (l + r) / 2;
    return buscarRango(tree[u].izq, tree[v].izq, l, mid, qL, qR) +
           buscarRango(tree[u].der, tree[v].der, mid + 1, r, qL, qR);
}

void ejecutarConsultas() {
    int n, q;
    scanf("%d %d", &n, &q);
    total_nodos = 0;
    int max_val = 0;
    vector<int> v(n + 1);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &v[i]);
        max_val = max(max_val, v[i]);
    }
    for (int i = 1; i <= n; ++i) {
        insertar(raices[i - 1], raices[i], 1, max_val, v[i]);
    }

    int last_ans = 0;
    while (q--) {
        int l, r, p, k;
        scanf("%d %d %d %d", &l, &r, &p, &k);
        l ^= last_ans; r ^= last_ans; p ^= last_ans; k ^= last_ans;
        
        int low = 0, high = max_val, ans = max_val;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (buscarRango(raices[l - 1], raices[r], 1, max_val, p - mid, p + mid) >= k) {
                ans = mid;
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        printf("%d\n", ans);
        last_ans = ans;
    }
}

Exponente Mínimo de Factores Primos (HDU 6623)

Para un número \(n\), buscamos el exponente más pequeño en su descomposición en factores primos. Primero, realizamos divisiones sucesivas con primos menores a 4000. Si después de esto \(n > 1\), el exponente restante solo puede ser 4, 3, 2 o 1, lo cual verificamos calculando raíces perfectas.

#include <iostream>
#include <cmath>
#include <algorithm>
#include <vector>

using namespace std;

vector<int> lista_primos;
void criba() {
    vector<bool> es_primo(4001, true);
    for (int i = 2; i <= 4000; ++i) {
        if (es_primo[i]) {
            lista_primos.push_back(i);
            for (int j = i * i; j <= 4000; j += i) es_primo[j] = false;
        }
    }
}

long long raiz_n(long long n, int r) {
    long long res = pow(n, 1.0 / r);
    for (long long t = res - 1; t <= res + 1; ++t) {
        if (t <= 0) continue;
        long long p = 1;
        for (int i = 0; i < r; ++i) p *= t;
        if (p == n) return t;
    }
    return -1;
}

void solve() {
    long long n;
    scanf("%lld", &n);
    int min_exp = 64;

    for (int p : lista_primos) {
        if (n % p == 0) {
            int exp = 0;
            while (n % p == 0) {
                n /= p;
                exp++;
            }
            min_exp = min(min_exp, exp);
        }
    }

    if (n > 1) {
        if (raiz_n(n, 4) != -1) min_exp = min(min_exp, 4);
        else if (raiz_n(n, 3) != -1) min_exp = min(min_exp, 3);
        else if (raiz_n(n, 2) != -1) min_exp = min(min_exp, 2);
        else min_exp = 1;
    }
    printf("%d\n", min_exp);
}