USACO 2020 January Contest, Platinum Problem 1. Cave Paintings

题目链接:http://usaco.org/index.php?page=viewproblem2&cpid=996

提交评测:https://www.luogu.com.cn/problem/P6008

 

题解:

  一开始,我想着从左往右进行统计方案数,然后发现转移方程太难写。从下往上进行统计就方便很多。首先要明白,不同的连通块的方案数乘积就是总的方案数。

  那么下面思考如何统计同一连通块中的方案数。假设现在统计到第i层:

  对于一段连续的空位,它有两种情况:

  1、它没有使得若干个块合并。那么这时这段区间的方案数是2

  2、使得若干个下层联通块合并,那么此时又分成对于每个下层连通块,有2种情况:(1)此连通块已经连通了第i层的块,那么此时对于这个连通块的方案数减一再乘到方案数中。(2)没有连通第i层块,直接此连通块的方案数乘到总方案数中。

  记得对于一段连续空位,把全部空位以及下层连通块合并,此操作可以并查集。

  时间复杂度:O(NMα(n*n))

参考代码:

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1005;
const int modu = 1e9 + 7;

char s[maxn][maxn];
int n, m;
int fa[maxn*maxn];
long long f[maxn*maxn];
vector<int> st;

int find(int x)
{
    if (fa[x] == 0) return x;
    return fa[x] = find(fa[x]);
}

int number(int i, int j)
{
    return i*m+j;
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 0; i < n; ++i)
        scanf("%s", s[i]);
    memset(fa, 0, sizeof(fa));
    memset(f, 0, sizeof(f));
    for (int i = n-2; i > 0; --i) {
        st.clear();
        for (int j = 0; j < m; ++j)
            if (s[i][j] == '.') {
                int x = find(number(i, j));
                if (s[i+1][j] == '.') {
                    int y = find(number(i+1, j));
                    st.push_back(y);
                }
                if (s[i][j-1] == '.') {
                    int y = find(number(i, j-1));
                    if (x != y) fa[y] = x;
                }
            }
            else if (s[i][j] == '#') {
                if (j > 0 && s[i][j-1] == '.') {
                    int x = find(number(i, j-1));
                    if (st.size() == 0) f[x] = 2;
                    else {
                        long long res = 1;
                        for (int k = 0; k < st.size(); ++k) {
                            int y = find(st[k]);
                            if (x != y) {
                                if (y / m == i) res = res * ((f[y]-1+modu)%modu) % modu;
                                else res = res*f[y] % modu;
                                fa[y] = x;
                            }
                        }
                        f[x] = (res + 1) % modu;
                    }
                    st.clear();
                }
            }
    }
    long long ans = 1;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < m; ++j)
            if (s[i][j] == '.' && fa[number(i, j)] == 0) {
                ans = ans*f[number(i, j)] % modu;
            }
    printf("%lld\n", ans);
    return 0;
}

 

上一篇:Cable Messenger:语音波纹曲线生成策略


下一篇:USACO 2020 January Contest, Platinum