[破碎的状态] APIO练习赛第一题
真是个神奇的题目..
服了..std竟然比我简单很多..而且我算法也没有严格复杂度证明(实际加了srand(time(0));后反复submit中就有75分)
果然思维不够跳跃..
题意:
这是一道交互题
你一共可以询问最多m次(Subtask 1/4: m =2n; Subtask 3: m=4n; Subtask 2: m=n2)
你要求出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; } } } } }