2>滑板鞋
一条可能套着若干个环的链，
n个点，m次询问
问从t出发，走k次，能到哪
[解法1]：
每次暴力找循环，然后用mod的思想求目标点
记得开ll
#include<cstdio> #include<cstdlib> #include<cstring> using namespace std; int n,m; const int N=1e5+3; int nx[N]; inline int read() { int x=0;char c=getchar(); while(c<'0' || c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x; } int main() { n=read(),m=read(); for(int i=1;i<=n;i++) nx[i]=read(); int st; long long k; int vis[N],pos; while(m--) { st=read(); scanf("%lld",&k); if(!k) { printf("%d ",st); continue; } memset(vis,0,sizeof(vis)); int cnt=0;pos=st; for( ;cnt<k && !vis[pos];pos=nx[pos]) vis[pos]=++cnt; if(cnt<k) { long long len=cnt-vis[pos]+1; k=(k-cnt)%len; while(k--) pos=nx[pos]; } printf("%d ",pos); } return 0; }
[解法2]：
优化，记录每个点后面点的第一个循环的编号，和长度，
用dfs，返回时登记，反正一定会有一个环
但是环什么的似乎会堆叠在一起，所以这里直接一个看xh[i].s是否更新，更新了直接乘前人阴
#include<cstdio> #include<cstdlib> #include<cstring> #include<vector> using namespace std; int n,m; const int N=1e5+3; int nx[N]; inline int read() { int x=0;char c=getchar(); while(c<'0' || c>'9') c=getchar(); while(c>='0'&&c<='9') x=(x<<3)+(x<<1)+c-'0',c=getchar(); return x; } struct node { int s,len,dis; }xh[N]; int vis[N],cnt; void dfs(int nw) { if(xh[nw].s ) return ; if(vis[nw] ) { xh[nw].s =nw; xh[nw].dis =0, xh[nw].len =cnt-vis[nw]+1; } else { vis[nw]=++cnt; dfs(nx[nw]); xh[nw]=xh[nx[nw]]; xh[nw].dis ++; } }bool lf[N],ok; int main() { n=read(),m=read(); for(int i=1;i<=n;i++) nx[i]=read(),lf[nx[i]]=true; for(int i=1;i<=n;i++) if(!lf[i]) dfs(i),ok=true; if(!ok) dfs(1); int st;long long k; while(m--) { st=read(); scanf("%lld",&k); if(k>=xh[st].dis ) { k-=xh[st].dis ,st=xh[st].s ; k%=xh[st].len ; while(k--) st=nx[st]; } else while(k--) st=nx[st]; printf("%d ",st); } return 0; }
进一步的优化，我这个水平就不会了
[正解]：
裸倍增
f[k,i]代表从i开始走2^k步会到哪里，
初始f[0,i]=next[i]
f[k,i]=f[k-1,f[k-1,i]]，复杂度m*log(n)
#include<cstdio> #include<cmath> using namespace std; int n,m; const int N=1e5+3; int nx[N][61]; long long bb[63]; signed main() { scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) scanf("%d",&nx[i][0]); bb[0]=1; for(int i=1;i<61;i++) { bb[i]=bb[i-1]<<1; for(int j=1;j<=n;j++) nx[j][i]=nx[nx[j][i-1]][i-1]; } long long kk; while(m--) { int st; scanf("%d%lld",&st,&kk); for(int i=60;i>=0;i--) if(kk&bb[i]) st=nx[st][i]; printf("%d ",st); } return 0; }
这解法真是神仙解法