CF285B 题解

发布时间 2023-09-10 14:15:48作者: 群星之路

不可多得的小清新模拟题!

思路分析

题目中已经暗示地很明显了,只能对 \(x\) 进行操作使得 \(x\) 变成 \(p_x\)

而我们现在可以操作的值唯独 \(s\),所以我们的思路就呼之欲出了。

我们重复将 \(s\) 迭代为 \(p_s\)。如果 \(s=t\),那么我们就找到了答案。如果 \(s\) 回到了原来的值,那么就说明进入了死循环,不可能找到答案,输出 \(-1\)

程序实现

#include <bits/stdc++.h>
using namespace std;
int n, s, t, cnt, ps;
// ps记录s的初值,cnt记录所需要的操作次数
int main() {
	cin >> n >> s >> t, ps = s;
	vector<int> p(n + 1); // 建立一个长度为n+1的数组
	for (int i = 1; i <= n; i++) cin >> p[i];
	if (s == t) { // 一定要进行特判
		cout << 0;
		return 0;
	}
	while (true) { // 反复迭代
		s = p[s], cnt++;
		if (s == t) {
			cout << cnt;
			return 0;
		}
		if (s == ps) {
			cout << -1;
			return 0;
		}
	}
	return 0;
}