题目背景
我的滑板鞋时尚时尚最时尚
回家的路上我情不自禁
摩擦 摩擦
在这光滑的地上摩擦
月光下我看到自己的身影有时很远有时很近
感到一种力量驱使我的脚步
有了滑板鞋天黑都不怕
题目描述
你在魅力之都购买了一双时尚的滑板鞋,你非常兴奋地到处摩擦!
hzwer很想问一个问题:按照你的行动方式,你从某个结点摩擦(移动)K步后能到的目的地
这显然是一个很简单的问题,但是蒟蒻hzwer总是问个不停,所以你决定写一个程序回答他的询问
输入格式
第一行两个数n,m表示结点个数和询问次数
接下来n行,第i个数一个数a[i]表示你在第i个结点的话,下一步会移动到第a[i]个结点
接下来m行,每行两个数t,k,蒟蒻hzwer询问如果你当前在第t个结点,k步之后你会到第几个节点
输出格式
m行为每次询问的结果
样例数据 1
备注
共十个测试点,每个测试点数据规模如下所示
1.n=10^2,m=n,k<=10^2
2.n=10^3,m=n,k<=10^3
3.n=10^4,m=1,k<=10^9
4.n=10^5,m=1,k<=10^9
5.n=10^5,m=1,k<=10^12
6.n=10^5,m=1,k<=10^15
7.n=10^5,m=1,k<=10^18
8.n=10^5,m=n,k<=10^12
9.n=10^5,m=n,k<=10^15
10.n=10^5,m=n,k<=10^18
倍增sb题
令f[i][j]表示i走2^j格之后能到达的点
读入f[i][0]
然后f[i][j]=f[f[i][j-1]][j-1]
就是先走2^(j-1)格再走2^(j-1)格
#include<cstdio> #include<iostream> #include<cstring> #include<cstdlib> #include<algorithm> #include<cmath> #include<queue> #include<deque> #include<set> #include<map> #include<ctime> #define LL long long #define inf 0x7ffffff #define pa pair<int,int> #define pi 3.1415926535897932384626433832795028841971 #define N 100010 using namespace std; int go[N][100]; int n,m; LL mul[100]; inline LL read() { LL x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int main() { n=read();m=read(); mul[0]=1; for (int i=1;i<=62;i++)mul[i]=mul[i-1]*2; for(int i=1;i<=n;i++)go[i][0]=read(); for(int i=1;i<=62;i++) for(int j=1;j<=n;j++) go[j][i]=go[go[j][i-1]][i-1]; for(int i=1;i<=m;i++) { int x=read(); LL y=read(); for (int j=62;j>=0;j--) if (y & mul[j]) { x=go[x][j]; } printf("%d\n",x); }