P8977 题解

xiaoqian02 · 2023-02-01 19:33:18 · 题解

刚打完比赛，来水个题解。

这篇题解讲 dfs 做法，但是我觉得应该也有 bfs 做法。

个人认为这篇题解还算比较好理解。

第一部分：思路

这道题我一直以为从任意点开始走都可以，于是耗了 15 分钟，直到同学提醒我……

既然只能从 1 开始，就好办一点。

首先，我们知道，一定不能经过权值为 -1 的点。因为如果在第 k 个点经过 -1，一定有 \sum\limits_{j=k+1}^{|P|} \frac{1}{2^{j-1}} + ( - \frac{1}{2^{k-1}}) < 0。不可能经过无穷多个点，取不到等号，反而亏了。

就这样，一个 -1 毁掉了一切。

所以，只能走 1 或 0。感谢良心的出题人与良心的小 L，没有搞出乱七八糟的权值。

同时，我们也能证明能走 1 时走 1 一定比走 0 优。而且根据题目里字典序的定义，最后不能有多余的 0，否则去掉了字典序更小。

直接这么写，其实 Subtask 5 就过了。但我们的目标不是 20 分，而是 100 分。

由于这道题的字典序比较坑，所以我们不用链式前向星，而是用 vector 来存边（邻接表）。存完边排个序就可以了。

具体 dfs 的过程写在 dfs 代码注释里（应该算比较详细了）。

bool dfs(int p,int fr,int dep)
//由于建了双向边，fr 存从哪里过来的，避免再回去
//dep 存深度，便于修改 qz 数组
//a 是权值，ed 是边（用 vector 存），nxt 存下一个怎么走最大（为 0 表示停下来最大），qz 是当前最大值（二进制）
//mx 存储从当前点出发能到的点权值的最大值，便于控制接下来全是 0 的情况
//dfs 函数是 bool 类型因为要存下来走这一条有没有更新最大值，如果更新了就要把 nxt 连过去。bg 就是存有没有更新的
{
    int mx=-1;
    bool bg=0;
    for(int i=0;i<ed[p].size();i++)
    {
        int k=ed[p][i];
        if(k==fr) continue;
        mx=max(mx,a[k]);
        if(a[k]==-1) continue;//-1 一定不走
        if(a[k]==1)//能走 1 一定走 1
        {
            if(qz[dep]==0)
            {
                if(mxd<dep) mxd=dep;//更新一下长度，便于之后再更新时清零
                qz[dep]=1;
                nxt[p]=k;//连过去
                bg=1;//能更新
                for(int j=dep+1;j<=mxd;j++) qz[j]=0;//后面全部清零
            }
            bool pp=dfs(k,p,dep+1);//这条路下去有没有更新
            if(pp) nxt[p]=k,bg=1;//更新了就连过去
        }
    }
    if(mx==-1) return 0;//走不下去了
    if(mx==0)
    {
        if(qz[dep]==1) return 0;//最大值能取到 1 但是接下来只有 0
        for(int i=0;i<ed[p].size();i++)
        {
            int k=ed[p][i];
            if(k==fr) continue;
            if(a[k]==-1) continue;
            bool pp=dfs(k,p,dep+1);
            if(pp) nxt[p]=k,bg=1;
        }
    }
    return bg;
}

dfs 结束之后还要特判。

• 如果 a_1=-1，后面是怎么加都加不到 0 的。所以我们什么都不干，直接 return 0; 就可以了。这个其实应该在 dfs 前判断，但因为也是特判，所以放到这里一起说。

• 如果 a_1=0 且 nxt_i=0，说明只走到 1 最优，当然这等同于什么都不干，所以也不输出。

最后输出一下，就能愉快地 AC 了。

第二部分：完整代码

dfs 部分前面给过，这一段就不加注释了。

#include<bits/stdc++.h>
using namespace std;
void IOS()//cin 优化
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}
vector<int> ed[500005];
//vector 存边
//P.S.本蒟蒻之前从来没用过 vector，这次是第一次
int n,u,v,mxd,a[500005],nxt[500005];
int qz[500005];
bool vis[500005];
bool dfs(int p,int fr,int dep)
{
    int mx=-1;
    bool bg=0;
    for(int i=0;i<ed[p].size();i++)
    {
        int k=ed[p][i];
        if(k==fr) continue;
        mx=max(mx,a[k]);
        if(a[k]==-1) continue;
        if(a[k]==1)
        {
            if(qz[dep]==0)
            {
                if(mxd<dep) mxd=dep;
                qz[dep]=1;
                nxt[p]=k;
                bg=1;
                for(int j=dep+1;j<=mxd;j++) qz[j]=0;
            }
            bool pp=dfs(k,p,dep+1);
            if(pp) nxt[p]=k,bg=1;
        }
    }
    if(mx==-1) return 0;
    if(mx==0)
    {
        if(qz[dep]==1) return 0;
        for(int i=0;i<ed[p].size();i++)
        {
            int k=ed[p][i];
            if(k==fr) continue;
            if(a[k]==-1) continue;
            bool pp=dfs(k,p,dep+1);
            if(pp) nxt[p]=k,bg=1;
        }
    }
    return bg;
}
int main()
{
    IOS();
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i<n;i++)
    {
        cin>>u>>v;
        ed[u].push_back(v);
        ed[v].push_back(u);
    }
    for(int i=1;i<=n;i++) sort(ed[i].begin(),ed[i].end());//排个序，方便按字典序来
    if(a[1]==-1) return 0;
    dfs(1,-1,0);
    if(a[1]==0&&!nxt[1]) return 0;
    for(int i=1;i;i=nxt[i]) cout<<i<<" ";
    cout<<endl;
    return 0;
}

第三部分：Others

这个小 L 确实很无聊

std 看起来好长啊

这题的数据需要加强一下，不然可以用可以过大多数数据的错解面向数据编程，然后过这道题。

有依赖的捆绑挺好的，有些错解大数据能过但小数据过不去，导致最后 20 分。

最后，如果你的代码过不去，给一组可能的 hack（至少 hack 掉了同机房的同学）：

Input:
10
0 0 0 0 0 1 0 0 0 1
1 2
2 3
3 4
4 5
5 6
1 7
7 8
8 9
9 10
Output:
1 7 8 9 10