11.5 做题记录

[ABC167D] Teleporter

一眼有循环节，然后就秒了。

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 2e5 + 10;
int n, k, a[N], vis[N], xhj = 0;
pair <int, int> bs[N];
 
signed main() {
	cin >> n >> k;
	for(int i = 1; i <= n; i++) cin >> a[i];
	int now = 1, qd = 0;
	if(k <= n) {
		while(k--) {	
		now = a[now];
		}
		cout<<now;
		return 0;
	}  
	for(int i = 1; i <= n; i++) {
		if(!vis[now]) vis[now] = 1, bs[now].first = i;
		else if(vis[now]) {
			qd = now;
			bs[now].second = i;
			xhj = i - bs[now].first;
			break;	
		}
		now = a[now];
	}
	now = 1;
	while(now != qd) {
		now = a[now]; k--;
	}
	k %= xhj;
	while(k--) {	
		now = a[now];
	}
	cout << now;
}