一道思维题
题目传送门
考虑从第 \(i\) 个整数 \(a_i\) 满足 \(i-n\le a_i\le i-1\) 入手。
但是这样看起来没有什么性质，所以我们考虑将它变形：\(1\le i-a_i\le n\)。
我们发现，如果有 \(a_i+a_j+...+a_k=0\) 就有 \((i-a_i)+(j-a_j)+...+(k-a_k)=i+j+...+k\)
因为有如上的性质，所以必然有一种情况形如： \(i-a_i=j,j-a_j=k,...x-a_x=i\)，所以可以进行 \(dfs\)。
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e6+50;
ll T,n,a[N],dfn[N],w[N],idx;
void sc(int le,int ri)
{
printf("%d\n",ri-le+1);
for(int i=le;i<=ri;i++)
printf("%d ",w[i]);
printf("\n");
}
void dfs(int wz)
{
if(dfn[wz])
{
sc(dfn[wz],idx);
return ;
}
dfn[wz]=++idx;
w[idx]=wz;
dfs(wz-a[wz]);
}
int main()
{
scanf("%lld",&T);
while(T--)
{
scanf("%lld",&n);
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
dfs(1);
idx=0;
for(int i=1;i<=n;i++)
dfn[i]=0,w[i]=0;
}
return 0;
}