Após resolver muitos problemas de ATT, percebi que minha capacidade de adivinhar soluções melhorou!!

11.11

A. [2011福建集训] Moldura de Foto

Após vinte minutos pensando, formulei uma conclusão que parecia correta. Como havia apenas um pequeno exemplo de entrada e o problema não mencionava self-loops, inclusive sugerindo que não havia, e os dados foram propositalmente construídos com self-loops, minha solução recebeu apenas 20 pontos.

No final, o ciclo deve ter grau 2 para cada vértice, então para vértices com grau maior que 2, precisamos fazer uma divisão. Se o grau to ímpar, vamos produzir um vértice de grau 1, e a resposta final é o número de divisões mais metade do número de vértices de grau 1. Nota especial: handles também casos onde o grafo não é conectado e vários componentes são ciclos, quando precisamos desmontar esses ciclos também.

atualização: O problema original não sei por que falhou, a diferença foi grande.

Alguns casos especiais

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

struct UnionFind {
    vector<int> parent, size, grau;
    
    UnionFind(int n) {
        parent.resize(n + 1);
        size.resize(n + 1, 1);
        grau.resize(n + 1, 0);
        for (int i = 0; i <= n; i++) parent[i] = i;
    }
    
    int find(int x) {
        if (parent[x] == x) return x;
        return parent[x] = find(parent[x]);
    }
    
    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x != y) {
            parent[x] = y;
            size[y] += size[x];
        }
    }
};

long long ler() {
    long long x = 0;
    int f = 1;
    char c = getchar();
    while (!isdigit(c)) {
        if (c == '-') f = -1;
        c = getchar();
    }
    while (isdigit(c)) {
        x = x * 10 + (c - '0');
        c = getchar();
    }
    return x * f;
}

int main() {
    int n = ler(), m = ler();
    UnionFind dsu(n + m + 5);
    int total = n;
    
    for (int i = 0; i < m; i++) {
        int u = ler(), v = ler();
        if (!u) u = ++n, total++;
        if (!v) v = ++n, total++;
        dsu.grau[u]++;
        dsu.grau[v]++;
        dsu.unite(u, v);
    }
    
    vector<int> contAlto(n + 1, 0), contImpar(n + 1, 0);
    vector<bool> marcado(n + 1, false);
    
    for (int i = 1; i <= n; i++) {
        int raiz = dsu.find(i);
        contAlto[raiz] += (dsu.grau[i] > 2);
        contImpar[raiz] += (dsu.grau[i] & 1);
        if (dsu.size[raiz] == 1 && dsu.grau[i] == 0) total--;
    }
    
    int resposta = 0, contador = 0;
    for (int i = 1; i <= n; i++) {
        int raiz = dsu.find(i);
        if (marcado[raiz]) continue;
        
        if (dsu.size[raiz] == 1) {
            if (dsu.grau[raiz] == 0) continue;
            contImpar[raiz] += 2;
            if (dsu.grau[raiz] == 2) resposta++;
        }
        
        marcado[raiz] = true;
        resposta += contAlto[raiz];
        
        if (!contImpar[raiz] && total > 1) {
            if (!contAlto[raiz]) resposta++;
            contImpar[raiz] += 2;
        }
        contador += contImpar[raiz];
    }
    
    cout << resposta + contador / 2;
    return 0;
}

B. [CQOI2013] Binário A+B

Problema relativamente simples, mas havia um detalhe tricky. Construí uma solução por tentativa, mas em alguns casos específicos (como abaixo) não funcionou, resultando em 90 pontos.

Para todos os casos exceto o mencionado acima, podemos usar ganância: colocamos os bits 1 da string binária com mais bits (chamada de string A) no final, e construímos o menor B possível que satisfaça as condições. O C resultante será o menor possível.

C.

Não modificado.

11.12

O mais simples, 100+100+40=240

A.

Após dez minutos pensando, formulei uma conclusão que parecia correta.

Primeiro, uma coluna deve ser processada continuamente. Para a mesma coluna, ordenamos as probabilidades de sucesso de forma crescente e processamos nessa ordem. Considere a ordem de processamento de colunas diferentes. Seja P_i a probabilidade de que a coluna i seja completamente eliminada, e E_i o número esperado de operações para a coluna i. Considere duas colunas adjacentes i, j:

• Se i vem antes de j, o número esperado de operações é E_i + (1 - P_i) * E_j.
• Se j vem antes de i, o número esperado de operações é E_j + (1 - P_j) * E_i.

i vem antes de j se e somente se E_i + (1 - P_i) * E_j ≤ E_j + (1 - P_j) * E_i, o que após manipulação resulta em P_i / E_i ≥ P_j / E_j.

Após ordenar as colunas, o DP de expectativa é bastante direto.

B.

Solução do Problema: Verificar se um d é válido é um problema de maximum clique, sendo difícil de resolver diretamente. **Para problemas NPC em grafos gerais, consideramos fortalecer restrições e transformar em problemas de grafo bipartido.**Enumeramos o diâmetro dos pontos selecionados (x_p, y_p), (x_q, y_q). Os outros pontos selecionados precisam estar dentro de um círculo com centro neles e raio d = dis(p, q). Os dois círculos se intersectam formando uma região. Conectando p, q, dividimos essa região em partes superior e inferior. Pontos na mesma parte têm distância ≤ d, então relações de repulsão ocorrem apenas entre as partes. Conectamos as relações de repulsão como arestas e calculamos o máximo conjunto independente do grafo bipartido. Complexidade de tempo O(n^5), constante muito pequena, pode passar.

Eu não quis enfrentar o NPC, então após resolver por bipartição, fiz uma abordagem gulosa: ordeno os pontos por grau de forma crescente. Se o ponto atual pode ser adicionado à maximum clique e após adicionar, a interseção dos vizinhos na maximum clique é ≥ m, então adiciono. Obviamente isso não tem correção, então embaralhamos 1777 vezes e passou.

Na verdade, não precisava de tantas vezes.

C. Árvore de Furukawa Nagisa

Mais uma vez, invertemos o pensamento difíceis. Definimos caminhos que satisfazem ≡ x (mod y) como bons, e os outros como maus. Um trio inválido tem exatamente dois pontos conectados simultaneamente a um caminho bom e um mau. Sejam in1_i e out1_i o número de caminhos bons que terminam em i e começam em i respectivamente, e analogamente in0_i e out0_i para caminhos maus. A contribuição desse ponto é: 2 * in1_i * in0_i + 2 * out1_i * out0_i + in1_i * out0_i + in0_i * out1_i

Como cada三元环 é contado duas vezes, o número de casos inválidos deve ser dividido por 2 no final. A resposta final é n^3 - ans/2. in1_i e out1_i podem ser encontrados usando divide and conquer na árvore, in0_i = n - in1_i, out0_i = n - out0_i.

Observações

Após completar o problema A, fiz um teste e descobri que estava errado. O motivo foi que durante a ordenação, simplesmente ordenei pela probabilidade de sucesso de forma decrescente, e para probabilidades iguais, pelo número esperado de operações de forma crescente.

bool cmp(int x, int y) {
    return s[x] == s[y] ? b[x] < b[y] : s[x] > s[y];
}

Então percebi que a probabilidade é decrescente e a expectativa é crescente, então escrevi 4 funções de comparação diferentes para obter o mínimo.

bool cmp1(int x, int y) { return (s[x] / max(b[x], 1e-8)) > (s[y] / max(b[y], 1e-8)); }
bool cmp2(int x, int y) { return s[x] == s[y] ? b[x] < b[y] : s[x] > s[y]; }
bool cmp3(int x, int y) { return b[x] == b[y] ? s[x] > s[y] : b[x] < b[y]; }
bool cmp4(int x, int y) { return s[x] - b[x] > s[y] - b[y]; }

Após a competição, descobri que a primeira função era a correta.