题解：P14002 [eJOI 2025] Navigation

· · 题解

题目链接

P14002 [eJOI 2025] Navigation

解题思路

先考虑树怎么做，容易想到我们可以令 0 表示没遍历过的点，1 表示遍历过但邻域没遍历完全的点，2 表示遍历过且邻域被遍历完全的点，直接 dfs 即可，次数为 2n 量级，但是直接写 Sub1 会爆，考虑如果在邻域点权没有 0 的时候去 1 节点时将这个节点染色为 2，可以通过 Sub1~4，获得 38 分。

考虑这个东西为什么会爆？发现环的时候会有以下情况：

dfs 到这里时，如果形成以下路径就倒闭了！

此时右下角这个节点就遍历不到了，因此这种情况下我们会挂掉。

那么比较显然，我们要用到颜色 3 时就是上图的这种情况，遇到进入环的点时，我们需要及时返回颜色 3 对应的节点，不然就会出现图 2 的情况，就倒闭了。

感受一下，注意到我们此时的路径都在这个环内，因此邻域一定只有 2 个颜色 1 的节点，那么我们只需要分讨以下这两个点给出的信息有什么不同（由于遍历到这两个点时邻域有颜色 3，因此我们可以知道是图 1 这种情况），发现进入这个环的点会有 \ge 2 个颜色 1，而这个点会有 1 个颜色 1，因此我们可以直接区分这两个点，那么我们发现这种情况就做完了！

当然我们这里有一个前提是存在一个入环点，考虑起点在环上的情况咋办。注意到起点在环上时，类似树的情况，我们可能会进入别的环，进入环时我们的算法就是对的，且由于我们遍历到第一次时，点的颜色类型为 1，因此我们最坏的情况就只有绕着这个环多走一圈，不会影响正确性。

分析一下次数，考虑到环的长度至少为 3，而对于一个长度为 3 的环操作次数为 6 次，而三元环与三元环可以存在一个点是重合的，因此后面每加 2 个点操作次数就会多 6，而前面说的沿着环多走一圈的情况一定次数不会比三元环套起来的操作次数更多，因此操作次数一定 \le 3n，可以通过此题。

std::pair<int, int> navigate(int x, std::vector<int> v)
{
    ll S=0,nw=0,c[4]={0,0,0,0},to[4]={-1,-1,-1,-1};
    forl(i,0,(ll)v.size()-1)
        c[v[i]]++,
        to[v[i]]=i;
    if(c[3])
    {
        if(c[1]>=2)
            return {1,to[3]};
        if(c[1]==0)
            exit(-1);
        return {0,to[3]};
    }
    if(c[0])
    {
        if(x==3)
            return {2,to[0]};
        return {1,to[0]};
    }
    if(c[1]==1)
        return {2,to[1]};
    if(c[1]==2)
    {
        if(x<=1)
            return {3,to[1]};
        if(x==3)
            forl(i,0,(ll)v.size()-1)
                if(v[i]==1)
                    return {2,i};
    }
    return {-1,-1};
}