牛客寒假算法集训营1 C题&&bfs

题目

小a正在玩一款星际探索游戏，小a需要驾驶着飞船从1号星球出发前往n号星球。其中每个星球有一个能量指数p。星球i能到达星球j当且仅当pi>pj。同时小a的飞船还有一个耐久度t，初始时为1号点的能量指数，若小a前往星球j，那么飞船的耐久度会变为t⊕pj(即t异或pj，关于其定义请自行百度)小a想知道到达n号星球时耐久度最大为多少。
注意：对于每个位置来说，从它出发可以到达的位置仅与两者的p有关，与下标无关
输入描述:
第一行一个整数n，表示星球数。接下来一行有n个整数，第i个整数表示pi
输出描述:
一个整数表示到达n号星球时最大的耐久度。不能到达n号星球或到达时的最大耐久度为0则输出-1
示例1
输入
3
457 456 23
输出
478
说明
小a有两种方法到达3号星球
第一种：1→2→3，最终耐久度为457⊕456⊕23=22
第二种：1→3，最终耐久度为457⊕23=478
示例2
输入
4
2 4 4 2
输出
-1
示例3
输入
5
234 233 123 2333 23
输出
253
备注:1⩽n,∀pi⩽3000

解题分析

这是一道bfs的题。这个题在比赛时用暴力能过，但在赛后提交代码时好像又添加了新的数据，有好多AC代码重新提交都WA了。

错误代码

#include<bits/stdc++.h>
using namespace std;
int main()
{
    int n,p,p1,l[3005],a=0;
    scanf("%d",&n);
    scanf("%d",&p1);
    for(int i=1;i<n;i++)
    {
        scanf("%d",&p);
        if(p<p1)
            l[a++]=p;
    }
    if(!a)
    {
        printf("-1");
    }
    else
    {
        int ma=0;
       // sort(l,l+a,greater<int>());
        for(int i=0;i<a;i++)
            for(int j=i+1;j<a;j++)
                if(l[j]<l[j+1])
            {
                ma=l[j];
                l[j]=l[j+1];
                l[j+1]=ma;
            }
        ma=0;
        for(int i=0;i<a;i++)
        {
            int b=p1;
            for(int j=i+1;j<a;j++)
            {
                b=b^l[j];
                if(b>ma)
                    ma=b;
            }
        }
        if(!ma)
            ma=-1;
        printf("%d",ma);
    }
    return 0;
}

不明白这个被什么卡住了T^T通过了91%的数据。各位大佬发现问题欢迎打扰。

AC代码（源自一位实力强大的神仙）

#include <bits/stdc++.h>
using namespace std;
int n,ans;
bool vis[5005];
int pre[3005];

void bfs()
{
    queue<int> q;      //定义一个int类型队列q
    memset(vis, false, sizeof(vis));      //初始化vis（全部未被访问）
    q.push(pre[1]);      //将第一个元素插入（pre下标从一开始）
    vis[pre[1]] = true;     //此点已被访问
    while(!q.empty())      //判断队列是否为空
    {
        int now = q.front();    //定义now为新的队列首元素
        q.pop();       //弹出队列首元素
        for(int i=2; i<=n; i++)    //往后遍历
        {
            if(now > pre[i])
            {
                int nex = (now ^ pre[i]);     //定义nex
                if(i == n) ans = max(ans, nex);     //遍历结束后，ans为最大的nex
                if(!vis[nex] && i < n)     //剪枝判断
                {
                    vis[nex] = true;
                    q.push(nex);
                }
            }
        }
    }
}

int main(void)
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        scanf("%d",&pre[i]);
    }
    ans = 0;
    bfs();
    printf("%d\n", ans > 0 ? ans : -1);    //ans>0输出ans，否则输出-1
    return 0;
}

这里有几个要注意的地方：



再次对大佬表示感谢
最后，祝大家新年快乐