Conteúdo

• QOJ10272
• CF1305G
• CF1039D
• CF1842F
• UOJ388
• P14428
• P14470
• P10681
• AGC020F
• CF618F

QOJ10272

Inicialmente, observamos que não é necessário adicionar arestas onde ambas as extremidades do intervalo não são a maioria absoluta; a demonstração é relativamente simples. Em seguida, consideramos arestas com ambas as extremidades como maioria absoluta. Podemos definir \(a_i = x\) com \(b_i = 1\) e caso contrário \(b_i = -1\), e calcular a soma prefixada \(c_i\) de \(b_i\). Assim, a aresta \((u, v)\) existe se e somente se \(c_u \le c_v\), o que pode ser resolvido com uma pilha monotônica ou explorando mais proprieaddes. Para arestas com apenas uma extremidade como maioria absoluta, assumimos o ponto esquerdo; para cada ponto direito, o ponto esquerdo ótimo é fixo. Para cada valor de \(a_i\), consideramos intervalos entre dois \(a_i\) consecutivos e usamos diferenciação para processar as conexões, que formam intervalos.

CF1305G

Primeiro, li incorretamente o enunciado. Cosnidere adicionar arestas com peso \(a_i + a_j\), incluindo um ponto com \(a_i = 0\). O peso total da MST menos os pesos dos vértices fornece a resposta. Aplicando o algoritmo de Borůvka, denotamos por \(\land\) a operação AND bit a bit. Para encontrar pontos com \(a_i \land a_j = 0\), determinamos o máximo \(a_j\) tal que \(a_j \land S = a_j\). Um truque eficiente é buscar o maior valor que não pertence ao mesmo componente conectado que o máximo, garantindo pelo menos um par válido.

CF1039D

Podemos resolver de forma gulosa em tempo \(O(n)\) para um valor específico \(k = k_0\). Como a rseposta assume apenas \(O(\sqrt{n})\) valores distintos, podemos calcular todas as possibilidades eficientemente.

CF1842F

Uma abordagem inicial envolve eliminar valores absolutos com programação dinâmica em árvores, mas é complexa. Alternativamente, fixando o centroide da árvore virtual, os valores absolutos desaparecem, e a resposta pode ser obtida por uma estratégia gulosa.

UOJ388

Para um intervalo dado, uma aresta \((u, v)\) contribui se e somente se, após sua remoção, ambos os componentes conetados resultantes possuem um número ímpar de pontos selecionados. Considere uma subárvore: se um elemento \(x\) da sequência pertence a ela, atribua peso \(1\); caso contrário, \(0\). Calcule a quantidade de posições pares e ímpares com soma prefixada par ou ímpar para determinar a contribuição. Uma árvore de segmentos permite modificações pontuais, e combinando com DSU on tree, a complexidade é \(O(n \log^2 n)\).

#include <bits/stdc++.h>
#define ll long long
using namespace std;

inline ll Leia() {
    int sinal = 1; ll valor = 0; char caractere = getchar();
    while (!isdigit(caractere)) { if (caractere == '-') sinal = -1; caractere = getchar(); }
    while (isdigit(caractere)) valor = (valor << 3) + (valor << 1) + (caractere ^ 48), caractere = getchar();
    return valor * sinal;
}

void Escreva(ll x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) Escreva(x / 10);
    putchar((x % 10) ^ 48);
}

const int MAXN = 100005;
const ll MOD = 998244353;
int numNos, numConsultas, tamanho[MAXN], filhoPesado[MAXN]; ll resposta;
vector<pair<int, ll>> arestas[MAXN];
vector<int> posicoes[MAXN];

struct ArvoreSegmentos {
    struct No { int ini, fim, xorSoma, cnt[2][2]; } nos[MAXN << 2];

    void Atualizar(int u) {
        bool paridade = (nos[u << 1].fim - nos[u << 1].ini + 1) & 1, soma = nos[u << 1].xorSoma;
        nos[u].xorSoma = nos[u << 1].xorSoma ^ nos[u << 1 | 1].xorSoma;
        nos[u].cnt[0][0] = nos[u << 1].cnt[0][0] + nos[u << 1 | 1].cnt[paridade][soma];
        nos[u].cnt[0][1] = nos[u << 1].cnt[0][1] + nos[u << 1 | 1].cnt[paridade][soma ^ 1];
        nos[u].cnt[1][0] = nos[u << 1].cnt[1][0] + nos[u << 1 | 1].cnt[paridade ^ 1][soma];
        nos[u].cnt[1][1] = nos[u << 1].cnt[1][1] + nos[u << 1 | 1].cnt[paridade ^ 1][soma ^ 1];
    }

    void Construir(int u, int l, int r) {
        nos[u].ini = l, nos[u].fim = r;
        if (l == r) {
            nos[u].xorSoma = nos[u].cnt[0][0] = nos[u].cnt[0][1] = nos[u].cnt[1][1] = 0;
            nos[u].cnt[1][0] = 1; return;
        }
        int meio = (l + r) >> 1;
        Construir(u << 1, l, meio), Construir(u << 1 | 1, meio + 1, r), Atualizar(u);
    }

    void Modificar(int u, int pos, int val) {
        int l = nos[u].ini, r = nos[u].fim, meio = (l + r) >> 1;
        if (l == r) {
            nos[u].xorSoma = val;
            nos[u].cnt[0][0] = nos[u].cnt[0][1] = nos[u].cnt[1][val ^ 1] = 0;
            nos[u].cnt[1][val] = 1; return;
        }
        Modificar(u << | (pos > meio), pos, val), Atualizar(u);
    }
} seg;

void DFS1(int no, int pai) {
    tamanho[no] = 1;
    for (auto [vizinho, peso] : arestas[no]) {
        if (vizinho != pai) {
            DFS1(vizinho, no), tamanho[no] += tamanho[vizinho];
            if (tamanho[filhoPesado[no]] < tamanho[vizinho]) filhoPesado[no] = vizinho;
        }
    }
}

void Inserir(int no, int val) {
    for (int pos : posicoes[no]) seg.Modificar(1, pos, val);
}

void Adicionar(int no, int pai, int val) {
    Inserir(no, val);
    for (auto [vizinho, peso] : arestas[no]) if (vizinho != pai) Adicionar(vizinho, no, val);
}

void DFS2(int no, int pai, ll peso, bool manter) {
    for (auto [vizinho, p] : arestas[no]) if (vizinho != pai && vizinho != filhoPesado[no]) DFS2(vizinho, no, p, false);
    if (filhoPesado[no]) for (auto [vizinho, p] : arestas[no]) if (vizinho == filhoPesado[no]) DFS2(vizinho, no, p, true);
    for (auto [vizinho, p] : arestas[no]) if (vizinho != pai && vizinho != filhoPesado[no]) Adicionar(vizinho, no, 1);
    Inserir(no, 1);
    resposta = (resposta + (1ll * seg.nos[1].cnt[0][0] * seg.nos[1].cnt[0][1] + 1ll * seg.nos[1].cnt[1][0] * seg.nos[1].cnt[1][1]) % MOD * peso) % MOD;
    if (!manter) Adicionar(no, pai, 0);
}

int main() {
    numNos = Leia(), numConsultas = Leia(), seg.Construir(1, 0, numConsultas);
    for (int i = 1; i < numNos; i++) {
        int u = Leia(), v = Leia(); ll w = Leia();
        arestas[u].emplace_back(v, w), arestas[v].emplace_back(u, w);
    }
    for (int i = 1; i <= numConsultas; i++) posicoes[Leia()].emplace_back(i);
    DFS1(1, 0), DFS2(1, 0, 0ll, false), Escreva(resposta);
}

P14428

Conclusão principal: sob a condição de que três pontos não são colineares, para cada par de triângulos válidos, existem exatamente duas retas que separam os dois triângulos em semiplanos distintos e intersectam ambos. Intuitivamente, escolha qualquer reta que separe os triângulos e rotacione-a no sentido horário ou anti-horário. Para resolver, enumeramos dois pontos como pontos de tangência, calculamos a contagem de cores em cada semiplano usando ordenação por ângulo polar e dois ponteiros. É necessário discutir a qual semiplano cada ponto pertence.

#include <bits/stdc++.h>
#define ll long long
using namespace std;

inline ll Leia() {
    int sinal = 1; ll valor = 0; char caractere = getchar();
    while (!isdigit(caractere)) { if (caractere == '-') sinal = -1; caractere = getchar(); }
    while (isdigit(caractere)) valor = (valor << 3) + (valor << 1) + (caractere ^ 48), caractere = getchar();
    return valor * sinal;
}

void Escreva(ll x) {
    if (x < 0) putchar('-'), x = -x;
    if (x > 9) Escreva(x / 10);
    putchar((x % 10) ^ 48);
}

const int MAXN = 3005;
int n;
struct Ponto {
    int x, y, cor; double angulo;
    friend bool operator<(Ponto a, Ponto b) { return a.angulo < b.angulo; }
} pontos[MAXN], buffer[MAXN << 1];

bool Verificar(Ponto a, Ponto b) { return 1ll * a.x * b.y - 1ll * a.y * b.x >= 0; }

int main() {
    int i, j, k = 0, total[3] = {0, 0, 0}; ll resposta = 0;
    n = Leia();
    for (i = 1; i <= n; i++) {
        pontos[i].x = Leia(), pontos[i].y = Leia(), pontos[i].cor = Leia();
        total[pontos[i].cor]++;
    }
    for (i = 1; i <= n; i++) {
        int t = 0, cnt[3] = {0, 0, 0}; k = 0;
        cnt[pontos[i].cor] = 1;
        for (j = 1; j <= n; j++) {
            if (j != i) {
                buffer[++k] = {pontos[j].x - pontos[i].x, pontos[j].y - pontos[i].y, pontos[j].cor, atan2(pontos[j].y - pontos[i].y, pontos[j].x - pontos[i].x)};
            }
        }
        sort(buffer + 1, buffer + k + 1);
        for (j = 1; j <= k; j++) buffer[j + k] = buffer[j];
        for (j = 1; j <= k; j++) {
            while (t < k + j - 1 && Verificar(buffer[j], buffer[t + 1])) cnt[buffer[++t].cor]++;
            ll res = 1ll;
            cnt[buffer[j].cor]--;
            if (pontos[i].cor == 0) res = cnt[1] * cnt[2];
            else if (pontos[i].cor == 1) res = cnt[0] * cnt[2];
            else res = cnt[0] * cnt[1];
            if (buffer[j].cor == 0) res *= (total[1] - cnt[1]) * (total[2] - cnt[2]);
            else if (buffer[j].cor == 1) res *= (total[0] - cnt[0]) * (total[2] - cnt[2]);
            else res *= (total[0] - cnt[0]) * (total[1] - cnt[1]);
            resposta += res;
            res = 1ll;
            cnt[pontos[i].cor]--;
            cnt[buffer[j].cor]++;
            if (buffer[j].cor == 0) res = cnt[1] * cnt[2];
            else if (buffer[j].cor == 1) res = cnt[0] * cnt[2];
            else res = cnt[0] * cnt[1];
            if (pontos[i].cor == 0) res *= (total[1] - cnt[1]) * (total[2] - cnt[2]);
            else if (pontos[i].cor == 1) res *= (total[0] - cnt[0]) * (total[2] - cnt[2]);
            else res *= (total[0] - cnt[0]) * (total[1] - cnt[1]);
            resposta += res;
            cnt[pontos[i].cor]++;
            cnt[buffer[j].cor]--;
        }
    }
    Escreva(resposta / 4);
}

P14470

Após um passo, existem apenas \(O(nV)\) intervalos. Podemos calcular ordenando por comprimento (ou posição esquerda). Uma árvore de índices binários (BIT) apresenta baixa constante, ou podemos usar união por tamanho para atingir complexidade estrita \(O(nV^2)\).

P10681

Enumeramos o total de uns \(s\). Primeiro, determinamos a linha ou coluna para o dois, depois distribuímos os dois por colunas em linhas distintas. As linhas são distinguíveis, com um coeficiente de \(\frac{s!}{2^{s - m}}\) (permutação arbitrária, mas os dois em uma coluna são indistinguíveis). Para evitar sobreposições, aplicamos princípio de inclusão-exclusão, considerando que na mesma linha podem ocorrer sequências AB e BA essencialmente idênticas. Finalmente, multiplicamos por \(2^{n - s}\).

AGC020F

Primeiro, quebramos o círculo em uma cadeia (colocando o arco mais longo no início para evitar casos especiais). Decomponmos coordenadas reais em partes inteira e fracionária; a ordem relativa das partes fracionárias é equiprovável. Fixamos essa ordem e usamos programação dinâmica com bitmask de forma bruta.

CF618F

Conjecturamos que uma solução sempre existe. Calculamos as somas prefixadas \(a'\) e \(b'\). Encontramos o último \(j\) tal que \(a_j' \le b_i'\). Se \(b_i' = a_j'\), a resposta é direta; caso contrário, como o intervalo de valores é \([1, n]\), temos \(b_i' - a_j' < n\). Pelo princípio da casa dos pombos, podemos construir uma solução diretamente.