P5372 题解

namelessgugugu · 2023-11-12 23:51:43 · 题解

做完之后有人告诉我这题上界卡的很死，除了官解做法都很难通过，我寻思这都给了两倍常数了还能卡属实是有点厉害。

哦什么，原来是我爆标了，那没事了。

题意

懒得写了，直接看链接吧。

题解

注意到对图进行黑白交替染色（认为 (1, 1) 被染成黑）后黑色格子比白色格子多 1 个，因此可知空点始终落在黑格子中。

而对于一个 1 \times 2 的积木，其正好覆盖一黑一白两个格子，且由于空点始终在黑格子上，会发现每次操作不改变积木覆盖到的白格子，因此也可以用一个白格子来指代一块积木。

想象一下，操作的过程大概相当于空点在黑点上借积木实现移动，所以可以如此建模：把黑格子当作点，白格子当作边，把空点当作在图上游走的棋子。

具体地，对于一个积木，设其初始位置为 ((x_1, y_1), (x_2, y_2))，其中 (x_1, y_1) 是白格子，最终位置为 ((x_1, y_1), (x_3, y_3))，则相当于需要棋子从 (x_3, y_3) 走到 (x_2, y_2) 一次，于是连一条 (x_3, y_3) \to (x_2, y_2) 的边。

而最后要做的就是让棋子把所有边都访问一遍，由于这张图除了起点终点每个点的入度出度都为 1，可以直接跑欧拉路径解决。

但是事情并没有那么简单，很显然这张图并没有保证连通，我们需要先对这张图做一些调整使其连通。

能做的调整其实就是让某个积木不一定被操作仅一次，而是有可能先被操作到一个中间态，再被操作到终态。如果让某个积木被操作正好两次，设中间态为 ((x_1, y_1), (x_4, y_4))，那么连边会改为 (x_3, y_3) \to (x_4, y_4) \to (x_2, y_2)，这样会提出一个新的要求：棋子必须先走过 (x_4, y_4) \to (x_2, y_2)，再走过 (x_3, y_3) \to (x_4, y_4)。

事实上，这样的调整已经足够解决这个问题，而且做法相当简单粗暴：

如果当前有一个 (x_1, y_1) 满足对应的 (x_2, y_2) 和 (x_3, y_3) 尚未与起点连通，且有一个 (x_4, y_4) 已经与起点连通，则直接把其设为中间态。这样就让 (x_2, y_2) 和 (x_3, y_3) 与起点连通了。

由于加中间态只会让 (x_4, y_4) 的出度入度各增加 1，故还是能跑欧拉路径，而且实际上跑出来一定满足刚刚的顺序要求，因为如果从起点出发的棋子都能先走到 (x_3, y_3) 了，显然这个点在调整前就已经与起点连通，那根本不会进行这个调整。

这同样也要求在代码实现时不能无脑调整，一定需要等到有必要调整时再调，所以实现应该是：对起点所在连通块进行遍历，如果遇到上述所说的可以调整的情况，则调整完后需要先遍历 (x_2, y_2) 所在的连通块，标记为已连通，以免之后有蒙古人再次对该连通块进行调整导致答案错误。

显然操作次数为总边数，而一个白格子至多贡献两条边，所以至多操作 nm - 1 次，比其他解法在操作次数上更优一些。

代码

写的时候在 int，pair<int, int> 和 int x, y 之间来回转化，所以比较屎山。

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <utility>
#include <vector>
#include <array>
#define FILEIO(filename) (freopen(filename ".in", "r", stdin), freopen(filename ".out", "w", stdout))
typedef long long ll;
typedef unsigned long long ull;
using std::pair, std::vector, std::array;
const int N = 2005, M = 4000005;
const int dx[8] = {1, 0, -1, 0, 1, 1, -1, -1}, dy[8] = {0, 1, 0, -1, 1, -1, 1, -1};
int n, m;
char a[2][N][N];
int edg[N][N];
inline int id(int x, int y)
{
    return (x - 1) * m + y;
}
inline pair<int, int> getp(int x)
{
    return {(x - 1) / m + 1, (x - 1) % m + 1};
}
inline pair<int, int> getpt(int x, int y, int o)
{
    if(a[o][x][y] == '<')
        return {x, y + 1};
    else if(a[o][x][y] == '>')
        return {x, y - 1};
    else if(a[o][x][y] == 'n')
        return {x + 1, y};
    else if(a[o][x][y] == 'u')
        return {x - 1, y};
    return {-1, -1};
}
inline int findedg(pair<int, int> f, pair<int, int> t)
{
    if(f == t)
        return -1;
    int d1 = t.first - f.first, d2 = t.second - f.second;
    for (int o = 0; o < 8;++o)
        if (d1 == dx[o] * (o < 4 ? 2 : 1) && d2 == dy[o] * (o < 4 ? 2 : 1))
            return o;
    return -2;
}
inline void addedg(pair<int, int> x, int o)
{
    edg[x.first][x.second] |= 1 << o;
    return;
}
int que[M], hd, tl;
bool vis[N][N];
void dfs(int x, int y)
{
    vis[x][y] = 1;
    que[++tl] = id(x, y);
    for (int o = 0; o < 8; ++o)
        if((edg[x][y] >> o) & 1)
        {
            int nx = x + dx[o] * (o < 4 ? 2 : 1), ny = y + dy[o] * (o < 4 ? 2 : 1);
            if(!vis[nx][ny])
                dfs(nx, ny);
        }
    return;
}
void bfs(int s)
{
    hd = 1, tl = 0;
    auto [sx, sy] = getp(s);
    dfs(sx, sy);
    while (hd <= tl)
    {
        auto [x, y] = getp(que[hd++]);
        for (int o = 0; o < 4;++o)
        {
            int nx = x + dx[o], ny = y + dy[o];
            if(nx < 1 || nx > n || ny < 1 || ny > m)
                continue;
            auto f = getpt(nx, ny, 1), t = getpt(nx, ny, 0);
            if(!vis[f.first][f.second])
            {
                dfs(f.first, f.second);
                int e1 = findedg(f, t);
                int e2 = findedg(f, {x, y}), e3 = findedg({x, y}, t);
                if(e1 != -1)
                    edg[f.first][f.second] ^= 1 << e1;
                if(e2 != -1)
                    addedg(f, e2);
                if(e3 != -1)
                    addedg({x, y}, e3);
            }
        }
    }
    return;
}
int res[M << 1], tt;
void getans(int x, int y)
{
    for (int o = 0; o < 8;++o)
        if ((edg[x][y] >> o) & 1)
        {
            int nx = x + dx[o] * (o < 4 ? 2 : 1), ny = y + dy[o] * (o < 4 ? 2 : 1);
            edg[x][y] ^= 1 << o;
            getans(nx, ny);
        }
    res[++tt] = id(x, y);
}
char ans[M << 1];
inline char operate(pair<int, int> f, pair<int, int> t)
{
    pair<int, int> ky = getpt(t.first, t.second, 0);
    int d1 = ky.first - f.first, d2 = ky.second - f.second;
    for (int o = 0; o < 4;++o)
        if(d1 == dx[o] && d2 == dy[o])
        {
            a[0][ky.first][ky.second] = "u>n<"[o];
            a[0][f.first][f.second] = "n<u>"[o];
            a[0][t.first][t.second] = 'o';
            return "DRUL"[o];
        }
    return 0;
}
int main(void)
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n;++i)
        scanf("%s", a[0][i] + 1);
    for (int i = 1; i <= n;++i)
        scanf("%s", a[1][i] + 1);
    int s = 0;
    for (int i = 1; i <= n;++i)
        for (int j = (i & 1 ? 2 : 1); j <= m;j += 2)
        {
            auto f = getpt(i, j, 1), t = getpt(i, j, 0);
            if(f != t)
                addedg(f, findedg(f, t));
        }
    for (int i = 1; i <= n;++i)
        for (int j = 1; j <= m;++j)
            if(a[0][i][j] == 'o')
            {
                s = id(i, j);
                break;
            }
    bfs(s);
    getans((s - 1) / m + 1, (s - 1) % m + 1);
    std::reverse(res + 1, res + 1 + tt);
    for (int i = 1; i < tt;++i)
        ans[i] = operate(getp(res[i]), getp(res[i + 1]));
    puts(ans + 1);
    return 0;
}