初一看，sb题，上去一个并查集，很快啊，返回一个MLE，定睛一看，系统开的内存很小，但是这个算法复杂度又是这么正确
因此考虑优化内存，这样用滚动数组优化即可
这里注意一个问题，平常并查集从那边指那边都是对的，但是滚动数组就不一样了，对于上一层的，一定要指向下一层，因为如果指向上一层，那么在做的时候，上上层的信息已经被滚掉了。这里是个细节，很容易想不清楚就wa死
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int,int> pll; const int N=1e6+10; const int mod=1e9+7; int a[4][100010]; int p[N]; int find(int x){ if(x!=p[x]){ p[x]=find(p[x]); } return p[x]; } int main(){ ios::sync_with_stdio(false); int n,m; cin>>n>>m; int ans=0; int i,j; for(i=1;i<=n;i++){ int now=i&1; string s; cin>>s; s=" "+s; for(int j=1;j<=m/4;j++){ int res; if(s[j]>=‘0‘&&s[j]<=‘9‘){ res=s[j]-‘0‘; } else{ res=s[j]-‘A‘+10; } a[now][j*4]=res&1,ans+=(res&1),res>>=1; a[now][j*4-1]=res&1,ans+=(res&1),res>>=1; a[now][j*4-2]=res&1,ans+=(res&1),res>>=1; a[now][j*4-3]=res&1,ans+=(res&1),res>>=1; } int tmp=now*m; for(int j=1;j<=m;j++){ p[tmp+j]=tmp+j; } for(int j=1;j<m;j++){ if(a[now][j]&&a[now][j+1]){ int pa=find(tmp+j); int pb=find(tmp+j+1); if(pa!=pb){ p[pb]=pa; ans--; } } } for(int j=1;j<=m;j++){ if(a[now][j]&&a[now^1][j]){ int pa=find(tmp+j); int pb=find((now^1)*m+j); if(pa!=pb){ p[pb]=pa; ans--; } } } } cout<<ans<<endl; return 0; }
原文：https://www.cnblogs.com/ctyakwf/p/14094020.html
