题解 [模拟赛 2022.11.24] 火柴

· · 个人记录

在 NKOJ 上被卡常成 60 \operatorname{pts} 了。摆烂。

首先把这张图建出来并边双缩点，接下来分两种情况讨论：

此时你可以拿任意一条删了以后可以换的边。

需要注意的是这里横竖边和斜叉边的方案数是不同的，因为你还可以把斜叉边换个方向。

把斜叉边换个方向需要稍微特判一下，下面先忽略这种情况。

考虑抓出原图的 dfs 生成树，这棵树一定包含所有割边。

若删了某条割边 (u, v)（假定 u = fa_v），则我们需要在 v 子树内外找一对原图中没有且不能跟原来的斜叉边交叉的边。

在原图上讨论一下哪些边可行，最后以 dfs 序为下标线段树合并即可（需要支持单点加、区间查）。

综上，时间复杂度为 O(nm \log nm)。细节有亿点多，可以参考一下代码。

代码：

#include <iostream>
#include <stack>
#include <vector>
#include <cstdio>
#include <cctype>

using namespace std;

typedef long long ll;

typedef struct {
    int nxt;
    int start;
    int end;
} Edge;

typedef struct {
    int ls;
    int rs;
    int sum;
} Node;

int cnt = 1, seg_id = 0;
int graph_id[707][707], val[707][707], head[490007], in[490007], low[490007], fa[490007], out[490007], belong[490007], root[490007];
char s[707][707];
bool vis[490007];
Edge edge[7840007];
Node tree[9800007];
stack<int> stk;
vector<int> v[490007];

inline void add_edge(int start, int end){
    cnt++;
    edge[cnt].nxt = head[start];
    head[start] = cnt;
    edge[cnt].start = start;
    edge[cnt].end = end;
}

void tarjan(int u, int father, int &id, int &bcc_cnt){
    in[u] = low[u] = ++id;
    vis[u] = true;
    stk.push(u);
    for (register int i = head[u]; i != 0; i = edge[i].nxt){
        if (i == father) continue;
        int x = edge[i].end;
        if (!vis[x]){
            fa[x] = u;
            tarjan(x, i ^ 1, id, bcc_cnt);
            low[u] = min(low[u], low[x]);
        } else {
            low[u] = min(low[u], in[x]);
        }
    }
    out[u] = id;
    if (in[u] == low[u]){
        int cur;
        bcc_cnt++;
        do {
            cur = stk.top();
            stk.pop();
            belong[cur] = bcc_cnt;
        } while (cur != u);
    }
}

inline void append(int x, int y){
    v[x].push_back(y);
    v[y].push_back(x);
}

inline bool check(int u, int v){
    return in[u] <= in[v] && in[v] <= out[u];
}

inline bool replace(int x, int y, int z, int w){
    if (in[z] < in[w]) swap(z, w);
    return belong[x] != belong[y] && belong[z] != belong[w] && check(z, x) != check(z, y);
}

inline void update(int x){
    tree[x].sum = tree[tree[x].ls].sum + tree[tree[x].rs].sum;
}

void inc(int &x, int l, int r, int pos){
    if (x == 0) x = ++seg_id;
    if (l == r){
        tree[x].sum++;
        return;
    }
    int mid = (l + r) >> 1;
    if (pos <= mid){
        inc(tree[x].ls, l, mid, pos);
    } else {
        inc(tree[x].rs, mid + 1, r, pos);
    }
    update(x);
}

int get_sum(int x, int L, int R, int l, int r){
    if (x == 0 || l > r) return 0;
    if (l <= L && R <= r) return tree[x].sum;
    int mid = (L + R) >> 1, ans = 0;
    if (l <= mid) ans = get_sum(tree[x].ls, L, mid, l, r);
    if (r > mid) ans += get_sum(tree[x].rs, mid + 1, R, l, r);
    return ans;
}

int merge(int x, int y, int l, int r){
    if (x == 0) return y;
    if (y == 0) return x;
    if (l == r){
        tree[x].sum += tree[y].sum;
        return x;
    }
    int mid = (l + r) >> 1;
    tree[x].ls = merge(tree[x].ls, tree[y].ls, l, mid);
    tree[x].rs = merge(tree[x].rs, tree[y].rs, mid + 1, r);
    update(x);
    return x;
}

ll dfs(int u, int n){
    int size = v[u].size();
    ll ans = 0;
    for (register int i = 0; i < size; i++){
        inc(root[u], 1, n, in[v[u][i]]);
    }
    for (register int i = head[u]; i != 0; i = edge[i].nxt){
        int x = edge[i].end;
        if (fa[x] == u){
            ans += dfs(x, n);
            if (belong[u] != belong[x]) ans += get_sum(root[x], 1, n, 1, in[x] - 1) + get_sum(root[x], 1, n, out[x] + 1, n);
            root[u] = merge(root[u], root[x], 1, n);
        }
    }
    return ans;
}

int main(){
    int n, m, dot_id = 0, dfn_id = 0, bcc_cnt = 0, rem = 0, x = 0, chdir = 0, y = 0;
    scanf("%d %d", &n, &m);
    for (register int i = 1; i <= n; i++){
        scanf("%s", &s[i][1]);
    }
    for (register int i = 1; i <= n; i++){
        for (register int j = 1; j <= m; j++){
            graph_id[i][j] = ++dot_id;
            val[i][j] = isdigit(s[i][j]) ? s[i][j] - '0' : s[i][j] - 'A' + 10;
        }
    }
    for (register int i = 1; i <= n; i++){
        for (register int j = 1; j <= m; j++){
            if (val[i][j] & 1){
                add_edge(graph_id[i][j], graph_id[i - 1][j + 1]);
                add_edge(graph_id[i - 1][j + 1], graph_id[i][j]);
            }
            if (val[i][j] & 2){
                add_edge(graph_id[i][j], graph_id[i][j + 1]);
                add_edge(graph_id[i][j + 1], graph_id[i][j]);
            }
            if (val[i][j] & 4){
                add_edge(graph_id[i][j], graph_id[i + 1][j + 1]);
                add_edge(graph_id[i + 1][j + 1], graph_id[i][j]);
            }
            if (val[i][j] & 8){
                add_edge(graph_id[i][j], graph_id[i + 1][j]);
                add_edge(graph_id[i + 1][j], graph_id[i][j]);
            }
        }
    }
    tarjan(1, 0, dfn_id, bcc_cnt);
    for (register int i = 1; i <= n; i++){
        for (register int j = 1; j <= m; j++){
            if (!(val[i][j] & 1)){
                if (i > 1 && j < m && !(val[i - 1][j] & 4)){
                    rem += 2;
                    append(graph_id[i][j], graph_id[i - 1][j + 1]);
                }
            } else {
                if (belong[graph_id[i][j]] == belong[graph_id[i - 1][j + 1]]) x++;
                if (!(val[i - 1][j] & 4) && replace(graph_id[i - 1][j], graph_id[i][j + 1], graph_id[i][j], graph_id[i - 1][j + 1])) chdir++;
            }
            if (!(val[i][j] & 2)){
                if (j < m){
                    rem++;
                    append(graph_id[i][j], graph_id[i][j + 1]);
                }
            } else if (belong[graph_id[i][j]] == belong[graph_id[i][j + 1]]){
                y++;
            }
            if (!(val[i][j] & 4)){
                if (i < n && j < m && !(val[i + 1][j] & 1)) append(graph_id[i][j], graph_id[i + 1][j + 1]);
            } else {
                if (belong[graph_id[i][j]] == belong[graph_id[i + 1][j + 1]]) x++;
                if (!(val[i + 1][j] & 1) && replace(graph_id[i + 1][j], graph_id[i][j + 1], graph_id[i][j], graph_id[i + 1][j + 1])) chdir++;
            }
            if (!(val[i][j] & 8)){
                if (i < n){
                    rem++;
                    append(graph_id[i][j], graph_id[i + 1][j]);
                }
            } else if (belong[graph_id[i][j]] == belong[graph_id[i + 1][j]]){
                y++;
            }
        }
    }
    cout << dfs(1, dot_id) + chdir + (ll)x * (rem + 1) + (ll)y * rem;
    return 0;
}