Luogu5513 [CEOI2013]Board

发布于 2020-10-22  41 次阅读


Link

因为是考试的题目,所以讲下部分分(无疑是暴露了考试的时候没有切掉这道题

10pts

这一档部分分最多只会有2^{10}个点,所以可以直接按照题目描述的方法建图,然后跑一边最短路

30pts

现在我们要从uv,假设一条路径上最浅的点是w

那么从uw同深度的点纵方向上至少要跳dep[u] - dep[w] - 1个点,对于v同理

dep[w]层上,u,v相遇就要跳|u\ mod\ 2^{dep[w]} - v\ mod\ 2^{dep[d]}|条边

所以我们可以枚举这个w的深度,则纵向边还需跳dep[u] - dep[v] - 2 * dep[w]

100pts

考虑正解

这个题最妙的地方就在于如何用给定字符串求出其与根最短路(只通过纵向边)

实际上返祖操作和往同层左右点跳的操作都可以转换为往左跳和往右跳

比如说返祖操作,相当于最后一个往左右儿子跳的那个操作不做

对于往同层右边的点跳,假如这个点现在是左儿子,那么相当于跳到右儿子去,就是一次返祖+往右跳

我们用0表示往左儿子跳,1往右儿子跳,我们现在只要维护一个二进制数,并且可以做一些操作

(建议在纸上手动模拟所有操作和与之对应的二进制操作,下面会直接给出答案)

  1. 对于往左儿子跳,相当于在二进制数的末尾填了一个0,往右儿子就是1
  2. 返祖就是去掉最后一位,注意要考虑进位
  3. 往同层左边的点跳,相当于给整个数-1,右边就是+1 (此部分墙裂建议模拟验证)

好了,我们现在只要维护一个二进制数的加法和进位操作就可以了

特别要注意的是,如果直接这么写一个二进制的高精度会被最后一个点卡(卡成O(n^2),可以构造一下)。所以你可以考虑使用线段树把操作的复杂度降到log级别,也可以看下文介绍的方法。

注意到返祖和同层跳点这里两种操作是互不影响的。也就是说,改变这两种操作的顺序对答案不会造成影响。同时这两种操作是唯二涉及进位的操作。如果每次进行这两种操作就进位就会被卡,所以其实可以把这两种操作记下来,最后同一进位。

Summary

这道题的启发就是,把一个不太好维护的操作转换成数的操作。在一棵二叉树上可以优先考虑二进制数。

Code

又到了我最喜欢的代码环节

#include <bits/stdc++.h>
using namespace std;

const int SIZE = 2e5 + 5;
const int inf = (1 << 20);

int lena, lenb;
int a[SIZE], b[SIZE];
char stra[SIZE], strb[SIZE];

inline void carryA(int pos)
{
    a[pos - 1] += ((a[pos] - (a[pos] & 1)) >> 1);
    a[pos] &= 1;
}

inline void carryB(int pos)
{
    b[pos - 1] += ((b[pos] - (b[pos] & 1)) >> 1);
    b[pos] &= 1;
}

inline void solve()
{
    int lentha = strlen(stra), lenthb = strlen(strb);
    for (register int i = 0; i < lentha; ++ i) {
        if (stra[i] == '1') a[++ lena] = 0;
        else if (stra[i] == '2') a[++ lena] = 1;
        else if (stra[i] == 'U') carryA(lena), -- lena;
        else if (stra[i] == 'L') -- a[lena];
        else if (stra[i] == 'R') ++ a[lena];
    }   
    for (register int i = lena; i > 1; -- i) carryA(i);

    for (register int i = 0; i < lenthb; ++ i) {
        if (strb[i] == '1') b[++ lenb] = 0;
        else if (strb[i] == '2') b[++ lenb] = 1;
        else if (strb[i] == 'U') carryB(lenb), -- lenb;
        else if (strb[i] == 'L') -- b[lenb];
        else if (strb[i] == 'R') ++ b[lenb];
    }   
    for (register int i = lenb; i > 1; -- i) carryB(i);
}

int main()
{
    scanf("%s", stra); scanf("%s", strb);
    solve();
    // printf("%d %d\n", lena, lenb);
    int len = std::min(lena, lenb), ans = 2e9, del = 0;
    for (register int i = 0; i <= len && abs(del) < inf; ++ i) {
        del = (del << 1) + (a[i] - b[i]);
        ans = std::min(ans, abs(del) + ((len - i) << 1));
    }   
    printf("%d\n", ans + abs(lena - lenb));
    return 0;
}

朴实沉毅