ABC267D 题解

前言

题目传送门！

更好的阅读体验？

两篇题解的代码写得很复杂，我是没有想到。

思路

很显然对于一个点，它必定会进入一个循环节。

如何判断它进入循环节了呢？当一个点被经过两次，就意味着已经有环了。

假设第一次进入的时候是 \(i\)，第二次是 \(j\)，循环节长度是 \(j - i\)。

当然进入环之前，可能有一部分不是环，所以 \(k \gets [k - (i - 1)] \bmod (j - i)\)。

然后题解又去统计循环的内容。这显然没有必要啊，直接暴力跑就完事了！

代码

#include <iostream>
#include <cstdio>
using namespace std;
const int N = 2e5 + 5;
typedef long long ll;
int a[N], dfn[N];
int main()
{
	int n; ll k;
	scanf("%d%lld", &n, &k);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
	int u = 1;
	for (ll i = 1; i <= k; i++)
	{
		if (dfn[u]) //循环节找到了 
		{
			k = (k - (i - 1)) % (i - dfn[u]);
			while (k--) u = a[u];
			cout << u;
			return 0;
		}
		dfn[u] = i, u = a[u];
	}
	cout << u;
	return 0;
}

希望能帮助到大家！