真是个神奇的题目..

服了..std竟然比我简单很多..而且我算法也没有严格复杂度证明(实际加了srand(time(0));后反复submit中就有75分)

果然思维不够跳跃..

题意:

这是一道交互题

你一共可以询问最多m次(Subtask 1/4: m =2n; Subtask 3: m=4n; Subtask 2: m=n²)

你要求出a到b的最短路径,每次询问你只能得到"任意两点的最短路-1"

一共n个点,告诉你你要从a走到b,求其中一条最短路

n<=1000,Subtask1保证任意两点的最短路唯一

蒟蒻的做法:

Subtask1:

我们把1~n都ping一遍s和t

之后我们可以知道,s-->t的路径唯一,所以只要找到所有s-->p-->t的路径长度和s-->t的长度一样即可

利用这个思路,我们就有了这样的算法:

int ss[1005];
int tt[1005];
void findRoute (int n, int s, int t)
{
    s--;
    t--;
    int i;
    for (i=0;i<n;i++)
    {
        if (i==s)
        {
            ss[i]=0;
        }
        else
        {
            ss[i]=ping(i+1,s+1)+1;
        }
    }
    for (i=0;i<n;i++)
    {
        if (i!=t)
        {
            tt[i]=ping(i+1,t+1)+1;
        }
        else
        {
            tt[i]=0;
        }
    }
    for (i=1;i<=n;i++)
    {
        int j;
        for (j=0;j<n;j++)
        {
            if ((ss[j]==i)&&(tt[j]==ss[t]-i))
            {
                travelTo(j+1);
            }
        }
    }
}

然后我们考虑,在此基础上Subtask 2/3/4会WA掉,因为会乱走

我们只要判定上一个点last到现在这个点j是否有路,就能解决掉2/3

因为保证询问复杂度是3n的,但不幸的很,我们也可以看到

Subtask 1挂了..

    int last=s;
    for (i=1;i<=n;i++)
    {
        int j;
        for (j=0;j<n;j++)
        {
            if ((ss[j]==i)&&(tt[j]==ss[t]-i))
            {
                if (ping(last+1,j+1)==0)
                {
                    travelTo(j+1);
                    last=j;
                    break;
                }
            }
        }
    }

然后..

我们还可以考虑,如果只有一个满足条件的可以直接选,也就是强行把Subtask 1给改对

    int last=s;
    for (i=1;i<=n;i++)
    {
        int j;
        int sigma=0;
        for (j=0;j<n;j++)
        {
            if ((ss[j]==i)&&(tt[j]==ss[t]-i))
            {
                sigma++;
            }
        }
        for (j=0;j<n;j++)
        {
            if ((ss[j]==i)&&(tt[j]==ss[t]-i))
            {
                sigma--;
                if ((sigma==0)||(ping(last+1,j+1)==0))
                {
                    travelTo(j+1);
                    last=j;
                    break;
                }
            }
        }
    }

在此,问题得到75%的分

后面25分有蒟蒻做法和标准做法两种

标准做法:

我们不询问s到别的点的距离,从s出发不断的走

走到的点如果满足是和现在联通的,并且是s的下一步就行了..

gg这么简单的想法我没想到还特么做的那么复杂..醉了

代码:

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include "network.h"
using namespace std;
int ss[1005];
int tt[1005];
void findRoute (int n, int s, int t)
{
    srand(time(0));
    s--;
    t--;
    int i;
    for (i=0;i<n;i++)
    {
        if (i!=t)
        {
            tt[i]=ping(i+1,t+1)+1;
        }
        else
        {
            tt[i]=0;
        }
    }
    printf("Debug : %d\n",tt[s]);
    int last=s;
    for (i=1;i<=n;i++)
    {
        int j;
        for (j=0;j<n;j++)
        {
            if (tt[j]==tt[s]-i)
            {
                if (ping(last+1,j+1)==0)
                {
                    travelTo(j+1);
                    last=j;
                    break;
                }
            }
        }
    }
}

所以..下面谈谈蒟蒻是怎么来随机骗分的

蒟蒻:

首先我们从s出发,记录s到每个点的路径

我们之前复杂度是O(3n)的

我们可以发现,某个点x如果到s的距离是d+1,那么从上一个点y到它要满足两条判定才行

1,x-->t的距离是正确的

2,x-->y有边,而且y到s的距离是d

那么两个ping会导致最坏情况下这里ping的复杂度依旧是O(2n)的

真的没办法了么?

随机!

随机一个点进行判定

期望是1/2(n+1)的位置就能找到正确的答案

那么..再加上x-->t的距离不一定满足

所以...就能有机会过掉

代码(无视return后面部分):

#include<set>
#include<map>
#include<list>
#include<queue>
#include<stack>
#include<math.h>
#include<string>
#include<time.h>
#include<bitset>
#include<vector>
#include<memory>
#include<utility>
#include<stdio.h>
#include<sstream>
#include<fstream>
#include<iostream>
#include<stdlib.h>
#include<string.h>
#include<algorithm>
#include "network.h"
using namespace std;
int ss[1005];
int tt[1005];
bool visit[1005];
vector<int> v[1005];
void dfs(int x,int now,int t,int d)
{
    if (x==t) return;
    int i=now;
    int k=(int)v[i].size();
    int sigma=v[i].size()-1;
    for (;sigma>0;)
    {
        int temp=rand()%k;
        if (visit[v[i][temp]]) continue;
        visit[v[i][temp]]=true;
        sigma--;
        if (v[i][temp]==t)
        {
            travelTo(t+1);
            return;
        }
        if ((ping(v[i][temp]+1,t+1)==d-now-1)&&(ping(x+1,v[i][temp]+1)==0))
        {
            travelTo(v[i][temp]+1);
            dfs(v[i][temp],now+1,t,d);
            return;
        }
    }
    int j;
    for (j=0;j<k;j++)
    {
        if (!visit[v[i][j]])
        {
            travelTo(v[i][j]+1);
            dfs(v[i][j],now+1,t,d);
        }
    }
}
void findRoute (int n, int s, int t)
{
    s--;
    t--;
    int i;
    for (i=0;i<n;i++)
    {
        if (i==s)
        {
            ss[i]=0;
        }
        else
        {
            ss[i]=ping(i+1,s+1)+1;
            v[ss[i]].push_back(i);
        }
    }
    dfs(s,1,t,ss[t]);
    return;
    for (i=0;i<n;i++)
    {
        if ((i!=t)&&(i!=s))
        {
            tt[i]=ping(i+1,t+1)+1;
        }
        else
        {
            tt[i]=0;
        }
    }
    //printf("Debug : %d\n",ss[t]);
    int last=s;
    for (i=1;i<=n;i++)
    {
        int j;
        int sigma=0;
        for (j=0;j<n;j++)
        {
            if ((ss[j]==i)&&(tt[j]==ss[t]-i))
            {
                sigma++;
            }
        }
        for (j=0;j<n;j++)
        {
            if ((ss[j]==i)&&(tt[j]==ss[t]-i))
            {
                sigma--;
                if ((sigma==0)||(ping(last+1,j+1)==0))
                {
                    travelTo(j+1);
                    last=j;
                    break;
                }
            }
        }
    }
}