MX Day 10

· · 生活·游记

Grid：

做法：

  1. 我们的思路大体是这样的，首先我们发现我们的每一条不同路径包含的障碍数是互不相同的，所以我们可以根据我们加入障碍的顺序计数；
  2. 之后，我们可以考虑合并障碍，因为我们发现如果障碍分别在(x+1,y)和(x,y+1)处，我们可以将(x,y)到(x+1,y+1)的所有格子全部设成障碍，这样是等价的；
  3. 之后，我们可以合并这些障碍，如果有一块联通快的八个方向中的一个方向有另一个联通块相连且有交点（可以是网格线交点），那么可以合并到一块，因为连在一起的联通快也是不可通行的。

code：

#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read()
{
    int x = 0, f = 1;
    char ch = getchar();
    while (!isdigit(ch))
    {
        if (ch == '-')
            f = -1;
        ch = getchar();
    }
    while (isdigit(ch))
    {
        x = x * 10 + ch - 48;
        ch = getchar();
    }
    return x * f;
}
const int N = 2005, M = 5e6, dx[] = {1, 1, 0}, dy[] = {0, 1, 1};
int n, m, cnt, ans = 1, op[M], fa[M], id[M];
string s[N];
int getf(int x)
{
    return fa[x] == x ? x : fa[x] = getf(fa[x]);
}
signed main()
{
    freopen("grid.in", "r", stdin);
    freopen("grid.out", "w", stdout);
    n = read(), m = read();
    for (int i = 0; i < n; i++)
    {
        cin >> s[i];
    }
    iota(fa, fa + n * m, 0);
    queue<array<int, 2>> q;
    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < m; y++)
        {
            if (s[x][y] == '#')
            {
                q.push({x, y});
            }
        }
    }
    auto upd = [&](int x, int y)
    {
        if (s[x][y] == '.')
        {
            s[x][y] = '#', q.push({x, y});
        }
    };
    auto chk = [&](int x, int y)
    {
        if (x < 0 || y < 0 || x > n - 2 || y > m - 2)
        {
            return;
        }
        if (s[x + 1][y] == '#' && s[x][y + 1] == '#')
        {
            upd(x, y), upd(x + 1, y + 1);
        }
    };
    while (!q.empty())
    {
        auto t = q.front();
        q.pop();
        int x = t[0], y = t[1];
        if (!x && y < m - 1)
        {
            upd(x, y + 1);
        }
        if (!y && x < n - 1)
        {
            upd(x + 1, y);
        }
        if (x == n - 1 && y)
        {
            upd(x, y - 1);
        }
        if (y == m - 1 && x)
        {
            upd(x - 1, y);
        }
        chk(x - 1, y);
        chk(x, y - 1);
    }
    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < m; y++)
        {
            if (s[x][y] == '#')
            {
                for (int o : {0, 1, 2})
                {
                    int nx = x + dx[o], ny = y + dy[o];
                    if (nx < 0 || ny < 0 || nx >= n || ny >= m || s[nx][ny] == '.')
                    {
                        continue;
                    }
                    int u = getf(x * m + y), v = getf(nx * m + ny);
                    if (u != v)
                    {
                        fa[u] = v;
                    }
                }
            }
        }
    }
    for (int x = 0; x < n; x++)
    {
        for (int y = 0; y < m; y++)
        {
            if (s[x][y] == '#')
            {
                int u = getf(x * m + y), &p = id[u];
                if (!p)
                {
                    p = ++cnt;
                }
                if (!x || y == m - 1)
                {
                    op[p] |= 1;
                }
                if (!y || x == n - 1)
                {
                    op[p] |= 2;
                }
            }
        }
    }
    for (int i = 1; i <= cnt; i++)
    {
        ans++;
        if (op[i] == 3)
        {
            cout << 0;
            return 0;
        }
        if (op[i])
        {
            ans--;
        }
    }
    cout << ans;
    return 0;
}

LCP：

做法：

  1. 首先，我们可以发现我们在求M组最大值时可以用容斥得到答案，容斥问题详解；
  2. 我们可以分类讨论，因为只有三种情况，要么M=1，要么M>1，所以我们这给了我们很大便利；
  3. 我们首先考虑M=1的情况：反正只有一条，直接LCA计算；
  4. 当M大于1时，我们可以发现，我们通过容斥的式子得知我们主要要求的是两条或者三条特定序列的最小LCP，所以，我们首先考虑我们要快速得到几组串的最小LCP，我们可以将每一条串的每一个字符以相对顺序组合在一起，也就是假设有aa和bc，我们的组合顺序是先将第一位a和b合在一起，再将a和c合在一起，形成abac，再和另外的新串求LCP；
  5. 这一思想的本质就是我们可以发现我们在找最小值时我们最小的长度也就是一一对应的……

T3：