1 条题解

  • 0
    @ 2021-11-19 9:21:20

    发现 inaii1i-n\le a_i\le i-1

    所以 ai=ij(1jn)a_i=i-j(1\le j\le n)

    那么可以构造成ai+aj=ij+jk=ika_i+a_j=i-j+j-k=i-k,关系形成一张图。

    只要找一条链就合法了。

    每个点一个出边,是个基环数,直接跑环就可以了。

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const int N=1e6+5;
    int _,n,a[N],vis[N];
    int main() {
        scanf("%d",&_);
        while(_--){
            scanf("%d",&n);
            for(int i=1;i<=n;i++){
                int x;
                scanf("%d",&x);
                a[i]=i-x;
            }
            for(int i=1;i<=n;i++)vis[i]=0;
            int now=1;
            for(;!vis[now];now=a[now])vis[now]=1;
            int t=now;
            vector<int> ans;
            ans.clear();
            for(;a[now]!=t;now=a[now])ans.push_back(now);
            ans.push_back(now);
            printf("%d\n",ans.size());
            for(int i:ans)printf("%d ",i);
            puts("");
        }
        return 0;
    }
    
    • 1

    信息

    ID
    25
    时间
    2000ms
    内存
    256MiB
    难度
    (无)
    标签
    递交数
    0
    已通过
    0
    上传者