3 条题解
-
4
每层每个连通块开个点,发现这个跑出来形如一个森林,跑个没有上司的舞会状物做完了。
#include<iostream> #include<algorithm> #include<vector> #define int long long using namespace std; const int N=1e3+7,MOD=1e9+7; int n,m,g[N][N],fa[N],ans=1,col[N][N],vis[N]; int dp[N][N][2],root[N][N]; vector<int> t[N]; int find(int x){ if(fa[x]==x) return x; return fa[x]=find(fa[x]); } void merge(int x,int y){ int fx=find(x),fy=find(y); if(fx==fy) return ; fa[fx]=fy; } int pw(int x,int b){ int res=1; for(;b;b>>=1,x=x*x%MOD) if(b&1) res=res*x%MOD; return res; } signed main(){ // freopen("ex.in","r",stdin); ios::sync_with_stdio(0); cin.tie(0); cin>>n>>m; for(int i=1;i<=n;i++){ for(int j=1;j<=m;j++){ char c; cin>>c; if(c=='#') g[i][j]=0; else g[i][j]=1; } } for(int i=n-1;i>1;i--){ for(int j=2;j<m;j++) fa[j]=g[i][j]?j:0; for(int j=2;j<m;j++) if(g[i][j] && g[i][j-1]) merge(j,j-1); for(int j=2;j<m;j++){ if(t[j].empty()) continue; int u=t[j][0]; for(int v : t[j]) merge(u,v); } for(int j=2;j<m;j++){ t[j].clear(); t[j].shrink_to_fit(); } for(int j=2;j<m;j++){ if(g[i-1][j] && g[i][j]){ int f=find(j); t[f].push_back(j); } } for(int j=2;j<m;j++){ col[i][j]=find(j); root[i][col[i][j]]=1; int x=col[i][j]; dp[i][x][0]=dp[i][x][1]=1; // cout<<col[i][j]<<' '; } // cout<<'\n'; } for(int i=n-1;i>1;i--){ for(int j=1;j<=m;j++) vis[j]=0; for(int j=2;j<m;j++){ int x=col[i][j],y=col[i+1][j]; if(x && y && !vis[y]){ // cout<<"# "<<x<<' '<<y<<' '<<dp[i+1][y][0]+dp[i+1][y][1]<<'\n'; (dp[i][x][1]*=dp[i+1][y][1])%=MOD; (dp[i][x][0]*=(dp[i+1][y][0]+dp[i+1][y][1]))%=MOD; root[i+1][y]=0; vis[y]=1; } } } for(int i=2;i<n;i++) for(int j=2;j<m;j++) if(root[i][j]){ if(dp[i][j][0]+dp[i][j][1]) ans=ans*(dp[i][j][0]+dp[i][j][1])%MOD; } cout<<ans; return 0; } -
4
一种较为好写的带权并查集的做法,合并上下、左右相邻的位置,合并时顺便合并两块的方案数。最后对所有极大连通块的方案数求积即可,无需统计每一行的连通块。
赛时想复杂了。
#include <bits/stdc++.h> #define int long long using namespace std; typedef long long ll; const int MOD = 1e9 + 7; const int N = 1e3 + 5, V = 1e6 + 5; ll n, m, ans; ll f(int x, int y) { return (x - 1) * m + y; } char s[N][N]; int fa[V], vis[V], val[V]; void init() { for(int i=1; i<=n; ++i) { for(int j=1; j<=m; ++j) { int cur = f(i, j); fa[cur] = cur; val[cur] = 1; } } } int get(int u) { if(fa[u] == u) return u; return fa[u] = get(fa[u]); } void merge(int u, int v) { int fu = get(u), fv = get(v); if(fu != fv) { fa[fv] = fu; val[fu] *= val[fv], val[fu] %= MOD; } } signed main() { ios :: sync_with_stdio(0); cin.tie(0), cout.tie(0); cin >> n >> m; for(int i=1; i<=n; ++i) { for(int j=1; j<=m; ++j) { cin >> s[i][j]; } } init(); for(int i=n-1; i>=2; --i) { for(int j=2; j<m; ++j) { if(s[i][j] == '#') continue; if(s[i][j - 1] == s[i][j]) merge(f(i, j - 1), f(i, j)); } for(int j=2; j<m; ++j) { if(s[i][j] == '#') continue; if(s[i + 1][j] == s[i][j]) merge(f(i, j), f(i + 1, j)); } for(int j=2; j<m; ++j) { int fn = get(f(i, j)); if(vis[fn]) continue; vis[fn] = 1, ++val[fn]; } } ans = 1; for(int i=n-1; i>=2; --i) { for(int j=2; j<m; ++j) { if(s[i][j] == '#') continue; if(fa[f(i, j)] == f(i, j)) ans *= val[f(i, j)], ans %= MOD; } } cout << ans << '\n'; return 0; } -
2
写了半天终于对了。应某些人的建议来写一篇题解(实则不建议我写我也会写的)(虽然这道题感觉确实没有到蓝的地步但我自己实现下来感觉也没有wzc说的绿题水准,我自己来看感觉差不多上位青吧)
ps:写题解的时候听歌感觉很不错啊。
正文:
首先我们要知道,这张图是可能被分成一个或数个连通块的,然后联通块之间没有任何关系,也就是说我们可以在弄完后分析每个连通块,然后最后乘法原理把结果乘起来即可。
然后就是分析每个联通块,因为高的会流向低的而低的不会流向高的,所以满足DP最优子结构,高的的状态可以由下面一层得到,我们从 到 循环(1和n是基岩层(bushi)) 然后每层的每个空格我们要分析两个问题:、他和哪些连通:用并查集合并。合并时,两个独立块的方案数相乘(乘法原理)。 、这个空格加水的情况:得到的结果 。
最后处理完之后就是汇总,即为前面说的把每个连通块的结果乘起来。具体做法为找根(并查集)。
这是思路,然后具体实现下来就是存图之后从下往上遍历,每行:遍历这一行每一个空格,每到一个空格就DP合并他能影响到的点(三向); 然后遍历一遍后就给当前层每个连通块 ,表示"在这一行主动放水灌满该块,用vis存储这个块有没有已经被灌满过(哈希一维存点);最后清空当前行 。然后重新遍历每个空格点,如果是根就将结果乘这个点的DP值,最后输出结果
代码如下:
#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,m; int dx[3]={0,1,0},dy[3]={1,0,-1}; ll fa[1000005],dp[1000005],ans=1; bool vis[1000005]; char c[1005][1005]; const ll MOD=1e9+7; void lhhsyn(){ ios::sync_with_stdio(false); cin.tie(0); } int Hash(int x,int y){ return (x-1)*m+y; } int find(ll x){ if(fa[x]==x)return x; return fa[x]=find(fa[x]); } bool is(ll x,ll y){ if(x>1&&y>1&&x<n&&y<m&&c[x][y]!='#')return 1; return 0; } void miku(ll x,ll y){ x=find(x),y=find(y); if(x==y)return; fa[x]=y; dp[y]=dp[x]*dp[y]%MOD; } int main(){ lhhsyn(); cin>>n>>m; int ccf=n*m; for(int i=1;i<=ccf;i++){ fa[i]=i; dp[i]=1; } string s; for(int i=1;i<=n;i++){ cin>>s; for(int j=0;j<s.size();j++){ c[i][j+1]=s[j]; } } for(int i=n-1;i>1;i--){ // 第一步:合并当前行空格与右/下/左三个方向的连通空格 for(int j=2;j<m;j++){ if(c[i][j]=='#')continue; for(int k=0;k<3;k++){ int xx=i+dx[k],yy=j+dy[k]; if(is(xx,yy))miku(Hash(i,j),Hash(xx,yy)); } } // 第二步:给当前层每个连通块 +1,表示"在这一行主动放水灌满该块" for(int j=2;j<m;j++){ if(c[i][j]=='#')continue; int tmp=find(Hash(i,j)); if(vis[tmp])continue; vis[tmp]=1; dp[tmp]=(dp[tmp]+1)%MOD; } // 第三步:清空当前层用过的 vis 标记 for(int j=2;j<m;j++){ if(c[i][j]=='#')continue; vis[find(Hash(i,j))]=0; } } // 最后:遍历所有内部空格,取每个连通块的根节点,方案数相乘 for(int i=2;i<n;i++){ for(int j=2;j<m;j++){ if(c[i][j]=='#')continue; int tmp=Hash(i,j); if(tmp==find(tmp))ans=ans*dp[tmp]%MOD;// 是根节点,代表一个独立连通块 } } cout<<ans; return 0; }总结:这个题是一个并查集 + 逐层 DP + 乘法原理 + 哈希(勉强算入)的一个题。核心在于把物理约束转化为组合计数。这个题也暴露了我并查集等数据结构还有图论等提高级知识薄弱的问题。
如果觉得讲的还行的话麻烦给个赞喵~
记录:2026/10/28 10:28开始补题--2026/10/28 16:22发布题解 (只能说我的并查集熟练度确实不高,然后我没有独立切青蓝题的实力)
- 1
信息
- ID
- 949
- 时间
- 1000ms
- 内存
- 256MiB
- 难度
- 6
- 标签
- (无)
- 递交数
- 36
- 已通过
- 12
- 上传者