E. Binary Matrix

题意

给一个很大的矩阵，问联通块的个数是多少。其中因为矩阵非常大，用的16进制输入的。

解法

这题非常卡常，光是读入量就已经1.6e7了，所以这里我使用了getchar()来读入。
然后对于联通块的个数，就是总的1个数 - 并查集合并的次数

考虑一行一行处理并查集，同一行遍历相邻两个字符，进行合并，不同行，就当前行跟上一行进行合并，在同为1的时候。
对于并查集的fa[]数组，其值需要再下一次做并查集的时候进行改变。

上一行的fa[]数组，范围是，下一行是, 当处理完这两行的后，要把下一行作为下一次操作的上一行，要做以下2个操作：

1. 将字符串进行拷贝到上一行
2. 将fa[]数组映射到，这样就不含引起并查集冲突。

代码

#pragma GCC optimize(2)
#include <bits/stdc++.h>
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e5+100;
const ll maxM = 1e6+10;
const ll inf = 1e8;
const ll inf2 = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

template<class T> void pt(T x){
    cout<<x<<" ";
}

template <typename T, typename... Args>
void pt(const T& t, const Args& ... data){
    cout<<t<<" ";
    pt(data...);
}


//--------------------------------------------

int N,M;
char line1[maxn];
char line2[maxn];
int fa[maxn*2];
int ind[maxn*2];
void work(char line[],int idx,char c){
    int v;
    if('0' <=c && c <='9') v = c - '0';
    else v = 10 + c-'A';
    int w[4],tail = 3;
    for(int i = 0;i<4;i++) w[i] = 0;
    while(v){
        w[tail--] = v%2;
        v/=2;
    }
    for(int i = 0;i<4;i++){
        line[idx+i] = '0'+w[i];
    }
}
int total = 0,bin = 0;
int find(int x){
    return x == fa[x] ? x : fa[x] = find(fa[x]);
}
void solve(){
    for(int j = 1;j<=M;j++) fa[M+j] = M+j;
    for(int j = 2;j<=M;j++){
        if(line2[j-1] == '1' && line2[j] == '1'){
            int fx = find(M + j-1),fy = find(M + j);
            if(fx != fy){
                bin++;
                fa[fx] = fy;
            }
        }
    }
    for(int j = 1;j<=M;j++){
        if(line1[j] == '1' && line2[j] == '1'){
            int fx = find(j),fy = find(M+j);
            if(fx != fy){
                bin++;
                fa[fx] = fy;
            }
        }
    }
}
void init(){ //把下一行的信息，拷贝到上一行，并重新映射fa数组
    for(int i = 1;i<=2*M;i++) ind[i] = 0;
    for(int j = 1;j<=M;j++) fa[M+j] = find(M+j);
    for(int j = 1;j<=M;j++){
        if(ind[fa[M+j]] == 0){
            ind[fa[M+j]] = j;
        }
    }
    for(int j = 1;j<=M;j++){
        fa[j] = ind[fa[M+j]];
    }
    for(int j = 1;j<=M;j++) line1[j] = line2[j];
}
int main(){
    // debug_in;

    read(N,M);
    for(int j = 1;j<=M;j++) fa[j] = j;
    for(int i = 1;i<=N;i++){
        for(int j = 1;j<=M/4;j++){
            char c;c = getchar();
            while(!(('0'<=c &&c <='9') || ('A'<=c && c<='F'))) c = getchar();//加快读入
            work(line2,(j-1)*4 + 1,c); //填入到字符数组中
        }
        for(int j = 1;j<=M;j++) if(line2[j] == '1') total++;
        if(i == 1) { //第一行特殊处理
            for(int j = 1;j<=M;j++) fa[M + j] = M + j;
            for(int j = 2;j<=M;j++) {
                if(line2[j-1] == '1' && line2[j] == '1'){
                    int fx = find(M + j-1),fy = find(M + j);
                    if(fx != fy){
                        bin++;
                        fa[fx] = fy;
                    }
                }
            }
            init();
        }
        else {
            solve();
            init();
        }

    }
    printf("%d\n",total - bin);


    return 0;
}