「NOIP模拟赛」滑板鞋

我的滑板鞋时尚时尚最时尚
回家的路上我情不自禁
摩擦摩擦
在这光滑的地上摩擦
月光下我看到自己的身影有时很远有时很近
感到一种力量驱使我的脚步
有了滑板鞋天黑都不怕

题目描述

你在魅力之都购买了一双时尚的滑板鞋，你非常兴奋地到处摩擦！

hzwer很想问一个问题：按照你的行动方式，你从某个结点摩擦（移动）K步后能到的目的地

这显然是一个很简单的问题，但是蒟蒻hzwer总是问个不停，所以你决定写一个程序回答他的询问

输入格式

第一行两个数n，m表示结点个数和询问次数

接下来n行，第i个数一个数a[i]表示你在第i个结点的话，下一步会移动到第a[i]个结点

接下来m行，每行两个数t,k，蒟蒻hzwer询问如果你当前在第t个结点，k步之后你会到第几个节点

输出格式

m行为每次询问的结果

样例数据 1

输入

3 2
2
3
2
1 2
2 4

输出

3
2

备注

共十个测试点，每个测试点数据规模如下所示

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

题解

第一种做法直接暴力找循环节。。。

可以得70分

正解裸倍增

f[k,i]代表从i开始走2^k步会到哪里，初始f[0,i]=next[i]

f[k,i]=f[k-1,f[k-1,i]]，复杂度m*log(n)

本题来自orz模拟赛

暴力

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<set>
#define inf 1000000000
#define ll long long
using namespace std;
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 n,m;
int a[100005];
bool vis[100005];
int main()
{
	n=read();m=read();
	for(int i=1;i<=n;i++)
		a[i]=read();
	for(int i=1;i<=m;i++)
	{
		int t=read();ll K=read();
		int bg,cnt=0;
		for(int i=1;i<=n;i++)vis[i]=0;
		for(int i=t;!vis[i];i=a[i])
		{
			vis[i]=1;
			bg=a[i];
		}
		while(K&&t!=bg)t=a[t],K--;
		if(K)
		{
			cnt=1;
			while(a[bg]!=t)cnt++,bg=a[bg];
			K%=cnt;
		}
		while(K--)t=a[t];
		printf("%d\n",t);
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<cstring>

#include<set>

#define inf 1000000000

#define ll long long

using namespace std;

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 n,m;

int a[100005];

bool vis[100005];

int main()

{

n=read();m=read();

for(int i=1;i<=n;i++)

a[i]=read();

for(int i=1;i<=m;i++)

{

int t=read();ll K=read();

int bg,cnt=0;

for(int i=1;i<=n;i++)vis[i]=0;

for(int i=t;!vis[i];i=a[i])

{

vis[i]=1;

bg=a[i];

}

while(K&&t!=bg)t=a[t],K--;

if(K)

{

cnt=1;

while(a[bg]!=t)cnt++,bg=a[bg];

K%=cnt;

}

while(K--)t=a[t];

printf("%d\n",t);

}

return 0;

}

正解

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<vector>
#define ll long long
using namespace std;
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;
}
ll bin[65];
int n,m;
int to[100005][65];
int main()
{
	n=read();m=read();
	bin[0]=1;for(int i=1;i<=60;i++)bin[i]=bin[i-1]<<1;
	for(int i=1;i<=n;i++)to[i][0]=read();
	for(int i=1;i<=60;i++)
		for(int j=1;j<=n;j++)
			to[j][i]=to[to[j][i-1]][i-1];
	for(int i=1;i<=m;i++)
	{
		int x=read();ll k=read();
		for(int t=0;t<=60;t++)if(k&bin[t])x=to[x][t];
		printf("%d\n",x);
	}
	return 0;
}

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<algorithm>

#include<cmath>

#include<vector>

#define ll long long

using namespace std;

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;

}

ll bin[65];

int n,m;

int to[100005][65];

int main()

{

n=read();m=read();

bin[0]=1;for(int i=1;i<=60;i++)bin[i]=bin[i-1]<<1;

for(int i=1;i<=n;i++)to[i][0]=read();

for(int i=1;i<=60;i++)

for(int j=1;j<=n;j++)

to[j][i]=to[to[j][i-1]][i-1];

for(int i=1;i<=m;i++)

{

int x=read();ll k=read();

for(int t=0;t<=60;t++)if(k&bin[t])x=to[x][t];

printf("%d\n",x);

}

return 0;

}

hzwer.com _ Home | http://hzwer.com

题目背景

题目描述

输入格式

输出格式

样例数据 1

备注

分类目录

热门文章

Myfriends

近期评论