Nesta análise, exploramos soluções para desafios específicos das competições NOIP A层联测9 e CSP模拟52. Cada problema demanda uma abordagem algorítmica única, com implementações em C++ projetadas para eficiência e clareza.

Problema 1: Congruência Quadrática Modular

O objetivo é determinar o maior inteiro positivo 'a' para o qual existe um 'b' satisfazendo a congruência x ≡ a² + b² (mod p). A solução baseia-se na pré-computação dos resíduos quadráticos módulo p.

A estratégia envolve:

• Gerar todos os valores de b² mod p para b de 0 a p-1.
• Para cada x no intervalo [0, p-1], iterar sobre a e verificar se (x - a²) mod p pertence ao conjunto de resíduos quadráticos.

A complexidade temporal esperada é O(p log p).

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int modulo;
    cin >> modulo;
    vector<bool> quadrados(modulo, false);
    for (long long b = 0; b < modulo; ++b) {
        quadrados[(b * b) % modulo] = true;
    }
    int maxValor = 0;
    for (int x = 0; x < modulo; ++x) {
        for (long long a = 0; a < modulo; ++a) {
            int residuo = (x - (a * a) % modulo + modulo) % modulo;
            if (quadrados[residuo]) {
                maxValor = max(maxValor, static_cast<int>(a));
                break;
            }
        }
    }
    cout << maxValor << endl;
    return 0;
}

Problema 2: Ciclos Mínimos em Grafos

Este problema requer a contagem de ciclos mínimos que incluem uma aresta específica em um grafo não-direcionado. A abordagem utiliza busca em largura (BFS) para cada aresta, calculando caminhos mais curtos quando a aresta é removida.

Para cada aresta (u, v), realiza-se uma BFS a partir de u, excluindo a aresta atual, para encontrar caminhos até v. O comprimento do caminho mais curto mais 1 (para a aresta removida) dá o tamanho do ciclo. Acumula-se a contagem de ciclos por tamanho e divide pelo tamanho para evitar contagens múltiplas.

A complexidade temporal é O(m(n + m)), onde n é o número de vértices e m é o número de arestas.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const int INFINITO = 1e9 + 7;

void bfsComExclusao(int inicio, int alvo, int arestaExcluida, vector<vector<int>>& adjacencia, vector<int>& dist, vector<int>& contagem) {
    fill(dist.begin(), dist.end(), -1);
    queue<int> fila;
    dist[inicio] = 0;
    fila.push(inicio);
    while (!fila.empty()) {
        int atual = fila.front();
        fila.pop();
        if (atual == alvo) break;
        for (int vizinho : adjacencia[atual]) {
            if (vizinho == arestaExcluida) continue;
            if (dist[vizinho] == -1) {
                dist[vizinho] = dist[atual] + 1;
                fila.push(vizinho);
            }
        }
    }
    if (dist[alvo] != -1) contagem[dist[alvo]]++;
}

int main() {
    int n, m;
    cin >> n >> m;
    vector<vector<int>> adj(n + 1);
    vector<pair<int, int>> arestas(m);
    for (int i = 0; i < m; ++i) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
        arestas[i] = {u, v};
    }
    vector<int> contagemCiclos(n + 1, 0);
    for (auto& aresta : arestas) {
        vector<int> dist(n + 1, -1);
        bfsComExclusao(aresta.first, aresta.second, aresta.second, adj, dist, contagemCiclos);
    }
    for (int tamanho = 3; tamanho <= n; ++tamanho) {
        if (contagemCiclos[tamanho] > 0) {
            cout << contagemCiclos[tamanho] / tamanho << endl;
            return 0;
        }
    }
    cout << 0 << endl;
    return 0;
}

Problema 3: Subsequência Crescente com Condição Especial

Dado um array de pares (a_i, b_i), o objetivo é encontrar a subsequência mais longa onde c_{i+1} > b_i * c_i. A solução adapta o algoritmo de subsequência crescente mais longa (LIS) com complexidade O(n log n).

Mantém-se um array de valores acumulados. Para cada elemento, utiliza-se busca binária para encontrar a posição adequada e atualizar o valor acumulado se a condição for satisfeita.

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<long long> a(n), b(n);
    for (int i = 0; i < n; ++i) cin >> a[i];
    for (int i = 0; i < n; ++i) cin >> b[i];
    vector<long long> acumulado;
    for (int i = 0; i < n; ++i) {
        auto it = lower_bound(acumulado.begin(), acumulado.end(), a[i]);
        if (it == acumulado.end()) {
            acumulado.push_back(a[i] * b[i]);
        } else {
            if (a[i] * b[i] < *it) {
                *it = a[i] * b[i];
            }
        }
    }
    cout << acumulado.size() << endl;
    return 0;
}

Problema 4: Árvore de Segmentos com Atualizações e Consultas Dinâmicas

Este problema envolve consultas para o máximo valor de a_x - a_y em intervalos, com suporte a atualizações de intervalo. A solução combina uma árvore de segmentos para manter máximos, mínimos e diferenças, e uma fila de prioridade para processar as consultas de forma eficiente.

A árvore de segmentos mantém informações como valor máximo, mínimo, e a maior diferença dentro do nó. Para consultas, utiliza-se uma abordagem inspirada em "super piano", dividindo o problema em subintervalos e usando uma fila de prioridade para extrair as melhores soluções.

A complexidaed temporal é O(n log n + k log n), onde k é o número total de consultas.

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

const long long INFINITO = 1e18;

struct NoSegmento {
    long long maximo, minimo, diferenca, posMax, posMin;
};

vector<NoSegmento> arvore;
vector<long long> lazy;
vector<long long> valores;

void construir(int no, int esq, int dir) {
    if (esq == dir) {
        arvore[no] = {valores[esq], valores[esq], 0, esq, esq};
        return;
    }
    int meio = (esq + dir) / 2;
    construir(2 * no, esq, meio);
    construir(2 * no + 1, meio + 1, dir);
    arvore[no].maximo = max(arvore[2 * no].maximo, arvore[2 * no + 1].maximo);
    arvore[no].minimo = min(arvore[2 * no].minimo, arvore[2 * no + 1].minimo);
    arvore[no].posMax = (arvore[2 * no].maximo > arvore[2 * no + 1].maximo) ? arvore[2 * no].posMax : arvore[2 * no + 1].posMax;
    arvore[no].posMin = (arvore[2 * no].minimo < arvore[2 * no + 1].minimo) ? arvore[2 * no].posMin : arvore[2 * no + 1].posMin;
    arvore[no].diferenca = max({arvore[2 * no].diferenca, arvore[2 * no + 1].diferenca, arvore[2 * no].maximo - arvore[2 * no + 1].minimo});
}

void propagar(int no, int esq, int dir) {
    if (lazy[no] != 0) {
        arvore[no].maximo += lazy[no];
        arvore[no].minimo += lazy[no];
        if (esq != dir) {
            lazy[2 * no] += lazy[no];
            lazy[2 * no + 1] += lazy[no];
        }
        lazy[no] = 0;
    }
}

void atualizar(int no, int esq, int dir, int l, int r, long long valor) {
    propagar(no, esq, dir);
    if (r < esq || dir < l) return;
    if (l <= esq && dir <= r) {
        arvore[no].maximo += valor;
        arvore[no].minimo += valor;
        lazy[no] += valor;
        return;
    }
    int meio = (esq + dir) / 2;
    atualizar(2 * no, esq, meio, l, r, valor);
    atualizar(2 * no + 1, meio + 1, dir, l, r, valor);
    arvore[no].maximo = max(arvore[2 * no].maximo, arvore[2 * no + 1].maximo);
    arvore[no].minimo = min(arvore[2 * no].minimo, arvore[2 * no + 1].minimo);
    arvore[no].posMax = (arvore[2 * no].maximo > arvore[2 * no + 1].maximo) ? arvore[2 * no].posMax : arvore[2 * no + 1].posMax;
    arvore[no].posMin = (arvore[2 * no].minimo < arvore[2 * no + 1].minimo) ? arvore[2 * no].posMin : arvore[2 * no + 1].posMin;
    arvore[no].diferenca = max({arvore[2 * no].diferenca, arvore[2 * no + 1].diferenca, arvore[2 * no].maximo - arvore[2 * no + 1].minimo});
}

NoSegmento consultar(int no, int esq, int dir, int l, int r) {
    propagar(no, esq, dir);
    if (r < esq || dir < l) return {-INFINITO, INFINITO, -INFINITO, -1, -1};
    if (l <= esq && dir <= r) return arvore[no];
    int meio = (esq + dir) / 2;
    NoSegmento esquerda = consultar(2 * no, esq, meio, l, r);
    NoSegmento direita = consultar(2 * no + 1, meio + 1, dir, l, r);
    NoSegmento resultado;
    resultado.maximo = max(esquerda.maximo, direita.maximo);
    resultado.minimo = min(esquerda.minimo, direita.minimo);
    resultado.posMax = (esquerda.maximo > direita.maximo) ? esquerda.posMax : direita.posMax;
    resultado.posMin = (esquerda.minimo < direita.minimo) ? esquerda.posMin : direita.posMin;
    resultado.diferenca = max({esquerda.diferenca, direita.diferenca, esquerda.maximo - direita.minimo});
    return resultado;
}

struct Consulta {
    int l1, r1, l2, r2, posMax, posMin;
    long long valor;
};

bool operator<(const Consulta& a, const Consulta& b) {
    return a.valor < b.valor;
}

int main() {
    int n, m;
    cin >> n >> m;
    valores.resize(n + 1);
    arvore.resize(4 * n);
    lazy.resize(4 * n, 0);
    for (int i = 1; i <= n; ++i) cin >> valores[i];
    construir(1, 1, n);
    for (int consulta = 0; consulta < m; ++consulta) {
        int tipo, l, r, k;
        cin >> tipo >> l >> r >> k;
        if (tipo == 1) {
            atualizar(1, 1, n, l, r, k);
        } else if (tipo == 2) {
            priority_queue<Consulta> fila;
            NoSegmento noInicial = consultar(1, 1, n, l, r);
            fila.push({l, r, l, r, noInicial.posMax, noInicial.posMin, noInicial.diferenca});
            long long soma = 0;
            for (int i = 0; i < k; ++i) {
                Consulta atual = fila.top();
                fila.pop();
                soma += atual.valor;
                int posMax = atual.posMax, posMin = atual.posMin;
                if (atual.l1 == atual.l2) {
                    int esq = atual.l1, dir = atual.r1;
                    if (esq != posMax) {
                        NoSegmento sub = consultar(1, 1, n, esq, posMax - 1);
                        fila.push({esq, posMax - 1, esq, posMax - 1, sub.posMax, sub.posMin, sub.diferenca});
                    }
                    if (posMax != dir) {
                        NoSegmento sub = consultar(1, 1, n, posMax, dir);
                        fila.push({posMax, dir, posMax, dir, sub.posMax, sub.posMin, sub.diferenca});
                    }
                    if (posMax != posMin) {
                        NoSegmento sub = consultar(1, 1, n, posMax, posMax);
                        fila.push({posMax, posMax, posMin, posMin, sub.posMax, sub.posMin, 0});
                    }
                } else {
                    if (atual.l1 != posMax) {
                        NoSegmento sub = consultar(1, 1, n, atual.l1, posMax - 1);
                        fila.push({atual.l1, posMax - 1, atual.l2, atual.r2, sub.posMax, sub.posMin, sub.diferenca});
                    }
                    if (posMin != atual.r2) {
                        NoSegmento sub = consultar(1, 1, n, posMin + 1, atual.r2);
                        fila.push({posMax, posMax, posMin + 1, atual.r2, sub.posMax, sub.posMin, sub.diferenca});
                    }
                }
            }
            cout << soma << endl;
        }
    }
    return 0;
}