5 Anonymous Informant

发布时间 2024-01-09 20:43:17作者: yufan1102

image
image
image

题目大致就是让你判断有没有一个a数组,选一个定点向左循环x次,这样的操作一个k次,能变成给定的b数组

其实这样的题目是死的,你要做的只不过是不断的倒推。

当你找不到一个可以操作的定点,说明是不行。

因为k很大不可以循环1e9次的,说明这个题目一定要缩小k的范围。这其中有一个思想就是如果模拟到了同一个点两次,说明这是一个循环,它可以一直执行操作,说明是可行的

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+10;
int vis[N],a[N];
void solve(){
	int n,k;
	cin>>n>>k;
	for(int i=1;i<=n;i++){
		cin>>a[i];
		vis[i]=0;
	}
	int last=1;
	for(int i=1;i<=k;i++){
		int cur=last-1;
		if(cur==0)cur=n;
		if(a[cur]>n){
			cout<<"No\n";
			return;
		}
		if(vis[cur]){
			cout<<"Yes\n";
			return;
		}
		vis[cur]=1;
		last=(cur-a[cur]+n)%n+1;
	}
	cout<<"Yes\n";
}
int main(){
	ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	int t=1;
	cin>>t;
	for(int i=1;i<=t;i++)solve();
	return 0;
}